src/cstringTable.c

   1 /*
   2 ** Splint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2002 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: splint@cs.virginia.edu
  21 ** To report a bug: splint-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 "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 (/*@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         /*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       /*@i32@*/ sfree (h->entries);
 190       sfree (h);
 191     }
 192 }
 193
 194 void
 195 cstringTable_free (/*@only@*/ cstringTable h)
 196 {
 197   int i;
 198
 199   llassert (cstringTable_isDefined (h));
 200
 201   for (i = 0; i < h->size; i++)
 202     {
 203  /*drl bee: si*/     hbucket_free (h->buckets[i]);
 204     }
 205
 206   sfree (h->buckets);
 207   sfree (h);
 208 }
 209
 210 static int
 211 cstringTable_countCollisions (cstringTable h)
 212 {
 213   int nc = 0;
 214   int i;
 215
 216   llassert (cstringTable_isDefined (h));
 217
 218   for (i = 0; i < h->size; i++)
 219     {
 220   /*drl bee: si*/    nc += hbucket_ncollisions (h->buckets[i]);
 221     }
 222
 223   return (nc);
 224 }
 225
 226
 227 static int
 228 cstringTable_countEmpty (cstringTable h)
 229 {
 230   int nc = 0;
 231   int i;
 232
 233   llassert (cstringTable_isDefined (h));
 234
 235   for (i = 0; i < h->size; i++)
 236     {
 237     /*drl bee: si*/    if (hbucket_isEmpty (h->buckets[i]))
 238         {
 239           nc++;
 240         }
 241     }
 242
 243   return (nc);
 244 }
 245
 246 /*
 247 ** hash function snarfed from quake/hash.c Hash_String
 248 ** by Stephen Harrison
 249 */
 250
 251 static unsigned int
 252 cstringTable_hashValue (/*@notnull@*/ cstringTable h, cstring key)
 253 {
 254   char *p;
 255   unsigned int hash_value = 0;
 256
 257   for (p = cstring_toCharsSafe (key); *p != '\0'; p++)
 258     {
 259     /*drl bee: nm*/    hash_value = (hash_value << 1) ^ g_randomNumbers[*p % 256];
 260     }
 261
 262   return (hash_value % h->size);
 263 }
 264
 265 static /*@exposed@*/ hbucket
 266 cstringTable_hash (/*@notnull@*/ cstringTable h, cstring key)
 267 {
 268   return h->buckets[cstringTable_hashValue (h, key)];
 269 }
 270
 271
 272 /*@only@*/ cstringTable
 273 cstringTable_create (int size)
 274 {
 275   int i;
 276   cstringTable h = (cstringTable) dmalloc (sizeof (*h));
 277
 278   h->size = size;
 279   h->nentries = 0;
 280   h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * size);
 281
 282   /*@+loopexec@*/
 283   for (i = 0; i < size; i++)
 284     {
 285      /*drl bee: dm*/   h->buckets[i] = hbucket_undefined;
 286     }
 287   /*@-loopexec@*/
 288   return h;
 289 }
 290
 291 cstring cstringTable_unparse (cstringTable h)
 292 {
 293   cstring res = cstring_newEmpty ();
 294   int i;
 295
 296   if (cstringTable_isDefined (h))
 297     {
 298       for (i = 0; i < h->size; i++)
 299         {
 300           /*drl bee: si*/  hbucket hb = h->buckets[i];
 301
 302           if (hb != NULL)
 303             {
 304               res = message ("%q%d. %q\n", res, i, hbucket_unparse (hb));
 305             }
 306         }
 307
 308       res = message ("%qsize: %d, 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: %d, collisions: %d, empty: %d\n",
 329                    h->size, cstringTable_countCollisions (h),
 330                    cstringTable_countEmpty (h)));
 331 }
 332
 333 static void
 334 cstringTable_rehash (/*@notnull@*/ cstringTable h)
 335 {
 336   /*
 337   ** rehashing based (loosely) on code by Steve Harrison
 338   */
 339
 340   int i;
 341   int oldsize = h->size;
 342   int newsize = 1 + ((oldsize * 26244) / 10000); /* 26244 = 162^2 */
 343   hbucket *oldbuckets = h->buckets;
 344
 345   h->size = newsize;
 346   h->nentries = 0;
 347   h->buckets = (hbucket *) dmalloc (sizeof (*h->buckets) * newsize);
 348
 349   /*@+loopexec@*/
 350   for (i = 0; i < newsize; i++)
 351     {
 352      /*drl bee: dm*/   h->buckets[i] = hbucket_undefined;
 353     }
 354   /*@=loopexec@*/
 355
 356   for (i = 0; i < oldsize; i++)
 357     {
 358      /*drl bee: dm*/   hbucket bucket = oldbuckets[i];
 359
 360     /*drl bee: dm*/    oldbuckets[i] = NULL;
 361
 362       if (!hbucket_isNull (bucket))
 363         {
 364           int j;
 365
 366           for (j = 0; j < bucket->size; j++)
 367             {
 368           /*drl bee: si*/      cstringTable_addEntry (h, bucket->entries[j]);
 369             }
 370
 371           /*
 372           ** evans 2001-03-24: new memory leak detected by Splint
 373           **   after I fixed the checkCompletelyDestroyed.
 374           */
 375
 376           sfree (bucket->entries);
 377           sfree (bucket);
 378         }
 379     }
 380
 381   sfree (oldbuckets);
 382 }
 383
 384 static void
 385 cstringTable_addEntry (/*@notnull@*/ cstringTable h, /*@only@*/ hentry e)
 386 {
 387   unsigned int hindex = cstringTable_hashValue (h, e->key);
 388
 389   /*
 390   ** using
 391   **   hbucket hb = h->buckets[hindex];
 392   ** instead reveals a bug I don't want to deal with right now!
 393   */
 394
 395    /*drl bee: si*/ if (hbucket_isNull (h->buckets[hindex]))
 396     {
 397       /*drl bee: si*/  h->buckets[hindex] = hbucket_single (e);
 398       h->nentries++;
 399     }
 400   else
 401     {
 402       if (hbucket_contains (h->buckets[hindex], e->key)) {
 403         llcontbug
 404           (message
 405            ("cstringTable: Attempt to add duplicate entry: %s "
 406             "[previous value %d, new value %d]",
 407             e->key, cstringTable_lookup (h, e->key), e->val));
 408         hentry_free (e);
 409         return;
 410       }
 411
 412       hbucket_add (h->buckets[hindex], e);
 413       h->nentries++;
 414     }
 415 }
 416
 417 void
 418 cstringTable_insert (cstringTable h, cstring key, int value)
 419 {
 420   unsigned int hindex;
 421   hbucket hb;
 422   hentry e;
 423
 424   llassert (cstringTable_isDefined (h));
 425
 426   h->nentries++;
 427
 428   if (h->nentries * 162 > h->size * 100)
 429     {
 430       cstringTable_rehash (h);
 431     }
 432
 433   e = hentry_create (key, value);
 434   hindex = cstringTable_hashValue (h, key);
 435
 436   /*drl bee: si*/  hb = h->buckets[hindex];
 437
 438   if (hbucket_isNull (hb))
 439     {
 440        /*drl bee: si*/ h->buckets[hindex] = hbucket_single (e);
 441     }
 442   else
 443     {
 444       llassert (!hbucket_contains (hb, e->key));
 445       hbucket_add (hb, e);
 446     }
 447 }
 448
 449 int
 450 cstringTable_lookup (cstringTable h, cstring key)
 451 {
 452   hbucket hb;
 453   llassert (cstringTable_isDefined (h));
 454
 455   hb = cstringTable_hash (h, key);
 456   return (hbucket_lookup (hb, key));
 457 }
 458
 459 void
 460 cstringTable_update (cstringTable h, cstring key, int newval)
 461 {
 462   hbucket hb;
 463
 464   llassert (cstringTable_isDefined (h));
 465
 466   hb = cstringTable_hash (h, key);
 467
 468   if (!hbucket_isNull (hb))
 469     {
 470       int i;
 471
 472       for (i = 0; i < hb->size; i++)
 473         {
 474           /*drl bee: si*/  if (cstring_equal (hb->entries[i]->key, key))
 475             {
 476           /*drl bee: si*/      hb->entries[i]->val = newval;
 477               return;
 478             }
 479         }
 480     }
 481
 482   llbug (message ("cstringTable_update: %s not found", key));
 483 }
 484
 485 /*
 486 ** This is needed if oldkey is going to be released.
 487 */
 488
 489 void
 490 cstringTable_replaceKey (cstringTable h, cstring oldkey, /*@only@*/ cstring newkey)
 491 {
 492   hbucket hb;
 493   llassert (cstringTable_isDefined (h));
 494
 495   hb = cstringTable_hash (h, oldkey);
 496   llassert (cstring_equal (oldkey, newkey));
 497
 498   if (!hbucket_isNull (hb))
 499     {
 500       int i;
 501
 502       for (i = 0; i < hb->size; i++)
 503         {
 504           /*drl bee: si*/  if (cstring_equal (hb->entries[i]->key, oldkey))
 505             {
 506           /*drl bee: si*/      hb->entries[i]->key = newkey;
 507               return;
 508             }
 509         }
 510     }
 511
 512   llbug (message ("cstringTable_replaceKey: %s not found", oldkey));
 513 }
 514
 515 void
 516 cstringTable_remove (cstringTable h, cstring key)
 517 {
 518   hbucket hb;
 519
 520   llassert (cstringTable_isDefined (h));
 521   hb = cstringTable_hash (h, key);
 522
 523   if (!hbucket_isNull (hb))
 524     {
 525       int i;
 526
 527       for (i = 0; i < hb->size; i++)
 528         {
 529           /*drl bee: si*/  if (cstring_equal (hb->entries[i]->key, key))
 530             {
 531               if (i < hb->size - 1)
 532                 {
 533                   /*drl bee: si*/
 534   /*drl bee: si*/  hb->entries[i] = hb->entries[hb->size - 1];
 535                 }
 536
 537               hb->size--;
 538               return;
 539             }
 540         }
 541     }
 542
 543   llbug (message ("cstringTable_removeKey: %s not found", key));
 544 }
 545
 546