src/cstringTable.c

   1 /*
   2 ** Splint - 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://www.splint.org
  23 */
  24 /*
  25 ** cstringTable.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 ** cstringTable is from string -> unsigned
  33 **
  34 */
  35
  36 # include "lclintMacros.nf"
  37 # include "basic.h"
  38 # include "randomNumbers.h"
  39
  40 /*@constant null hbucket hbucket_undefined; @*/
  41 # define hbucket_undefined 0
  42
  43 static void
  44 cstringTable_addEntry (/*@notnull@*/ cstringTable p_h, /*@only@*/ hentry p_e)
  45      /*@modifies p_h@*/ ;
  46
  47 static /*@truenull@*/ bool hbucket_isNull (/*@null@*/ hbucket h)
  48 {
  49   return (h == hbucket_undefined);
  50 }
  51
  52 static hentry hentry_create (/*@keep@*/ cstring key, int val)
  53 {
  54   hentry h = (hentry) dmalloc (sizeof (*h));
  55
  56   h->key = key;
  57   h->val = val;
  58   llassert (val != HBUCKET_DNE); /*@i523 way bogus! */
  59
  60   return (h);
  61 }
  62
  63 static void hentry_free (/*@only@*/ hentry h)
  64 {
  65   cstring_free (h->key);
  66   sfree (h);
  67 }
  68
  69 static bool
  70 hbucket_isEmpty (hbucket h)
  71 {
  72   return (h == hbucket_undefined || h->size == 0);
  73 }
  74
  75 static cstring
  76 hbucket_unparse (hbucket h)
  77 {
  78   cstring s = cstring_undefined;
  79
  80   if (!hbucket_isNull (h))
  81     {
  82       int i;
  83
  84       for (i = 0; i < h->size; i++)
  85         {
  86           s = message ("%q %s:%d", s, h->entries[i]->key, h->entries[i]->val);
  87         }
  88     }
  89
  90   return s;
  91 }
  92
  93 static hbucket
  94 hbucket_single (/*@only@*/ hentry e)
  95 {
  96   hbucket h = (hbucket) dmalloc (sizeof (*h));
  97
  98   h->size = 1;
  99   h->nspace = HBUCKET_BASESIZE - 1;
 100   h->entries = (hentry *) dmalloc (HBUCKET_BASESIZE * sizeof (*h->entries));
 101   h->entries[0] = e;
 102
 103   return (h);
 104 }
 105
 106 static void
 107 hbucket_grow (/*@notnull@*/ hbucket h)
 108 {
 109   int i;
 110   hentry *newentries;
 111
 112   h->nspace += HBUCKET_BASESIZE;
 113
 114   newentries = (hentry *)
 115     dmalloc ((h->size + HBUCKET_BASESIZE) * sizeof (*newentries));
 116
 117   for (i = 0; i < h->size; i++)
 118     {
 119       newentries[i] = h->entries[i];
 120     }
 121
 122   /*@i32@*/ sfree (h->entries);
 123   h->entries = newentries;
 124 /*@i23@*/ }
 125
 126 static int hbucket_lookup (hbucket p_h, cstring p_key);
 127
 128 static bool hbucket_contains (hbucket p_h, cstring p_key) /*@*/ {
 129   return (hbucket_lookup (p_h, p_key) != HBUCKET_DNE);
 130 }
 131
 132 /*
 133 ** bizarre duplicate behaviour
 134 ** required for duplicate entries
 135 */
 136
 137 static void
 138 hbucket_add (/*@notnull@*/ hbucket h, /*@only@*/ hentry e)
 139 {
 140   int exloc = hbucket_lookup (h, e->key);
 141
 142   llassert (exloc == HBUCKET_DNE);
 143
 144   if (h->nspace == 0)
 145     {
 146       hbucket_grow (h);
 147     }
 148
 149   llassert (e->val != HBUCKET_DNE);
 150   h->entries[h->size] = e;
 151   h->size++;
 152   h->nspace--;
 153 }
 154
 155 static int
 156 hbucket_ncollisions (hbucket h)
 157 {
 158   if (!hbucket_isNull (h) && (h->size > 1))
 159     return (h->size - 1);
 160   else
 161     return 0;
 162 }
 163
 164 int
 165 hbucket_lookup (hbucket h, cstring key)
 166 {
 167   if (!hbucket_isNull (h))
 168     {
 169       int i;
 170
 171       for (i = 0; i < h->size; i++)
 172         {
 173           if (cstring_equal (h->entries[i]->key, key))
 174             {
 175               return h->entries[i]->val;
 176             }
 177         }
 178     }
 179
 180   return HBUCKET_DNE;
 181 }
 182
 183 static
 184 void hbucket_free (/*@only@*/ hbucket h)
 185 {
 186   if (!hbucket_isNull (h))
 187     {
 188       /*@i32@*/ sfree (h->entries);
 189       sfree (h);
 190     }
 191 }
 192
 193 void
 194 cstringTable_free (/*@only@*/ cstringTable h)
 195 {
 196   int i;
 197
 198   llassert (cstringTable_isDefined (h));
 199
 200   for (i = 0; i < h->size; i++)
 201     {
 202       hbucket_free (h->buckets[i]);
 203     }
 204
 205   sfree (h->buckets);
 206   sfree (h);
 207 }
 208
 209 static int
 210 cstringTable_countCollisions (cstringTable h)
 211 {
 212   int nc = 0;
 213   int i;
 214
 215   llassert (cstringTable_isDefined (h));
 216
 217   for (i = 0; i < h->size; i++)
 218     {
 219       nc += hbucket_ncollisions (h->buckets[i]);
 220     }
 221
 222   return (nc);
 223 }
 224
 225
 226 static int
 227 cstringTable_countEmpty (cstringTable h)
 228 {
 229   int nc = 0;
 230   int i;
 231
 232   llassert (cstringTable_isDefined (h));
 233
 234   for (i = 0; i < h->size; i++)
 235     {
 236       if (hbucket_isEmpty (h->buckets[i]))
 237         {
 238           nc++;
 239         }
 240     }
 241
 242   return (nc);
 243 }
 244
 245 /*
 246 ** hash function snarfed from quake/hash.c Hash_String
 247 ** by Stephen Harrison
 248 */
 249
 250 static unsigned int
 251 cstringTable_hashValue (/*@notnull@*/ cstringTable h, cstring key)
 252 {
 253   char *p;
 254   unsigned int hash_value = 0;
 255
 256   for (p = cstring_toCharsSafe (key); *p != '\0'; p++)
 257     {
 258       hash_value = (hash_value << 1) ^ g_randomNumbers[*p % 256];
 259     }
 260
 261   return (hash_value % h->size);
 262 }
 263
 264 static /*@exposed@*/ hbucket
 265 cstringTable_hash (/*@notnull@*/ cstringTable h, cstring key)
 266 {
 267   return h->buckets[cstringTable_hashValue (h, key)];
 268 }
 269
 270
 271 /*@only@*/ cstringTable
 272 cstringTable_create (int size)
 273 {
 274   int i;
 275   cstringTable h = (cstringTable) dmalloc (sizeof (*h));
 276
 277   h->size = size;
 278   h->nentries = 0;
 279   h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * size);
 280
 281   /*@+loopexec@*/
 282   for (i = 0; i < size; i++)
 283     {
 284       h->buckets[i] = hbucket_undefined;
 285     }
 286   /*@-loopexec@*/
 287   return h;
 288 }
 289
 290 cstring cstringTable_unparse (cstringTable h)
 291 {
 292   cstring res = cstring_newEmpty ();
 293   int i;
 294
 295   if (cstringTable_isDefined (h))
 296     {
 297       for (i = 0; i < h->size; i++)
 298         {
 299           hbucket hb = h->buckets[i];
 300
 301           if (hb != NULL)
 302             {
 303               res = message ("%q%d. %q\n", res, i, hbucket_unparse (hb));
 304             }
 305         }
 306
 307       res = message ("%qsize: %d, collisions: %d, empty: %d",
 308                      res,
 309                      h->size,
 310                      cstringTable_countCollisions (h),
 311                      cstringTable_countEmpty (h));
 312     }
 313   else
 314     {
 315       cstring_free (res);
 316       res = cstring_makeLiteral ("< empty cstring table >");
 317     }
 318
 319   return res;
 320 }
 321
 322
 323 /*@only@*/ cstring
 324 cstringTable_stats (cstringTable h)
 325 {
 326   llassert (cstringTable_isDefined (h));
 327   return (message ("size: %d, collisions: %d, empty: %d\n",
 328                    h->size, cstringTable_countCollisions (h),
 329                    cstringTable_countEmpty (h)));
 330 }
 331
 332 static void
 333 cstringTable_rehash (/*@notnull@*/ cstringTable h)
 334 {
 335   /*
 336   ** rehashing based (loosely) on code by Steve Harrison
 337   */
 338
 339   int i;
 340   int oldsize = h->size;
 341   int newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */
 342   hbucket *oldbuckets = h->buckets;
 343
 344   h->size = newsize;
 345   h->nentries = 0;
 346   h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * newsize);
 347
 348   /*@+loopexec@*/
 349   for (i = 0; i < newsize; i++)
 350     {
 351       h->buckets[i] = hbucket_undefined;
 352     }
 353   /*@=loopexec@*/
 354
 355   for (i = 0; i < oldsize; i++)
 356     {
 357       hbucket bucket = oldbuckets[i];
 358
 359       oldbuckets[i] = NULL;
 360
 361       if (!hbucket_isNull (bucket))
 362         {
 363           int j;
 364
 365           for (j = 0; j < bucket->size; j++)
 366             {
 367               cstringTable_addEntry (h, bucket->entries[j]);
 368             }
 369
 370           /*
 371           ** evans 2001-03-24: new memory leak detected by Splint
 372           **   after I fixed the checkCompletelyDestroyed.
 373           */
 374
 375           sfree (bucket->entries);
 376           sfree (bucket);
 377         }
 378     }
 379
 380   sfree (oldbuckets);
 381 }
 382
 383 static void
 384 cstringTable_addEntry (/*@notnull@*/ cstringTable h, /*@only@*/ hentry e)
 385 {
 386   unsigned int hindex = cstringTable_hashValue (h, e->key);
 387
 388   /*
 389   ** using
 390   **   hbucket hb = h->buckets[hindex];
 391   ** instead reveals a bug I don't want to deal with right now!
 392   */
 393
 394   if (hbucket_isNull (h->buckets[hindex]))
 395     {
 396       h->buckets[hindex] = hbucket_single (e);
 397       h->nentries++;
 398     }
 399   else
 400     {
 401       if (hbucket_contains (h->buckets[hindex], e->key)) {
 402         llcontbug
 403           (message
 404            ("cstringTable: Attempt to add duplicate entry: %s "
 405             "[previous value %d, new value %d]",
 406             e->key, cstringTable_lookup (h, e->key), e->val));
 407         hentry_free (e);
 408         return;
 409       }
 410
 411       hbucket_add (h->buckets[hindex], e);
 412       h->nentries++;
 413     }
 414 }
 415
 416 void
 417 cstringTable_insert (cstringTable h, cstring key, int value)
 418 {
 419   unsigned int hindex;
 420   hbucket hb;
 421   hentry e;
 422
 423   llassert (cstringTable_isDefined (h));
 424
 425   h->nentries++;
 426
 427   if (h->nentries * 162 > h->size * 100)
 428     {
 429       cstringTable_rehash (h);
 430     }
 431
 432   e = hentry_create (key, value);
 433   hindex = cstringTable_hashValue (h, key);
 434
 435   hb = h->buckets[hindex];
 436
 437   if (hbucket_isNull (hb))
 438     {
 439       h->buckets[hindex] = hbucket_single (e);
 440     }
 441   else
 442     {
 443       llassert (!hbucket_contains (hb, e->key));
 444       hbucket_add (hb, e);
 445     }
 446 }
 447
 448 int
 449 cstringTable_lookup (cstringTable h, cstring key)
 450 {
 451   hbucket hb;
 452   llassert (cstringTable_isDefined (h));
 453
 454   hb = cstringTable_hash (h, key);
 455   return (hbucket_lookup (hb, key));
 456 }
 457
 458 void
 459 cstringTable_update (cstringTable h, cstring key, int newval)
 460 {
 461   hbucket hb;
 462
 463   llassert (cstringTable_isDefined (h));
 464
 465   hb = cstringTable_hash (h, key);
 466
 467   if (!hbucket_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               hb->entries[i]->val = newval;
 476               return;
 477             }
 478         }
 479     }
 480
 481   llbug (message ("cstringTable_update: %s not found", key));
 482 }
 483
 484 /*
 485 ** This is needed if oldkey is going to be released.
 486 */
 487
 488 void
 489 cstringTable_replaceKey (cstringTable h, cstring oldkey, /*@only@*/ cstring newkey)
 490 {
 491   hbucket hb;
 492   llassert (cstringTable_isDefined (h));
 493
 494   hb = cstringTable_hash (h, oldkey);
 495   llassert (cstring_equal (oldkey, newkey));
 496
 497   if (!hbucket_isNull (hb))
 498     {
 499       int i;
 500
 501       for (i = 0; i < hb->size; i++)
 502         {
 503           if (cstring_equal (hb->entries[i]->key, oldkey))
 504             {
 505               hb->entries[i]->key = newkey;
 506               return;
 507             }
 508         }
 509     }
 510
 511   llbug (message ("cstringTable_replaceKey: %s not found", oldkey));
 512 }
 513
 514 void
 515 cstringTable_remove (cstringTable h, cstring key)
 516 {
 517   hbucket hb;
 518
 519   llassert (cstringTable_isDefined (h));
 520   hb = cstringTable_hash (h, key);
 521
 522   if (!hbucket_isNull (hb))
 523     {
 524       int i;
 525
 526       for (i = 0; i < hb->size; i++)
 527         {
 528           if (cstring_equal (hb->entries[i]->key, key))
 529             {
 530               if (i < hb->size - 1)
 531                 {
 532                   hb->entries[i] = hb->entries[hb->size - 1];
 533                 }
 534
 535               hb->size--;
 536               return;
 537             }
 538         }
 539     }
 540
 541   llbug (message ("cstringTable_removeKey: %s not found", key));
 542 }
 543
 544