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