cde/programs/nsgmls/PointerTable.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 libraries 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: PointerTable.C /main/1 1996/07/29 17:01:40 cde-hp $ */
  24 // Copyright (c) 1994 James Clark
  25 // See the file COPYING for copying permission.
  26
  27 #ifndef PointerTable_DEF_INCLUDED
  28 #define PointerTable_DEF_INCLUDED 1
  29
  30 #include <stdlib.h>
  31
  32 #ifdef SP_NAMESPACE
  33 namespace SP_NAMESPACE {
  34 #endif
  35
  36 template<class P, class K, class HF, class KF>
  37 PointerTable<P, K, HF, KF>::PointerTable()
  38 : used_(0), usedLimit_(0), null_(0)
  39 {
  40 }
  41
  42 template<class P, class K, class HF, class KF>
  43 void PointerTable<P, K, HF, KF>::clear()
  44 {
  45   vec_.clear();
  46   used_ = 0;
  47   usedLimit_ = 0;
  48 }
  49
  50 template<class P, class K, class HF, class KF>
  51 P PointerTable<P, K, HF, KF>::insert(P p, Boolean replace)
  52 {
  53   size_t h;
  54   if (vec_.size() == 0) {
  55     vec_.assign(8, P(0));
  56     usedLimit_ = 4;
  57     h = startIndex(KF::key(*p));
  58   }
  59   else {
  60     for (h = startIndex(KF::key(*p)); vec_[h] != 0 ; h = nextIndex(h))
  61       if (KF::key(*vec_[h]) == KF::key(*p)) {
  62         if (replace) {
  63           P tem(vec_[h]);
  64           vec_[h] = p;
  65           return tem;
  66         }
  67         else
  68           return vec_[h];
  69       }
  70     if (used_ >= usedLimit_) {
  71       if (vec_.size() > size_t(-1)/2) {
  72         if (usedLimit_ == vec_.size() - 1)
  73           abort();              // FIXME throw an exception
  74         else
  75           usedLimit_ = vec_.size() - 1;
  76       }
  77       else {
  78         // rehash
  79         Vector<P> oldVec(vec_.size()*2, P(0));
  80         vec_.swap(oldVec);
  81         usedLimit_ = vec_.size() / 2;
  82         for (size_t i = 0; i < oldVec.size(); i++)
  83           if (oldVec[i] != 0) {
  84             size_t j;
  85             for (j = startIndex(KF::key(*oldVec[i]));
  86                  vec_[j] != 0;
  87                  j = nextIndex(j))
  88               ;
  89             vec_[j] = oldVec[i];
  90           }
  91         for (h = startIndex(KF::key(*p)); vec_[h] != 0; h = nextIndex(h))
  92           ;
  93       }
  94     }
  95   }
  96   used_++;
  97   vec_[h] = p;
  98   return 0;
  99 }
 100
 101 template<class P, class K, class HF, class KF>
 102 const P &PointerTable<P, K, HF, KF>::lookup(const K &k) const
 103 {
 104   if (used_ > 0) {
 105     for (size_t i = startIndex(k); vec_[i] != 0; i = nextIndex(i))
 106       if (KF::key(*vec_[i]) == k)
 107         return vec_[i];
 108   }
 109   return null_;
 110 }
 111
 112 template<class P, class K, class HF, class KF>
 113 P PointerTable<P, K, HF, KF>::remove(const K &k)
 114 {
 115   if (used_ > 0) {
 116     for (size_t i = startIndex(k); vec_[i] != 0; i = nextIndex(i))
 117       if (KF::key(*vec_[i]) == k) {
 118         P p = vec_[i];
 119         do {
 120           vec_[i] = P(0);
 121           size_t j = i;
 122           size_t r;
 123           do {
 124             i = nextIndex(i);
 125             if (vec_[i] == 0)
 126               break;
 127             r = startIndex(KF::key(*vec_[i]));
 128           } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
 129           vec_[j] = vec_[i];
 130         } while (vec_[i] != 0);
 131         --used_;
 132         return p;
 133       }
 134   }
 135   return 0;
 136 }
 137
 138 template<class P, class K, class HF, class KF>
 139 void PointerTable<P, K, HF, KF>::swap(PointerTable<P, K, HF, KF> &to)
 140 {
 141   vec_.swap(to.vec_);
 142   size_t tem = to.used_;
 143   to.used_ = used_;
 144   used_ = tem;
 145   tem = to.usedLimit_;
 146   to.usedLimit_ = usedLimit_;
 147   usedLimit_ = tem;
 148 }
 149
 150 template<class P, class K, class HF, class KF>
 151 PointerTableIter<P, K, HF, KF>::PointerTableIter(const PointerTable<P, K, HF, KF> &table)
 152 : tablePtr_(&table), i_(0)
 153 {
 154 }
 155
 156 template<class P, class K, class HF, class KF>
 157 const P &PointerTableIter<P, K, HF, KF>::next()
 158 {
 159   for (; i_ < tablePtr_->vec_.size(); i_++)
 160     if (tablePtr_->vec_[i_] != 0)
 161       return tablePtr_->vec_[i_++];
 162   return tablePtr_->null_;
 163 }
 164
 165 #ifdef SP_NAMESPACE
 166 }
 167 #endif
 168
 169 #endif /* not PointerTable_DEF_INCLUDED */