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