OffsetOrderedList.cxx revision 7c478bd95313f5f23a4c958a745db2134aa03244
// Copyright (c) 1994 James Clark
// See the file COPYING for copying permission.
#pragma ident "%Z%%M% %I% %E% SMI"
#include "splib.h"
#include "OffsetOrderedList.h"
#include "macros.h"
#ifdef SP_NAMESPACE
namespace SP_NAMESPACE {
#endif
{
}
{
// At any position in the list there's a current offset.
// The offset is initially zero.
// A byte of 255 says add 255 to the current offset.
// A byte B < 255, says that there's an item in the list whose
// offset is the current offset + B, and that B + 1 should be
// added to the current offset.
while (count >= 255) {
addByte(255);
count -= 255;
}
}
void OffsetOrderedList::addByte(unsigned char b)
{
last = new OffsetOrderedListBlock;
}
else {
}
blockUsed_ = 0;
}
if (b == 255)
else {
}
blockUsed_++;
}
// Find the last offset <= off.
Offset &foundOffset) const
{
// Invariant:
// blocks with index < i have offset <= off
// blocks with index >= lim have offset > off
size_t i = 0;
// Most commonly we'll want to know the about positions near the end,
// so optimize this case.
i = lim;
i = lim - 1;
else {
// Do a binary search.
while (i < lim) {
else
i = mid + 1;
}
}
if (i == 0)
return 0;
return 1;
}
// Note that an item with offset X can only occur in a block with offset > X
// i is now the first block with offset > off
: int(OffsetOrderedListBlock::size));
for (;;) {
j--;
if (bytes[j] != 255) {
curIndex -= 1;
curOff -= 1;
break;
}
if (j == 0) {
if (i == 0)
return 0;
i--;
j = OffsetOrderedListBlock::size;
}
}
return 1;
}
#ifdef SP_NAMESPACE
}
#endif