cde/programs/nsgmls/OffsetOrderedList.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   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)
  10  * any later version.
  11  *
  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
  16  * details.
  17  *
  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
  22  */
  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.
  26
  27 #include "splib.h"
  28 #include "OffsetOrderedList.h"
  29 #include "macros.h"
  30
  31 #ifdef SP_NAMESPACE
  32 namespace SP_NAMESPACE {
  33 #endif
  34
  35 OffsetOrderedList::OffsetOrderedList()
  36 : blockUsed_(OffsetOrderedListBlock::size)
  37 {
  38 }
  39
  40 void OffsetOrderedList::append(Offset offset)
  41 {
  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) {
  52     addByte(255);
  53     count -= 255;
  54   }
  55   addByte(count);
  56 }
  57
  58 void OffsetOrderedList::addByte(unsigned char b)
  59 {
  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) {
  65       last->nextIndex = 0;
  66       last->offset = 0;
  67     }
  68     else {
  69       OffsetOrderedListBlock &lastButOne = *blocks_[blocks_.size() - 2];
  70       last->nextIndex = lastButOne.nextIndex;
  71       last->offset = lastButOne.offset;
  72     }
  73     blockUsed_ = 0;
  74   }
  75   blocks_.back()->bytes[blockUsed_++] = b;
  76   if (b == 255)
  77     blocks_.back()->offset += 255;
  78   else {
  79     blocks_.back()->offset += b + 1;
  80     blocks_.back()->nextIndex += 1;
  81   }
  82 }
  83
  84 // Find the last offset <= off.
  85
  86 Boolean OffsetOrderedList::findPreceding(Offset off,
  87                                          size_t &foundIndex,
  88                                          Offset &foundOffset) const
  89 {
  90   // Invariant:
  91   // blocks with index < i have offset <= off
  92   // blocks with index >= lim have offset > off
  93   size_t i = 0;
  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)
  98     i = lim;
  99   else if (lim > 1 && blocks_[lim - 2]->offset <= off)
 100     i = lim - 1;
 101   else {
 102     // Do a binary search.
 103     while (i < lim) {
 104       size_t mid = i + (lim - i)/2;
 105       if (blocks_[mid]->offset > off)
 106         lim = mid;
 107       else
 108         i = mid + 1;
 109     }
 110   }
 111   if (i == blocks_.size()) {
 112     if (i == 0)
 113       return 0;
 114     foundIndex = blocks_.back()->nextIndex - 1;
 115     foundOffset = blocks_.back()->offset - 1;
 116     return 1;
 117   }
 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
 124            ? blockUsed_
 125            : int(OffsetOrderedListBlock::size));
 126   for (;;) {
 127     j--;
 128     if (bytes[j] != 255) {
 129       curIndex -= 1;
 130       curOff -= 1;
 131       if (curOff <= off)
 132         break;
 133     }
 134     curOff -= bytes[j];
 135     if (j == 0) {
 136       if (i == 0)
 137         return 0;
 138       i--;
 139       j = OffsetOrderedListBlock::size;
 140       curOff = blocks_[i]->offset;
 141       curIndex = blocks_[i]->nextIndex;
 142       bytes = blocks_[i]->bytes;
 143     }
 144   }
 145   foundIndex = curIndex;
 146   foundOffset = curOff;
 147   return 1;
 148 }
 149
 150 #ifdef SP_NAMESPACE
 151 }
 152 #endif