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