2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these librararies and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
23 /* $XConsortium: OffsetOrderedList.C /main/1 1996/07/29 16:59:05 cde-hp $ */
24 // Copyright (c) 1994 James Clark
25 // See the file COPYING for copying permission.
28 #include "OffsetOrderedList.h"
32 namespace SP_NAMESPACE {
35 OffsetOrderedList::OffsetOrderedList()
36 : blockUsed_(OffsetOrderedListBlock::size)
40 void OffsetOrderedList::append(Offset offset)
42 // At any position in the list there's a current offset.
43 // The offset is initially zero.
44 // A byte of 255 says add 255 to the current offset.
45 // A byte B < 255, says that there's an item in the list whose
46 // offset is the current offset + B, and that B + 1 should be
47 // added to the current offset.
48 Offset curOffset = blocks_.size() > 0 ? blocks_.back()->offset : 0;
49 ASSERT(offset >= curOffset);
50 Offset count = offset - curOffset;
51 while (count >= 255) {
58 void OffsetOrderedList::addByte(unsigned char b)
60 if (blockUsed_ >= OffsetOrderedListBlock::size) {
61 blocks_.resize(blocks_.size() + 1);
62 Owner<OffsetOrderedListBlock> &last = blocks_.back();
63 last = new OffsetOrderedListBlock;
64 if (blocks_.size() == 1) {
69 OffsetOrderedListBlock &lastButOne = *blocks_[blocks_.size() - 2];
70 last->nextIndex = lastButOne.nextIndex;
71 last->offset = lastButOne.offset;
75 blocks_.back()->bytes[blockUsed_++] = b;
77 blocks_.back()->offset += 255;
79 blocks_.back()->offset += b + 1;
80 blocks_.back()->nextIndex += 1;
84 // Find the last offset <= off.
86 Boolean OffsetOrderedList::findPreceding(Offset off,
88 Offset &foundOffset) const
91 // blocks with index < i have offset <= off
92 // blocks with index >= lim have offset > off
94 size_t lim = blocks_.size();
95 // Most commonly we'll want to know the about positions near the end,
96 // so optimize this case.
97 if (lim > 0 && blocks_[lim - 1]->offset <= off)
99 else if (lim > 1 && blocks_[lim - 2]->offset <= off)
102 // Do a binary search.
104 size_t mid = i + (lim - i)/2;
105 if (blocks_[mid]->offset > off)
111 if (i == blocks_.size()) {
114 foundIndex = blocks_.back()->nextIndex - 1;
115 foundOffset = blocks_.back()->offset - 1;
118 // Note that an item with offset X can only occur in a block with offset > X
119 // i is now the first block with offset > off
120 Offset curOff = blocks_[i]->offset;
121 size_t curIndex = blocks_[i]->nextIndex;
122 const unsigned char *bytes = blocks_[i]->bytes;
123 int j = (i == blocks_.size() - 1
125 : int(OffsetOrderedListBlock::size));
128 if (bytes[j] != 255) {
139 j = OffsetOrderedListBlock::size;
140 curOff = blocks_[i]->offset;
141 curIndex = blocks_[i]->nextIndex;
142 bytes = blocks_[i]->bytes;
145 foundIndex = curIndex;
146 foundOffset = curOff;