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 = calloc((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 = 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                 free(jc);
 178                 if((jc=jn)) jn = jc->next;
 179             }
 180             p->table[i] = NULL ;
 181         }
 182         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         }
 231         else {
 232             if (pkey == htip->pkey) {
 233                 break;
 234             }
 235         }
 236     }
 237     return htip;
 238 }
 239
 240 void *hTabFindByKey(hTab *h, int key, const void *pkey, int (*compare)(const void *, const void *))
 241 {
 242     const hashtItem *item;
 243
 244     if ((item = _findByKey(h, key, pkey, compare)))
 245         return item->item;
 246     return NULL;
 247 }
 248
 249 int hTabDeleteByKey(hTab **h, int key, const void *pkey, int (*compare)(const void *, const void *))
 250 {
 251     hashtItem *htip, **htipp ;
 252
 253     if (!(*h))
 254         return 0;
 255
 256     /* first check if anything exists in the slot */
 257     if (! (*h)->table[key] )
 258         return 0;
 259
 260     /* delete specific item */
 261     /* if a compare function is given then use the compare */
 262     /* function to find the item, else just compare the items */
 263
 264     htipp = &((*h)->table[key]);
 265     htip = (*h)->table[key];
 266     for (; htip; htip = htip->next) {
 267         if (
 268             (compare && compare(pkey, htip->pkey)) ||
 269             pkey == htip->pkey) {
 270             *htipp=htip->next;
 271             break;
 272         }
 273         htipp=&(htip->next);
 274     }
 275     (*h)->nItems-- ;
 276
 277     if (!(*h)->nItems) {
 278         *h = NULL;
 279     }
 280     return 1;
 281 }
 282
 283 /*-----------------------------------------------------------------*/
 284 /* hTabIsInTable - will determine if an Item is in the hasht       */
 285 /*-----------------------------------------------------------------*/
 286 int hTabIsInTable (hTab *htab, int key,
 287                    void *item , int (*compareFunc)(void *,void *))
 288 {
 289     if (_findItem(htab, key, item, compareFunc))
 290         return 1;
 291     return 0;
 292 }
 293
 294 /*-----------------------------------------------------------------*/
 295 /* hTabFirstItem - returns the first Item in the hTab              */
 296 /*-----------------------------------------------------------------*/
 297 void *hTabFirstItem (hTab *htab, int *k)
 298 {
 299     int key ;
 300
 301     if (!htab)
 302         return NULL ;
 303
 304     for ( key = htab->minKey ; key <= htab->maxKey ; key++ ) {
 305         if (htab->table[key]) {
 306             htab->currItem = htab->table[key];
 307             htab->currKey  = key ;
 308             *k = key ;
 309             return htab->table[key]->item;
 310         }
 311     }
 312     return NULL ;
 313 }
 314
 315 /*-----------------------------------------------------------------*/
 316 /* hTabNextItem - returns the next item in the hTab                */
 317 /*-----------------------------------------------------------------*/
 318 void *hTabNextItem (hTab *htab, int *k)
 319 {
 320     int key ;
 321
 322     if (!htab)
 323         return NULL;
 324
 325     /* if this chain not ended then */
 326     if (htab->currItem->next) {
 327         *k = htab->currItem->key ;
 328         return (htab->currItem = htab->currItem->next)->item ;
 329     }
 330
 331     /* find the next chain which has something */
 332     for ( key = htab->currKey + 1; key <= htab->maxKey ; key++ ) {
 333         if (htab->table[key]) {
 334             htab->currItem = htab->table[key];
 335             *k = htab->currKey  = key ;
 336             return htab->table[key]->item;
 337         }
 338     }
 339
 340     return NULL ;
 341 }
 342
 343 /*-----------------------------------------------------------------*/
 344 /* hTabFirstItemWK - returns the first Item in the hTab for a key  */
 345 /*-----------------------------------------------------------------*/
 346 void *hTabFirstItemWK (hTab *htab, int wk)
 347 {
 348
 349     if (!htab)
 350         return NULL ;
 351
 352     if (wk < htab->minKey || wk > htab->maxKey )
 353         return NULL;
 354
 355     htab->currItem = htab->table[wk] ;
 356     htab->currKey  = wk ;
 357
 358     return (htab->table[wk] ? htab->table[wk]->item : NULL);
 359 }
 360
 361 /*-----------------------------------------------------------------*/
 362 /* hTabNextItem - returns the next item in the hTab for a key      */
 363 /*-----------------------------------------------------------------*/
 364 void *hTabNextItemWK (hTab *htab )
 365 {
 366
 367     if (!htab)
 368         return NULL;
 369
 370     /* if this chain not ended then */
 371     if (htab->currItem->next) {
 372         return (htab->currItem = htab->currItem->next)->item ;
 373     }
 374
 375     return NULL ;
 376 }
 377
 378 /*-----------------------------------------------------------------*/
 379 /* hTabFromTable - hash Table from a hash table                    */
 380 /*-----------------------------------------------------------------*/
 381 hTab *hTabFromTable (hTab *htab)
 382 {
 383     hTab *nhtab ;
 384     hashtItem *htip;
 385     int key ;
 386
 387     if (!htab)
 388         return NULL ;
 389
 390     nhtab = newHashTable(htab->size);
 391
 392     for (key = htab->minKey; key <= htab->maxKey ; key++ ) {
 393
 394         for (htip = htab->table[key] ; htip ; htip = htip->next)
 395             hTabAddItem (&nhtab, htip->key, htip->item);
 396     }
 397
 398     return nhtab ;
 399 }
 400
 401 /*-----------------------------------------------------------------*/
 402 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2*/
 403 /*-----------------------------------------------------------------*/
 404 int isHtabsEqual (hTab *htab1, hTab *htab2,
 405                   int (*compareFunc)(void *,void *))
 406 {
 407     void *item;
 408     int key;
 409
 410     if ( htab1 == htab2 )
 411         return 1;
 412
 413     if (htab1 == NULL || htab2 == NULL )
 414         return 0;
 415
 416     /* if they are different sizes then */
 417     if ( htab1->nItems != htab2->nItems)
 418         return 0;
 419
 420     /* now do an item by item check */
 421     for ( item = hTabFirstItem (htab1,&key) ;item;
 422           item = hTabNextItem (htab1,&key))
 423         if (!hTabIsInTable (htab2, key, item, compareFunc))
 424             return 0;
 425
 426     return 1;
 427 }
 428
 429
 430 /*-----------------------------------------------------------------*/
 431 /* hTabSearch - returns the first Item with the specified key      */
 432 /*-----------------------------------------------------------------*/
 433 hashtItem *hTabSearch (hTab *htab, int key )
 434 {
 435     if (!htab)
 436         return NULL ;
 437
 438     if ((key < htab->minKey)||(key>htab->maxKey))
 439         return NULL ;
 440
 441     if (!htab->table[key])
 442         return NULL ;
 443
 444     return htab->table[key] ;
 445 }
 446
 447 /*-----------------------------------------------------------------*/
 448 /* hTabItemWithKey - returns the first item with the given key     */
 449 /*-----------------------------------------------------------------*/
 450 void *hTabItemWithKey (hTab *htab, int key )
 451 {
 452     hashtItem *htip;
 453
 454     if (!(htip = hTabSearch(htab,key)))
 455         return NULL;
 456
 457     return htip->item;
 458 }
 459
 460 /*-----------------------------------------------------------------*/
 461 /*hTabAddItemIfNotP - adds an item with nothing found with key     */
 462 /*-----------------------------------------------------------------*/
 463 void hTabAddItemIfNotP (hTab **htab, int key, void *item)
 464 {
 465     if (!*htab) {
 466         hTabAddItem (htab,key,item);
 467         return;
 468     }
 469
 470     if (hTabItemWithKey(*htab,key))
 471         return ;
 472
 473     hTabAddItem(htab,key,item);
 474 }
 475
 476 /** Simple implementation of a hash table which uses
 477     string (key, value) pairs.  If a key already exists in the
 478     table, the newly added value will replace it.
 479     This is used for the assembler token table.  The replace existing
 480     condition is used to implement inheritance.
 481 */
 482 static int _compare(const void *s1, const void *s2)
 483 {
 484     return !strcmp(s1, s2);
 485 }
 486
 487 static int _hash(const char *sz)
 488 {
 489     /* Dumb for now */
 490     return *sz;
 491 }
 492
 493 void shash_add(hTab **h, const char *szKey, const char *szValue)
 494 {
 495     int key = _hash(szKey);
 496     /* First, delete any that currently exist */
 497     hTabDeleteByKey(h, key, szKey, _compare);
 498     /* Now add in ours */
 499     hTabAddItemLong(h, key, gc_strdup(szKey), gc_strdup(szValue));
 500 }
 501
 502 const char *shash_find(hTab *h, const char *szKey)
 503 {
 504     int key = _hash(szKey);
 505     return (char *)hTabFindByKey(h, key, szKey, _compare);
 506 }