lib/OffsetOrderedList.cxx

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