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 "SDCChasht.h"
  30
  31 #define DEFAULT_HTAB_SIZE 128
  32
  33 /*-----------------------------------------------------------------*/
  34 /* newHashtItem - creates a new hashtable Item                     */
  35 /*-----------------------------------------------------------------*/
  36 static hashtItem *_newHashtItem (int key, void *pkey, void *item)
  37 {
  38     hashtItem *htip;
  39
  40     ALLOC(htip,sizeof(hashtItem));
  41
  42     htip->key = key ;
  43     htip->pkey = pkey;
  44     htip->item = item;
  45     htip->next = NULL ;
  46     return htip;
  47 }
  48
  49 /*-----------------------------------------------------------------*/
  50 /* newHashTable - allocates a new hashtable of size                */
  51 /*-----------------------------------------------------------------*/
  52 hTab *newHashTable (int size)
  53 {
  54     hTab *htab;
  55
  56     ALLOC(htab,sizeof(hTab));
  57
  58     if (!(htab->table = GC_malloc((size +1)* sizeof(hashtItem *)))) {
  59         fprintf(stderr,"out of virtual memory %s %d\n",
  60                 __FILE__,(size +1)* sizeof(hashtItem *));
  61         exit(1);
  62     }
  63     htab->minKey = htab->size = size ;
  64     return htab;
  65 }
  66
  67
  68 void hTabAddItemLong(hTab **htab, int key, void *pkey, void *item)
  69 {
  70     hashtItem *htip ;
  71     hashtItem *last ;
  72
  73     if (!(*htab) )
  74         *htab = newHashTable ( DEFAULT_HTAB_SIZE  );
  75
  76     if (key > (*htab)->size ) {
  77         int i;
  78         (*htab)->table = GC_realloc ((*htab)->table,
  79                                      (key*2 + 2)*sizeof(hashtItem *));
  80         for ( i = (*htab)->size +1; i <= (key*2 + 1); i++ )
  81             (*htab)->table[i] = NULL ;
  82         (*htab)->size = key*2 + 1;
  83     }
  84
  85     /* update the key */
  86     if ((*htab)->maxKey < key )
  87         (*htab)->maxKey = key ;
  88
  89     if ((*htab)->minKey > key )
  90         (*htab)->minKey = key ;
  91
  92     /* create the item */
  93     htip = _newHashtItem(key, pkey, item);
  94
  95     /* if there is a clash then goto end of chain */
  96     if ((last = (*htab)->table[key])) {
  97         while (last->next)
  98             last = last->next ;
  99         last->next = htip ;
 100     } else
 101         /* else just add it */
 102         (*htab)->table[key] = htip ;
 103     (*htab)->nItems++ ;
 104 }
 105
 106 /*-----------------------------------------------------------------*/
 107 /* hTabAddItem - adds an item to the hash table                    */
 108 /*-----------------------------------------------------------------*/
 109 void hTabAddItem (hTab **htab, int key, void *item )
 110 {
 111     hTabAddItemLong(htab, key, NULL, item);
 112 }
 113
 114 /*-----------------------------------------------------------------*/
 115 /* hTabDeleteItem - either delete an item                          */
 116 /*-----------------------------------------------------------------*/
 117 void hTabDeleteItem (hTab **htab, int key ,
 118                      const void *item, DELETE_ACTION action,
 119                      int (*compareFunc)(const void *, const void *))
 120 {
 121     hashtItem *htip, **htipp ;
 122
 123     if (!(*htab))
 124         return ;
 125
 126     /* first check if anything exists in the slot */
 127     if (! (*htab)->table[key] )
 128         return ;
 129
 130     /* if delete chain */
 131     if ( action == DELETE_CHAIN )
 132         (*htab)->table[key] = NULL ;
 133     else {
 134
 135         /* delete specific item */
 136         /* if a compare function is given then use the compare */
 137         /* function to find the item, else just compare the items */
 138
 139         htipp = &((*htab)->table[key]);
 140         htip = (*htab)->table[key];
 141         for (; htip; htip = htip->next) {
 142
 143             if (compareFunc ? compareFunc(item,htip->item) :
 144                 (item == htip->item) ) {
 145                 *htipp=htip->next;
 146                 break;
 147             }
 148
 149             htipp=&(htip->next);
 150         }
 151
 152     }
 153
 154     (*htab)->nItems-- ;
 155
 156     if (!(*htab)->nItems) {
 157         *htab = NULL;
 158     }
 159 }
 160
 161 /*-----------------------------------------------------------------*/
 162 /* hTabDeleteAll - deletes all items in a hash table to reduce mem */
 163 /*                 leaks written by                                */
 164 /*                "BESSIERE Jerome" <BESSIERE_Jerome@stna.dgac.fr> */
 165 /*-----------------------------------------------------------------*/
 166 void hTabDeleteAll(hTab * p)
 167 {
 168     if (p && p->table) {
 169         register int i;
 170         register hashtItem *jc,*jn;
 171         for (i=0;i<p->size;i++) {
 172
 173             if (!(jc = p->table[i])) continue;
 174             jn = jc->next;
 175             while(jc){
 176                 GC_free(jc);
 177                 if((jc=jn)) jn = jc->next;
 178             }
 179             p->table[i] = NULL ;
 180         }
 181         GC_free(p->table);
 182     }
 183 }
 184
 185 /*-----------------------------------------------------------------*/
 186 /* hTabClearAll - clear all entries in the table (does not free)    */
 187 /*-----------------------------------------------------------------*/
 188 void hTabClearAll (hTab *htab)
 189 {
 190
 191     if (!htab || !htab->table) {
 192         printf("null table\n");
 193         return ;
 194     }
 195     memset(htab->table, 0, htab->size*sizeof(hashtItem *));
 196
 197     htab->minKey = htab->size;
 198     htab->currKey = htab->nItems = htab->maxKey = 0;
 199 }
 200
 201 static const hashtItem *_findItem(hTab *htab, int key, void *item, int (*compareFunc)(void *, void *))
 202 {
 203     hashtItem *htip;
 204
 205     for (htip = htab->table[key] ; htip ; htip = htip->next ) {
 206         /* if a compare function is given use it */
 207         if (compareFunc && compareFunc(item,htip->item))
 208             break;
 209         else
 210             if (item == htip->item)
 211                 break;
 212     }
 213     return htip;
 214 }
 215
 216 static const hashtItem *_findByKey(hTab *htab, int key, const void *pkey, int (*compare)(const void *, const void *))
 217 {
 218     hashtItem *htip;
 219
 220     assert(compare);
 221
 222     if (!htab)
 223         return NULL;
 224
 225     for (htip = htab->table[key] ; htip ; htip = htip->next ) {
 226         /* if a compare function is given use it */
 227         if (compare && compare(pkey, htip->pkey))
 228             break;
 229         else
 230             if (pkey == htip->pkey)
 231                 break;
 232     }
 233     return htip;
 234 }
 235
 236 void *hTabFindByKey(hTab *h, int key, const void *pkey, int (*compare)(const void *, const void *))
 237 {
 238     const hashtItem *item;
 239
 240     if ((item = _findByKey(h, key, pkey, compare)))
 241         return item->item;
 242     return NULL;
 243 }
 244
 245 int hTabDeleteByKey(hTab **h, int key, const void *pkey, int (*compare)(const void *, const void *))
 246 {
 247     hashtItem *htip, **htipp ;
 248
 249     if (!(*h))
 250         return 0;
 251
 252     /* first check if anything exists in the slot */
 253     if (! (*h)->table[key] )
 254         return 0;
 255
 256     /* delete specific item */
 257     /* if a compare function is given then use the compare */
 258     /* function to find the item, else just compare the items */
 259
 260     htipp = &((*h)->table[key]);
 261     htip = (*h)->table[key];
 262     for (; htip; htip = htip->next) {
 263         if (
 264             (compare && compare(pkey, htip->pkey)) ||
 265             pkey == htip->pkey) {
 266             *htipp=htip->next;
 267             break;
 268         }
 269         htipp=&(htip->next);
 270     }
 271     (*h)->nItems-- ;
 272
 273     if (!(*h)->nItems) {
 274         *h = NULL;
 275     }
 276     return 1;
 277 }
 278
 279 /*-----------------------------------------------------------------*/
 280 /* hTabIsInTable - will determine if an Item is in the hasht       */
 281 /*-----------------------------------------------------------------*/
 282 int hTabIsInTable (hTab *htab, int key,
 283                    void *item , int (*compareFunc)(void *,void *))
 284 {
 285     if (_findItem(htab, key, item, compareFunc))
 286         return 1;
 287     return 0;
 288 }
 289
 290 /*-----------------------------------------------------------------*/
 291 /* hTabFirstItem - returns the first Item in the hTab              */
 292 /*-----------------------------------------------------------------*/
 293 void *hTabFirstItem (hTab *htab, int *k)
 294 {
 295     int key ;
 296
 297     if (!htab)
 298         return NULL ;
 299
 300     for ( key = htab->minKey ; key <= htab->maxKey ; key++ ) {
 301         if (htab->table[key]) {
 302             htab->currItem = htab->table[key];
 303             htab->currKey  = key ;
 304             *k = key ;
 305             return htab->table[key]->item;
 306         }
 307     }
 308     return NULL ;
 309 }
 310
 311 /*-----------------------------------------------------------------*/
 312 /* hTabNextItem - returns the next item in the hTab                */
 313 /*-----------------------------------------------------------------*/
 314 void *hTabNextItem (hTab *htab, int *k)
 315 {
 316     int key ;
 317
 318     if (!htab)
 319         return NULL;
 320
 321     /* if this chain not ended then */
 322     if (htab->currItem->next) {
 323         *k = htab->currItem->key ;
 324         return (htab->currItem = htab->currItem->next)->item ;
 325     }
 326
 327     /* find the next chain which has something */
 328     for ( key = htab->currKey + 1; key <= htab->maxKey ; key++ ) {
 329         if (htab->table[key]) {
 330             htab->currItem = htab->table[key];
 331             *k = htab->currKey  = key ;
 332             return htab->table[key]->item;
 333         }
 334     }
 335
 336     return NULL ;
 337 }
 338
 339 /*-----------------------------------------------------------------*/
 340 /* hTabFirstItemWK - returns the first Item in the hTab for a key  */
 341 /*-----------------------------------------------------------------*/
 342 void *hTabFirstItemWK (hTab *htab, int wk)
 343 {
 344
 345     if (!htab)
 346         return NULL ;
 347
 348     if (wk < htab->minKey || wk > htab->maxKey )
 349         return NULL;
 350
 351     htab->currItem = htab->table[wk] ;
 352     htab->currKey  = wk ;
 353
 354     return (htab->table[wk] ? htab->table[wk]->item : NULL);
 355 }
 356
 357 /*-----------------------------------------------------------------*/
 358 /* hTabNextItem - returns the next item in the hTab for a key      */
 359 /*-----------------------------------------------------------------*/
 360 void *hTabNextItemWK (hTab *htab )
 361 {
 362
 363     if (!htab)
 364         return NULL;
 365
 366     /* if this chain not ended then */
 367     if (htab->currItem->next) {
 368         return (htab->currItem = htab->currItem->next)->item ;
 369     }
 370
 371     return NULL ;
 372 }
 373
 374 /*-----------------------------------------------------------------*/
 375 /* hTabFromTable - hash Table from a hash table                    */
 376 /*-----------------------------------------------------------------*/
 377 hTab *hTabFromTable (hTab *htab)
 378 {
 379     hTab *nhtab ;
 380     hashtItem *htip;
 381     int key ;
 382
 383     if (!htab)
 384         return NULL ;
 385
 386     nhtab = newHashTable(htab->size);
 387
 388     for (key = htab->minKey; key <= htab->maxKey ; key++ ) {
 389
 390         for (htip = htab->table[key] ; htip ; htip = htip->next)
 391             hTabAddItem (&nhtab, htip->key, htip->item);
 392     }
 393
 394     return nhtab ;
 395 }
 396
 397 /*-----------------------------------------------------------------*/
 398 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2*/
 399 /*-----------------------------------------------------------------*/
 400 int isHtabsEqual (hTab *htab1, hTab *htab2,
 401                   int (*compareFunc)(void *,void *))
 402 {
 403     void *item;
 404     int key;
 405
 406     if ( htab1 == htab2 )
 407         return 1;
 408
 409     if (htab1 == NULL || htab2 == NULL )
 410         return 0;
 411
 412     /* if they are different sizes then */
 413     if ( htab1->nItems != htab2->nItems)
 414         return 0;
 415
 416     /* now do an item by item check */
 417     for ( item = hTabFirstItem (htab1,&key) ;item;
 418           item = hTabNextItem (htab1,&key))
 419         if (!hTabIsInTable (htab2, key, item, compareFunc))
 420             return 0;
 421
 422     return 1;
 423 }
 424
 425
 426 /*-----------------------------------------------------------------*/
 427 /* hTabSearch - returns the first Item with the specified key      */
 428 /*-----------------------------------------------------------------*/
 429 hashtItem *hTabSearch (hTab *htab, int key )
 430 {
 431     if (!htab)
 432         return NULL ;
 433
 434     if ((key < htab->minKey)||(key>htab->maxKey))
 435         return NULL ;
 436
 437     if (!htab->table[key])
 438         return NULL ;
 439
 440     return htab->table[key] ;
 441 }
 442
 443 /*-----------------------------------------------------------------*/
 444 /* hTabItemWithKey - returns the first item with the given key     */
 445 /*-----------------------------------------------------------------*/
 446 void *hTabItemWithKey (hTab *htab, int key )
 447 {
 448     hashtItem *htip;
 449
 450     if (!(htip = hTabSearch(htab,key)))
 451         return NULL;
 452
 453     return htip->item;
 454 }
 455
 456 /*-----------------------------------------------------------------*/
 457 /*hTabAddItemIfNotP - adds an item with nothing found with key     */
 458 /*-----------------------------------------------------------------*/
 459 void hTabAddItemIfNotP (hTab **htab, int key, void *item)
 460 {
 461     if (!*htab) {
 462         hTabAddItem (htab,key,item);
 463         return;
 464     }
 465
 466     if (hTabItemWithKey(*htab,key))
 467         return ;
 468
 469     hTabAddItem(htab,key,item);
 470 }
 471
 472 /** Simple implementation of a hash table which uses
 473     string (key, value) pairs.  If a key already exists in the
 474     table, the newly added value will replace it.
 475     This is used for the assembler token table.  The replace existing
 476     condition is used to implement inheritance.
 477 */
 478 static int _compare(const void *s1, const void *s2)
 479 {
 480     return !strcmp(s1, s2);
 481 }
 482
 483 static int _hash(const char *sz)
 484 {
 485     /* Dumb for now */
 486     return *sz;
 487 }
 488
 489 void shash_add(hTab **h, const char *szKey, const char *szValue)
 490 {
 491     int key = _hash(szKey);
 492     /* First, delete any that currently exist */
 493     hTabDeleteByKey(h, key, szKey, _compare);
 494     /* Now add in ours */
 495     hTabAddItemLong(h, key, gc_strdup(szKey), gc_strdup(szValue));
 496 }
 497
 498 const char *shash_find(hTab *h, const char *szKey)
 499 {
 500     int key = _hash(szKey);
 501     return (char *)hTabFindByKey(h, key, szKey, _compare);
 502 }