1 /* -----------------------------------------------------------------------------
2 * hash.c
3 *
4 * Implements a simple hash table object.
5 *
6 * Author(s) : David Beazley (beazley@cs.uchicago.edu)
7 *
8 * Copyright (C) 1999-2000. The University of Chicago
9 * See the file LICENSE for information on usage and redistribution.
10 * ----------------------------------------------------------------------------- */
11
12 static char cvsroot[] = "$Header: /cvs/projects/SWILL/Source/Objects/hash.c,v 1.1 2002/02/19 19:16:49 beazley Exp $";
13
14 #include "dohint.h"
15
16 extern DohObjInfo DohHashType;
17
18 /* Hash node */
19 typedef struct HashNode {
20 DOH *key;
21 DOH *object;
22 struct HashNode *next;
23 } HashNode;
24
25 /* Hash object */
26 typedef struct Hash {
27 DOH *file;
28 int line;
29 HashNode **hashtable;
30 int hashsize;
31 int currentindex;
32 int nitems;
33 HashNode *current;
34 } Hash;
35
36 /* Key interning structure */
37 typedef struct KeyValue {
38 char *cstr;
39 DOH *sstr;
40 struct KeyValue *left;
41 struct KeyValue *right;
42 } KeyValue;
43
44 static KeyValue *root = 0;
45
46 /* Find or create a key in the interned key table */
find_key(DOH * doh_c)47 static DOH *find_key (DOH *doh_c) {
48 char *c = (char *) doh_c;
49 KeyValue *r, *s;
50 int d = 0;
51 /* OK, sure, we use a binary tree for maintaining interned
52 symbols. Then we use their hash values for accessing secondary
53 hash tables. */
54 r = root;
55 s = 0;
56 while (r) {
57 s = r;
58 d = strcmp(r->cstr,c);
59 if (d == 0) return r->sstr;
60 if (d < 0) r = r->left;
61 else r = r->right;
62 }
63 /* fprintf(stderr,"Interning '%s'\n", c);*/
64 r = (KeyValue *) DohMalloc(sizeof(KeyValue));
65 r->cstr = (char *) DohMalloc(strlen(c)+1);
66 strcpy(r->cstr,c);
67 r->sstr = NewString(c);
68 DohIntern(r->sstr);
69 r->left = 0;
70 r->right = 0;
71 if (!s) { root = r; }
72 else {
73 if (d < 0) s->left = r;
74 else s->right = r;
75 }
76 return r->sstr;
77 }
78
79 #define HASH_INIT_SIZE 7
80
81 /* Create a new hash node */
NewNode(DOH * k,void * obj)82 static HashNode *NewNode(DOH *k, void *obj) {
83 HashNode *hn = (HashNode *) DohMalloc(sizeof(HashNode));
84 hn->key = k;
85 Incref(hn->key);
86 hn->object = obj;
87 Incref(obj);
88 hn->next = 0;
89 return hn;
90 }
91
92 /* Delete a hash node */
DelNode(HashNode * hn)93 static void DelNode(HashNode *hn) {
94 Delete(hn->key);
95 Delete(hn->object);
96 DohFree(hn);
97 }
98
99 /* -----------------------------------------------------------------------------
100 * DelHash()
101 *
102 * Delete a hash table.
103 * ----------------------------------------------------------------------------- */
104
105 static void
DelHash(DOH * ho)106 DelHash(DOH *ho) {
107 Hash *h = (Hash *) ObjData(ho);
108 HashNode *n,*next;
109 int i;
110
111 for (i = 0; i < h->hashsize; i++) {
112 if ((n = h->hashtable[i])) {
113 while (n) {
114 next = n->next;
115 DelNode(n);
116 n = next;
117 }
118 }
119 }
120 DohFree(h->hashtable);
121 h->hashtable = 0;
122 h->hashsize = 0;
123 DohFree(h);
124 }
125
126 /* -----------------------------------------------------------------------------
127 * Hash_clear()
128 *
129 * Clear all of the entries in the hash table.
130 * ----------------------------------------------------------------------------- */
131
132 static void
Hash_clear(DOH * ho)133 Hash_clear(DOH *ho) {
134 Hash *h = (Hash *) ObjData(ho);
135 HashNode *n,*next;
136 int i;
137
138 for (i = 0; i < h->hashsize; i++) {
139 if ((n = h->hashtable[i])) {
140 while (n) {
141 next = n->next;
142 DelNode(n);
143 n = next;
144 }
145 }
146 h->hashtable[i] = 0;
147 }
148 h->nitems = 0;
149 }
150
151 /* resize the hash table */
resize(Hash * h)152 static void resize(Hash *h) {
153 HashNode *n, *next, **table;
154 int oldsize, newsize;
155 int i, p, hv;
156
157 if (h->nitems < 2*h->hashsize) return;
158
159 /* Too big. We have to rescale everything now */
160 oldsize = h->hashsize;
161
162 /* Calculate a new size */
163 newsize = 2*oldsize+1;
164 p = 3;
165 while (p < (newsize >> 1)) {
166 if (((newsize/p)*p) == newsize) {
167 newsize+=2;
168 p = 3;
169 continue;
170 }
171 p = p + 2;
172 }
173
174 table = (HashNode **) DohMalloc(newsize*sizeof(HashNode *));
175 for (i = 0; i < newsize; i++ ) {
176 table[i] = 0;
177 }
178
179 /* Walk down the old set of nodes and re-place */
180 h->hashsize = newsize;
181 for (i = 0; i < oldsize; i++) {
182 n = h->hashtable[i];
183 while (n) {
184 hv = Hashval(n->key) % newsize;
185 next = n->next;
186 n->next = table[hv];
187 table[hv] = n;
188 n = next;
189 }
190 }
191 DohFree(h->hashtable);
192 h->hashtable = table;
193 }
194
195 /* -----------------------------------------------------------------------------
196 * Hash_setattr()
197 *
198 * Set an attribute in the hash table. Deletes the existing entry if it already
199 * exists.
200 * ----------------------------------------------------------------------------- */
201
202 static int
Hash_setattr(DOH * ho,DOH * k,DOH * obj)203 Hash_setattr(DOH *ho, DOH *k, DOH *obj) {
204 int hv;
205 HashNode *n, *prev;
206 Hash *h = (Hash *) ObjData(ho);
207
208 if (!obj) {
209 return DohDelattr(ho,k);
210 }
211 if (!DohCheck(k)) k = find_key(k);
212 if (!DohCheck(obj)) {
213 obj = NewString((char *) obj);
214 Decref(obj);
215 }
216 hv = (Hashval(k)) % h->hashsize;
217 n = h->hashtable[hv];
218 prev = 0;
219 while (n) {
220 if (Cmp(n->key,k) == 0) {
221 /* Node already exists. Just replace its contents */
222 if (n->object == obj) {
223 /* Whoa. Same object. Do nothing */
224 return 1;
225 }
226 Delete(n->object);
227 n->object = obj;
228 Incref(obj);
229 return 1; /* Return 1 to indicate a replacement */
230 } else {
231 prev = n;
232 n = n->next;
233 }
234 }
235 /* Add this to the table */
236 n = NewNode(k,obj);
237 if (prev) prev->next = n;
238 else h->hashtable[hv] = n;
239 h->nitems++;
240 resize(h);
241 return 0;
242 }
243
244 /* -----------------------------------------------------------------------------
245 * Hash_getattr()
246 *
247 * Get an attribute from the hash table. Returns 0 if it doesn't exist.
248 * ----------------------------------------------------------------------------- */
249
250 static DOH *
Hash_getattr(DOH * ho,DOH * k)251 Hash_getattr(DOH *ho, DOH *k) {
252 int hv;
253 HashNode *n;
254 Hash *h = (Hash *) ObjData(ho);
255
256 if (!DohCheck(k)) k = find_key(k);
257 hv = Hashval(k) % h->hashsize;
258 n = h->hashtable[hv];
259 while (n) {
260 if (Cmp(n->key, k) == 0) return n->object;
261 n = n->next;
262 }
263 return 0;
264 }
265
266 /* -----------------------------------------------------------------------------
267 * Hash_delattr()
268 *
269 * Delete an object from the hash table.
270 * ----------------------------------------------------------------------------- */
271
272 static int
Hash_delattr(DOH * ho,DOH * k)273 Hash_delattr(DOH *ho, DOH *k) {
274 HashNode *n, *prev;
275 int hv;
276 Hash *h = (Hash *) ObjData(ho);
277
278 if (!DohCheck(k)) k = find_key(k);
279 hv = Hashval(k) % h->hashsize;
280 n = h->hashtable[hv];
281 prev = 0;
282 while (n) {
283 if (Cmp(n->key, k) == 0) {
284 /* Found it, kill it */
285
286 if (prev) {
287 prev->next = n->next;
288 } else {
289 h->hashtable[hv] = n->next;
290 }
291 /* Need to check for iterator location */
292 if (n == h->current) {
293 h->current = prev; /* Move back to previous node. When next is called, will move to next node */
294 if (!h->current) h->currentindex--; /* No previous node. Move back one slot */
295 }
296 DelNode(n);
297 h->nitems--;
298 return 1;
299 }
300 prev = n;
301 n = n->next;
302 }
303 return 0;
304 }
305
306 /* General purpose iterators */
307 static HashNode *
hash_first(DOH * ho)308 hash_first(DOH *ho) {
309 Hash *h = (Hash *) ObjData(ho);
310 h->currentindex = 0;
311 h->current = 0;
312 while ((h->currentindex < h->hashsize) && !h->hashtable[h->currentindex])
313 h->currentindex++;
314 if (h->currentindex >= h->hashsize) return 0;
315 h->current = h->hashtable[h->currentindex];
316 return h->current;
317 }
318
319 static HashNode *
hash_next(DOH * ho)320 hash_next(DOH *ho) {
321 Hash *h = (Hash *) ObjData(ho);
322 if (h->currentindex < 0) return hash_first(ho);
323
324 /* Try to move to the next entry */
325 if (h->current) {
326 h->current = h->current->next;
327 }
328 if (h->current) {
329 return h->current;
330 }
331 h->currentindex++;
332 while ((h->currentindex < h->hashsize) && !h->hashtable[h->currentindex])
333 h->currentindex++;
334 if (h->currentindex >= h->hashsize) return 0;
335 h->current = h->hashtable[h->currentindex];
336 return h->current;
337 }
338
339 /* -----------------------------------------------------------------------------
340 * Hash_firstkey()
341 *
342 * Return first hash-table key.
343 * ----------------------------------------------------------------------------- */
344
345 static DOH *
Hash_firstkey(DOH * ho)346 Hash_firstkey(DOH *ho) {
347 HashNode *hn = hash_first(ho);
348 if (hn) return hn->key;
349 return 0;
350 }
351
352 /* -----------------------------------------------------------------------------
353 * Hash_nextkey()
354 *
355 * Return next hash table key.
356 * ----------------------------------------------------------------------------- */
357
358 static DOH *
Hash_nextkey(DOH * ho)359 Hash_nextkey(DOH *ho) {
360 HashNode *hn = hash_next(ho);
361 if (hn) return hn->key;
362 return 0;
363 }
364
365 /* -----------------------------------------------------------------------------
366 * Hash_keys(DOH *)
367 *
368 * Return a list of keys
369 * ----------------------------------------------------------------------------- */
370
371 static DOH *
Hash_keys(DOH * so)372 Hash_keys(DOH *so) {
373 DOH *keys;
374 DOH *k;
375
376 keys = NewList();
377 k = Firstkey(so);
378 while (k) {
379 Append(keys,k);
380 k = Nextkey(so);
381 }
382 return keys;
383 }
384
385 /* -----------------------------------------------------------------------------
386 * Hash_str()
387 *
388 * Create a string representation of a hash table (mainly for debugging).
389 * ----------------------------------------------------------------------------- */
390
391 static DOH *
Hash_str(DOH * ho)392 Hash_str(DOH *ho) {
393 int i,j;
394 HashNode *n;
395 DOH *s;
396 static int indent = 4;
397 Hash *h = (Hash *) ObjData(ho);
398
399 s = NewString("");
400 if (ObjGetMark(ho)) {
401 Printf(s,"Hash(0x%x)",ho);
402 return s;
403 }
404 ObjSetMark(ho,1);
405 Printf(s,"Hash {\n");
406 for (i = 0; i < h->hashsize; i++) {
407 n = h->hashtable[i];
408 while (n) {
409 for (j = 0; j < indent; j++) Putc(' ',s);
410 indent+=4;
411 Printf(s,"'%s' : %s, \n", n->key, n->object);
412 indent-=4;
413 n = n->next;
414 }
415 }
416 for (j = 0; j < (indent-4); j++) Putc(' ',s);
417 Printf(s,"}\n");
418 ObjSetMark(ho,0);
419 return s;
420 }
421
422 /* -----------------------------------------------------------------------------
423 * Hash_len()
424 *
425 * Return number of entries in the hash table.
426 * ----------------------------------------------------------------------------- */
427
428 static int
Hash_len(DOH * ho)429 Hash_len(DOH *ho) {
430 Hash *h = (Hash *) ObjData(ho);
431 return h->nitems;
432 }
433
434 /* -----------------------------------------------------------------------------
435 * CopyHash()
436 *
437 * Make a copy of a hash table. Note: this is a shallow copy.
438 * ----------------------------------------------------------------------------- */
439
440 static DOH *
CopyHash(DOH * ho)441 CopyHash(DOH *ho) {
442 Hash *h, *nh;
443 HashNode *n;
444 DOH *nho;
445
446 int i;
447 h = (Hash *) ObjData(ho);
448 nh = (Hash *) DohMalloc(sizeof(Hash));
449 nh->hashsize = h->hashsize;
450 nh->hashtable = (HashNode **) DohMalloc(nh->hashsize*sizeof(HashNode *));
451 for (i = 0; i < nh->hashsize; i++) {
452 nh->hashtable[i] = 0;
453 }
454 nh->currentindex = -1;
455 nh->current = 0;
456 nh->nitems = 0;
457 nh->line = h->line;
458 nh->file = h->file;
459 if (nh->file) Incref(nh->file);
460
461 nho = DohObjMalloc(&DohHashType, nh);
462 for (i = 0; i < h->hashsize; i++) {
463 if ((n = h->hashtable[i])) {
464 while (n) {
465 Hash_setattr(nho, n->key, n->object);
466 n = n->next;
467 }
468 }
469 }
470 return nho;
471 }
472
473
474
475 static void
Hash_setfile(DOH * ho,DOH * file)476 Hash_setfile(DOH *ho, DOH *file) {
477 DOH *fo;
478 Hash *h = (Hash *) ObjData(ho);
479
480 if (!DohCheck(file)) {
481 fo = NewString(file);
482 Decref(fo);
483 } else fo = file;
484 Incref(fo);
485 Delete(h->file);
486 h->file = fo;
487 }
488
489 static DOH *
Hash_getfile(DOH * ho)490 Hash_getfile(DOH *ho) {
491 Hash *h = (Hash *) ObjData(ho);
492 return h->file;
493 }
494
495 static void
Hash_setline(DOH * ho,int line)496 Hash_setline(DOH *ho, int line) {
497 Hash *h = (Hash *) ObjData(ho);
498 h->line = line;
499 }
500
501 static int
Hash_getline(DOH * ho)502 Hash_getline(DOH *ho) {
503 Hash *h = (Hash *) ObjData(ho);
504 return h->line;
505 }
506
507 /* -----------------------------------------------------------------------------
508 * type information
509 * ----------------------------------------------------------------------------- */
510
511 static DohHashMethods HashHashMethods = {
512 Hash_getattr,
513 Hash_setattr,
514 Hash_delattr,
515 Hash_firstkey,
516 Hash_nextkey,
517 Hash_keys,
518 };
519
520 DohObjInfo DohHashType = {
521 "Hash", /* objname */
522 DelHash, /* doh_del */
523 CopyHash, /* doh_copy */
524 Hash_clear, /* doh_clear */
525 Hash_str, /* doh_str */
526 0, /* doh_data */
527 0, /* doh_dump */
528 Hash_len, /* doh_len */
529 0, /* doh_hash */
530 0, /* doh_cmp */
531 Hash_setfile, /* doh_setfile */
532 Hash_getfile, /* doh_getfile */
533 Hash_setline, /* doh_setline */
534 Hash_getline, /* doh_getline */
535 &HashHashMethods, /* doh_mapping */
536 0, /* doh_sequence */
537 0, /* doh_file */
538 0, /* doh_string */
539 0, /* doh_positional */
540 0,
541 };
542
543 /* -----------------------------------------------------------------------------
544 * NewHash()
545 *
546 * Create a new hash table.
547 * ----------------------------------------------------------------------------- */
548
549 DOH *
DohNewHash()550 DohNewHash() {
551 Hash *h;
552 int i;
553 static int init = 0;
554 h = (Hash *) DohMalloc(sizeof(Hash));
555 h->hashsize = HASH_INIT_SIZE;
556 h->hashtable = (HashNode **) DohMalloc(h->hashsize*sizeof(HashNode *));
557 for (i = 0; i < h->hashsize; i++) {
558 h->hashtable[i] = 0;
559 }
560 h->currentindex = -1;
561 h->current = 0;
562 h->nitems = 0;
563 h->file = 0;
564 h->line = 0;
565 return DohObjMalloc(&DohHashType,h);
566 }
567