Debian Codegraph @

libhylafax/Dictionary.c++

raw
1 /* $Id$ */
2 /*
3 * Copyright (c) 1990-1996 Sam Leffler
4 * Copyright (c) 1991-1996 Silicon Graphics, Inc.
5 * HylaFAX is a trademark of Silicon Graphics
6 *
7 * Permission to use, copy, modify, distribute, and sell this software and
8 * its documentation for any purpose is hereby granted without fee, provided
9 * that (i) the above copyright notices and this permission notice appear in
10 * all copies of the software and related documentation, and (ii) the names of
11 * Sam Leffler and Silicon Graphics may not be used in any advertising or
12 * publicity relating to the software without the specific, prior written
13 * permission of Sam Leffler and Silicon Graphics.
14 *
15 * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
17 * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
18 *
19 * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
20 * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
21 * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
22 * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF
23 * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
24 * OF THIS SOFTWARE.
25 */
26 #include "Dictionary.h"
27
28 #define DEFAULTSIZE 31
29
30 fxIMPLEMENT_PtrArray(fxDictBuckets,fxDictBucket *)
31 fxIMPLEMENT_PtrArray(fxDictIters, fxDictIter *)
32
33 #define KEYAT(base) (base)
34 #define VALUEAT(base) (void*)(((char*)base) + keysize)
35
36 #define KEY(b) KEYAT((b)->kvmem)
37 #define VALUE(b) VALUEAT((b)->kvmem)
38
39 fxDictionary::fxDictionary(u_int ksize, u_int vsize,u_int initsize)
40 {
41 if (initsize == 0) initsize = DEFAULTSIZE;
42 buckets.resize(initsize);
43 keysize = ksize;
44 valuesize = vsize;
45 numItems = 0;
46 }
47
48 fxDictionary::fxDictionary(const fxDictionary& a)
49 {
50 for (u_int i = 0; i < a.buckets.length(); i++) {
51 const fxDictBucket* sb = a.buckets[i];
52 while (sb) {
53 addInternal(KEY(sb),VALUE(sb));
54 sb = sb->next;
55 }
56 }
57 }
58
59 fxDictionary::~fxDictionary()
60 {
61 }
62
63 void fxDictionary::cleanup()
64 {
65 u_int i;
66 u_int l = buckets.length();
67 for (i=0; i < l; i++) {
68 fxDictBucket* bucket = buckets[i];
69 while (bucket) {
70 fxDictBucket* bucket2 = bucket->next;
71 destroyKey(KEY(bucket));
72 destroyValue(VALUE(bucket));
73 delete bucket;
74 bucket = bucket2;
75 }
76 buckets[i] = 0;
77 }
78 l = iters.length();
79 for (i=0; i < l; i++) {
80 iters[i]->dict = 0;
81 iters[i]->node = 0;
82 iters[i]->invalid = true;
83 }
84 }
85
86 fxDictBucket::~fxDictBucket()
87 {
88 if (kvmem) free(kvmem);
89 }
90
91 void
92 fxDictionary::operator=(const fxDictionary &a)
93 {
94 assert(keysize == a.getKeySize());
95 assert(valuesize == a.getValueSize());
96 if (this == &a) return;
97 this->fxDictionary::~fxDictionary(); // NB: need this for HP C++ 3.4
98 for (u_int i = 0; i < a.buckets.length(); i++) {
99 const fxDictBucket* db = a.buckets[i];
100 while (db) {
101 addInternal(KEY(db), VALUE(db));
102 db = db->next;
103 }
104 }
105 }
106
107 void
108 fxDictionary::addInternal(const void* key, const void* value)
109 {
110 u_int index = (u_int)(hashKey(key) % buckets.length());
111 fxDictBucket* bucket = buckets[index];
112 while (bucket && compareKeys(key,KEY(bucket))) {
113 bucket = bucket->next;
114 }
115 if (bucket) { // just change the value
116 destroyValue(VALUE(bucket));
117 copyValue(value,VALUE(bucket));
118 return;
119 } else {
120 void * kvmem = malloc(keysize + valuesize);
121 copyKey(key,KEYAT(kvmem));
122 copyValue(value,VALUEAT(kvmem));
123 fxDictBucket* newbucket = new fxDictBucket(kvmem,buckets[index]);
124 buckets[index] = newbucket;
125 numItems++;
126 }
127 }
128
129 const void*
130 fxDictionary::find(const void* key, const void **keyp) const
131 {
132 u_int index = (u_int)(hashKey(key) % buckets.length());
133 const fxDictBucket* bucket = buckets[index];
134 while (bucket && compareKeys(key,KEY(bucket))) bucket = bucket->next;
135 if (bucket) {
136 if (keyp != 0) *keyp = &KEY(bucket);
137 return VALUE(bucket);
138 } else {
139 if (keyp != 0) *keyp = 0;
140 return 0;
141 }
142 }
143
144 void*
145 fxDictionary::findCreate(const void* key)
146 {
147 u_int index = (u_int)(hashKey(key) % buckets.length());
148 fxDictBucket* bucket = buckets[index];
149 while (bucket && compareKeys(key,KEY(bucket))) bucket = bucket->next;
150 if (bucket)
151 return VALUE(bucket);
152 else {
153 char* kvmem = (char*)malloc(keysize + valuesize);
154 copyKey(key,KEYAT(kvmem));
155 createValue(VALUEAT(kvmem));
156 fxDictBucket* bucket = new fxDictBucket(kvmem,buckets[index]);
157 buckets[index] = bucket;
158 numItems++;
159 return VALUEAT(kvmem);
160 }
161 }
162
163 void
164 fxDictionary::remove(const void* key)
165 {
166 u_int index = (u_int)(hashKey(key) % buckets.length());
167 fxDictBucket* bucket = buckets[index];
168 fxDictBucket** prev = &buckets[index];
169 while (bucket && compareKeys(key,KEY(bucket))) {
170 prev = &bucket->next;
171 bucket = bucket->next;
172 }
173 if (bucket) {
174 *prev = bucket->next;
175 destroyKey(KEY(bucket));
176 destroyValue(VALUE(bucket));
177 invalidateIters(bucket);
178 delete bucket;
179 numItems--;
180 }
181 }
182
183 void *
184 fxDictionary::cut(const void* key)
185 {
186 u_int index = (u_int)(hashKey(key) % buckets.length());
187 fxDictBucket* bucket = buckets[index];
188 fxDictBucket** prev = &buckets[index];
189 while (bucket && compareKeys(key,KEY(bucket))) {
190 prev = &bucket->next;
191 bucket = bucket->next;
192 }
193 if (bucket) {
194 *prev = bucket->next;
195 void * v = malloc(valuesize);
196 memcpy(v,VALUE(bucket),valuesize);
197 destroyKey(KEY(bucket));
198 // no need to destroy value because it has moved to *v
199 invalidateIters(bucket);
200 delete bucket;
201 numItems--;
202 return v;
203 } else {
204 return 0;
205 }
206 }
207
208 u_long
209 fxDictionary::hashKey(const void* key) const
210 {
211 u_long u = 0;
212 const u_long* p = (const u_long*)key;
213 u_int l = keysize;
214 while (l>=sizeof (u_long)) {
215 u ^= *p++;
216 l -= sizeof (u_long);
217 }
218 return u;
219 }
220
221 void fxDictionary::destroyKey(void *) const { }
222 void fxDictionary::destroyValue(void *) const { }
223
224 void
225 fxDictionary::addIter(fxDictIter* i)
226 {
227 iters.append(i);
228 }
229
230 void
231 fxDictionary::removeIter(fxDictIter* i)
232 {
233 iters.remove(iters.find(i));
234 }
235
236 void
237 fxDictionary::invalidateIters(const fxDictBucket *db)
238 {
239 u_int l = iters.length();
240 for (u_int i = 0; i<l; i++) {
241 fxDictIter* di = iters[i];
242 if (di->node == db) {
243 (*di)++;
244 if (di->dict) di->invalid = true;
245 }
246 }
247 }
248
249 //----------------------------------------------------------------------
250
251 fxDictIter::fxDictIter()
252 {
253 invalid = false;
254 dict = 0;
255 bucket = 0;
256 node = 0;
257 }
258
259 fxDictIter::fxDictIter(fxDictionary& d)
260 {
261 invalid = false;
262 dict = &d;
263 bucket = 0;
264 node = d.buckets[bucket];
265 d.addIter(this);
266 if (!node) advanceToValid();
267 }
268
269 fxDictIter::~fxDictIter()
270 {
271 if (dict) dict->removeIter(this);
272 }
273
274 void
275 fxDictIter::operator=(fxDictionary& d)
276 {
277 if (dict) dict->removeIter(this);
278 dict = &d;
279 bucket = 0;
280 node = d.buckets[bucket];
281 invalid = false;
282 d.addIter(this);
283 if (!node) advanceToValid();
284 }
285
286 void *
287 fxDictIter::getKey() const
288 {
289 if (invalid) return 0;
290 else return KEY(node);
291 }
292
293 void *
294 fxDictIter::getValue() const
295 {
296 if (invalid) return 0;
297 else return (char *)node->kvmem + dict->keysize;
298 }
299
300 void
301 fxDictIter::increment()
302 {
303 if (!dict) return;
304 if (invalid) {
305 invalid = false;
306 return;
307 }
308 node = node->next;
309 if (node) return;
310
311 // otherwise, find another node!
312 advanceToValid();
313 }
314
315 void
316 fxDictIter::advanceToValid()
317 {
318 u_int len = dict->buckets.length();
319 fxDictBucket * n;
320 for(;;) {
321 bucket++;
322 assert(bucket<=len);
323 if (bucket == len) {
324 dict->removeIter(this); // it's done with us
325 dict = 0;
326 invalid = true;
327 break;
328 }
329 if ((n = dict->buckets[bucket])) { // NB: intentional =
330 node = n;
331 invalid = false;
332 break;
333 }
334 }
335 }