src/genericTable.c

   1 /*
   2 ** Splint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2003 University of Virginia,
   4 **         Massachusetts Institute of Technology
   5 **
   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.
  10 **
  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.
  15 **
  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.
  19 **
  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
  23 */
  24 /*
  25 ** genericTable.c
  26 **
  27 ** A genericTable is a mapping from string keys to void * objects.
  28 ** We sacrific type checking here for code reuse.
  29 */
  30
  31 # include "splintMacros.nf"
  32 # include "basic.h"
  33 # include "randomNumbers.h"
  34
  35 /*@constant null ghbucket ghbucket_undefined; @*/
  36 # define ghbucket_undefined 0
  37
  38 static /*@nullwhentrue@*/ bool ghbucket_isNull (/*@null@*/ ghbucket h)
  39 {
  40   return (h == ghbucket_undefined);
  41 }
  42
  43 static ghentry
  44 ghentry_create (/*@keep@*/ cstring key, /*@keep@*/ void *val)
  45 {
  46   ghentry h = (ghentry) dmalloc (sizeof (*h));
  47
  48   h->key = key;
  49
  50   llassert (val != NULL);
  51   h->val = val;
  52
  53   return (h);
  54 }
  55
  56 static void
  57 ghentry_free (/*@only@*/ ghentry ghe)
  58 {
  59   cstring_free (ghe->key);
  60   /* can't free val contents */
  61   sfree (ghe->val);
  62   sfree (ghe);
  63 }
  64
  65 static bool
  66 ghbucket_isEmpty (ghbucket h)
  67 {
  68   return (h == ghbucket_undefined || h->size == 0);
  69 }
  70
  71 int genericTable_size (genericTable h)
  72 {
  73   if (genericTable_isDefined (h)) {
  74     return h->nentries;
  75   } else {
  76     return 0;
  77   }
  78 }
  79
  80 # if 0
  81 static /*@unused@*/ cstring
  82 ghbucket_unparse (ghbucket h)
  83 {
  84   cstring s = cstring_undefined;
  85
  86   if (!ghbucket_isNull (h))
  87     {
  88       int i;
  89
  90       for (i = 0; i < h->size; i++)
  91         {
  92           s = message ("%q %s", s, h->entries[i]->key);
  93         }
  94     }
  95
  96   return s;
  97 }
  98 # endif
  99
 100 static ghbucket ghbucket_single (/*@keep@*/ ghentry e)
 101 {
 102   ghbucket h = (ghbucket) dmalloc (sizeof (*h));
 103
 104   h->size = 1;
 105   h->nspace = GHBUCKET_BASESIZE - 1;
 106   h->entries = (ghentry *) dmalloc (GHBUCKET_BASESIZE * sizeof (*h->entries));
 107   h->entries[0] = e;
 108
 109   return (h);
 110 }
 111
 112 static void
 113 ghbucket_grow (/*@notnull@*/ ghbucket h)
 114 {
 115   int i;
 116   ghentry *newentries;
 117
 118   h->nspace += GHBUCKET_BASESIZE;
 119
 120   newentries = (ghentry *)
 121     dmalloc ((h->size + GHBUCKET_BASESIZE) * sizeof (*newentries));
 122
 123   for (i = 0; i < h->size; i++)
 124     {
 125       newentries[i] = h->entries[i];
 126     }
 127
 128   sfree (h->entries);
 129   h->entries = newentries;
 130   /*@-compmempass@*/
 131 } /*@=compmempass*/ /* Spurious warnings reported for h->entries */
 132
 133 static /*@null@*/ /*@exposed@*/ void *ghbucket_lookup (ghbucket p_h, cstring p_key);
 134
 135 /*
 136 ** bizarre duplicate behaviour
 137 ** required for duplicate entries
 138 */
 139
 140 static void
 141 ghbucket_add (/*@notnull@*/ ghbucket h, /*@only@*/ ghentry e)
 142 {
 143     void *exloc = ghbucket_lookup (h, e->key);
 144
 145     if (exloc != NULL) {
 146       llassert (FALSE);
 147     }
 148
 149     if (h->nspace == 0) {
 150         ghbucket_grow (h);
 151     }
 152
 153     h->entries[h->size] = e;
 154     h->size++;
 155     h->nspace--;
 156 }
 157
 158 static int
 159 ghbucket_ncollisions (ghbucket h)
 160 {
 161   if (!ghbucket_isNull (h) && (h->size > 1))
 162     return (h->size - 1);
 163   else
 164     return 0;
 165 }
 166
 167 /*@exposed@*/ /*@null@*/ void *
 168 ghbucket_lookup (ghbucket h, cstring key)
 169 {
 170   if (!ghbucket_isNull (h))
 171     {
 172       int i;
 173
 174       for (i = 0; i < h->size; i++)
 175         {
 176           if (cstring_equal (h->entries[i]->key, key))
 177             {
 178                 return h->entries[i]->val;
 179             }
 180         }
 181     }
 182
 183   return NULL;
 184 }
 185
 186 static
 187 void ghbucket_free (/*@only@*/ ghbucket h)
 188 {
 189   if (!ghbucket_isNull (h))
 190     {
 191       int i;
 192
 193       for (i = 0; i < h->size; i++)
 194         {
 195           ghentry_free (h->entries[i]);
 196         }
 197
 198       sfree (h->entries);
 199       sfree (h);
 200     }
 201 }
 202
 203 void
 204 genericTable_free (/*@only@*/ genericTable h)
 205 {
 206   if (genericTable_isDefined (h))
 207     {
 208       int i;
 209
 210       for (i = 0; i < h->size; i++)
 211         {
 212           ghbucket_free (h->buckets[i]);
 213         }
 214
 215       sfree (h->buckets);
 216       sfree (h);
 217     }
 218 }
 219
 220 static int
 221 genericTable_countCollisions (genericTable h)
 222 {
 223   int nc = 0;
 224   int i;
 225
 226   llassert (genericTable_isDefined (h));
 227
 228   for (i = 0; i < h->size; i++)
 229     {
 230       nc += ghbucket_ncollisions (h->buckets[i]);
 231     }
 232
 233   return (nc);
 234 }
 235
 236
 237 static int
 238 genericTable_countEmpty (genericTable h)
 239 {
 240   int nc = 0;
 241   int i;
 242
 243   llassert (genericTable_isDefined (h));
 244
 245   for (i = 0; i < h->size; i++)
 246     {
 247       if (ghbucket_isEmpty (h->buckets[i]))
 248         {
 249           nc++;
 250         }
 251     }
 252
 253   return (nc);
 254 }
 255
 256 /*
 257 ** hash function snarfed from quake/hash.c Hash_String
 258 ** by Stephen Harrison
 259 */
 260
 261 static unsigned int
 262 genericTable_hashValue (/*@notnull@*/ genericTable h, cstring key)
 263 {
 264   char *p;
 265   unsigned int hash_value = 0;
 266
 267   llassert (h->size != 0);
 268
 269   for (p = cstring_toCharsSafe (key); *p != '\0'; p++)
 270     {
 271       hash_value = (hash_value << 1) ^ g_randomNumbers[*p % 256];
 272     }
 273
 274   return (hash_value % h->size);
 275 }
 276
 277 static /*@exposed@*/ ghbucket
 278 genericTable_hash (/*@notnull@*/ genericTable h, cstring key)
 279 {
 280   return h->buckets[genericTable_hashValue (h, key)];
 281 }
 282
 283
 284 /*@only@*/ genericTable
 285 genericTable_create (int size)
 286 {
 287   int i;
 288   genericTable h = (genericTable) dmalloc (sizeof (*h));
 289
 290   llassert (size > 0);
 291   h->size = size;
 292   h->nentries = 0;
 293   h->buckets = (ghbucket *) dmalloc (sizeof (*h->buckets) * size);
 294
 295   /*@+loopexec@*/
 296   for (i = 0; i < size; i++)
 297     {
 298       h->buckets[i] = ghbucket_undefined;
 299     }
 300   /*@-loopexec@*/
 301   return h;
 302 }
 303
 304 # if 0
 305 /*@-mustfree@*/
 306 static /*@unused@*/ void
 307 genericTable_print (genericTable h)
 308 {
 309   int i;
 310
 311   if (genericTable_isDefined (h)) {
 312     for (i = 0; i < h->size; i++)
 313       {
 314         ghbucket hb = h->buckets[i];
 315
 316         if (hb != NULL)
 317           {
 318             llmsg (message ("%d. %s\n", i, ghbucket_unparse (hb)));
 319           }
 320       }
 321
 322     llmsg (message ("size: %d, collisions: %d, empty: %d",
 323                     h->size,
 324                     genericTable_countCollisions (h),
 325                     genericTable_countEmpty (h)));
 326   } else {
 327     llmsglit ("Empty hash table.");
 328   }
 329 }
 330 /*@=mustfree@*/
 331 # endif
 332
 333 /*@only@*/ cstring
 334 genericTable_stats (genericTable h)
 335 {
 336   llassert (genericTable_isDefined (h));
 337   return (message ("size: %d, collisions: %d, empty: %d\n",
 338                    h->size, genericTable_countCollisions (h),
 339                    genericTable_countEmpty (h)));
 340 }
 341
 342 static void
 343 genericTable_addEntry (/*@notnull@*/ genericTable h, /*@only@*/ ghentry e)
 344 {
 345   unsigned int hindex = genericTable_hashValue (h, e->key);
 346   /*
 347   ** using
 348   **   ghbucket hb = h->buckets[hindex];
 349   ** instead reveals a bug I don't want to deal with right now!
 350   */
 351
 352   h->nentries++;
 353
 354   if (ghbucket_isNull (h->buckets[hindex]))
 355     {
 356       h->buckets[hindex] = ghbucket_single (e);
 357     }
 358   else
 359     {
 360       ghbucket_add (h->buckets[hindex], e);
 361     }
 362 }
 363
 364 void
 365 genericTable_insert (genericTable h, cstring key, void *value)
 366 {
 367   unsigned int hindex;
 368   ghbucket hb;
 369   ghentry e;
 370
 371   llassert (genericTable_isDefined (h));
 372
 373   /*
 374   ** rehashing based (loosely) on code by Steve Harrison
 375   */
 376
 377   if (h->nentries * 162 > h->size * 100)
 378     {
 379       int i;
 380       int oldsize = h->size;
 381       int newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */
 382       ghbucket *oldbuckets = h->buckets;
 383
 384       DPRINTF (("Rehashing..."));
 385       h->size = newsize;
 386       h->nentries = 0;
 387       h->buckets = (ghbucket *) dmalloc (sizeof (*h->buckets) * newsize);
 388
 389       /*@+loopexec@*/
 390       for (i = 0; i < newsize; i++)
 391         {
 392           h->buckets[i] = ghbucket_undefined;
 393         }
 394       /*@=loopexec@*/
 395
 396       for (i = 0; i < oldsize; i++)
 397         {
 398           ghbucket bucket = oldbuckets[i];
 399
 400           oldbuckets[i] = NULL;
 401
 402           if (!ghbucket_isNull (bucket))
 403             {
 404               int j;
 405
 406               for (j = 0; j < bucket->size; j++)
 407                 {
 408                   genericTable_addEntry (h, bucket->entries[j]);
 409                 }
 410
 411               sfree (bucket->entries); /* evans 2001-03-24: Splint caught this */
 412               sfree (bucket);
 413             }
 414         }
 415
 416       sfree (oldbuckets);
 417     }
 418
 419   /* evans 2000-12-22: this was before the rehash!  Lost an entry size! */
 420   h->nentries++;
 421   e = ghentry_create (key, value);
 422   hindex = genericTable_hashValue (h, key);
 423   hb = h->buckets[hindex];
 424
 425   if (ghbucket_isNull (hb))
 426       {
 427         h->buckets[hindex] = ghbucket_single (e);
 428       }
 429   else
 430       {
 431         ghbucket_add (hb, e);
 432       }
 433 }
 434
 435 /*@null@*/ /*@exposed@*/ void *
 436 genericTable_lookup (genericTable h, cstring key)
 437 {
 438   ghbucket hb;
 439   void *res;
 440   llassert (genericTable_isDefined (h));
 441
 442   hb = genericTable_hash (h, key);
 443   res = ghbucket_lookup (hb, key);
 444
 445   /* if (res == NULL) { DPRINTF (("Lookup not found: %s", key)); } */
 446   return res;
 447 }
 448
 449 void
 450 genericTable_update (genericTable h, cstring key, /*@only@*/ void *newval)
 451 {
 452   ghbucket hb;
 453
 454   llassert (genericTable_isDefined (h));
 455
 456   hb = genericTable_hash (h, key);
 457
 458   if (!ghbucket_isNull (hb))
 459     {
 460       int i;
 461
 462       for (i = 0; i < hb->size; i++)
 463         {
 464           if (cstring_equal (hb->entries[i]->key, key))
 465             {
 466               llassert (newval != NULL);
 467               hb->entries[i]->val = newval;
 468               return;
 469             }
 470         }
 471     }
 472
 473   llbug (message ("genericTable_update: %s not found", key));
 474 }
 475
 476 void
 477 genericTable_remove (genericTable h, cstring key)
 478 {
 479   ghbucket hb;
 480
 481   llassert (genericTable_isDefined (h));
 482   hb = genericTable_hash (h, key);
 483
 484   if (!ghbucket_isNull (hb))
 485     {
 486       int i;
 487
 488       for (i = 0; i < hb->size; i++)
 489         {
 490           if (cstring_equal (hb->entries[i]->key, key))
 491             {
 492               if (i < hb->size - 1)
 493                 {
 494                   hb->entries[i] = hb->entries[hb->size - 1];
 495                 }
 496
 497               hb->size--;
 498               return;
 499             }
 500         }
 501     }
 502
 503   llbug (message ("genericTable_removeKey: %s not found", key));
 504 }
 505
 506 bool genericTable_contains (genericTable h, cstring key)
 507 {
 508   return (genericTable_lookup (h, key) != NULL);
 509 }