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 "cstringHash.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 # ifdef DEADCODE
  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 # endif /* DEADCODE */
  93
  94 static hbucket
  95 hbucket_single (/*@only@*/ hentry e)
  96 {
  97   hbucket h = (hbucket) dmalloc (sizeof (*h));
  98
  99   h->size = 1;
 100   h->nspace = HBUCKET_BASESIZE - 1;
 101   h->entries = (hentry *) dmalloc (HBUCKET_BASESIZE * sizeof (*h->entries));
 102  h->entries[0] = e;
 103
 104   return (h);
 105 }
 106
 107 static void
 108 hbucket_grow (/*@notnull@*/ hbucket h)
 109 {
 110   int i;
 111   hentry *newentries;
 112
 113   h->nspace += HBUCKET_BASESIZE;
 114
 115   newentries = (hentry *)
 116     dmalloc ((h->size + HBUCKET_BASESIZE) * sizeof (*newentries));
 117
 118   for (i = 0; i < h->size; i++)
 119     {
 120       newentries[i] = h->entries[i];
 121     }
 122
 123   sfree (h->entries);
 124   h->entries = newentries;
 125   /*@-compmempass@*/
 126 } /*@=compmempass@*/ /* Spurious warnings reported - shouldn't need this */
 127
 128 static int hbucket_lookup (hbucket p_h, cstring p_key);
 129
 130 static bool hbucket_contains (hbucket p_h, cstring p_key) /*@*/ {
 131   return (hbucket_lookup (p_h, p_key) != HBUCKET_DNE);
 132 }
 133
 134 /*
 135 ** bizarre duplicate behaviour
 136 ** required for duplicate entries
 137 */
 138
 139 static void
 140 hbucket_add (/*@notnull@*/ hbucket h, /*@only@*/ hentry e)
 141 {
 142   int exloc = hbucket_lookup (h, e->key);
 143
 144   llassert (exloc == HBUCKET_DNE);
 145
 146   if (h->nspace == 0)
 147     {
 148       hbucket_grow (h);
 149     }
 150
 151   llassert (e->val != HBUCKET_DNE);
 152   h->entries[h->size] = e;
 153   h->size++;
 154   h->nspace--;
 155 }
 156
 157 # ifdef DEADCODE
 158 static int
 159 hbucket_ncollisions (hbucket h)
 160 {
 161   if (!hbucket_isNull (h) && (h->size > 1))
 162     return (h->size - 1);
 163   else
 164     return 0;
 165 }
 166 # endif /* DEADCODE */
 167
 168 int
 169 hbucket_lookup (hbucket h, cstring key)
 170 {
 171   if (!hbucket_isNull (h))
 172     {
 173       int i;
 174
 175       for (i = 0; i < h->size; i++)
 176         {
 177          if (cstring_equal (h->entries[i]->key, key))
 178             {
 179               return h->entries[i]->val;
 180             }
 181         }
 182     }
 183
 184   return HBUCKET_DNE;
 185 }
 186
 187 static
 188 void hbucket_free (/*@only@*/ hbucket h)
 189 {
 190   if (!hbucket_isNull (h))
 191     {
 192       int i;
 193       /* evans 2002-07-12: added this to free entries (splint warning had been suppressed) */
 194       for (i = 0; i < h->size; i++)
 195         {
 196           hentry_free (h->entries[i]);
 197         }
 198
 199       sfree (h->entries);
 200       sfree (h);
 201     }
 202 }
 203
 204 void
 205 cstringTable_free (/*@only@*/ cstringTable h)
 206 {
 207   unsigned long i;
 208
 209   llassert (cstringTable_isDefined (h));
 210
 211   for (i = 0; i < h->size; i++)
 212     {
 213       hbucket_free (h->buckets[i]);
 214     }
 215
 216   sfree (h->buckets);
 217   sfree (h);
 218 }
 219
 220 # ifdef DEADCODE
 221 static int
 222 cstringTable_countCollisions (cstringTable h)
 223 {
 224   int nc = 0;
 225   unsigned long i;
 226
 227   llassert (cstringTable_isDefined (h));
 228
 229   for (i = 0; i < h->size; i++)
 230     {
 231      nc += hbucket_ncollisions (h->buckets[i]);
 232     }
 233
 234   return (nc);
 235 }
 236
 237
 238 static int
 239 cstringTable_countEmpty (cstringTable h)
 240 {
 241   int nc = 0;
 242   unsigned long i;
 243
 244   llassert (cstringTable_isDefined (h));
 245
 246   for (i = 0; i < h->size; i++)
 247     {
 248        if (hbucket_isEmpty (h->buckets[i]))
 249         {
 250           nc++;
 251         }
 252     }
 253
 254   return (nc);
 255 }
 256 # endif /* DEADCODE */
 257
 258 static unsigned int
 259 cstringTable_hashValue (/*@notnull@*/ cstringTable h, cstring key)
 260 {
 261   return (cstring_hashValue(key) % 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 (unsigned long size)
 273 {
 274   unsigned long 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 # ifdef DEADCODE
 291 cstring cstringTable_unparse (cstringTable h)
 292 {
 293   cstring res = cstring_newEmpty ();
 294   unsigned long i;
 295
 296   if (cstringTable_isDefined (h))
 297     {
 298       for (i = 0; i < h->size; i++)
 299         {
 300            hbucket hb = h->buckets[i];
 301
 302           if (hb != NULL)
 303             {
 304               res = message ("%q%wl. %q\n", res, i, hbucket_unparse (hb));
 305             }
 306         }
 307
 308       res = message ("%qsize: %wl, collisions: %d, empty: %d",
 309                      res,
 310                      h->size,
 311                      cstringTable_countCollisions (h),
 312                      cstringTable_countEmpty (h));
 313     }
 314   else
 315     {
 316       cstring_free (res);
 317       res = cstring_makeLiteral ("< empty cstring table >");
 318     }
 319
 320   return res;
 321 }
 322
 323
 324 /*@only@*/ cstring
 325 cstringTable_stats (cstringTable h)
 326 {
 327   llassert (cstringTable_isDefined (h));
 328   return (message ("size: %wl, collisions: %d, empty: %d\n",
 329                    h->size, cstringTable_countCollisions (h),
 330                    cstringTable_countEmpty (h)));
 331 }
 332 # endif /* DEADCODE */
 333
 334 static void
 335 cstringTable_rehash (/*@notnull@*/ cstringTable h)
 336 {
 337   /*
 338   ** rehashing based (loosely) on code by Steve Harrison
 339   */
 340
 341   unsigned long i;
 342   /* Fix provided by Thomas Mertz (int -> unsigned long), 21 Apr 2004 */
 343   unsigned long oldsize = h->size;
 344   unsigned long newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */
 345   hbucket *oldbuckets = h->buckets;
 346
 347   h->size = newsize;
 348   h->nentries = 0;
 349   h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * newsize);
 350
 351   /*@+loopexec@*/
 352   for (i = 0; i < newsize; i++)
 353     {
 354        h->buckets[i] = hbucket_undefined;
 355     }
 356   /*@=loopexec@*/
 357
 358   for (i = 0; i < oldsize; i++)
 359     {
 360        hbucket bucket = oldbuckets[i];
 361
 362        oldbuckets[i] = NULL;
 363
 364       if (!hbucket_isNull (bucket))
 365         {
 366           int j;
 367
 368           for (j = 0; j < bucket->size; j++)
 369             {
 370                cstringTable_addEntry (h, bucket->entries[j]);
 371             }
 372
 373           /*
 374           ** evans 2001-03-24: new memory leak detected by Splint
 375           **   after I fixed the checkCompletelyDestroyed.
 376           */
 377
 378           sfree (bucket->entries);
 379           sfree (bucket);
 380         }
 381     }
 382
 383   sfree (oldbuckets);
 384 }
 385
 386 static void
 387 cstringTable_addEntry (/*@notnull@*/ cstringTable h, /*@only@*/ hentry e)
 388 {
 389   unsigned int hindex = cstringTable_hashValue (h, e->key);
 390
 391   /*
 392   ** using
 393   **   hbucket hb = h->buckets[hindex];
 394   ** instead reveals a bug I don't want to deal with right now!
 395   */
 396
 397    if (hbucket_isNull (h->buckets[hindex]))
 398     {
 399        h->buckets[hindex] = hbucket_single (e);
 400       h->nentries++;
 401     }
 402   else
 403     {
 404       if (hbucket_contains (h->buckets[hindex], e->key)) {
 405         llcontbug
 406           (message
 407            ("cstringTable: Attempt to add duplicate entry: %s "
 408             "[previous value %d, new value %d]",
 409             e->key, cstringTable_lookup (h, e->key), e->val));
 410         hentry_free (e);
 411         return;
 412       }
 413
 414       hbucket_add (h->buckets[hindex], e);
 415       h->nentries++;
 416     }
 417 }
 418
 419 void
 420 cstringTable_insert (cstringTable h, cstring key, int value)
 421 {
 422   unsigned long hindex;
 423   hbucket hb;
 424   hentry e;
 425
 426   llassert (cstringTable_isDefined (h));
 427
 428   h->nentries++;
 429
 430   if (h->nentries * 162 > h->size * 100)
 431     {
 432       cstringTable_rehash (h);
 433     }
 434
 435   hindex = cstringTable_hashValue (h, key);
 436   e = hentry_create (key, value);
 437
 438    hb = h->buckets[hindex];
 439
 440   if (hbucket_isNull (hb))
 441     {
 442        h->buckets[hindex] = hbucket_single (e);
 443     }
 444   else
 445     {
 446       llassert (!hbucket_contains (hb, e->key));
 447       hbucket_add (hb, e);
 448     }
 449 }
 450
 451 int
 452 cstringTable_lookup (cstringTable h, cstring key)
 453 {
 454   hbucket hb;
 455   llassert (cstringTable_isDefined (h));
 456
 457   hb = cstringTable_hash (h, key);
 458   return (hbucket_lookup (hb, key));
 459 }
 460
 461 # ifdef DEADCODE
 462 void
 463 cstringTable_update (cstringTable h, cstring key, int newval)
 464 {
 465   hbucket hb;
 466
 467   llassert (cstringTable_isDefined (h));
 468
 469   hb = cstringTable_hash (h, key);
 470
 471   if (!hbucket_isNull (hb))
 472     {
 473       int i;
 474
 475       for (i = 0; i < hb->size; i++)
 476         {
 477            if (cstring_equal (hb->entries[i]->key, key))
 478             {
 479                    hb->entries[i]->val = newval;
 480               return;
 481             }
 482         }
 483     }
 484
 485   llbug (message ("cstringTable_update: %s not found", key));
 486 }
 487 # endif /* DEADCODE */
 488
 489 /*
 490 ** This is needed if oldkey is going to be released.
 491 */
 492
 493 void
 494 cstringTable_replaceKey (cstringTable h, cstring oldkey, /*@only@*/ cstring newkey)
 495 {
 496   hbucket hb;
 497   llassert (cstringTable_isDefined (h));
 498
 499   hb = cstringTable_hash (h, oldkey);
 500   llassert (cstring_equal (oldkey, newkey));
 501
 502   if (!hbucket_isNull (hb))
 503     {
 504       int i;
 505
 506       for (i = 0; i < hb->size; i++)
 507         {
 508            if (cstring_equal (hb->entries[i]->key, oldkey))
 509             {
 510               hb->entries[i]->key = newkey;
 511               return;
 512             }
 513         }
 514     }
 515
 516   llbug (message ("cstringTable_replaceKey: %s not found", oldkey));
 517 }
 518
 519 void
 520 cstringTable_remove (cstringTable h, cstring key)
 521 {
 522   hbucket hb;
 523
 524   llassert (cstringTable_isDefined (h));
 525   hb = cstringTable_hash (h, key);
 526
 527   if (!hbucket_isNull (hb))
 528     {
 529       int i;
 530
 531       for (i = 0; i < hb->size; i++)
 532         {
 533            if (cstring_equal (hb->entries[i]->key, key))
 534             {
 535               if (i < hb->size - 1)
 536                 {
 537                                   hb->entries[i] = hb->entries[hb->size - 1];
 538                 }
 539
 540               hb->size--;
 541               return;
 542             }
 543         }
 544     }
 545
 546   llbug (message ("cstringTable_removeKey: %s not found", key));
 547 }
 548
 549