2 ** Splint - annotation-assisted static program checker
3 ** Copyright (C) 1994-2000 University of Virginia,
4 ** Massachusetts Institute of Technology
6 ** This program is free software; you can redistribute it and/or modify it
7 ** under the terms of the GNU General Public License as published by the
8 ** Free Software Foundation; either version 2 of the License, or (at your
9 ** option) any later version.
11 ** This program is distributed in the hope that it will be useful, but
12 ** WITHOUT ANY WARRANTY; without even the implied warranty of
13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 ** General Public License for more details.
16 ** The GNU General Public License is available from http://www.gnu.org/ or
17 ** the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
18 ** MA 02111-1307, USA.
20 ** For information on splint: splint@cs.virginia.edu
21 ** To report a bug: splint-bug@cs.virginia.edu
22 ** For more information: http://www.splint.org
27 ** Since hsearch defined in <search.h> only allows one hash table,
28 ** I'll implement my own.
30 ** Try to find a decent hash function, etc. later...
32 ** hashTable is from string -> unsigned
36 # include "splintMacros.nf"
39 /*@constant null hbucket hbucket_undefined; @*/
40 # define hbucket_undefined 0
42 static /*@truenull@*/ bool hbucket_isNull (/*@null@*/ hbucket h)
44 return (h == hbucket_undefined);
48 hentry_create (cstring key, int val)
58 hbucket_isEmpty (hbucket h)
60 return (h == hbucket_undefined || h->size == 0);
64 hbucket_unparse (hbucket h)
66 cstring s = cstring_undefined;
68 if (!hbucket_isNull (h))
72 for (i = 0; i < h->size; i++)
74 s = message ("%q %s:%d", s, h->entries[i].key, h->entries[i].val);
82 hbucket_single (hentry e)
84 hbucket h = (hbucket) dmalloc (sizeof (*h));
87 h->nspace = HBUCKET_BASESIZE - 1;
88 h->entries = (hentry *) dmalloc (HBUCKET_BASESIZE * sizeof (*h->entries));
95 hbucket_grow (/*@notnull@*/ hbucket h)
100 h->nspace += HBUCKET_BASESIZE;
102 newentries = (hentry *)
103 dmalloc ((h->size + HBUCKET_BASESIZE) * sizeof (*newentries));
105 for (i = 0; i < h->size; i++)
107 newentries[i] = h->entries[i];
111 h->entries = newentries;
114 static int hbucket_lookup (hbucket p_h, cstring p_key);
117 ** bizarre duplicate behaviour
118 ** required for duplicate entries
122 hbucket_add (/*@notnull@*/ hbucket h, hentry e)
124 int exloc = hbucket_lookup (h, e.key);
127 if (exloc != HBUCKET_DNE)
129 h->entries[exloc].key = e.key;
130 h->entries[exloc].val = e.val;
139 h->entries[h->size] = e;
145 hbucket_ncollisions (hbucket h)
147 if (!hbucket_isNull (h) && (h->size > 1))
148 return (h->size - 1);
154 hbucket_lookup (hbucket h, cstring key)
156 if (!hbucket_isNull (h))
160 for (i = 0; i < h->size; i++)
162 if (cstring_equal (h->entries[i].key, key))
164 return h->entries[i].val;
173 void hbucket_free (/*@only@*/ hbucket h)
175 if (!hbucket_isNull (h))
183 hashTable_free (/*@only@*/ hashTable h)
187 for (i = 0; i < h->size; i++)
189 hbucket_free (h->buckets[i]);
197 hashTable_countCollisions (hashTable h)
202 for (i = 0; i < h->size; i++)
204 nc += hbucket_ncollisions (h->buckets[i]);
212 hashTable_countEmpty (hashTable h)
217 for (i = 0; i < h->size; i++)
219 if (hbucket_isEmpty (h->buckets[i]))
229 ** hash function snarfed from quake/hash.c Hash_String
230 ** by Stephen Harrison
234 * Here are 256 random numbers for use in the hash function
238 static unsigned int RandomNumbers[256] =
240 #include "256_random_numbers.nf"
245 hashTable_hashValue (hashTable h, cstring key)
248 unsigned int hash_value = 0;
250 for (p = cstring_toCharsSafe (key); *p != '\0'; p++)
252 hash_value = (hash_value << 1) ^ RandomNumbers[*p % 256];
255 return (hash_value % h->size);
258 static /*@exposed@*/ hbucket
259 hashTable_hash (hashTable h, cstring key)
261 return h->buckets[hashTable_hashValue (h, key)];
266 hashTable_create (int size)
269 hashTable h = (hashTable) dmalloc (sizeof (*h));
273 h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * size);
276 for (i = 0; i < size; i++)
278 h->buckets[i] = hbucket_undefined;
285 static /*@unused@*/ void
286 hashTable_print (hashTable h)
290 for (i = 0; i < h->size; i++)
292 hbucket hb = h->buckets[i];
296 llmsg (message ("%d. %s\n", i, hbucket_unparse (hb)));
300 llmsg (message ("size: %d, collisions: %d, empty: %d",
302 hashTable_countCollisions (h),
303 hashTable_countEmpty (h)));
308 hashTable_stats (hashTable h)
310 return (message ("size: %d, collisions: %d, empty: %d\n",
311 h->size, hashTable_countCollisions (h),
312 hashTable_countEmpty (h)));
316 hashTable_addEntry (hashTable h, hentry e)
318 unsigned int hindex = hashTable_hashValue (h, e.key);
321 ** hbucket hb = h->buckets[hindex];
322 ** instead reveals a bug I don't want to deal with right now!
327 if (hbucket_isNull (h->buckets[hindex]))
329 h->buckets[hindex] = hbucket_single (e);
333 hbucket_add (h->buckets[hindex], e);
338 hashTable_insert (hashTable h, cstring key, int value)
348 ** rehashing based (loosely) on code by Steve Harrison
351 if (h->nentries * 162 > h->size * 100)
354 int oldsize = h->size;
355 int newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */
356 hbucket *oldbuckets = h->buckets;
361 h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * newsize);
364 for (i = 0; i < newsize; i++)
366 h->buckets[i] = hbucket_undefined;
370 for (i = 0; i < oldsize; i++)
372 hbucket bucket = oldbuckets[i];
374 if (!hbucket_isNull (bucket))
378 for (j = 0; j < bucket->size; j++)
380 hashTable_addEntry (h, bucket->entries[j]);
391 e = hentry_create (key, value);
392 hindex = hashTable_hashValue (h, key);
393 hb = h->buckets[hindex];
395 if (hbucket_isNull (hb))
397 h->buckets[hindex] = hbucket_single (e);
407 hashTable_lookup (hashTable h, cstring key)
409 hbucket hb = hashTable_hash (h, key);
411 return (hbucket_lookup (hb, key));
415 ** This is needed if oldkey is going to be released.
419 hashTable_replaceKey (hashTable h, cstring oldkey, /*@dependent@*/ cstring newkey)
421 hbucket hb = hashTable_hash (h, oldkey);
423 llassert (cstring_equal (oldkey, newkey));
425 if (!hbucket_isNull (hb))
429 for (i = 0; i < hb->size; i++)
431 if (cstring_equal (hb->entries[i].key, oldkey))
433 hb->entries[i].key = newkey;
439 llbug (message ("hashTable_replaceKey: %s not found", oldkey));
443 hashTable_remove (hashTable h, cstring key)
445 hbucket hb = hashTable_hash (h, key);
447 if (!hbucket_isNull (hb))
451 for (i = 0; i < hb->size; i++)
453 if (cstring_equal (hb->entries[i].key, key))
455 if (i < hb->size - 1)
457 hb->entries[i] = hb->entries[hb->size - 1];
466 llbug (message ("hashTable_removeKey: %s not found", key));