cde/programs/nsgmls/OffsetOrderedList.C

   1 /* $XConsortium: OffsetOrderedList.C /main/1 1996/07/29 16:59:05 cde-hp $ */
   2 // Copyright (c) 1994 James Clark
   3 // See the file COPYING for copying permission.
   4
   5 #include "splib.h"
   6 #include "OffsetOrderedList.h"
   7 #include "macros.h"
   8
   9 #ifdef SP_NAMESPACE
  10 namespace SP_NAMESPACE {
  11 #endif
  12
  13 OffsetOrderedList::OffsetOrderedList()
  14 : blockUsed_(OffsetOrderedListBlock::size)
  15 {
  16 }
  17
  18 void OffsetOrderedList::append(Offset offset)
  19 {
  20   // At any position in the list there's a current offset.
  21   // The offset is initially zero.
  22   // A byte of 255 says add 255 to the current offset.
  23   // A byte B < 255, says that there's an item in the list whose
  24   // offset is the current offset + B, and that B + 1 should be
  25   // added to the current offset.
  26   Offset curOffset = blocks_.size() > 0  ? blocks_.back()->offset : 0;
  27   ASSERT(offset >= curOffset);
  28   Offset count = offset - curOffset;
  29   while (count >= 255) {
  30     addByte(255);
  31     count -= 255;
  32   }
  33   addByte(count);
  34 }
  35
  36 void OffsetOrderedList::addByte(unsigned char b)
  37 {
  38   if (blockUsed_ >= OffsetOrderedListBlock::size) {
  39     blocks_.resize(blocks_.size() + 1);
  40     Owner<OffsetOrderedListBlock> &last = blocks_.back();
  41     last = new OffsetOrderedListBlock;
  42     if (blocks_.size() == 1) {
  43       last->nextIndex = 0;
  44       last->offset = 0;
  45     }
  46     else {
  47       OffsetOrderedListBlock &lastButOne = *blocks_[blocks_.size() - 2];
  48       last->nextIndex = lastButOne.nextIndex;
  49       last->offset = lastButOne.offset;
  50     }
  51     blockUsed_ = 0;
  52   }
  53   blocks_.back()->bytes[blockUsed_++] = b;
  54   if (b == 255)
  55     blocks_.back()->offset += 255;
  56   else {
  57     blocks_.back()->offset += b + 1;
  58     blocks_.back()->nextIndex += 1;
  59   }
  60 }
  61
  62 // Find the last offset <= off.
  63
  64 Boolean OffsetOrderedList::findPreceding(Offset off,
  65                                          size_t &foundIndex,
  66                                          Offset &foundOffset) const
  67 {
  68   // Invariant:
  69   // blocks with index < i have offset <= off
  70   // blocks with index >= lim have offset > off
  71   size_t i = 0;
  72   size_t lim = blocks_.size();
  73   // Most commonly we'll want to know the about positions near the end,
  74   // so optimize this case.
  75   if (lim > 0 && blocks_[lim - 1]->offset <= off)
  76     i = lim;
  77   else if (lim > 1 && blocks_[lim - 2]->offset <= off)
  78     i = lim - 1;
  79   else {
  80     // Do a binary search.
  81     while (i < lim) {
  82       size_t mid = i + (lim - i)/2;
  83       if (blocks_[mid]->offset > off)
  84         lim = mid;
  85       else
  86         i = mid + 1;
  87     }
  88   }
  89   if (i == blocks_.size()) {
  90     if (i == 0)
  91       return 0;
  92     foundIndex = blocks_.back()->nextIndex - 1;
  93     foundOffset = blocks_.back()->offset - 1;
  94     return 1;
  95   }
  96   // Note that an item with offset X can only occur in a block with offset > X
  97   // i is now the first block with offset > off
  98   Offset curOff = blocks_[i]->offset;
  99   size_t curIndex = blocks_[i]->nextIndex;
 100   const unsigned char *bytes = blocks_[i]->bytes;
 101   int j = (i == blocks_.size() - 1
 102            ? blockUsed_
 103            : int(OffsetOrderedListBlock::size));
 104   for (;;) {
 105     j--;
 106     if (bytes[j] != 255) {
 107       curIndex -= 1;
 108       curOff -= 1;
 109       if (curOff <= off)
 110         break;
 111     }
 112     curOff -= bytes[j];
 113     if (j == 0) {
 114       if (i == 0)
 115         return 0;
 116       i--;
 117       j = OffsetOrderedListBlock::size;
 118       curOff = blocks_[i]->offset;
 119       curIndex = blocks_[i]->nextIndex;
 120       bytes = blocks_[i]->bytes;
 121     }
 122   }
 123   foundIndex = curIndex;
 124   foundOffset = curOff;
 125   return 1;
 126 }
 127
 128 #ifdef SP_NAMESPACE
 129 }
 130 #endif