src/genericTable.c

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