git.gag.com Git - fw/sdcc/blob - 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 <assert.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_calloc (1, 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_calloc (1, sizeof (hTab));
  61
  62   if (!(htab->table = calloc ((size + 1), sizeof (hashtItem *))))
  63     {
  64       fprintf (stderr, "out of virtual memory %s %d\n",
  65                __FILE__, (size + 1) * 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               free (jc);
 197               if ((jc = jn))
 198                 jn = jc->next;
 199             }
 200           p->table[i] = NULL;
 201         }
 202       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
 283   if (!(*h))
 284     return 0;
 285
 286   /* first check if anything exists in the slot */
 287   if (!(*h)->table[key])
 288     return 0;
 289
 290   /* delete specific item */
 291   /* if a compare function is given then use the compare */
 292   /* function to find the item, else just compare the items */
 293
 294   htipp = &((*h)->table[key]);
 295   htip = (*h)->table[key];
 296   for (; htip; htip = htip->next)
 297     {
 298       if (
 299            (compare && compare (pkey, htip->pkey)) ||
 300            pkey == htip->pkey)
 301         {
 302           *htipp = htip->next;
 303           break;
 304         }
 305       htipp = &(htip->next);
 306     }
 307   (*h)->nItems--;
 308
 309   if (!(*h)->nItems)
 310     {
 311       *h = NULL;
 312     }
 313   return 1;
 314 }
 315
 316 /*-----------------------------------------------------------------*/
 317 /* hTabIsInTable - will determine if an Item is in the hasht       */
 318 /*-----------------------------------------------------------------*/
 319 int
 320 hTabIsInTable (hTab * htab, int key,
 321                void *item, int (*compareFunc) (void *, void *))
 322 {
 323   if (_findItem (htab, key, item, compareFunc))
 324     return 1;
 325   return 0;
 326 }
 327
 328 /*-----------------------------------------------------------------*/
 329 /* hTabFirstItem - returns the first Item in the hTab              */
 330 /*-----------------------------------------------------------------*/
 331 void *
 332 hTabFirstItem (hTab * htab, int *k)
 333 {
 334   int key;
 335
 336   if (!htab)
 337     return NULL;
 338
 339   for (key = htab->minKey; key <= htab->maxKey; key++)
 340     {
 341       if (htab->table[key])
 342         {
 343           htab->currItem = htab->table[key];
 344           htab->currKey = key;
 345           *k = key;
 346           return htab->table[key]->item;
 347         }
 348     }
 349   return NULL;
 350 }
 351
 352 /*-----------------------------------------------------------------*/
 353 /* hTabNextItem - returns the next item in the hTab                */
 354 /*-----------------------------------------------------------------*/
 355 void *
 356 hTabNextItem (hTab * htab, int *k)
 357 {
 358   int key;
 359
 360   if (!htab)
 361     return NULL;
 362
 363   /* if this chain not ended then */
 364   if (htab->currItem->next)
 365     {
 366       *k = htab->currItem->key;
 367       return (htab->currItem = htab->currItem->next)->item;
 368     }
 369
 370   /* find the next chain which has something */
 371   for (key = htab->currKey + 1; key <= htab->maxKey; key++)
 372     {
 373       if (htab->table[key])
 374         {
 375           htab->currItem = htab->table[key];
 376           *k = htab->currKey = key;
 377           return htab->table[key]->item;
 378         }
 379     }
 380
 381   return NULL;
 382 }
 383
 384 /*-----------------------------------------------------------------*/
 385 /* hTabFirstItemWK - returns the first Item in the hTab for a key  */
 386 /*-----------------------------------------------------------------*/
 387 void *
 388 hTabFirstItemWK (hTab * htab, int wk)
 389 {
 390
 391   if (!htab)
 392     return NULL;
 393
 394   if (wk < htab->minKey || wk > htab->maxKey)
 395     return NULL;
 396
 397   htab->currItem = htab->table[wk];
 398   htab->currKey = wk;
 399
 400   return (htab->table[wk] ? htab->table[wk]->item : NULL);
 401 }
 402
 403 /*-----------------------------------------------------------------*/
 404 /* hTabNextItem - returns the next item in the hTab for a key      */
 405 /*-----------------------------------------------------------------*/
 406 void *
 407 hTabNextItemWK (hTab * htab)
 408 {
 409
 410   if (!htab)
 411     return NULL;
 412
 413   /* if this chain not ended then */
 414   if (htab->currItem->next)
 415     {
 416       return (htab->currItem = htab->currItem->next)->item;
 417     }
 418
 419   return NULL;
 420 }
 421
 422 /*-----------------------------------------------------------------*/
 423 /* hTabFromTable - hash Table from a hash table                    */
 424 /*-----------------------------------------------------------------*/
 425 hTab *
 426 hTabFromTable (hTab * htab)
 427 {
 428   hTab *nhtab;
 429   hashtItem *htip;
 430   int key;
 431
 432   if (!htab)
 433     return NULL;
 434
 435   nhtab = newHashTable (htab->size);
 436
 437   for (key = htab->minKey; key <= htab->maxKey; key++)
 438     {
 439
 440       for (htip = htab->table[key]; htip; htip = htip->next)
 441         hTabAddItem (&nhtab, htip->key, htip->item);
 442     }
 443
 444   return nhtab;
 445 }
 446
 447 /*-----------------------------------------------------------------*/
 448 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2 */
 449 /*-----------------------------------------------------------------*/
 450 int
 451 isHtabsEqual (hTab * htab1, hTab * htab2,
 452               int (*compareFunc) (void *, void *))
 453 {
 454   void *item;
 455   int key;
 456
 457   if (htab1 == htab2)
 458     return 1;
 459
 460   if (htab1 == NULL || htab2 == NULL)
 461     return 0;
 462
 463   /* if they are different sizes then */
 464   if (htab1->nItems != htab2->nItems)
 465     return 0;
 466
 467   /* now do an item by item check */
 468   for (item = hTabFirstItem (htab1, &key); item;
 469        item = hTabNextItem (htab1, &key))
 470     if (!hTabIsInTable (htab2, key, item, compareFunc))
 471       return 0;
 472
 473   return 1;
 474 }
 475
 476
 477 /*-----------------------------------------------------------------*/
 478 /* hTabSearch - returns the first Item with the specified key      */
 479 /*-----------------------------------------------------------------*/
 480 hashtItem *
 481 hTabSearch (hTab * htab, int key)
 482 {
 483   if (!htab)
 484     return NULL;
 485
 486   if ((key < htab->minKey) || (key > htab->maxKey))
 487     return NULL;
 488
 489   if (!htab->table[key])
 490     return NULL;
 491
 492   return htab->table[key];
 493 }
 494
 495 /*-----------------------------------------------------------------*/
 496 /* hTabItemWithKey - returns the first item with the given key     */
 497 /*-----------------------------------------------------------------*/
 498 void *
 499 hTabItemWithKey (hTab * htab, int key)
 500 {
 501   hashtItem *htip;
 502
 503   if (!(htip = hTabSearch (htab, key)))
 504     return NULL;
 505
 506   return htip->item;
 507 }
 508
 509 /*-----------------------------------------------------------------*/
 510 /*hTabAddItemIfNotP - adds an item with nothing found with key     */
 511 /*-----------------------------------------------------------------*/
 512 void
 513 hTabAddItemIfNotP (hTab ** htab, int key, void *item)
 514 {
 515   if (!*htab)
 516     {
 517       hTabAddItem (htab, key, item);
 518       return;
 519     }
 520
 521   if (hTabItemWithKey (*htab, key))
 522     return;
 523
 524   hTabAddItem (htab, key, item);
 525 }
 526
 527 /** Simple implementation of a hash table which uses
 528     string (key, value) pairs.  If a key already exists in the
 529     table, the newly added value will replace it.
 530     This is used for the assembler token table.  The replace existing
 531     condition is used to implement inheritance.
 532 */
 533 static int
 534 _compare (const void *s1, const void *s2)
 535 {
 536   return !strcmp (s1, s2);
 537 }
 538
 539 static int
 540 _hash (const char *sz)
 541 {
 542   /* Dumb for now */
 543   return *sz;
 544 }
 545
 546 void
 547 shash_add (hTab ** h, const char *szKey, const char *szValue)
 548 {
 549   int key = _hash (szKey);
 550   /* First, delete any that currently exist */
 551   hTabDeleteByKey (h, key, szKey, _compare);
 552   /* Now add in ours */
 553   hTabAddItemLong (h, key, gc_strdup (szKey), gc_strdup (szValue));
 554 }
 555
 556 const char *
 557 shash_find (hTab * h, const char *szKey)
 558 {
 559   int key = _hash (szKey);
 560   return (char *) hTabFindByKey (h, key, szKey, _compare);
 561 }