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"
33 #define DEFAULT_HTAB_SIZE 128
35 /*-----------------------------------------------------------------*/
36 /* newHashtItem - creates a new hashtable Item */
37 /*-----------------------------------------------------------------*/
39 _newHashtItem (int key, void *pkey, void *item)
43 htip = Safe_calloc (1, sizeof (hashtItem));
52 /*-----------------------------------------------------------------*/
53 /* newHashTable - allocates a new hashtable of size */
54 /*-----------------------------------------------------------------*/
56 newHashTable (int size)
60 htab = Safe_calloc (1, sizeof (hTab));
62 if (!(htab->table = calloc ((size + 1), sizeof (hashtItem *))))
64 fprintf (stderr, "out of virtual memory %s %d\n",
65 __FILE__, (size + 1) * sizeof (hashtItem *));
68 htab->minKey = htab->size = size;
74 hTabAddItemLong (hTab ** htab, int key, void *pkey, void *item)
80 *htab = newHashTable (DEFAULT_HTAB_SIZE);
82 if (key > (*htab)->size)
85 (*htab)->table = Safe_realloc ((*htab)->table,
86 (key * 2 + 2) * sizeof (hashtItem *));
87 for (i = (*htab)->size + 1; i <= (key * 2 + 1); i++)
88 (*htab)->table[i] = NULL;
89 (*htab)->size = key * 2 + 1;
93 if ((*htab)->maxKey < key)
94 (*htab)->maxKey = key;
96 if ((*htab)->minKey > key)
97 (*htab)->minKey = key;
100 htip = _newHashtItem (key, pkey, item);
102 /* if there is a clash then goto end of chain */
103 if ((last = (*htab)->table[key]))
110 /* else just add it */
111 (*htab)->table[key] = htip;
115 /*-----------------------------------------------------------------*/
116 /* hTabAddItem - adds an item to the hash table */
117 /*-----------------------------------------------------------------*/
119 hTabAddItem (hTab ** htab, int key, void *item)
121 hTabAddItemLong (htab, key, NULL, item);
124 /*-----------------------------------------------------------------*/
125 /* hTabDeleteItem - either delete an item */
126 /*-----------------------------------------------------------------*/
128 hTabDeleteItem (hTab ** htab, int key,
129 const void *item, DELETE_ACTION action,
130 int (*compareFunc) (const void *, const void *))
132 hashtItem *htip, **htipp;
137 /* first check if anything exists in the slot */
138 if (!(*htab)->table[key])
141 /* if delete chain */
142 if (action == DELETE_CHAIN)
143 (*htab)->table[key] = NULL;
147 /* delete specific item */
148 /* if a compare function is given then use the compare */
149 /* function to find the item, else just compare the items */
151 htipp = &((*htab)->table[key]);
152 htip = (*htab)->table[key];
153 for (; htip; htip = htip->next)
156 if (compareFunc ? compareFunc (item, htip->item) :
157 (item == htip->item))
163 htipp = &(htip->next);
170 if (!(*htab)->nItems)
176 /*-----------------------------------------------------------------*/
177 /* hTabDeleteAll - deletes all items in a hash table to reduce mem */
178 /* leaks written by */
179 /* "BESSIERE Jerome" <BESSIERE_Jerome@stna.dgac.fr> */
180 /*-----------------------------------------------------------------*/
182 hTabDeleteAll (hTab * p)
187 register hashtItem *jc, *jn;
188 for (i = 0; i < p->size; i++)
191 if (!(jc = p->table[i]))
206 /*-----------------------------------------------------------------*/
207 /* hTabClearAll - clear all entries in the table (does not free) */
208 /*-----------------------------------------------------------------*/
210 hTabClearAll (hTab * htab)
213 if (!htab || !htab->table)
215 printf ("null table\n");
218 memset (htab->table, 0, htab->size * sizeof (hashtItem *));
220 htab->minKey = htab->size;
221 htab->currKey = htab->nItems = htab->maxKey = 0;
224 static const hashtItem *
225 _findItem (hTab * htab, int key, void *item, int (*compareFunc) (void *, void *))
229 for (htip = htab->table[key]; htip; htip = htip->next)
231 /* if a compare function is given use it */
232 if (compareFunc && compareFunc (item, htip->item))
234 else if (item == htip->item)
240 static const hashtItem *
241 _findByKey (hTab * htab, int key, const void *pkey, int (*compare) (const void *, const void *))
250 for (htip = htab->table[key]; htip; htip = htip->next)
252 /* if a compare function is given use it */
253 if (compare && compare (pkey, htip->pkey))
259 if (pkey == htip->pkey)
269 hTabFindByKey (hTab * h, int key, const void *pkey, int (*compare) (const void *, const void *))
271 const hashtItem *item;
273 if ((item = _findByKey (h, key, pkey, compare)))
279 hTabDeleteByKey (hTab ** h, int key, const void *pkey, int (*compare) (const void *, const void *))
281 hashtItem *htip, **htipp;
286 /* first check if anything exists in the slot */
287 if (!(*h)->table[key])
290 /* delete specific item */
291 /* if a compare function is given then use the compare */
292 /* function to find the item, else just compare the items */
294 htipp = &((*h)->table[key]);
295 htip = (*h)->table[key];
296 for (; htip; htip = htip->next)
299 (compare && compare (pkey, htip->pkey)) ||
305 htipp = &(htip->next);
316 /*-----------------------------------------------------------------*/
317 /* hTabIsInTable - will determine if an Item is in the hasht */
318 /*-----------------------------------------------------------------*/
320 hTabIsInTable (hTab * htab, int key,
321 void *item, int (*compareFunc) (void *, void *))
323 if (_findItem (htab, key, item, compareFunc))
328 /*-----------------------------------------------------------------*/
329 /* hTabFirstItem - returns the first Item in the hTab */
330 /*-----------------------------------------------------------------*/
332 hTabFirstItem (hTab * htab, int *k)
339 for (key = htab->minKey; key <= htab->maxKey; key++)
341 if (htab->table[key])
343 htab->currItem = htab->table[key];
346 return htab->table[key]->item;
352 /*-----------------------------------------------------------------*/
353 /* hTabNextItem - returns the next item in the hTab */
354 /*-----------------------------------------------------------------*/
356 hTabNextItem (hTab * htab, int *k)
363 /* if this chain not ended then */
364 if (htab->currItem->next)
366 *k = htab->currItem->key;
367 return (htab->currItem = htab->currItem->next)->item;
370 /* find the next chain which has something */
371 for (key = htab->currKey + 1; key <= htab->maxKey; key++)
373 if (htab->table[key])
375 htab->currItem = htab->table[key];
376 *k = htab->currKey = key;
377 return htab->table[key]->item;
384 /*-----------------------------------------------------------------*/
385 /* hTabFirstItemWK - returns the first Item in the hTab for a key */
386 /*-----------------------------------------------------------------*/
388 hTabFirstItemWK (hTab * htab, int wk)
394 if (wk < htab->minKey || wk > htab->maxKey)
397 htab->currItem = htab->table[wk];
400 return (htab->table[wk] ? htab->table[wk]->item : NULL);
403 /*-----------------------------------------------------------------*/
404 /* hTabNextItem - returns the next item in the hTab for a key */
405 /*-----------------------------------------------------------------*/
407 hTabNextItemWK (hTab * htab)
413 /* if this chain not ended then */
414 if (htab->currItem->next)
416 return (htab->currItem = htab->currItem->next)->item;
422 /*-----------------------------------------------------------------*/
423 /* hTabFromTable - hash Table from a hash table */
424 /*-----------------------------------------------------------------*/
426 hTabFromTable (hTab * htab)
435 nhtab = newHashTable (htab->size);
437 for (key = htab->minKey; key <= htab->maxKey; key++)
440 for (htip = htab->table[key]; htip; htip = htip->next)
441 hTabAddItem (&nhtab, htip->key, htip->item);
447 /*-----------------------------------------------------------------*/
448 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2 */
449 /*-----------------------------------------------------------------*/
451 isHtabsEqual (hTab * htab1, hTab * htab2,
452 int (*compareFunc) (void *, void *))
460 if (htab1 == NULL || htab2 == NULL)
463 /* if they are different sizes then */
464 if (htab1->nItems != htab2->nItems)
467 /* now do an item by item check */
468 for (item = hTabFirstItem (htab1, &key); item;
469 item = hTabNextItem (htab1, &key))
470 if (!hTabIsInTable (htab2, key, item, compareFunc))
477 /*-----------------------------------------------------------------*/
478 /* hTabSearch - returns the first Item with the specified key */
479 /*-----------------------------------------------------------------*/
481 hTabSearch (hTab * htab, int key)
486 if ((key < htab->minKey) || (key > htab->maxKey))
489 if (!htab->table[key])
492 return htab->table[key];
495 /*-----------------------------------------------------------------*/
496 /* hTabItemWithKey - returns the first item with the given key */
497 /*-----------------------------------------------------------------*/
499 hTabItemWithKey (hTab * htab, int key)
503 if (!(htip = hTabSearch (htab, key)))
509 /*-----------------------------------------------------------------*/
510 /*hTabAddItemIfNotP - adds an item with nothing found with key */
511 /*-----------------------------------------------------------------*/
513 hTabAddItemIfNotP (hTab ** htab, int key, void *item)
517 hTabAddItem (htab, key, item);
521 if (hTabItemWithKey (*htab, key))
524 hTabAddItem (htab, key, item);
527 /** Simple implementation of a hash table which uses
528 string (key, value) pairs. If a key already exists in the
529 table, the newly added value will replace it.
530 This is used for the assembler token table. The replace existing
531 condition is used to implement inheritance.
534 _compare (const void *s1, const void *s2)
536 return !strcmp (s1, s2);
540 _hash (const char *sz)
547 shash_add (hTab ** h, const char *szKey, const char *szValue)
549 int key = _hash (szKey);
550 /* First, delete any that currently exist */
551 hTabDeleteByKey (h, key, szKey, _compare);
552 /* Now add in ours */
553 hTabAddItemLong (h, key, gc_strdup (szKey), gc_strdup (szValue));
557 shash_find (hTab * h, const char *szKey)
559 int key = _hash (szKey);
560 return (char *) hTabFindByKey (h, key, szKey, _compare);