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   unsigned 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   unsigned long 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   unsigned long 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 (unsigned long size)
 280 {
 281   unsigned long 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   unsigned long 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%ul. %q\n", res, i, hbucket_unparse (hb));
 311             }
 312         }
 313
 314       res = message ("%qsize: %ul, 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: %ul, 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   unsigned long i;
 347   /* Fix provided by Thomas Mertz (int -> unsigned long), 21 Apr 2004 */
 348   unsigned long oldsize = h->size;
 349   unsigned long newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */
 350   hbucket *oldbuckets = h->buckets;
 351
 352   h->size = newsize;
 353   h->nentries = 0;
 354   h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * newsize);
 355
 356   /*@+loopexec@*/
 357   for (i = 0; i < newsize; i++)
 358     {
 359        h->buckets[i] = hbucket_undefined;
 360     }
 361   /*@=loopexec@*/
 362
 363   for (i = 0; i < oldsize; i++)
 364     {
 365        hbucket bucket = oldbuckets[i];
 366
 367        oldbuckets[i] = NULL;
 368
 369       if (!hbucket_isNull (bucket))
 370         {
 371           int j;
 372
 373           for (j = 0; j < bucket->size; j++)
 374             {
 375                cstringTable_addEntry (h, bucket->entries[j]);
 376             }
 377
 378           /*
 379           ** evans 2001-03-24: new memory leak detected by Splint
 380           **   after I fixed the checkCompletelyDestroyed.
 381           */
 382
 383           sfree (bucket->entries);
 384           sfree (bucket);
 385         }
 386     }
 387
 388   sfree (oldbuckets);
 389 }
 390
 391 static void
 392 cstringTable_addEntry (/*@notnull@*/ cstringTable h, /*@only@*/ hentry e)
 393 {
 394   unsigned int hindex = cstringTable_hashValue (h, e->key);
 395
 396   /*
 397   ** using
 398   **   hbucket hb = h->buckets[hindex];
 399   ** instead reveals a bug I don't want to deal with right now!
 400   */
 401
 402    if (hbucket_isNull (h->buckets[hindex]))
 403     {
 404        h->buckets[hindex] = hbucket_single (e);
 405       h->nentries++;
 406     }
 407   else
 408     {
 409       if (hbucket_contains (h->buckets[hindex], e->key)) {
 410         llcontbug
 411           (message
 412            ("cstringTable: Attempt to add duplicate entry: %s "
 413             "[previous value %d, new value %d]",
 414             e->key, cstringTable_lookup (h, e->key), e->val));
 415         hentry_free (e);
 416         return;
 417       }
 418
 419       hbucket_add (h->buckets[hindex], e);
 420       h->nentries++;
 421     }
 422 }
 423
 424 void
 425 cstringTable_insert (cstringTable h, cstring key, int value)
 426 {
 427   unsigned long hindex;
 428   hbucket hb;
 429   hentry e;
 430
 431   llassert (cstringTable_isDefined (h));
 432
 433   h->nentries++;
 434
 435   if (h->nentries * 162 > h->size * 100)
 436     {
 437       cstringTable_rehash (h);
 438     }
 439
 440   hindex = cstringTable_hashValue (h, key);
 441   e = hentry_create (key, value);
 442
 443    hb = h->buckets[hindex];
 444
 445   if (hbucket_isNull (hb))
 446     {
 447        h->buckets[hindex] = hbucket_single (e);
 448     }
 449   else
 450     {
 451       llassert (!hbucket_contains (hb, e->key));
 452       hbucket_add (hb, e);
 453     }
 454 }
 455
 456 int
 457 cstringTable_lookup (cstringTable h, cstring key)
 458 {
 459   hbucket hb;
 460   llassert (cstringTable_isDefined (h));
 461
 462   hb = cstringTable_hash (h, key);
 463   return (hbucket_lookup (hb, key));
 464 }
 465
 466 void
 467 cstringTable_update (cstringTable h, cstring key, int newval)
 468 {
 469   hbucket hb;
 470
 471   llassert (cstringTable_isDefined (h));
 472
 473   hb = cstringTable_hash (h, key);
 474
 475   if (!hbucket_isNull (hb))
 476     {
 477       int i;
 478
 479       for (i = 0; i < hb->size; i++)
 480         {
 481            if (cstring_equal (hb->entries[i]->key, key))
 482             {
 483                    hb->entries[i]->val = newval;
 484               return;
 485             }
 486         }
 487     }
 488
 489   llbug (message ("cstringTable_update: %s not found", key));
 490 }
 491
 492 /*
 493 ** This is needed if oldkey is going to be released.
 494 */
 495
 496 void
 497 cstringTable_replaceKey (cstringTable h, cstring oldkey, /*@only@*/ cstring newkey)
 498 {
 499   hbucket hb;
 500   llassert (cstringTable_isDefined (h));
 501
 502   hb = cstringTable_hash (h, oldkey);
 503   llassert (cstring_equal (oldkey, newkey));
 504
 505   if (!hbucket_isNull (hb))
 506     {
 507       int i;
 508
 509       for (i = 0; i < hb->size; i++)
 510         {
 511            if (cstring_equal (hb->entries[i]->key, oldkey))
 512             {
 513               hb->entries[i]->key = newkey;
 514               return;
 515             }
 516         }
 517     }
 518
 519   llbug (message ("cstringTable_replaceKey: %s not found", oldkey));
 520 }
 521
 522 void
 523 cstringTable_remove (cstringTable h, cstring key)
 524 {
 525   hbucket hb;
 526
 527   llassert (cstringTable_isDefined (h));
 528   hb = cstringTable_hash (h, key);
 529
 530   if (!hbucket_isNull (hb))
 531     {
 532       int i;
 533
 534       for (i = 0; i < hb->size; i++)
 535         {
 536            if (cstring_equal (hb->entries[i]->key, key))
 537             {
 538               if (i < hb->size - 1)
 539                 {
 540                                   hb->entries[i] = hb->entries[hb->size - 1];
 541                 }
 542
 543               hb->size--;
 544               return;
 545             }
 546         }
 547     }
 548
 549   llbug (message ("cstringTable_removeKey: %s not found", key));
 550 }
 551
 552