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