1 /*-----------------------------------------------------------------
2 SDCChast.c - contains support routines for hashtables
4 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
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
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.
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.
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 -------------------------------------------------------------------------*/
29 #include "SDCCglobl.h"
30 #include "SDCChasht.h"
32 #define DEFAULT_HTAB_SIZE 128
34 /*-----------------------------------------------------------------*/
35 /* newHashtItem - creates a new hashtable Item */
36 /*-----------------------------------------------------------------*/
37 static hashtItem *_newHashtItem (int key, void *pkey, void *item)
41 ALLOC(htip,sizeof(hashtItem));
50 /*-----------------------------------------------------------------*/
51 /* newHashTable - allocates a new hashtable of size */
52 /*-----------------------------------------------------------------*/
53 hTab *newHashTable (int size)
57 ALLOC(htab,sizeof(hTab));
59 if (!(htab->table = calloc((size +1), sizeof(hashtItem *)))) {
60 fprintf(stderr,"out of virtual memory %s %d\n",
61 __FILE__,(size +1)* sizeof(hashtItem *));
64 htab->minKey = htab->size = size ;
69 void hTabAddItemLong(hTab **htab, int key, void *pkey, void *item)
75 *htab = newHashTable ( DEFAULT_HTAB_SIZE );
77 if (key > (*htab)->size ) {
79 (*htab)->table = realloc ((*htab)->table,
80 (key*2 + 2)*sizeof(hashtItem *));
81 for ( i = (*htab)->size +1; i <= (key*2 + 1); i++ )
82 (*htab)->table[i] = NULL ;
83 (*htab)->size = key*2 + 1;
87 if ((*htab)->maxKey < key )
88 (*htab)->maxKey = key ;
90 if ((*htab)->minKey > key )
91 (*htab)->minKey = key ;
94 htip = _newHashtItem(key, pkey, item);
96 /* if there is a clash then goto end of chain */
97 if ((last = (*htab)->table[key])) {
102 /* else just add it */
103 (*htab)->table[key] = htip ;
107 /*-----------------------------------------------------------------*/
108 /* hTabAddItem - adds an item to the hash table */
109 /*-----------------------------------------------------------------*/
110 void hTabAddItem (hTab **htab, int key, void *item )
112 hTabAddItemLong(htab, key, NULL, item);
115 /*-----------------------------------------------------------------*/
116 /* hTabDeleteItem - either delete an item */
117 /*-----------------------------------------------------------------*/
118 void hTabDeleteItem (hTab **htab, int key ,
119 const void *item, DELETE_ACTION action,
120 int (*compareFunc)(const void *, const void *))
122 hashtItem *htip, **htipp ;
127 /* first check if anything exists in the slot */
128 if (! (*htab)->table[key] )
131 /* if delete chain */
132 if ( action == DELETE_CHAIN )
133 (*htab)->table[key] = NULL ;
136 /* delete specific item */
137 /* if a compare function is given then use the compare */
138 /* function to find the item, else just compare the items */
140 htipp = &((*htab)->table[key]);
141 htip = (*htab)->table[key];
142 for (; htip; htip = htip->next) {
144 if (compareFunc ? compareFunc(item,htip->item) :
145 (item == htip->item) ) {
157 if (!(*htab)->nItems) {
162 /*-----------------------------------------------------------------*/
163 /* hTabDeleteAll - deletes all items in a hash table to reduce mem */
164 /* leaks written by */
165 /* "BESSIERE Jerome" <BESSIERE_Jerome@stna.dgac.fr> */
166 /*-----------------------------------------------------------------*/
167 void hTabDeleteAll(hTab * p)
171 register hashtItem *jc,*jn;
172 for (i=0;i<p->size;i++) {
174 if (!(jc = p->table[i])) continue;
178 if((jc=jn)) jn = jc->next;
186 /*-----------------------------------------------------------------*/
187 /* hTabClearAll - clear all entries in the table (does not free) */
188 /*-----------------------------------------------------------------*/
189 void hTabClearAll (hTab *htab)
192 if (!htab || !htab->table) {
193 printf("null table\n");
196 memset(htab->table, 0, htab->size*sizeof(hashtItem *));
198 htab->minKey = htab->size;
199 htab->currKey = htab->nItems = htab->maxKey = 0;
202 static const hashtItem *_findItem(hTab *htab, int key, void *item, int (*compareFunc)(void *, void *))
206 for (htip = htab->table[key] ; htip ; htip = htip->next ) {
207 /* if a compare function is given use it */
208 if (compareFunc && compareFunc(item,htip->item))
211 if (item == htip->item)
217 static const hashtItem *_findByKey(hTab *htab, int key, const void *pkey, int (*compare)(const void *, const void *))
226 for (htip = htab->table[key] ; htip ; htip = htip->next) {
227 /* if a compare function is given use it */
228 if (compare && compare(pkey, htip->pkey)) {
232 if (pkey == htip->pkey) {
240 void *hTabFindByKey(hTab *h, int key, const void *pkey, int (*compare)(const void *, const void *))
242 const hashtItem *item;
244 if ((item = _findByKey(h, key, pkey, compare)))
249 int hTabDeleteByKey(hTab **h, int key, const void *pkey, int (*compare)(const void *, const void *))
251 hashtItem *htip, **htipp ;
256 /* first check if anything exists in the slot */
257 if (! (*h)->table[key] )
260 /* delete specific item */
261 /* if a compare function is given then use the compare */
262 /* function to find the item, else just compare the items */
264 htipp = &((*h)->table[key]);
265 htip = (*h)->table[key];
266 for (; htip; htip = htip->next) {
268 (compare && compare(pkey, htip->pkey)) ||
269 pkey == htip->pkey) {
283 /*-----------------------------------------------------------------*/
284 /* hTabIsInTable - will determine if an Item is in the hasht */
285 /*-----------------------------------------------------------------*/
286 int hTabIsInTable (hTab *htab, int key,
287 void *item , int (*compareFunc)(void *,void *))
289 if (_findItem(htab, key, item, compareFunc))
294 /*-----------------------------------------------------------------*/
295 /* hTabFirstItem - returns the first Item in the hTab */
296 /*-----------------------------------------------------------------*/
297 void *hTabFirstItem (hTab *htab, int *k)
304 for ( key = htab->minKey ; key <= htab->maxKey ; key++ ) {
305 if (htab->table[key]) {
306 htab->currItem = htab->table[key];
307 htab->currKey = key ;
309 return htab->table[key]->item;
315 /*-----------------------------------------------------------------*/
316 /* hTabNextItem - returns the next item in the hTab */
317 /*-----------------------------------------------------------------*/
318 void *hTabNextItem (hTab *htab, int *k)
325 /* if this chain not ended then */
326 if (htab->currItem->next) {
327 *k = htab->currItem->key ;
328 return (htab->currItem = htab->currItem->next)->item ;
331 /* find the next chain which has something */
332 for ( key = htab->currKey + 1; key <= htab->maxKey ; key++ ) {
333 if (htab->table[key]) {
334 htab->currItem = htab->table[key];
335 *k = htab->currKey = key ;
336 return htab->table[key]->item;
343 /*-----------------------------------------------------------------*/
344 /* hTabFirstItemWK - returns the first Item in the hTab for a key */
345 /*-----------------------------------------------------------------*/
346 void *hTabFirstItemWK (hTab *htab, int wk)
352 if (wk < htab->minKey || wk > htab->maxKey )
355 htab->currItem = htab->table[wk] ;
358 return (htab->table[wk] ? htab->table[wk]->item : NULL);
361 /*-----------------------------------------------------------------*/
362 /* hTabNextItem - returns the next item in the hTab for a key */
363 /*-----------------------------------------------------------------*/
364 void *hTabNextItemWK (hTab *htab )
370 /* if this chain not ended then */
371 if (htab->currItem->next) {
372 return (htab->currItem = htab->currItem->next)->item ;
378 /*-----------------------------------------------------------------*/
379 /* hTabFromTable - hash Table from a hash table */
380 /*-----------------------------------------------------------------*/
381 hTab *hTabFromTable (hTab *htab)
390 nhtab = newHashTable(htab->size);
392 for (key = htab->minKey; key <= htab->maxKey ; key++ ) {
394 for (htip = htab->table[key] ; htip ; htip = htip->next)
395 hTabAddItem (&nhtab, htip->key, htip->item);
401 /*-----------------------------------------------------------------*/
402 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2*/
403 /*-----------------------------------------------------------------*/
404 int isHtabsEqual (hTab *htab1, hTab *htab2,
405 int (*compareFunc)(void *,void *))
410 if ( htab1 == htab2 )
413 if (htab1 == NULL || htab2 == NULL )
416 /* if they are different sizes then */
417 if ( htab1->nItems != htab2->nItems)
420 /* now do an item by item check */
421 for ( item = hTabFirstItem (htab1,&key) ;item;
422 item = hTabNextItem (htab1,&key))
423 if (!hTabIsInTable (htab2, key, item, compareFunc))
430 /*-----------------------------------------------------------------*/
431 /* hTabSearch - returns the first Item with the specified key */
432 /*-----------------------------------------------------------------*/
433 hashtItem *hTabSearch (hTab *htab, int key )
438 if ((key < htab->minKey)||(key>htab->maxKey))
441 if (!htab->table[key])
444 return htab->table[key] ;
447 /*-----------------------------------------------------------------*/
448 /* hTabItemWithKey - returns the first item with the given key */
449 /*-----------------------------------------------------------------*/
450 void *hTabItemWithKey (hTab *htab, int key )
454 if (!(htip = hTabSearch(htab,key)))
460 /*-----------------------------------------------------------------*/
461 /*hTabAddItemIfNotP - adds an item with nothing found with key */
462 /*-----------------------------------------------------------------*/
463 void hTabAddItemIfNotP (hTab **htab, int key, void *item)
466 hTabAddItem (htab,key,item);
470 if (hTabItemWithKey(*htab,key))
473 hTabAddItem(htab,key,item);
476 /** Simple implementation of a hash table which uses
477 string (key, value) pairs. If a key already exists in the
478 table, the newly added value will replace it.
479 This is used for the assembler token table. The replace existing
480 condition is used to implement inheritance.
482 static int _compare(const void *s1, const void *s2)
484 return !strcmp(s1, s2);
487 static int _hash(const char *sz)
493 void shash_add(hTab **h, const char *szKey, const char *szValue)
495 int key = _hash(szKey);
496 /* First, delete any that currently exist */
497 hTabDeleteByKey(h, key, szKey, _compare);
498 /* Now add in ours */
499 hTabAddItemLong(h, key, gc_strdup(szKey), gc_strdup(szValue));
502 const char *shash_find(hTab *h, const char *szKey)
504 int key = _hash(szKey);
505 return (char *)hTabFindByKey(h, key, szKey, _compare);