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); /*@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         /*drl bee: si*/  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  /*drl bee: dm*/ 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    /*drl bee: dm*/
 120       /*drl bee: si*/  newentries[i] = h->entries[i];
 121     }
 122
 123   /*@i32@*/ sfree (h->entries);
 124   h->entries = newentries;
 125 /*@i23@*/ }
 126
 127 static int hbucket_lookup (hbucket p_h, cstring p_key);
 128
 129 static bool hbucket_contains (hbucket p_h, cstring p_key) /*@*/ {
 130   return (hbucket_lookup (p_h, p_key) != HBUCKET_DNE);
 131 }
 132
 133 /*
 134 ** bizarre duplicate behaviour
 135 ** required for duplicate entries
 136 */
 137
 138 static void
 139 hbucket_add (/*@notnull@*/ hbucket h, /*@only@*/ hentry e)
 140 {
 141   int exloc = hbucket_lookup (h, e->key);
 142
 143   llassert (exloc == HBUCKET_DNE);
 144
 145   if (h->nspace == 0)
 146     {
 147       hbucket_grow (h);
 148     }
 149
 150   llassert (e->val != HBUCKET_DNE);
 151   /*drl bee: si*/ h->entries[h->size] = e;
 152   h->size++;
 153   h->nspace--;
 154 }
 155
 156 static int
 157 hbucket_ncollisions (hbucket h)
 158 {
 159   if (!hbucket_isNull (h) && (h->size > 1))
 160     return (h->size - 1);
 161   else
 162     return 0;
 163 }
 164
 165 int
 166 hbucket_lookup (hbucket h, cstring key)
 167 {
 168   if (!hbucket_isNull (h))
 169     {
 170       int i;
 171
 172       for (i = 0; i < h->size; i++)
 173         {
 174         /*drl bee: si*/  if (cstring_equal (h->entries[i]->key, key))
 175             {
 176               return h->entries[i]->val;
 177             }
 178         }
 179     }
 180
 181   return HBUCKET_DNE;
 182 }
 183
 184 static
 185 void hbucket_free (/*@only@*/ hbucket h)
 186 {
 187   if (!hbucket_isNull (h))
 188     {
 189       int i;
 190       /* evans 2002-07-12: added this to free entries (splint warning had been suppressed) */
 191       for (i = 0; i < h->size; i++)
 192         {
 193           hentry_free (h->entries[i]);
 194         }
 195
 196       sfree (h->entries);
 197       sfree (h);
 198     }
 199 }
 200
 201 void
 202 cstringTable_free (/*@only@*/ cstringTable h)
 203 {
 204   int i;
 205
 206   llassert (cstringTable_isDefined (h));
 207
 208   for (i = 0; i < h->size; i++)
 209     {
 210       /*drl bee: si*/ hbucket_free (h->buckets[i]);
 211     }
 212
 213   sfree (h->buckets);
 214   sfree (h);
 215 }
 216
 217 static int
 218 cstringTable_countCollisions (cstringTable h)
 219 {
 220   int nc = 0;
 221   int i;
 222
 223   llassert (cstringTable_isDefined (h));
 224
 225   for (i = 0; i < h->size; i++)
 226     {
 227   /*drl bee: si*/    nc += hbucket_ncollisions (h->buckets[i]);
 228     }
 229
 230   return (nc);
 231 }
 232
 233
 234 static int
 235 cstringTable_countEmpty (cstringTable h)
 236 {
 237   int nc = 0;
 238   int i;
 239
 240   llassert (cstringTable_isDefined (h));
 241
 242   for (i = 0; i < h->size; i++)
 243     {
 244     /*drl bee: si*/    if (hbucket_isEmpty (h->buckets[i]))
 245         {
 246           nc++;
 247         }
 248     }
 249
 250   return (nc);
 251 }
 252
 253 /*
 254 ** hash function snarfed from quake/hash.c Hash_String
 255 ** by Stephen Harrison
 256 */
 257
 258 static unsigned int
 259 cstringTable_hashValue (/*@notnull@*/ cstringTable h, cstring key)
 260 {
 261   char *p;
 262   unsigned int hash_value = 0;
 263
 264   for (p = cstring_toCharsSafe (key); *p != '\0'; p++)
 265     {
 266       /*drl bee: nm*/ hash_value = (hash_value << 1) ^ g_randomNumbers[*p % 256];
 267     }
 268
 269   return (hash_value % h->size);
 270 }
 271
 272 static /*@exposed@*/ hbucket
 273 cstringTable_hash (/*@notnull@*/ cstringTable h, cstring key)
 274 {
 275   return h->buckets[cstringTable_hashValue (h, key)];
 276 }
 277
 278
 279 /*@only@*/ cstringTable
 280 cstringTable_create (int size)
 281 {
 282   int i;
 283   cstringTable h = (cstringTable) dmalloc (sizeof (*h));
 284
 285   h->size = size;
 286   h->nentries = 0;
 287   h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * size);
 288
 289   /*@+loopexec@*/
 290   for (i = 0; i < size; i++)
 291     {
 292      /*drl bee: dm*/   h->buckets[i] = hbucket_undefined;
 293     }
 294   /*@-loopexec@*/
 295   return h;
 296 }
 297
 298 cstring cstringTable_unparse (cstringTable h)
 299 {
 300   cstring res = cstring_newEmpty ();
 301   int i;
 302
 303   if (cstringTable_isDefined (h))
 304     {
 305       for (i = 0; i < h->size; i++)
 306         {
 307           /*drl bee: si*/  hbucket hb = h->buckets[i];
 308
 309           if (hb != NULL)
 310             {
 311               res = message ("%q%d. %q\n", res, i, hbucket_unparse (hb));
 312             }
 313         }
 314
 315       res = message ("%qsize: %d, collisions: %d, empty: %d",
 316                      res,
 317                      h->size,
 318                      cstringTable_countCollisions (h),
 319                      cstringTable_countEmpty (h));
 320     }
 321   else
 322     {
 323       cstring_free (res);
 324       res = cstring_makeLiteral ("< empty cstring table >");
 325     }
 326
 327   return res;
 328 }
 329
 330
 331 /*@only@*/ cstring
 332 cstringTable_stats (cstringTable h)
 333 {
 334   llassert (cstringTable_isDefined (h));
 335   return (message ("size: %d, collisions: %d, empty: %d\n",
 336                    h->size, cstringTable_countCollisions (h),
 337                    cstringTable_countEmpty (h)));
 338 }
 339
 340 static void
 341 cstringTable_rehash (/*@notnull@*/ cstringTable h)
 342 {
 343   /*
 344   ** rehashing based (loosely) on code by Steve Harrison
 345   */
 346
 347   int i;
 348   int oldsize = h->size;
 349   int 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      /*drl bee: dm*/   h->buckets[i] = hbucket_undefined;
 360     }
 361   /*@=loopexec@*/
 362
 363   for (i = 0; i < oldsize; i++)
 364     {
 365      /*drl bee: dm*/   hbucket bucket = oldbuckets[i];
 366
 367     /*drl bee: dm*/    oldbuckets[i] = NULL;
 368
 369       if (!hbucket_isNull (bucket))
 370         {
 371           int j;
 372
 373           for (j = 0; j < bucket->size; j++)
 374             {
 375           /*drl bee: si*/      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    /*drl bee: si*/ if (hbucket_isNull (h->buckets[hindex]))
 403     {
 404       /*drl bee: si*/  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 int 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   /*drl bee: si*/  hb = h->buckets[hindex];
 444
 445   if (hbucket_isNull (hb))
 446     {
 447        /*drl bee: si*/ 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           /*drl bee: si*/  if (cstring_equal (hb->entries[i]->key, key))
 482             {
 483               /*drl bee: si*/      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           /*drl bee: si*/  if (cstring_equal (hb->entries[i]->key, oldkey))
 512             {
 513               /*drl bee: si*/ 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           /*drl bee: si*/  if (cstring_equal (hb->entries[i]->key, key))
 537             {
 538               if (i < hb->size - 1)
 539                 {
 540                   /*drl bee: si*/
 541                   hb->entries[i] = hb->entries[hb->size - 1];
 542                 }
 543
 544               hb->size--;
 545               return;
 546             }
 547         }
 548     }
 549
 550   llbug (message ("cstringTable_removeKey: %s not found", key));
 551 }
 552
 553