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