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