1 // Copyright (c) 1994 James Clark
2 // See the file COPYING for copying permission.
3 #pragma ident "%Z%%M% %I% %E% SMI"
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>
PointerTable()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>
clear()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>
insert(P p,Boolean replace)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>
lookup(const K & k) const80 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>
remove(const K & k)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>
swap(PointerTable<P,K,HF,KF> & to)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>
PointerTableIter(const PointerTable<P,K,HF,KF> & table)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>
next()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 */
148