sdcc/src/SDCChasht.c

   1 /*-----------------------------------------------------------------
   2     SDCChast.c - contains support routines for hashtables
   3
   4     Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
   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, or (at your option) any
   9     later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  19
  20     In other words, you are welcome to use, share and improve this program.
  21     You are forbidden to forbid anyone else to use, share and improve
  22     what you give them.   Help stamp out software-hoarding!
  23 -------------------------------------------------------------------------*/
  24
  25 #include <stdio.h>
  26 #include <string.h>
  27 #include <limits.h>
  28 #include "SDCCerr.h"
  29 #include "SDCCglobl.h"
  30 #include "SDCChasht.h"
  31 #include "newalloc.h"
  32
  33 #define DEFAULT_HTAB_SIZE 128
  34
  35 /*-----------------------------------------------------------------*/
  36 /* newHashtItem - creates a new hashtable Item                     */
  37 /*-----------------------------------------------------------------*/
  38 static hashtItem *
  39 _newHashtItem (int key, void *pkey, void *item)
  40 {
  41   hashtItem *htip;
  42
  43   htip = Safe_alloc ( sizeof (hashtItem));
  44
  45   htip->key = key;
  46   htip->pkey = pkey;
  47   htip->item = item;
  48   htip->next = NULL;
  49   return htip;
  50 }
  51
  52 /*-----------------------------------------------------------------*/
  53 /* newHashTable - allocates a new hashtable of size                */
  54 /*-----------------------------------------------------------------*/
  55 hTab *
  56 newHashTable (int size)
  57 {
  58   hTab *htab;
  59
  60   htab = Safe_alloc ( sizeof (hTab));
  61
  62   if (!(htab->table = Safe_alloc ((size + 1) * sizeof (hashtItem *))))
  63     {
  64       fprintf (stderr, "out of virtual memory %s %d\n",
  65                __FILE__, (size + 1) * (int) sizeof (hashtItem *));
  66       exit (1);
  67     }
  68   htab->minKey = htab->size = size;
  69   return htab;
  70 }
  71
  72
  73 void
  74 hTabAddItemLong (hTab ** htab, int key, void *pkey, void *item)
  75 {
  76   hashtItem *htip;
  77   hashtItem *last;
  78
  79   if (!(*htab))
  80     *htab = newHashTable (DEFAULT_HTAB_SIZE);
  81
  82   if (key > (*htab)->size)
  83     {
  84       int i;
  85       (*htab)->table = Safe_realloc ((*htab)->table,
  86                                      (key * 2 + 2) * sizeof (hashtItem *));
  87       for (i = (*htab)->size + 1; i <= (key * 2 + 1); i++)
  88         (*htab)->table[i] = NULL;
  89       (*htab)->size = key * 2 + 1;
  90     }
  91
  92   /* update the key */
  93   if ((*htab)->maxKey < key)
  94     (*htab)->maxKey = key;
  95
  96   if ((*htab)->minKey > key)
  97     (*htab)->minKey = key;
  98
  99   /* create the item */
 100   htip = _newHashtItem (key, pkey, item);
 101
 102   /* if there is a clash then goto end of chain */
 103   if ((last = (*htab)->table[key]))
 104     {
 105       while (last->next)
 106         last = last->next;
 107       last->next = htip;
 108     }
 109   else
 110     /* else just add it */
 111     (*htab)->table[key] = htip;
 112   (*htab)->nItems++;
 113 }
 114
 115 /*-----------------------------------------------------------------*/
 116 /* hTabAddItem - adds an item to the hash table                    */
 117 /*-----------------------------------------------------------------*/
 118 void
 119 hTabAddItem (hTab ** htab, int key, void *item)
 120 {
 121   hTabAddItemLong (htab, key, NULL, item);
 122 }
 123
 124 /*-----------------------------------------------------------------*/
 125 /* hTabDeleteItem - either delete an item                          */
 126 /*-----------------------------------------------------------------*/
 127 void
 128 hTabDeleteItem (hTab ** htab, int key,
 129                 const void *item, DELETE_ACTION action,
 130                 int (*compareFunc) (const void *, const void *))
 131 {
 132   hashtItem *htip, **htipp;
 133
 134   if (!(*htab))
 135     return;
 136
 137   /* first check if anything exists in the slot */
 138   if (!(*htab)->table[key])
 139     return;
 140
 141   /* if delete chain */
 142   if (action == DELETE_CHAIN)
 143     (*htab)->table[key] = NULL;
 144   else
 145     {
 146
 147       /* delete specific item */
 148       /* if a compare function is given then use the compare */
 149       /* function to find the item, else just compare the items */
 150
 151       htipp = &((*htab)->table[key]);
 152       htip = (*htab)->table[key];
 153       for (; htip; htip = htip->next)
 154         {
 155
 156           if (compareFunc ? compareFunc (item, htip->item) :
 157               (item == htip->item))
 158             {
 159               *htipp = htip->next;
 160               break;
 161             }
 162
 163           htipp = &(htip->next);
 164         }
 165
 166     }
 167
 168   (*htab)->nItems--;
 169
 170   if (!(*htab)->nItems)
 171     {
 172       *htab = NULL;
 173     }
 174 }
 175
 176 /*-----------------------------------------------------------------*/
 177 /* hTabDeleteAll - deletes all items in a hash table to reduce mem */
 178 /*                 leaks written by                                */
 179 /*                "BESSIERE Jerome" <BESSIERE_Jerome@stna.dgac.fr> */
 180 /*-----------------------------------------------------------------*/
 181 void
 182 hTabDeleteAll (hTab * p)
 183 {
 184   if (p && p->table)
 185     {
 186       register int i;
 187       register hashtItem *jc, *jn;
 188       for (i = 0; i < p->size; i++)
 189         {
 190
 191           if (!(jc = p->table[i]))
 192             continue;
 193           jn = jc->next;
 194           while (jc)
 195             {
 196               Safe_free (jc);
 197               if ((jc = jn))
 198                 jn = jc->next;
 199             }
 200           p->table[i] = NULL;
 201         }
 202       Safe_free (p->table);
 203     }
 204 }
 205
 206 /*-----------------------------------------------------------------*/
 207 /* hTabClearAll - clear all entries in the table (does not free)    */
 208 /*-----------------------------------------------------------------*/
 209 void
 210 hTabClearAll (hTab * htab)
 211 {
 212
 213   if (!htab || !htab->table)
 214     {
 215       printf ("null table\n");
 216       return;
 217     }
 218   memset (htab->table, 0, htab->size * sizeof (hashtItem *));
 219
 220   htab->minKey = htab->size;
 221   htab->currKey = htab->nItems = htab->maxKey = 0;
 222 }
 223
 224 static const hashtItem *
 225 _findItem (hTab * htab, int key, void *item, int (*compareFunc) (void *, void *))
 226 {
 227   hashtItem *htip;
 228
 229   for (htip = htab->table[key]; htip; htip = htip->next)
 230     {
 231       /* if a compare function is given use it */
 232       if (compareFunc && compareFunc (item, htip->item))
 233         break;
 234       else if (item == htip->item)
 235         break;
 236     }
 237   return htip;
 238 }
 239
 240 static const hashtItem *
 241 _findByKey (hTab * htab, int key, const void *pkey, int (*compare) (const void *, const void *))
 242 {
 243   hashtItem *htip;
 244
 245   assert (compare);
 246
 247   if (!htab)
 248     return NULL;
 249
 250   for (htip = htab->table[key]; htip; htip = htip->next)
 251     {
 252       /* if a compare function is given use it */
 253       if (compare && compare (pkey, htip->pkey))
 254         {
 255           break;
 256         }
 257       else
 258         {
 259           if (pkey == htip->pkey)
 260             {
 261               break;
 262             }
 263         }
 264     }
 265   return htip;
 266 }
 267
 268 void *
 269 hTabFindByKey (hTab * h, int key, const void *pkey, int (*compare) (const void *, const void *))
 270 {
 271   const hashtItem *item;
 272
 273   if ((item = _findByKey (h, key, pkey, compare)))
 274     return item->item;
 275   return NULL;
 276 }
 277
 278 int
 279 hTabDeleteByKey (hTab ** h, int key, const void *pkey, int (*compare) (const void *, const void *))
 280 {
 281   hashtItem *htip, **htipp;
 282   bool found = FALSE;
 283
 284   if (!(*h))
 285     return 0;
 286
 287   /* first check if anything exists in the slot */
 288   if (!(*h)->table[key])
 289     return 0;
 290
 291   /* delete specific item */
 292   /* if a compare function is given then use the compare */
 293   /* function to find the item, else just compare the items */
 294
 295   htipp = &((*h)->table[key]);
 296   htip = (*h)->table[key];
 297   for (; htip; htip = htip->next)
 298     {
 299       if (
 300            (compare && compare (pkey, htip->pkey)) ||
 301            pkey == htip->pkey)
 302         {
 303           *htipp = htip->next;
 304           found = TRUE;
 305           break;
 306         }
 307       htipp = &(htip->next);
 308     }
 309
 310   if (found == TRUE)
 311     {
 312       (*h)->nItems--;
 313
 314       if (!(*h)->nItems)
 315         {
 316           *h = NULL;
 317         }
 318     }
 319
 320   return 1;
 321 }
 322
 323 /*-----------------------------------------------------------------*/
 324 /* hTabIsInTable - will determine if an Item is in the hasht       */
 325 /*-----------------------------------------------------------------*/
 326 int
 327 hTabIsInTable (hTab * htab, int key,
 328                void *item, int (*compareFunc) (void *, void *))
 329 {
 330   if (_findItem (htab, key, item, compareFunc))
 331     return 1;
 332   return 0;
 333 }
 334
 335 /*-----------------------------------------------------------------*/
 336 /* hTabFirstItem - returns the first Item in the hTab              */
 337 /*-----------------------------------------------------------------*/
 338 void *
 339 hTabFirstItem (hTab * htab, int *k)
 340 {
 341   int key;
 342
 343   if (!htab)
 344     return NULL;
 345
 346   for (key = htab->minKey; key <= htab->maxKey; key++)
 347     {
 348       if (htab->table[key])
 349         {
 350           htab->currItem = htab->table[key];
 351           htab->currKey = key;
 352           *k = key;
 353           return htab->table[key]->item;
 354         }
 355     }
 356   return NULL;
 357 }
 358
 359 /*-----------------------------------------------------------------*/
 360 /* hTabNextItem - returns the next item in the hTab                */
 361 /*-----------------------------------------------------------------*/
 362 void *
 363 hTabNextItem (hTab * htab, int *k)
 364 {
 365   int key;
 366
 367   if (!htab)
 368     return NULL;
 369
 370   /* if this chain not ended then */
 371   if (htab->currItem->next)
 372     {
 373       *k = htab->currItem->key;
 374       return (htab->currItem = htab->currItem->next)->item;
 375     }
 376
 377   /* find the next chain which has something */
 378   for (key = htab->currKey + 1; key <= htab->maxKey; key++)
 379     {
 380       if (htab->table[key])
 381         {
 382           htab->currItem = htab->table[key];
 383           *k = htab->currKey = key;
 384           return htab->table[key]->item;
 385         }
 386     }
 387
 388   return NULL;
 389 }
 390
 391 /*-----------------------------------------------------------------*/
 392 /* hTabFirstItemWK - returns the first Item in the hTab for a key  */
 393 /*-----------------------------------------------------------------*/
 394 void *
 395 hTabFirstItemWK (hTab * htab, int wk)
 396 {
 397
 398   if (!htab)
 399     return NULL;
 400
 401   if (wk < htab->minKey || wk > htab->maxKey)
 402     return NULL;
 403
 404   htab->currItem = htab->table[wk];
 405   htab->currKey = wk;
 406
 407   return (htab->table[wk] ? htab->table[wk]->item : NULL);
 408 }
 409
 410 /*-----------------------------------------------------------------*/
 411 /* hTabNextItem - returns the next item in the hTab for a key      */
 412 /*-----------------------------------------------------------------*/
 413 void *
 414 hTabNextItemWK (hTab * htab)
 415 {
 416
 417   if (!htab)
 418     return NULL;
 419
 420   /* if this chain not ended then */
 421   if (htab->currItem->next)
 422     {
 423       return (htab->currItem = htab->currItem->next)->item;
 424     }
 425
 426   return NULL;
 427 }
 428
 429 /*-----------------------------------------------------------------*/
 430 /* hTabFromTable - hash Table from a hash table                    */
 431 /*-----------------------------------------------------------------*/
 432 hTab *
 433 hTabFromTable (hTab * htab)
 434 {
 435   hTab *nhtab;
 436   hashtItem *htip;
 437   int key;
 438
 439   if (!htab)
 440     return NULL;
 441
 442   nhtab = newHashTable (htab->size);
 443
 444   for (key = htab->minKey; key <= htab->maxKey; key++)
 445     {
 446
 447       for (htip = htab->table[key]; htip; htip = htip->next)
 448         hTabAddItem (&nhtab, htip->key, htip->item);
 449     }
 450
 451   return nhtab;
 452 }
 453
 454 /*-----------------------------------------------------------------*/
 455 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2 */
 456 /*-----------------------------------------------------------------*/
 457 int
 458 isHtabsEqual (hTab * htab1, hTab * htab2,
 459               int (*compareFunc) (void *, void *))
 460 {
 461   void *item;
 462   int key;
 463
 464   if (htab1 == htab2)
 465     return 1;
 466
 467   if (htab1 == NULL || htab2 == NULL)
 468     return 0;
 469
 470   /* if they are different sizes then */
 471   if (htab1->nItems != htab2->nItems)
 472     return 0;
 473
 474   /* now do an item by item check */
 475   for (item = hTabFirstItem (htab1, &key); item;
 476        item = hTabNextItem (htab1, &key))
 477     if (!hTabIsInTable (htab2, key, item, compareFunc))
 478       return 0;
 479
 480   return 1;
 481 }
 482
 483
 484 /*-----------------------------------------------------------------*/
 485 /* hTabSearch - returns the first Item with the specified key      */
 486 /*-----------------------------------------------------------------*/
 487 hashtItem *
 488 hTabSearch (hTab * htab, int key)
 489 {
 490   if (!htab)
 491     return NULL;
 492
 493   if ((key < htab->minKey) || (key > htab->maxKey))
 494     return NULL;
 495
 496   if (!htab->table[key])
 497     return NULL;
 498
 499   return htab->table[key];
 500 }
 501
 502 /*-----------------------------------------------------------------*/
 503 /* hTabItemWithKey - returns the first item with the given key     */
 504 /*-----------------------------------------------------------------*/
 505 void *
 506 hTabItemWithKey (hTab * htab, int key)
 507 {
 508   hashtItem *htip;
 509
 510   if (!(htip = hTabSearch (htab, key)))
 511     return NULL;
 512
 513   return htip->item;
 514 }
 515
 516 /*-----------------------------------------------------------------*/
 517 /* hTabMaxKey - return the maxKey of item in the hashTable         */
 518 /*-----------------------------------------------------------------*/
 519 int hTabMaxKey (hTab *htab)
 520 {
 521     return (htab ? htab->maxKey : 0);
 522 }
 523
 524 /*-----------------------------------------------------------------*/
 525 /*hTabAddItemIfNotP - adds an item with nothing found with key     */
 526 /*-----------------------------------------------------------------*/
 527 void
 528 hTabAddItemIfNotP (hTab ** htab, int key, void *item)
 529 {
 530   if (!*htab)
 531     {
 532       hTabAddItem (htab, key, item);
 533       return;
 534     }
 535
 536   if (hTabItemWithKey (*htab, key))
 537     return;
 538
 539   hTabAddItem (htab, key, item);
 540 }
 541
 542 /** Simple implementation of a hash table which uses
 543     string (key, value) pairs.  If a key already exists in the
 544     table, the newly added value will replace it.
 545     This is used for the assembler token table.  The replace existing
 546     condition is used to implement inheritance.
 547 */
 548 static int
 549 _compare (const void *s1, const void *s2)
 550 {
 551   return !strcmp (s1, s2);
 552 }
 553
 554 static int
 555 _hash (const char *sz)
 556 {
 557   /* Dumb for now */
 558   return *sz;
 559 }
 560
 561 void
 562 shash_add (hTab ** h, const char *szKey, const char *szValue)
 563 {
 564   char *val;
 565   int key = _hash (szKey);
 566
 567   /* Find value of the item */
 568   val = (char *)hTabFindByKey(*h, key, szKey, _compare);
 569   /* Delete any that currently exist */
 570   hTabDeleteByKey(h, key, szKey, _compare);
 571   /* Deallocate old value in not NULL */
 572   if (val != NULL)
 573     Safe_free(val);
 574   /* Duplicate new value if not NULL */
 575   if (szValue != NULL)
 576     szValue = Safe_strdup(szValue);
 577   /* Now add in ours */
 578   hTabAddItemLong (h, key, Safe_strdup (szKey), (void *)szValue);
 579 }
 580
 581 const char *
 582 shash_find (hTab * h, const char *szKey)
 583 {
 584   int key = _hash (szKey);
 585   return (char *) hTabFindByKey (h, key, szKey, _compare);
 586 }