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 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 static unsigned int
 260 genericTable_hashValue (/*@notnull@*/ genericTable h, cstring key)
 261 {
 262   llassert (h->size != 0);
 263   return (cstring_hashValue(key) % h->size);
 264 }
 265
 266 static /*@exposed@*/ ghbucket
 267 genericTable_hash (/*@notnull@*/ genericTable h, cstring key)
 268 {
 269   return h->buckets[genericTable_hashValue (h, key)];
 270 }
 271
 272
 273 /*@only@*/ genericTable
 274 genericTable_create (int size)
 275 {
 276   int i;
 277   genericTable h = (genericTable) dmalloc (sizeof (*h));
 278
 279   llassert (size > 0);
 280   h->size = size;
 281   h->nentries = 0;
 282   h->buckets = (ghbucket *) dmalloc (sizeof (*h->buckets) * size);
 283
 284   /*@+loopexec@*/
 285   for (i = 0; i < size; i++)
 286     {
 287       h->buckets[i] = ghbucket_undefined;
 288     }
 289   /*@-loopexec@*/
 290   return h;
 291 }
 292
 293 # if 0
 294 /*@-mustfree@*/
 295 static /*@unused@*/ void
 296 genericTable_print (genericTable h)
 297 {
 298   int i;
 299
 300   if (genericTable_isDefined (h)) {
 301     for (i = 0; i < h->size; i++)
 302       {
 303         ghbucket hb = h->buckets[i];
 304
 305         if (hb != NULL)
 306           {
 307             llmsg (message ("%d. %s\n", i, ghbucket_unparse (hb)));
 308           }
 309       }
 310
 311     llmsg (message ("size: %d, collisions: %d, empty: %d",
 312                     h->size,
 313                     genericTable_countCollisions (h),
 314                     genericTable_countEmpty (h)));
 315   } else {
 316     llmsglit ("Empty hash table.");
 317   }
 318 }
 319 /*@=mustfree@*/
 320 # endif
 321
 322 /*@only@*/ cstring
 323 genericTable_stats (genericTable h)
 324 {
 325   llassert (genericTable_isDefined (h));
 326   return (message ("size: %d, collisions: %d, empty: %d\n",
 327                    h->size, genericTable_countCollisions (h),
 328                    genericTable_countEmpty (h)));
 329 }
 330
 331 static void
 332 genericTable_addEntry (/*@notnull@*/ genericTable h, /*@only@*/ ghentry e)
 333 {
 334   unsigned int hindex = genericTable_hashValue (h, e->key);
 335   /*
 336   ** using
 337   **   ghbucket hb = h->buckets[hindex];
 338   ** instead reveals a bug I don't want to deal with right now!
 339   */
 340
 341   h->nentries++;
 342
 343   if (ghbucket_isNull (h->buckets[hindex]))
 344     {
 345       h->buckets[hindex] = ghbucket_single (e);
 346     }
 347   else
 348     {
 349       ghbucket_add (h->buckets[hindex], e);
 350     }
 351 }
 352
 353 void
 354 genericTable_insert (genericTable h, cstring key, void *value)
 355 {
 356   unsigned int hindex;
 357   ghbucket hb;
 358   ghentry e;
 359
 360   llassert (genericTable_isDefined (h));
 361
 362   /*
 363   ** rehashing based (loosely) on code by Steve Harrison
 364   */
 365
 366   if (h->nentries * 162 > h->size * 100)
 367     {
 368       int i;
 369       int oldsize = h->size;
 370       int newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */
 371       ghbucket *oldbuckets = h->buckets;
 372
 373       DPRINTF (("Rehashing..."));
 374       h->size = newsize;
 375       h->nentries = 0;
 376       h->buckets = (ghbucket *) dmalloc (sizeof (*h->buckets) * newsize);
 377
 378       /*@+loopexec@*/
 379       for (i = 0; i < newsize; i++)
 380         {
 381           h->buckets[i] = ghbucket_undefined;
 382         }
 383       /*@=loopexec@*/
 384
 385       for (i = 0; i < oldsize; i++)
 386         {
 387           ghbucket bucket = oldbuckets[i];
 388
 389           oldbuckets[i] = NULL;
 390
 391           if (!ghbucket_isNull (bucket))
 392             {
 393               int j;
 394
 395               for (j = 0; j < bucket->size; j++)
 396                 {
 397                   genericTable_addEntry (h, bucket->entries[j]);
 398                 }
 399
 400               sfree (bucket->entries); /* evans 2001-03-24: Splint caught this */
 401               sfree (bucket);
 402             }
 403         }
 404
 405       sfree (oldbuckets);
 406     }
 407
 408   /* evans 2000-12-22: this was before the rehash!  Lost an entry size! */
 409   h->nentries++;
 410   e = ghentry_create (key, value);
 411   hindex = genericTable_hashValue (h, key);
 412   hb = h->buckets[hindex];
 413
 414   if (ghbucket_isNull (hb))
 415       {
 416         h->buckets[hindex] = ghbucket_single (e);
 417       }
 418   else
 419       {
 420         ghbucket_add (hb, e);
 421       }
 422 }
 423
 424 /*@null@*/ /*@exposed@*/ void *
 425 genericTable_lookup (genericTable h, cstring key)
 426 {
 427   ghbucket hb;
 428   void *res;
 429   llassert (genericTable_isDefined (h));
 430
 431   hb = genericTable_hash (h, key);
 432   res = ghbucket_lookup (hb, key);
 433
 434   /* if (res == NULL) { DPRINTF (("Lookup not found: %s", key)); } */
 435   return res;
 436 }
 437
 438 void
 439 genericTable_update (genericTable h, cstring key, /*@only@*/ void *newval)
 440 {
 441   ghbucket hb;
 442
 443   llassert (genericTable_isDefined (h));
 444
 445   hb = genericTable_hash (h, key);
 446
 447   if (!ghbucket_isNull (hb))
 448     {
 449       int i;
 450
 451       for (i = 0; i < hb->size; i++)
 452         {
 453           if (cstring_equal (hb->entries[i]->key, key))
 454             {
 455               llassert (newval != NULL);
 456               hb->entries[i]->val = newval;
 457               return;
 458             }
 459         }
 460     }
 461
 462   llbug (message ("genericTable_update: %s not found", key));
 463 }
 464
 465 void
 466 genericTable_remove (genericTable h, cstring key)
 467 {
 468   ghbucket hb;
 469
 470   llassert (genericTable_isDefined (h));
 471   hb = genericTable_hash (h, key);
 472
 473   if (!ghbucket_isNull (hb))
 474     {
 475       int i;
 476
 477       for (i = 0; i < hb->size; i++)
 478         {
 479           if (cstring_equal (hb->entries[i]->key, key))
 480             {
 481               if (i < hb->size - 1)
 482                 {
 483                   hb->entries[i] = hb->entries[hb->size - 1];
 484                 }
 485
 486               hb->size--;
 487               return;
 488             }
 489         }
 490     }
 491
 492   llbug (message ("genericTable_removeKey: %s not found", key));
 493 }
 494
 495 bool genericTable_contains (genericTable h, cstring key)
 496 {
 497   return (genericTable_lookup (h, key) != NULL);
 498 }