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     }
 147
 148     (*htab)->nItems-- ;
 149
 150     if (!(*htab)->nItems) {
 151         *htab = NULL;
 152     }
 153 }
 154
 155 /*-----------------------------------------------------------------*/
 156 /* hTabDeleteAll - deletes all items in a hash table to reduce mem */
 157 /*                 leaks written by                                */
 158 /*                "BESSIERE Jerome" <BESSIERE_Jerome@stna.dgac.fr> */
 159 /*-----------------------------------------------------------------*/
 160 void hTabDeleteAll(hTab * p)
 161 {
 162     if (p && p->table) {
 163         register int i;
 164         register hashtItem *jc,*jn;
 165         for (i=0;i<p->size;i++) {
 166
 167             if (!(jc = p->table[i])) continue;
 168             jn = jc->next;
 169             while(jc){
 170                 GC_free(jc);
 171                 if((jc=jn)) jn = jc->next;
 172             }
 173             p->table[i] = NULL ;
 174         }
 175         GC_free(p->table);
 176     }
 177 }
 178
 179 /*-----------------------------------------------------------------*/
 180 /* hTabClearAll - clear all entries inthe table (does not free)    */
 181 /*-----------------------------------------------------------------*/
 182 void hTabClearAll (hTab *htab)
 183 {
 184
 185     if (!htab || !htab->table) {
 186         printf("null table\n");
 187         return ;
 188     }
 189     memset(htab->table, 0, htab->size*sizeof(hashtItem *));
 190
 191     htab->minKey = htab->size;
 192     htab->currKey = htab->nItems = htab->maxKey = 0;
 193 }
 194
 195 /*-----------------------------------------------------------------*/
 196 /* hTabIsInTable - will determine if an Item is in the hasht       */
 197 /*-----------------------------------------------------------------*/
 198 int hTabIsInTable (hTab *htab, int key,
 199                    void *item , int (*compareFunc)(void *,void *))
 200 {
 201     hashtItem *htip ;
 202
 203     for (htip = htab->table[key] ; htip ; htip = htip->next ) {
 204         /* if a compare function is given use it */
 205         if (compareFunc && (*compareFunc)(item,htip->item))
 206             break ;
 207         else
 208             if (item == htip->item)
 209                 break;
 210     }
 211
 212     if ( htip)
 213         return 1;
 214     return 0;
 215 }
 216
 217 /*-----------------------------------------------------------------*/
 218 /* hTabFirstItem - returns the first Item in the hTab              */
 219 /*-----------------------------------------------------------------*/
 220 void *hTabFirstItem (hTab *htab, int *k)
 221 {
 222     int key ;
 223
 224     if (!htab)
 225         return NULL ;
 226
 227     for ( key = htab->minKey ; key <= htab->maxKey ; key++ ) {
 228         if (htab->table[key]) {
 229             htab->currItem = htab->table[key];
 230             htab->currKey  = key ;
 231             *k = key ;
 232             return htab->table[key]->item;
 233         }
 234     }
 235     return NULL ;
 236 }
 237
 238 /*-----------------------------------------------------------------*/
 239 /* hTabNextItem - returns the next item in the hTab                */
 240 /*-----------------------------------------------------------------*/
 241 void *hTabNextItem (hTab *htab, int *k)
 242 {
 243     int key ;
 244
 245     if (!htab)
 246         return NULL;
 247
 248     /* if this chain not ended then */
 249     if (htab->currItem->next) {
 250         *k = htab->currItem->key ;
 251         return (htab->currItem = htab->currItem->next)->item ;
 252     }
 253
 254     /* find the next chain which has something */
 255     for ( key = htab->currKey + 1; key <= htab->maxKey ; key++ ) {
 256         if (htab->table[key]) {
 257             htab->currItem = htab->table[key];
 258             *k = htab->currKey  = key ;
 259             return htab->table[key]->item;
 260         }
 261     }
 262
 263     return NULL ;
 264 }
 265
 266 /*-----------------------------------------------------------------*/
 267 /* hTabFirstItemWK - returns the first Item in the hTab for a key  */
 268 /*-----------------------------------------------------------------*/
 269 void *hTabFirstItemWK (hTab *htab, int wk)
 270 {
 271
 272     if (!htab)
 273         return NULL ;
 274
 275     if (wk < htab->minKey || wk > htab->maxKey )
 276         return NULL;
 277
 278     htab->currItem = htab->table[wk] ;
 279     htab->currKey  = wk ;
 280
 281     return (htab->table[wk] ? htab->table[wk]->item : NULL);
 282 }
 283
 284 /*-----------------------------------------------------------------*/
 285 /* hTabNextItem - returns the next item in the hTab for a key      */
 286 /*-----------------------------------------------------------------*/
 287 void *hTabNextItemWK (hTab *htab )
 288 {
 289
 290     if (!htab)
 291         return NULL;
 292
 293     /* if this chain not ended then */
 294     if (htab->currItem->next) {
 295         return (htab->currItem = htab->currItem->next)->item ;
 296     }
 297
 298     return NULL ;
 299 }
 300
 301 /*-----------------------------------------------------------------*/
 302 /* hTabFromTable - hash Table from a hash table                    */
 303 /*-----------------------------------------------------------------*/
 304 hTab *hTabFromTable (hTab *htab)
 305 {
 306     hTab *nhtab ;
 307     hashtItem *htip;
 308     int key ;
 309
 310     if (!htab)
 311         return NULL ;
 312
 313     nhtab = newHashTable(htab->size);
 314
 315     for (key = htab->minKey; key <= htab->maxKey ; key++ ) {
 316
 317         for (htip = htab->table[key] ; htip ; htip = htip->next)
 318             hTabAddItem (&nhtab, htip->key, htip->item);
 319     }
 320
 321     return nhtab ;
 322 }
 323
 324 /*-----------------------------------------------------------------*/
 325 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2*/
 326 /*-----------------------------------------------------------------*/
 327 int isHtabsEqual (hTab *htab1, hTab *htab2,
 328                   int (*compareFunc)(void *,void *))
 329 {
 330     void *item;
 331     int key;
 332
 333     if ( htab1 == htab2 )
 334         return 1;
 335
 336     if (htab1 == NULL || htab2 == NULL )
 337         return 0;
 338
 339     /* if they are different sizes then */
 340     if ( htab1->nItems != htab2->nItems)
 341         return 0;
 342
 343     /* now do an item by item check */
 344     for ( item = hTabFirstItem (htab1,&key) ;item;
 345           item = hTabNextItem (htab1,&key))
 346         if (!hTabIsInTable (htab2, key, item, compareFunc))
 347             return 0;
 348
 349     return 1;
 350 }
 351
 352
 353 /*-----------------------------------------------------------------*/
 354 /* hTabSearch - returns the first Item with the specified key      */
 355 /*-----------------------------------------------------------------*/
 356 hashtItem *hTabSearch (hTab *htab, int key )
 357 {
 358     if (!htab)
 359         return NULL ;
 360
 361     if ((key < htab->minKey)||(key>htab->maxKey))
 362         return NULL ;
 363
 364     if (!htab->table[key])
 365         return NULL ;
 366
 367     return htab->table[key] ;
 368 }
 369
 370 /*-----------------------------------------------------------------*/
 371 /* hTabItemWithKey - returns the first item with the gievn key     */
 372 /*-----------------------------------------------------------------*/
 373 void *hTabItemWithKey (hTab *htab, int key )
 374 {
 375     hashtItem *htip;
 376
 377     if (!(htip = hTabSearch(htab,key)))
 378         return NULL;
 379
 380     return htip->item;
 381 }
 382
 383 /*-----------------------------------------------------------------*/
 384 /*hTabAddItemIfNotP - adds an item with nothing found with key     */
 385 /*-----------------------------------------------------------------*/
 386 void hTabAddItemIfNotP (hTab **htab, int key, void *item)
 387 {
 388     if (!*htab) {
 389         hTabAddItem (htab,key,item);
 390         return;
 391     }
 392
 393     if (hTabItemWithKey(*htab,key))
 394         return ;
 395
 396     hTabAddItem(htab,key,item);
 397 }