2 ** Splint - annotation-assisted static program checker
3 ** Copyright (C) 1994-2003 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: info@splint.org
21 ** To report a bug: splint-bug@splint.org
22 ** For more information: http://www.splint.org
27 ** A genericTable is a mapping from string keys to void * objects.
28 ** We sacrific type checking here for code reuse.
31 # include "splintMacros.nf"
33 # include "randomNumbers.h"
35 /*@constant null ghbucket ghbucket_undefined; @*/
36 # define ghbucket_undefined 0
38 static /*@nullwhentrue@*/ bool ghbucket_isNull (/*@null@*/ ghbucket h)
40 return (h == ghbucket_undefined);
44 ghentry_create (/*@keep@*/ cstring key, /*@keep@*/ void *val)
46 ghentry h = (ghentry) dmalloc (sizeof (*h));
50 llassert (val != NULL);
57 ghentry_free (/*@only@*/ ghentry ghe)
59 cstring_free (ghe->key);
60 /* can't free val contents */
66 ghbucket_isEmpty (ghbucket h)
68 return (h == ghbucket_undefined || h->size == 0);
71 int genericTable_size (genericTable h)
73 if (genericTable_isDefined (h)) {
81 static /*@unused@*/ cstring
82 ghbucket_unparse (ghbucket h)
84 cstring s = cstring_undefined;
86 if (!ghbucket_isNull (h))
90 for (i = 0; i < h->size; i++)
92 s = message ("%q %s", s, h->entries[i]->key);
100 static ghbucket ghbucket_single (/*@keep@*/ ghentry e)
102 ghbucket h = (ghbucket) dmalloc (sizeof (*h));
105 h->nspace = GHBUCKET_BASESIZE - 1;
106 h->entries = (ghentry *) dmalloc (GHBUCKET_BASESIZE * sizeof (*h->entries));
113 ghbucket_grow (/*@notnull@*/ ghbucket h)
118 h->nspace += GHBUCKET_BASESIZE;
120 newentries = (ghentry *)
121 dmalloc ((h->size + GHBUCKET_BASESIZE) * sizeof (*newentries));
123 for (i = 0; i < h->size; i++)
125 newentries[i] = h->entries[i];
129 h->entries = newentries;
131 } /*@=compmempass*/ /* Spurious warnings reported for h->entries */
133 static /*@null@*/ /*@exposed@*/ void *ghbucket_lookup (ghbucket p_h, cstring p_key);
136 ** bizarre duplicate behaviour
137 ** required for duplicate entries
141 ghbucket_add (/*@notnull@*/ ghbucket h, /*@only@*/ ghentry e)
143 void *exloc = ghbucket_lookup (h, e->key);
146 llcontbug (message ("ghbucket_add: adding duplicate entry: %s",
152 if (h->nspace == 0) {
156 h->entries[h->size] = e;
162 ghbucket_ncollisions (ghbucket h)
164 if (!ghbucket_isNull (h) && (h->size > 1))
165 return (h->size - 1);
170 /*@exposed@*/ /*@null@*/ void *
171 ghbucket_lookup (ghbucket h, cstring key)
173 if (!ghbucket_isNull (h))
177 for (i = 0; i < h->size; i++)
179 if (cstring_equal (h->entries[i]->key, key))
181 return h->entries[i]->val;
190 void ghbucket_free (/*@only@*/ ghbucket h)
192 if (!ghbucket_isNull (h))
196 for (i = 0; i < h->size; i++)
198 ghentry_free (h->entries[i]);
207 genericTable_free (/*@only@*/ genericTable h)
209 if (genericTable_isDefined (h))
213 for (i = 0; i < h->size; i++)
215 ghbucket_free (h->buckets[i]);
224 genericTable_countCollisions (genericTable h)
229 llassert (genericTable_isDefined (h));
231 for (i = 0; i < h->size; i++)
233 nc += ghbucket_ncollisions (h->buckets[i]);
241 genericTable_countEmpty (genericTable h)
246 llassert (genericTable_isDefined (h));
248 for (i = 0; i < h->size; i++)
250 if (ghbucket_isEmpty (h->buckets[i]))
260 ** hash function snarfed from quake/hash.c Hash_String
261 ** by Stephen Harrison
265 genericTable_hashValue (/*@notnull@*/ genericTable h, cstring key)
268 unsigned int hash_value = 0;
270 llassert (h->size != 0);
272 for (p = cstring_toCharsSafe (key); *p != '\0'; p++)
274 hash_value = (hash_value << 1) ^ g_randomNumbers[*p % 256];
277 return (hash_value % h->size);
280 static /*@exposed@*/ ghbucket
281 genericTable_hash (/*@notnull@*/ genericTable h, cstring key)
283 return h->buckets[genericTable_hashValue (h, key)];
287 /*@only@*/ genericTable
288 genericTable_create (int size)
291 genericTable h = (genericTable) dmalloc (sizeof (*h));
296 h->buckets = (ghbucket *) dmalloc (sizeof (*h->buckets) * size);
299 for (i = 0; i < size; i++)
301 h->buckets[i] = ghbucket_undefined;
309 static /*@unused@*/ void
310 genericTable_print (genericTable h)
314 if (genericTable_isDefined (h)) {
315 for (i = 0; i < h->size; i++)
317 ghbucket hb = h->buckets[i];
321 llmsg (message ("%d. %s\n", i, ghbucket_unparse (hb)));
325 llmsg (message ("size: %d, collisions: %d, empty: %d",
327 genericTable_countCollisions (h),
328 genericTable_countEmpty (h)));
330 llmsglit ("Empty hash table.");
337 genericTable_stats (genericTable h)
339 llassert (genericTable_isDefined (h));
340 return (message ("size: %d, collisions: %d, empty: %d\n",
341 h->size, genericTable_countCollisions (h),
342 genericTable_countEmpty (h)));
346 genericTable_addEntry (/*@notnull@*/ genericTable h, /*@only@*/ ghentry e)
348 unsigned int hindex = genericTable_hashValue (h, e->key);
351 ** ghbucket hb = h->buckets[hindex];
352 ** instead reveals a bug I don't want to deal with right now!
357 if (ghbucket_isNull (h->buckets[hindex]))
359 h->buckets[hindex] = ghbucket_single (e);
363 ghbucket_add (h->buckets[hindex], e);
368 genericTable_insert (genericTable h, cstring key, void *value)
374 llassert (genericTable_isDefined (h));
377 ** rehashing based (loosely) on code by Steve Harrison
380 if (h->nentries * 162 > h->size * 100)
383 int oldsize = h->size;
384 int newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */
385 ghbucket *oldbuckets = h->buckets;
387 DPRINTF (("Rehashing..."));
390 h->buckets = (ghbucket *) dmalloc (sizeof (*h->buckets) * newsize);
393 for (i = 0; i < newsize; i++)
395 h->buckets[i] = ghbucket_undefined;
399 for (i = 0; i < oldsize; i++)
401 ghbucket bucket = oldbuckets[i];
403 oldbuckets[i] = NULL;
405 if (!ghbucket_isNull (bucket))
409 for (j = 0; j < bucket->size; j++)
411 genericTable_addEntry (h, bucket->entries[j]);
414 sfree (bucket->entries); /* evans 2001-03-24: Splint caught this */
422 /* evans 2000-12-22: this was before the rehash! Lost an entry size! */
424 e = ghentry_create (key, value);
425 hindex = genericTable_hashValue (h, key);
426 hb = h->buckets[hindex];
428 if (ghbucket_isNull (hb))
430 h->buckets[hindex] = ghbucket_single (e);
434 ghbucket_add (hb, e);
438 /*@null@*/ /*@exposed@*/ void *
439 genericTable_lookup (genericTable h, cstring key)
443 llassert (genericTable_isDefined (h));
445 hb = genericTable_hash (h, key);
446 res = ghbucket_lookup (hb, key);
448 /* if (res == NULL) { DPRINTF (("Lookup not found: %s", key)); } */
453 genericTable_update (genericTable h, cstring key, /*@only@*/ void *newval)
457 llassert (genericTable_isDefined (h));
459 hb = genericTable_hash (h, key);
461 if (!ghbucket_isNull (hb))
465 for (i = 0; i < hb->size; i++)
467 if (cstring_equal (hb->entries[i]->key, key))
469 llassert (newval != NULL);
470 hb->entries[i]->val = newval;
476 llbug (message ("genericTable_update: %s not found", key));
480 genericTable_remove (genericTable h, cstring key)
484 llassert (genericTable_isDefined (h));
485 hb = genericTable_hash (h, key);
487 if (!ghbucket_isNull (hb))
491 for (i = 0; i < hb->size; i++)
493 if (cstring_equal (hb->entries[i]->key, key))
495 if (i < hb->size - 1)
497 hb->entries[i] = hb->entries[hb->size - 1];
506 llbug (message ("genericTable_removeKey: %s not found", key));
509 bool genericTable_contains (genericTable h, cstring key)
511 return (genericTable_lookup (h, key) != NULL);