cde/programs/nsgmls/PointerTable.C

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