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 "cstringHash.h"
  34
  35 /*@constant null ghbucket ghbucket_undefined; @*/
  36 # define ghbucket_undefined 0
  37
  38 /*@constant int GHBUCKET_BASESIZE; @*/
  39 # define GHBUCKET_BASESIZE 2
  40
  41 static /*@nullwhentrue@*/ bool ghbucket_isNull (/*@null@*/ ghbucket h)
  42 {
  43   return (h == ghbucket_undefined);
  44 }
  45
  46 static ghentry
  47 ghentry_create (/*@keep@*/ cstring key, /*@keep@*/ void *val)
  48 {
  49   ghentry h = (ghentry) dmalloc (sizeof (*h));
  50
  51   h->key = key;
  52
  53   llassert (val != NULL);
  54   h->val = val;
  55
  56   return (h);
  57 }
  58
  59 static void
  60 ghentry_free (/*@only@*/ ghentry ghe)
  61 {
  62   cstring_free (ghe->key);
  63   /* can't free val contents */
  64   sfree (ghe->val);
  65   sfree (ghe);
  66 }
  67
  68 # if 0
  69 static bool
  70 ghbucket_isEmpty (ghbucket h)
  71 {
  72   return (h == ghbucket_undefined || h->size == 0);
  73 }
  74 # endif
  75
  76 int genericTable_size (genericTable h)
  77 {
  78   if (genericTable_isDefined (h)) {
  79     return h->nentries;
  80   } else {
  81     return 0;
  82   }
  83 }
  84
  85 # if 0
  86 static /*@unused@*/ cstring
  87 ghbucket_unparse (ghbucket h)
  88 {
  89   cstring s = cstring_undefined;
  90
  91   if (!ghbucket_isNull (h))
  92     {
  93       int i;
  94
  95       for (i = 0; i < h->size; i++)
  96         {
  97           s = message ("%q %s", s, h->entries[i]->key);
  98         }
  99     }
 100
 101   return s;
 102 }
 103 # endif
 104
 105 static ghbucket ghbucket_single (/*@keep@*/ ghentry e)
 106 {
 107   ghbucket h = (ghbucket) dmalloc (sizeof (*h));
 108
 109   h->size = 1;
 110   h->nspace = GHBUCKET_BASESIZE - 1;
 111   h->entries = (ghentry *) dmalloc (GHBUCKET_BASESIZE * sizeof (*h->entries));
 112   h->entries[0] = e;
 113
 114   return (h);
 115 }
 116
 117 static void
 118 ghbucket_grow (/*@notnull@*/ ghbucket h)
 119 {
 120   int i;
 121   ghentry *newentries;
 122
 123   h->nspace += GHBUCKET_BASESIZE;
 124
 125   newentries = (ghentry *)
 126     dmalloc ((h->size + GHBUCKET_BASESIZE) * sizeof (*newentries));
 127
 128   for (i = 0; i < h->size; i++)
 129     {
 130       newentries[i] = h->entries[i];
 131     }
 132
 133   sfree (h->entries);
 134   h->entries = newentries;
 135   /*@-compmempass@*/
 136 } /*@=compmempass*/ /* Spurious warnings reported for h->entries */
 137
 138 static /*@null@*/ /*@exposed@*/ void *ghbucket_lookup (ghbucket p_h, cstring p_key);
 139
 140 /*
 141 ** bizarre duplicate behaviour
 142 ** required for duplicate entries
 143 */
 144
 145 static void
 146 ghbucket_add (/*@notnull@*/ ghbucket h, /*@only@*/ ghentry e)
 147 {
 148   void *exloc = ghbucket_lookup (h, e->key);
 149
 150   if (exloc != NULL) {
 151     llcontbug (message ("ghbucket_add: adding duplicate entry: %s",
 152                         e->key));
 153     ghentry_free (e);
 154     return;
 155   }
 156
 157   if (h->nspace == 0) {
 158     ghbucket_grow (h);
 159   }
 160
 161   h->entries[h->size] = e;
 162   h->size++;
 163   h->nspace--;
 164 }
 165
 166 # if 0
 167 static int
 168 ghbucket_ncollisions (ghbucket h)
 169 {
 170   if (!ghbucket_isNull (h) && (h->size > 1))
 171     return (h->size - 1);
 172   else
 173     return 0;
 174 }
 175 # endif
 176
 177 /*@exposed@*/ /*@null@*/ void *
 178 ghbucket_lookup (ghbucket h, cstring key)
 179 {
 180   if (!ghbucket_isNull (h))
 181     {
 182       int i;
 183
 184       for (i = 0; i < h->size; i++)
 185         {
 186           if (cstring_equal (h->entries[i]->key, key))
 187             {
 188                 return h->entries[i]->val;
 189             }
 190         }
 191     }
 192
 193   return NULL;
 194 }
 195
 196 static
 197 void ghbucket_free (/*@only@*/ ghbucket h)
 198 {
 199   if (!ghbucket_isNull (h))
 200     {
 201       int i;
 202
 203       for (i = 0; i < h->size; i++)
 204         {
 205           ghentry_free (h->entries[i]);
 206         }
 207
 208       sfree (h->entries);
 209       sfree (h);
 210     }
 211 }
 212
 213 void
 214 genericTable_free (/*@only@*/ genericTable h)
 215 {
 216   if (genericTable_isDefined (h))
 217     {
 218       int i;
 219
 220       for (i = 0; i < h->size; i++)
 221         {
 222           ghbucket_free (h->buckets[i]);
 223         }
 224
 225       sfree (h->buckets);
 226       sfree (h);
 227     }
 228 }
 229
 230 # if 0
 231 static int
 232 genericTable_countCollisions (genericTable h)
 233 {
 234   int nc = 0;
 235   int i;
 236
 237   llassert (genericTable_isDefined (h));
 238
 239   for (i = 0; i < h->size; i++)
 240     {
 241       nc += ghbucket_ncollisions (h->buckets[i]);
 242     }
 243
 244   return (nc);
 245 }
 246
 247
 248 static int
 249 genericTable_countEmpty (genericTable h)
 250 {
 251   int nc = 0;
 252   int i;
 253
 254   llassert (genericTable_isDefined (h));
 255
 256   for (i = 0; i < h->size; i++)
 257     {
 258       if (ghbucket_isEmpty (h->buckets[i]))
 259         {
 260           nc++;
 261         }
 262     }
 263
 264   return (nc);
 265 }
 266 # endif
 267
 268 static unsigned int
 269 genericTable_hashValue (/*@notnull@*/ genericTable h, cstring key)
 270 {
 271   llassert (h->size != 0);
 272   return (cstring_hashValue(key) % h->size);
 273 }
 274
 275 static /*@exposed@*/ ghbucket
 276 genericTable_hash (/*@notnull@*/ genericTable h, cstring key)
 277 {
 278   return h->buckets[genericTable_hashValue (h, key)];
 279 }
 280
 281
 282 /*@only@*/ genericTable
 283 genericTable_create (int size)
 284 {
 285   int i;
 286   genericTable h = (genericTable) dmalloc (sizeof (*h));
 287
 288   llassert (size > 0);
 289   h->size = size;
 290   h->nentries = 0;
 291   h->buckets = (ghbucket *) dmalloc (sizeof (*h->buckets) * size);
 292
 293   /*@+loopexec@*/
 294   for (i = 0; i < size; i++)
 295     {
 296       h->buckets[i] = ghbucket_undefined;
 297     }
 298   /*@-loopexec@*/
 299   return h;
 300 }
 301
 302 # if 0
 303 /*@-mustfree@*/
 304 static /*@unused@*/ void
 305 genericTable_print (genericTable h)
 306 {
 307   int i;
 308
 309   if (genericTable_isDefined (h)) {
 310     for (i = 0; i < h->size; i++)
 311       {
 312         ghbucket hb = h->buckets[i];
 313
 314         if (hb != NULL)
 315           {
 316             llmsg (message ("%d. %s\n", i, ghbucket_unparse (hb)));
 317           }
 318       }
 319
 320     llmsg (message ("size: %d, collisions: %d, empty: %d",
 321                     h->size,
 322                     genericTable_countCollisions (h),
 323                     genericTable_countEmpty (h)));
 324   } else {
 325     llmsglit ("Empty hash table.");
 326   }
 327 }
 328 /*@=mustfree@*/
 329 # endif
 330
 331 # ifdef DEADCODE
 332 /*@only@*/ cstring
 333 genericTable_stats (genericTable h)
 334 {
 335   llassert (genericTable_isDefined (h));
 336   return (message ("size: %d, collisions: %d, empty: %d\n",
 337                    h->size, genericTable_countCollisions (h),
 338                    genericTable_countEmpty (h)));
 339 }
 340 # endif /* DEADCODE */
 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 # ifdef DEADCODE
 477 void
 478 genericTable_remove (genericTable h, cstring key)
 479 {
 480   ghbucket hb;
 481
 482   llassert (genericTable_isDefined (h));
 483   hb = genericTable_hash (h, key);
 484
 485   if (!ghbucket_isNull (hb))
 486     {
 487       int i;
 488
 489       for (i = 0; i < hb->size; i++)
 490         {
 491           if (cstring_equal (hb->entries[i]->key, key))
 492             {
 493               if (i < hb->size - 1)
 494                 {
 495                   hb->entries[i] = hb->entries[hb->size - 1];
 496                 }
 497
 498               hb->size--;
 499               return;
 500             }
 501         }
 502     }
 503
 504   llbug (message ("genericTable_removeKey: %s not found", key));
 505 }
 506 # endif /* DEADCODE */
 507
 508 bool genericTable_contains (genericTable h, cstring key)
 509 {
 510   return (genericTable_lookup (h, key) != NULL);
 511 }