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     llcontbug (message ("ghbucket_add: adding duplicate entry: %s",
 147                         e->key));
 148     ghentry_free (e);
 149     return;
 150   }
 151
 152   if (h->nspace == 0) {
 153     ghbucket_grow (h);
 154   }
 155
 156   h->entries[h->size] = e;
 157   h->size++;
 158   h->nspace--;
 159 }
 160
 161 static int
 162 ghbucket_ncollisions (ghbucket h)
 163 {
 164   if (!ghbucket_isNull (h) && (h->size > 1))
 165     return (h->size - 1);
 166   else
 167     return 0;
 168 }
 169
 170 /*@exposed@*/ /*@null@*/ void *
 171 ghbucket_lookup (ghbucket h, cstring key)
 172 {
 173   if (!ghbucket_isNull (h))
 174     {
 175       int i;
 176
 177       for (i = 0; i < h->size; i++)
 178         {
 179           if (cstring_equal (h->entries[i]->key, key))
 180             {
 181                 return h->entries[i]->val;
 182             }
 183         }
 184     }
 185
 186   return NULL;
 187 }
 188
 189 static
 190 void ghbucket_free (/*@only@*/ ghbucket h)
 191 {
 192   if (!ghbucket_isNull (h))
 193     {
 194       int i;
 195
 196       for (i = 0; i < h->size; i++)
 197         {
 198           ghentry_free (h->entries[i]);
 199         }
 200
 201       sfree (h->entries);
 202       sfree (h);
 203     }
 204 }
 205
 206 void
 207 genericTable_free (/*@only@*/ genericTable h)
 208 {
 209   if (genericTable_isDefined (h))
 210     {
 211       int i;
 212
 213       for (i = 0; i < h->size; i++)
 214         {
 215           ghbucket_free (h->buckets[i]);
 216         }
 217
 218       sfree (h->buckets);
 219       sfree (h);
 220     }
 221 }
 222
 223 static int
 224 genericTable_countCollisions (genericTable h)
 225 {
 226   int nc = 0;
 227   int i;
 228
 229   llassert (genericTable_isDefined (h));
 230
 231   for (i = 0; i < h->size; i++)
 232     {
 233       nc += ghbucket_ncollisions (h->buckets[i]);
 234     }
 235
 236   return (nc);
 237 }
 238
 239
 240 static int
 241 genericTable_countEmpty (genericTable h)
 242 {
 243   int nc = 0;
 244   int i;
 245
 246   llassert (genericTable_isDefined (h));
 247
 248   for (i = 0; i < h->size; i++)
 249     {
 250       if (ghbucket_isEmpty (h->buckets[i]))
 251         {
 252           nc++;
 253         }
 254     }
 255
 256   return (nc);
 257 }
 258
 259 /*
 260 ** hash function snarfed from quake/hash.c Hash_String
 261 ** by Stephen Harrison
 262 */
 263
 264 static unsigned int
 265 genericTable_hashValue (/*@notnull@*/ genericTable h, cstring key)
 266 {
 267   char *p;
 268   unsigned int hash_value = 0;
 269
 270   llassert (h->size != 0);
 271
 272   for (p = cstring_toCharsSafe (key); *p != '\0'; p++)
 273     {
 274       hash_value = (hash_value << 1) ^ g_randomNumbers[*p % 256];
 275     }
 276
 277   return (hash_value % h->size);
 278 }
 279
 280 static /*@exposed@*/ ghbucket
 281 genericTable_hash (/*@notnull@*/ genericTable h, cstring key)
 282 {
 283   return h->buckets[genericTable_hashValue (h, key)];
 284 }
 285
 286
 287 /*@only@*/ genericTable
 288 genericTable_create (int size)
 289 {
 290   int i;
 291   genericTable h = (genericTable) dmalloc (sizeof (*h));
 292
 293   llassert (size > 0);
 294   h->size = size;
 295   h->nentries = 0;
 296   h->buckets = (ghbucket *) dmalloc (sizeof (*h->buckets) * size);
 297
 298   /*@+loopexec@*/
 299   for (i = 0; i < size; i++)
 300     {
 301       h->buckets[i] = ghbucket_undefined;
 302     }
 303   /*@-loopexec@*/
 304   return h;
 305 }
 306
 307 # if 0
 308 /*@-mustfree@*/
 309 static /*@unused@*/ void
 310 genericTable_print (genericTable h)
 311 {
 312   int i;
 313
 314   if (genericTable_isDefined (h)) {
 315     for (i = 0; i < h->size; i++)
 316       {
 317         ghbucket hb = h->buckets[i];
 318
 319         if (hb != NULL)
 320           {
 321             llmsg (message ("%d. %s\n", i, ghbucket_unparse (hb)));
 322           }
 323       }
 324
 325     llmsg (message ("size: %d, collisions: %d, empty: %d",
 326                     h->size,
 327                     genericTable_countCollisions (h),
 328                     genericTable_countEmpty (h)));
 329   } else {
 330     llmsglit ("Empty hash table.");
 331   }
 332 }
 333 /*@=mustfree@*/
 334 # endif
 335
 336 /*@only@*/ cstring
 337 genericTable_stats (genericTable h)
 338 {
 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)));
 343 }
 344
 345 static void
 346 genericTable_addEntry (/*@notnull@*/ genericTable h, /*@only@*/ ghentry e)
 347 {
 348   unsigned int hindex = genericTable_hashValue (h, e->key);
 349   /*
 350   ** using
 351   **   ghbucket hb = h->buckets[hindex];
 352   ** instead reveals a bug I don't want to deal with right now!
 353   */
 354
 355   h->nentries++;
 356
 357   if (ghbucket_isNull (h->buckets[hindex]))
 358     {
 359       h->buckets[hindex] = ghbucket_single (e);
 360     }
 361   else
 362     {
 363       ghbucket_add (h->buckets[hindex], e);
 364     }
 365 }
 366
 367 void
 368 genericTable_insert (genericTable h, cstring key, void *value)
 369 {
 370   unsigned int hindex;
 371   ghbucket hb;
 372   ghentry e;
 373
 374   llassert (genericTable_isDefined (h));
 375
 376   /*
 377   ** rehashing based (loosely) on code by Steve Harrison
 378   */
 379
 380   if (h->nentries * 162 > h->size * 100)
 381     {
 382       int i;
 383       int oldsize = h->size;
 384       int newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */
 385       ghbucket *oldbuckets = h->buckets;
 386
 387       DPRINTF (("Rehashing..."));
 388       h->size = newsize;
 389       h->nentries = 0;
 390       h->buckets = (ghbucket *) dmalloc (sizeof (*h->buckets) * newsize);
 391
 392       /*@+loopexec@*/
 393       for (i = 0; i < newsize; i++)
 394         {
 395           h->buckets[i] = ghbucket_undefined;
 396         }
 397       /*@=loopexec@*/
 398
 399       for (i = 0; i < oldsize; i++)
 400         {
 401           ghbucket bucket = oldbuckets[i];
 402
 403           oldbuckets[i] = NULL;
 404
 405           if (!ghbucket_isNull (bucket))
 406             {
 407               int j;
 408
 409               for (j = 0; j < bucket->size; j++)
 410                 {
 411                   genericTable_addEntry (h, bucket->entries[j]);
 412                 }
 413
 414               sfree (bucket->entries); /* evans 2001-03-24: Splint caught this */
 415               sfree (bucket);
 416             }
 417         }
 418
 419       sfree (oldbuckets);
 420     }
 421
 422   /* evans 2000-12-22: this was before the rehash!  Lost an entry size! */
 423   h->nentries++;
 424   e = ghentry_create (key, value);
 425   hindex = genericTable_hashValue (h, key);
 426   hb = h->buckets[hindex];
 427
 428   if (ghbucket_isNull (hb))
 429       {
 430         h->buckets[hindex] = ghbucket_single (e);
 431       }
 432   else
 433       {
 434         ghbucket_add (hb, e);
 435       }
 436 }
 437
 438 /*@null@*/ /*@exposed@*/ void *
 439 genericTable_lookup (genericTable h, cstring key)
 440 {
 441   ghbucket hb;
 442   void *res;
 443   llassert (genericTable_isDefined (h));
 444
 445   hb = genericTable_hash (h, key);
 446   res = ghbucket_lookup (hb, key);
 447
 448   /* if (res == NULL) { DPRINTF (("Lookup not found: %s", key)); } */
 449   return res;
 450 }
 451
 452 void
 453 genericTable_update (genericTable h, cstring key, /*@only@*/ void *newval)
 454 {
 455   ghbucket hb;
 456
 457   llassert (genericTable_isDefined (h));
 458
 459   hb = genericTable_hash (h, key);
 460
 461   if (!ghbucket_isNull (hb))
 462     {
 463       int i;
 464
 465       for (i = 0; i < hb->size; i++)
 466         {
 467           if (cstring_equal (hb->entries[i]->key, key))
 468             {
 469               llassert (newval != NULL);
 470               hb->entries[i]->val = newval;
 471               return;
 472             }
 473         }
 474     }
 475
 476   llbug (message ("genericTable_update: %s not found", key));
 477 }
 478
 479 void
 480 genericTable_remove (genericTable h, cstring key)
 481 {
 482   ghbucket hb;
 483
 484   llassert (genericTable_isDefined (h));
 485   hb = genericTable_hash (h, key);
 486
 487   if (!ghbucket_isNull (hb))
 488     {
 489       int i;
 490
 491       for (i = 0; i < hb->size; i++)
 492         {
 493           if (cstring_equal (hb->entries[i]->key, key))
 494             {
 495               if (i < hb->size - 1)
 496                 {
 497                   hb->entries[i] = hb->entries[hb->size - 1];
 498                 }
 499
 500               hb->size--;
 501               return;
 502             }
 503         }
 504     }
 505
 506   llbug (message ("genericTable_removeKey: %s not found", key));
 507 }
 508
 509 bool genericTable_contains (genericTable h, cstring key)
 510 {
 511   return (genericTable_lookup (h, key) != NULL);
 512 }