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 "common.h"
  26
  27 #define DEFAULT_HTAB_SIZE 128
  28
  29 /*-----------------------------------------------------------------*/
  30 /* newHashtItem - creates a new hashtable Item                     */
  31 /*-----------------------------------------------------------------*/
  32  hashtItem *newHashtItem (int key, void *item)
  33 {
  34     hashtItem *htip;
  35
  36     ALLOC(htip,sizeof(hashtItem));
  37
  38     htip->key = key ;
  39     htip->item = item;
  40     htip->next = NULL ;
  41     return htip;
  42 }
  43
  44 /*-----------------------------------------------------------------*/
  45 /* newHashTable - allocates a new hashtable of size                */
  46 /*-----------------------------------------------------------------*/
  47 hTab *newHashTable (int size)
  48 {
  49     hTab *htab;
  50
  51     ALLOC(htab,sizeof(hTab));
  52
  53     if (!(htab->table = GC_malloc((size +1)* sizeof(hashtItem *)))) {
  54         fprintf(stderr,"out of virtual memory %s %d\n",
  55                 __FILE__,(size +1)* sizeof(hashtItem *));
  56         exit(1);
  57     }
  58     htab->minKey = htab->size = size ;
  59     return htab;
  60 }
  61
  62
  63 /*-----------------------------------------------------------------*/
  64 /* hTabAddItem - adds an item to the hash table                    */
  65 /*-----------------------------------------------------------------*/
  66 void hTabAddItem (hTab **htab, int key, void *item )
  67 {
  68     hashtItem *htip ;
  69     hashtItem *last ;
  70
  71     if (!(*htab) )
  72         *htab = newHashTable ( DEFAULT_HTAB_SIZE  );
  73
  74     if (key > (*htab)->size ) {
  75         int i;
  76         (*htab)->table = GC_realloc ((*htab)->table,
  77                                      (key*2 + 2)*sizeof(hashtItem *));
  78         for ( i = (*htab)->size +1; i <= (key*2 + 1); i++ )
  79             (*htab)->table[i] = NULL ;
  80         (*htab)->size = key*2 + 1;
  81     }
  82
  83     /* update the key */
  84     if ((*htab)->maxKey < key )
  85         (*htab)->maxKey = key ;
  86
  87     if ((*htab)->minKey > key )
  88         (*htab)->minKey = key ;
  89
  90     /* create the item */
  91     htip = newHashtItem (key,item);
  92
  93     /* if there is a clash then goto end of chain */
  94     if ((last = (*htab)->table[key])) {
  95         while (last->next)
  96             last = last->next ;
  97         last->next = htip ;
  98     } else
  99         /* else just add it */
 100         (*htab)->table[key] = htip ;
 101     (*htab)->nItems++ ;
 102 }
 103
 104 /*-----------------------------------------------------------------*/
 105 /* hTabDeleteItem - either delete an item                          */
 106 /*-----------------------------------------------------------------*/
 107 void hTabDeleteItem (hTab **htab, int key ,
 108                      void *item, int action ,
 109                      int (*compareFunc)(void *,void *))
 110 {
 111     hashtItem *htip, **htipp ;
 112
 113     if (!(*htab))
 114         return ;
 115
 116     /* first check if anything exists in the slot */
 117     if (! (*htab)->table[key] )
 118         return ;
 119
 120     /* if delete chain */
 121     if ( action == DELETE_CHAIN )
 122         (*htab)->table[key] = NULL ;
 123     else {
 124
 125         /* delete specific item */
 126         /* if a compare function is given then use the compare */
 127         /* function to find the item, else just compare the items */
 128
 129         htipp = &((*htab)->table[key]);
 130         htip = (*htab)->table[key];
 131         for (; htip; htip = htip->next) {
 132
 133             if (compareFunc ? (*compareFunc)(item,htip->item) :
 134                 (item == htip->item) ) {
 135                 *htipp=htip->next;
 136                 break;
 137             }
 138
 139             htipp=&(htip->next);
 140         }
 141
 142         /*          GC_free(htip); */
 143     }
 144
 145     (*htab)->nItems-- ;
 146
 147     if (!(*htab)->nItems) {
 148         *htab = NULL;
 149     }
 150 }
 151
 152 /*-----------------------------------------------------------------*/
 153 /* hTabDeleteAll - deletes all items in a hash table to reduce mem */
 154 /*                 leaks written by                                */
 155 /*                "BESSIERE Jerome" <BESSIERE_Jerome@stna.dgac.fr> */
 156 /*-----------------------------------------------------------------*/
 157 void hTabDeleteAll(hTab * p)
 158 {
 159     if (p && p->table) {
 160         register int i;
 161         register hashtItem *jc,*jn;
 162         for (i=0;i<p->size;i++) {
 163
 164             if (!(jc = p->table[i])) continue;
 165             jn = jc->next;
 166             while(jc){
 167                 GC_free(jc);
 168                 if((jc=jn)) jn = jc->next;
 169             }
 170             p->table[i] = NULL ;
 171         }
 172         GC_free(p->table);
 173     }
 174 }
 175
 176 /*-----------------------------------------------------------------*/
 177 /* hTabClearAll - clear all entries inthe table (does not free)    */
 178 /*-----------------------------------------------------------------*/
 179 void hTabClearAll (hTab *htab)
 180 {
 181
 182     if (!htab || !htab->table) {
 183         printf("null table\n");
 184         return ;
 185     }
 186     memset(htab->table, 0, htab->size*sizeof(hashtItem *));
 187
 188     htab->minKey = htab->size;
 189     htab->currKey = htab->nItems = htab->maxKey = 0;
 190 }
 191
 192 /*-----------------------------------------------------------------*/
 193 /* hTabIsInTable - will determine if an Item is in the hasht       */
 194 /*-----------------------------------------------------------------*/
 195 int hTabIsInTable (hTab *htab, int key,
 196                    void *item , int (*compareFunc)(void *,void *))
 197 {
 198     hashtItem *htip ;
 199
 200     for (htip = htab->table[key] ; htip ; htip = htip->next ) {
 201         /* if a compare function is given use it */
 202         if (compareFunc && (*compareFunc)(item,htip->item))
 203             break ;
 204         else
 205             if (item == htip->item)
 206                 break;
 207     }
 208
 209     if ( htip)
 210         return 1;
 211     return 0;
 212 }
 213
 214 /*-----------------------------------------------------------------*/
 215 /* hTabFirstItem - returns the first Item in the hTab              */
 216 /*-----------------------------------------------------------------*/
 217 void *hTabFirstItem (hTab *htab, int *k)
 218 {
 219     int key ;
 220
 221     if (!htab)
 222         return NULL ;
 223
 224     for ( key = htab->minKey ; key <= htab->maxKey ; key++ ) {
 225         if (htab->table[key]) {
 226             htab->currItem = htab->table[key];
 227             htab->currKey  = key ;
 228             *k = key ;
 229             return htab->table[key]->item;
 230         }
 231     }
 232     return NULL ;
 233 }
 234
 235 /*-----------------------------------------------------------------*/
 236 /* hTabNextItem - returns the next item in the hTab                */
 237 /*-----------------------------------------------------------------*/
 238 void *hTabNextItem (hTab *htab, int *k)
 239 {
 240     int key ;
 241
 242     if (!htab)
 243         return NULL;
 244
 245     /* if this chain not ended then */
 246     if (htab->currItem->next) {
 247         *k = htab->currItem->key ;
 248         return (htab->currItem = htab->currItem->next)->item ;
 249     }
 250
 251     /* find the next chain which has something */
 252     for ( key = htab->currKey + 1; key <= htab->maxKey ; key++ ) {
 253         if (htab->table[key]) {
 254             htab->currItem = htab->table[key];
 255             *k = htab->currKey  = key ;
 256             return htab->table[key]->item;
 257         }
 258     }
 259
 260     return NULL ;
 261 }
 262
 263 /*-----------------------------------------------------------------*/
 264 /* hTabFirstItemWK - returns the first Item in the hTab for a key  */
 265 /*-----------------------------------------------------------------*/
 266 void *hTabFirstItemWK (hTab *htab, int wk)
 267 {
 268
 269     if (!htab)
 270         return NULL ;
 271
 272     if (wk < htab->minKey || wk > htab->maxKey )
 273         return NULL;
 274
 275     htab->currItem = htab->table[wk] ;
 276     htab->currKey  = wk ;
 277
 278     return (htab->table[wk] ? htab->table[wk]->item : NULL);
 279 }
 280
 281 /*-----------------------------------------------------------------*/
 282 /* hTabNextItem - returns the next item in the hTab for a key      */
 283 /*-----------------------------------------------------------------*/
 284 void *hTabNextItemWK (hTab *htab )
 285 {
 286
 287     if (!htab)
 288         return NULL;
 289
 290     /* if this chain not ended then */
 291     if (htab->currItem->next) {
 292         return (htab->currItem = htab->currItem->next)->item ;
 293     }
 294
 295     return NULL ;
 296 }
 297
 298 /*-----------------------------------------------------------------*/
 299 /* hTabFromTable - hash Table from a hash table                    */
 300 /*-----------------------------------------------------------------*/
 301 hTab *hTabFromTable (hTab *htab)
 302 {
 303     hTab *nhtab ;
 304     hashtItem *htip;
 305     int key ;
 306
 307     if (!htab)
 308         return NULL ;
 309
 310     nhtab = newHashTable(htab->size);
 311
 312     for (key = htab->minKey; key <= htab->maxKey ; key++ ) {
 313
 314         for (htip = htab->table[key] ; htip ; htip = htip->next)
 315             hTabAddItem (&nhtab, htip->key, htip->item);
 316     }
 317
 318     return nhtab ;
 319 }
 320
 321 /*-----------------------------------------------------------------*/
 322 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2*/
 323 /*-----------------------------------------------------------------*/
 324 int isHtabsEqual (hTab *htab1, hTab *htab2,
 325                   int (*compareFunc)(void *,void *))
 326 {
 327     void *item;
 328     int key;
 329
 330     if ( htab1 == htab2 )
 331         return 1;
 332
 333     if (htab1 == NULL || htab2 == NULL )
 334         return 0;
 335
 336     /* if they are different sizes then */
 337     if ( htab1->nItems != htab2->nItems)
 338         return 0;
 339
 340     /* now do an item by item check */
 341     for ( item = hTabFirstItem (htab1,&key) ;item;
 342           item = hTabNextItem (htab1,&key))
 343         if (!hTabIsInTable (htab2, key, item, compareFunc))
 344             return 0;
 345
 346     return 1;
 347 }
 348
 349
 350 /*-----------------------------------------------------------------*/
 351 /* hTabSearch - returns the first Item with the specified key      */
 352 /*-----------------------------------------------------------------*/
 353 hashtItem *hTabSearch (hTab *htab, int key )
 354 {
 355     if (!htab)
 356         return NULL ;
 357
 358     if ((key < htab->minKey)||(key>htab->maxKey))
 359         return NULL ;
 360
 361     if (!htab->table[key])
 362         return NULL ;
 363
 364     return htab->table[key] ;
 365 }
 366
 367 /*-----------------------------------------------------------------*/
 368 /* hTabItemWithKey - returns the first item with the gievn key     */
 369 /*-----------------------------------------------------------------*/
 370 void *hTabItemWithKey (hTab *htab, int key )
 371 {
 372     hashtItem *htip;
 373
 374     if (!(htip = hTabSearch(htab,key)))
 375         return NULL;
 376
 377     return htip->item;
 378 }
 379
 380 /*-----------------------------------------------------------------*/
 381 /*hTabAddItemIfNotP - adds an item with nothing found with key     */
 382 /*-----------------------------------------------------------------*/
 383 void hTabAddItemIfNotP (hTab **htab, int key, void *item)
 384 {
 385     if (!*htab) {
 386         hTabAddItem (htab,key,item);
 387         return;
 388     }
 389
 390     if (hTabItemWithKey(*htab,key))
 391         return ;
 392
 393     hTabAddItem(htab,key,item);
 394 }