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(1,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(1,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 }