Commit | Line | Data |
---|---|---|
e87b4ac1 PR |
1 | // This may look like C code, but it is really -*- C++ -*- |
2 | /* | |
3 | Copyright (C) 1988 Free Software Foundation | |
4 | written by Doug Lea (dl@rocky.oswego.edu) | |
5 | ||
6 | This file is part of the GNU C++ Library. This library is free | |
7 | software; you can redistribute it and/or modify it under the terms of | |
8 | the GNU Library General Public License as published by the Free | |
9 | Software Foundation; either version 2 of the License, or (at your | |
10 | option) any later version. This library is distributed in the hope | |
11 | that it will be useful, but WITHOUT ANY WARRANTY; without even the | |
12 | implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR | |
13 | PURPOSE. See the GNU Library General Public License for more details. | |
14 | You should have received a copy of the GNU Library General Public | |
15 | License along with this library; if not, write to the Free Software | |
16 | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. | |
17 | */ | |
18 | ||
19 | #ifdef __GNUG__ | |
20 | #pragma implementation | |
21 | #endif | |
22 | #include "<T>.VHBag.h" | |
23 | ||
24 | /* codes for status fields */ | |
25 | ||
26 | #define EMPTYCELL 0 | |
27 | #define VALIDCELL 1 | |
28 | #define DELETEDCELL 2 | |
29 | ||
30 | ||
31 | <T>VHBag::<T>VHBag(unsigned int sz) | |
32 | { | |
33 | tab = new <T>[size = sz]; | |
34 | status = new char[size]; | |
35 | for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL; | |
36 | count = 0; | |
37 | } | |
38 | ||
39 | <T>VHBag::<T>VHBag(<T>VHBag& a) | |
40 | { | |
41 | tab = new <T>[size = a.size]; | |
42 | status = new char[size]; | |
43 | for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL; | |
44 | count = 0; | |
45 | for (Pix p = a.first(); p; a.next(p)) add(a(p)); | |
46 | } | |
47 | ||
48 | ||
49 | /* | |
50 | * hashing method: double hash based on high bits of hash fct, | |
51 | * followed by linear probe. Can't do too much better if table | |
52 | * sizes not constrained to be prime. | |
53 | */ | |
54 | ||
55 | ||
56 | static inline unsigned int doublehashinc(unsigned int h, unsigned int s) | |
57 | { | |
58 | unsigned int dh = ((h / s) % s); | |
59 | return (dh > 1)? dh : 1; | |
60 | } | |
61 | ||
62 | Pix <T>VHBag::seek(<T&> key, Pix p) | |
63 | { | |
64 | <T>* t = (<T>*) p; | |
65 | if (t == 0 || !<T>EQ(*t, key)) | |
66 | { | |
67 | unsigned int hashval = <T>HASH(key); | |
68 | unsigned int h = hashval % size; | |
69 | for (unsigned int i = 0; i <= size; ++i) | |
70 | { | |
71 | if (status[h] == EMPTYCELL) | |
72 | return 0; | |
73 | else if (status[h] == VALIDCELL && <T>EQ(key, tab[h])) | |
74 | return Pix(&tab[h]); | |
75 | if (i == 0) | |
76 | h = (h + doublehashinc(hashval, size)) % size; | |
77 | else if (++h >= size) | |
78 | h -= size; | |
79 | } | |
80 | return 0; | |
81 | } | |
82 | else | |
83 | { | |
84 | int seent = 0; | |
85 | unsigned int hashval = <T>HASH(key); | |
86 | unsigned int h = hashval % size; | |
87 | for (unsigned int i = 0; i <= size; ++i) | |
88 | { | |
89 | if (status[h] == EMPTYCELL) | |
90 | return 0; | |
91 | else if (&tab[h] == t) | |
92 | seent = 1; | |
93 | else if (seent && status[h] == VALIDCELL && <T>EQ(key, tab[h])) | |
94 | return Pix(&tab[h]); | |
95 | if (i == 0) | |
96 | h = (h + doublehashinc(hashval, size)) % size; | |
97 | else if (++h >= size) | |
98 | h -= size; | |
99 | } | |
100 | return 0; | |
101 | } | |
102 | } | |
103 | ||
104 | int <T>VHBag::nof(<T&> item) | |
105 | { | |
106 | int n = 0; | |
107 | unsigned int hashval = <T>HASH(item); | |
108 | unsigned int h = hashval % size; | |
109 | unsigned int firsth = size; | |
110 | for (unsigned int i = 0; i <= size; ++i) | |
111 | { | |
112 | if (status[h] == EMPTYCELL) | |
113 | return n; | |
114 | else if (h != firsth && status[h] == VALIDCELL && <T>EQ(item, tab[h])) | |
115 | { | |
116 | ++n; | |
117 | if (firsth >= size) | |
118 | firsth = h; | |
119 | } | |
120 | if (i == 0) | |
121 | h = (h + doublehashinc(hashval, size)) % size; | |
122 | else if (++h >= size) | |
123 | h -= size; | |
124 | } | |
125 | return n; | |
126 | } | |
127 | ||
128 | ||
129 | Pix <T>VHBag::add(<T&> item) | |
130 | { | |
131 | if (HASHTABLE_TOO_CROWDED(count, size)) | |
132 | resize(); | |
133 | unsigned int bestspot = size; | |
134 | unsigned int hashval = <T>HASH(item); | |
135 | unsigned int h = hashval % size; | |
136 | for (unsigned int i = 0; i <= size; ++i) | |
137 | { | |
138 | if (status[h] == EMPTYCELL) | |
139 | { | |
140 | if (bestspot >= size) bestspot = h; | |
141 | tab[bestspot] = item; | |
142 | status[bestspot] = VALIDCELL; | |
143 | ++count; | |
144 | return Pix(&tab[bestspot]); | |
145 | } | |
146 | else if (status[h] == DELETEDCELL) | |
147 | { | |
148 | if (bestspot >= size) bestspot = h; | |
149 | } | |
150 | ||
151 | if (i == 0) | |
152 | h = (h + doublehashinc(hashval, size)) % size; | |
153 | else if (++h >= size) | |
154 | h -= size; | |
155 | } | |
156 | tab[bestspot] = item; | |
157 | status[bestspot] = VALIDCELL; | |
158 | ++count; | |
159 | return Pix(&tab[bestspot]); | |
160 | } | |
161 | ||
162 | ||
163 | void <T>VHBag::del(<T&> key) | |
164 | { | |
165 | unsigned int hashval = <T>HASH(key); | |
166 | unsigned int h = hashval % size; | |
167 | for (unsigned int i = 0; i <= size; ++i) | |
168 | { | |
169 | if (status[h] == EMPTYCELL) | |
170 | return; | |
171 | else if (status[h] == VALIDCELL && <T>EQ(key, tab[h])) | |
172 | { | |
173 | status[h] = DELETEDCELL; | |
174 | --count; | |
175 | return; | |
176 | } | |
177 | if (i == 0) | |
178 | h = (h + doublehashinc(hashval, size)) % size; | |
179 | else if (++h >= size) | |
180 | h -= size; | |
181 | } | |
182 | } | |
183 | ||
184 | void <T>VHBag::remove(<T&> key) | |
185 | { | |
186 | unsigned int hashval = <T>HASH(key); | |
187 | unsigned int h = hashval % size; | |
188 | for (unsigned int i = 0; i <= size; ++i) | |
189 | { | |
190 | if (status[h] == EMPTYCELL) | |
191 | return; | |
192 | else if (status[h] == VALIDCELL && <T>EQ(key, tab[h])) | |
193 | { | |
194 | status[h] = DELETEDCELL; | |
195 | --count; | |
196 | } | |
197 | if (i == 0) | |
198 | h = (h + doublehashinc(hashval, size)) % size; | |
199 | else if (++h >= size) | |
200 | h -= size; | |
201 | } | |
202 | } | |
203 | ||
204 | void <T>VHBag::clear() | |
205 | { | |
206 | for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL; | |
207 | count = 0; | |
208 | } | |
209 | ||
210 | void <T>VHBag::resize(unsigned int newsize) | |
211 | { | |
212 | if (newsize <= count) | |
213 | { | |
214 | newsize = DEFAULT_INITIAL_CAPACITY; | |
215 | while (HASHTABLE_TOO_CROWDED(count, newsize)) newsize <<= 1; | |
216 | } | |
217 | <T>* oldtab = tab; | |
218 | char* oldstatus = status; | |
219 | unsigned int oldsize = size; | |
220 | tab = new <T>[size = newsize]; | |
221 | status = new char[size]; | |
222 | for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL; | |
223 | count = 0; | |
224 | for (i = 0; i < oldsize; ++i) if (oldstatus[i] == VALIDCELL) add(oldtab[i]); | |
225 | delete [] oldtab; | |
226 | delete oldstatus; | |
227 | } | |
228 | ||
229 | Pix <T>VHBag::first() | |
230 | { | |
231 | for (unsigned int pos = 0; pos < size; ++pos) | |
232 | if (status[pos] == VALIDCELL) return Pix(&tab[pos]); | |
233 | return 0; | |
234 | } | |
235 | ||
236 | void <T>VHBag::next(Pix& i) | |
237 | { | |
238 | if (i == 0) return; | |
239 | unsigned int pos = ((unsigned)i - (unsigned)tab) / sizeof(<T>) + 1; | |
240 | for (; pos < size; ++pos) | |
241 | if (status[pos] == VALIDCELL) | |
242 | { | |
243 | i = Pix(&tab[pos]); | |
244 | return; | |
245 | } | |
246 | i = 0; | |
247 | } | |
248 | ||
249 | ||
250 | int <T>VHBag::OK() | |
251 | { | |
252 | int v = tab != 0; | |
253 | v &= status != 0; | |
254 | int n = 0; | |
255 | for (unsigned int i = 0; i < size; ++i) | |
256 | { | |
257 | if (status[i] == VALIDCELL) ++n; | |
258 | else if (status[i] != DELETEDCELL && status[i] != EMPTYCELL) | |
259 | v = 0; | |
260 | } | |
261 | v &= n == count; | |
262 | if (!v) error("invariant failure"); | |
263 | return v; | |
264 | } |