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