src/hashTable.c

   1 /*
   2 ** LCLint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2000 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 ** hashTable.c
  26 **
  27 ** Since hsearch defined in <search.h> only allows one hash table,
  28 ** I'll implement my own.
  29 **
  30 ** Try to find a decent hash function, etc. later...
  31 **
  32 ** hashTable is from string -> unsigned
  33 **
  34 */
  35
  36 # include "lclintMacros.nf"
  37 # include "basic.h"
  38
  39 /*@constant null hbucket hbucket_undefined; @*/
  40 # define hbucket_undefined 0
  41
  42 static /*@truenull@*/ bool hbucket_isNull (/*@null@*/ hbucket h)
  43 {
  44   return (h == hbucket_undefined);
  45 }
  46
  47 static hentry
  48 hentry_create (cstring key, int val)
  49 {
  50   hentry h;
  51
  52   h.key = key;
  53   h.val = val;
  54   return (h);
  55 }
  56
  57 static bool
  58 hbucket_isEmpty (hbucket h)
  59 {
  60   return (h == hbucket_undefined || h->size == 0);
  61 }
  62
  63 static cstring
  64 hbucket_unparse (hbucket h)
  65 {
  66   cstring s = cstring_undefined;
  67
  68   if (!hbucket_isNull (h))
  69     {
  70       int i;
  71
  72       for (i = 0; i < h->size; i++)
  73         {
  74           s = message ("%q %s:%d", s, h->entries[i].key, h->entries[i].val);
  75         }
  76     }
  77
  78   return s;
  79 }
  80
  81 static hbucket
  82 hbucket_single (hentry e)
  83 {
  84   hbucket h = (hbucket) dmalloc (sizeof (*h));
  85
  86   h->size = 1;
  87   h->nspace = HBUCKET_BASESIZE - 1;
  88   h->entries = (hentry *) dmalloc (HBUCKET_BASESIZE * sizeof (*h->entries));
  89   h->entries[0] = e;
  90
  91   return (h);
  92 }
  93
  94 static void
  95 hbucket_grow (/*@notnull@*/ hbucket h)
  96 {
  97   int i;
  98   hentry *newentries;
  99
 100   h->nspace += HBUCKET_BASESIZE;
 101
 102   newentries = (hentry *)
 103     dmalloc ((h->size + HBUCKET_BASESIZE) * sizeof (*newentries));
 104
 105   for (i = 0; i < h->size; i++)
 106     {
 107       newentries[i] = h->entries[i];
 108     }
 109
 110   sfree (h->entries);
 111   h->entries = newentries;
 112 }
 113
 114 static int hbucket_lookup (hbucket p_h, cstring p_key);
 115
 116 /*
 117 ** bizarre duplicate behaviour
 118 ** required for duplicate entries
 119 */
 120
 121 static void
 122 hbucket_add (/*@notnull@*/ hbucket h, hentry e)
 123 {
 124   int exloc = hbucket_lookup (h, e.key);
 125
 126
 127   if (exloc != HBUCKET_DNE)
 128     {
 129       h->entries[exloc].key = e.key;
 130       h->entries[exloc].val = e.val;
 131       return;
 132     }
 133
 134   if (h->nspace == 0)
 135     {
 136             hbucket_grow (h);
 137     }
 138
 139   h->entries[h->size] = e;
 140   h->size++;
 141   h->nspace--;
 142 }
 143
 144 static int
 145 hbucket_ncollisions (hbucket h)
 146 {
 147   if (!hbucket_isNull (h) && (h->size > 1))
 148     return (h->size - 1);
 149   else
 150     return 0;
 151 }
 152
 153 int
 154 hbucket_lookup (hbucket h, cstring key)
 155 {
 156   if (!hbucket_isNull (h))
 157     {
 158       int i;
 159
 160       for (i = 0; i < h->size; i++)
 161         {
 162           if (cstring_equal (h->entries[i].key, key))
 163             {
 164               return h->entries[i].val;
 165             }
 166         }
 167     }
 168
 169   return HBUCKET_DNE;
 170 }
 171
 172 static
 173 void hbucket_free (/*@only@*/ hbucket h)
 174 {
 175   if (!hbucket_isNull (h))
 176     {
 177       sfree (h->entries);
 178       sfree (h);
 179     }
 180 }
 181
 182 void
 183 hashTable_free (/*@only@*/ hashTable h)
 184 {
 185   int i;
 186
 187   for (i = 0; i < h->size; i++)
 188     {
 189       hbucket_free (h->buckets[i]);
 190     }
 191
 192   sfree (h->buckets);
 193   sfree (h);
 194 }
 195
 196 static int
 197 hashTable_countCollisions (hashTable h)
 198 {
 199   int nc = 0;
 200   int i;
 201
 202   for (i = 0; i < h->size; i++)
 203     {
 204       nc += hbucket_ncollisions (h->buckets[i]);
 205     }
 206
 207   return (nc);
 208 }
 209
 210
 211 static int
 212 hashTable_countEmpty (hashTable h)
 213 {
 214   int nc = 0;
 215   int i;
 216
 217   for (i = 0; i < h->size; i++)
 218     {
 219       if (hbucket_isEmpty (h->buckets[i]))
 220         {
 221           nc++;
 222         }
 223     }
 224
 225   return (nc);
 226 }
 227
 228 /*
 229 ** hash function snarfed from quake/hash.c Hash_String
 230 ** by Stephen Harrison
 231 */
 232
 233 /*
 234  * Here are 256 random numbers for use in the hash function
 235  */
 236
 237 /*@+ignoresigns@*/
 238 static unsigned int RandomNumbers[256] =
 239 {
 240 #include "256_random_numbers.nf"
 241 };
 242 /*@=ignoresigns@*/
 243
 244 static unsigned int
 245 hashTable_hashValue (hashTable h, cstring key)
 246 {
 247   char *p;
 248   unsigned int hash_value = 0;
 249
 250   for (p = cstring_toCharsSafe (key); *p != '\0'; p++)
 251     {
 252       hash_value = (hash_value << 1) ^ RandomNumbers[*p % 256];
 253     }
 254
 255   return (hash_value % h->size);
 256 }
 257
 258 static /*@exposed@*/ hbucket
 259 hashTable_hash (hashTable h, cstring key)
 260 {
 261   return h->buckets[hashTable_hashValue (h, key)];
 262 }
 263
 264
 265 /*@only@*/ hashTable
 266 hashTable_create (int size)
 267 {
 268   int i;
 269   hashTable h = (hashTable) dmalloc (sizeof (*h));
 270
 271   h->size = size;
 272   h->nentries = 0;
 273   h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * size);
 274
 275   /*@+loopexec@*/
 276   for (i = 0; i < size; i++)
 277     {
 278       h->buckets[i] = hbucket_undefined;
 279     }
 280   /*@-loopexec@*/
 281   return h;
 282 }
 283
 284 /*@-mustfree@*/
 285 static /*@unused@*/ void
 286 hashTable_print (hashTable h)
 287 {
 288   int i;
 289
 290   for (i = 0; i < h->size; i++)
 291     {
 292       hbucket hb = h->buckets[i];
 293
 294       if (hb != NULL)
 295         {
 296           llmsg (message ("%d. %s\n", i, hbucket_unparse (hb)));
 297         }
 298     }
 299
 300   llmsg (message ("size: %d, collisions: %d, empty: %d",
 301                   h->size,
 302                   hashTable_countCollisions (h),
 303                   hashTable_countEmpty (h)));
 304 }
 305 /*@=mustfree@*/
 306
 307 /*@only@*/ cstring
 308 hashTable_stats (hashTable h)
 309 {
 310   return (message ("size: %d, collisions: %d, empty: %d\n",
 311                         h->size, hashTable_countCollisions (h),
 312                         hashTable_countEmpty (h)));
 313 }
 314
 315 static void
 316 hashTable_addEntry (hashTable h, hentry e)
 317 {
 318   unsigned int hindex = hashTable_hashValue (h, e.key);
 319   /*
 320   ** using
 321   **   hbucket hb = h->buckets[hindex];
 322   ** instead reveals a bug I don't want to deal with right now!
 323   */
 324
 325   h->nentries++;
 326
 327   if (hbucket_isNull (h->buckets[hindex]))
 328     {
 329       h->buckets[hindex] = hbucket_single (e);
 330     }
 331   else
 332     {
 333       hbucket_add (h->buckets[hindex], e);
 334     }
 335 }
 336
 337 void
 338 hashTable_insert (hashTable h, cstring key, int value)
 339 {
 340   unsigned int hindex;
 341   hbucket hb;
 342   hentry e;
 343
 344
 345   h->nentries++;
 346
 347   /*
 348   ** rehashing based (loosely) on code by Steve Harrison
 349   */
 350
 351   if (h->nentries * 162 > h->size * 100)
 352     {
 353       int i;
 354       int oldsize = h->size;
 355       int newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */
 356       hbucket *oldbuckets = h->buckets;
 357
 358
 359       h->size = newsize;
 360       h->nentries = 0;
 361       h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * newsize);
 362
 363       /*@+loopexec@*/
 364       for (i = 0; i < newsize; i++)
 365         {
 366           h->buckets[i] = hbucket_undefined;
 367         }
 368       /*@=loopexec@*/
 369
 370       for (i = 0; i < oldsize; i++)
 371         {
 372           hbucket bucket = oldbuckets[i];
 373
 374           if (!hbucket_isNull (bucket))
 375             {
 376               int j;
 377
 378               for (j = 0; j < bucket->size; j++)
 379                 {
 380                   hashTable_addEntry (h, bucket->entries[j]);
 381                 }
 382
 383               sfree (bucket);
 384             }
 385         }
 386
 387       sfree (oldbuckets);
 388     }
 389
 390
 391   e = hentry_create (key, value);
 392   hindex = hashTable_hashValue (h, key);
 393   hb = h->buckets[hindex];
 394
 395   if (hbucket_isNull (hb))
 396     {
 397             h->buckets[hindex] = hbucket_single (e);
 398     }
 399   else
 400     {
 401             hbucket_add (hb, e);
 402     }
 403
 404   }
 405
 406 int
 407 hashTable_lookup (hashTable h, cstring key)
 408 {
 409   hbucket hb = hashTable_hash (h, key);
 410
 411   return (hbucket_lookup (hb, key));
 412 }
 413
 414 /*
 415 ** This is needed if oldkey is going to be released.
 416 */
 417
 418 void
 419 hashTable_replaceKey (hashTable h, cstring oldkey, /*@dependent@*/ cstring newkey)
 420 {
 421   hbucket hb = hashTable_hash (h, oldkey);
 422
 423   llassert (cstring_equal (oldkey, newkey));
 424
 425   if (!hbucket_isNull (hb))
 426     {
 427       int i;
 428
 429       for (i = 0; i < hb->size; i++)
 430         {
 431           if (cstring_equal (hb->entries[i].key, oldkey))
 432             {
 433               hb->entries[i].key = newkey;
 434               return;
 435             }
 436         }
 437     }
 438
 439   llbug (message ("hashTable_replaceKey: %s not found", oldkey));
 440 }
 441
 442 void
 443 hashTable_remove (hashTable h, cstring key)
 444 {
 445   hbucket hb = hashTable_hash (h, key);
 446
 447   if (!hbucket_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               if (i < hb->size - 1)
 456                 {
 457                   hb->entries[i] = hb->entries[hb->size - 1];
 458                 }
 459
 460               hb->size--;
 461               return;
 462             }
 463         }
 464     }
 465
 466   llbug (message ("hashTable_removeKey: %s not found", key));
 467 }
 468
 469