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 "SDCCerr.h"
29 #include "SDCCglobl.h"
30 #include "SDCChasht.h"
31 #include "newalloc.h"
32
33 #define DEFAULT_HTAB_SIZE 128
34
35 /*-----------------------------------------------------------------*/
36 /* newHashtItem - creates a new hashtable Item */
37 /*-----------------------------------------------------------------*/
38 static hashtItem *
_newHashtItem(int key,void * pkey,void * item)39 _newHashtItem (int key, void *pkey, void *item)
40 {
41 hashtItem *htip;
42
43 htip = Safe_alloc ( sizeof (hashtItem));
44
45 htip->key = key;
46 htip->pkey = pkey;
47 htip->item = item;
48 htip->next = NULL;
49 return htip;
50 }
51
52 /*-----------------------------------------------------------------*/
53 /* newHashTable - allocates a new hashtable of size */
54 /*-----------------------------------------------------------------*/
55 hTab *
newHashTable(int size)56 newHashTable (int size)
57 {
58 hTab *htab;
59
60 htab = Safe_alloc ( sizeof (hTab));
61
62 if (!(htab->table = Safe_alloc ((size + 1) * sizeof (hashtItem *))))
63 {
64 fprintf (stderr, "out of virtual memory %s %d\n",
65 __FILE__, (size + 1) * (int) sizeof (hashtItem *));
66 exit (1);
67 }
68 htab->minKey = htab->size = size;
69 return htab;
70 }
71
72
73 void
hTabAddItemLong(hTab ** htab,int key,void * pkey,void * item)74 hTabAddItemLong (hTab ** htab, int key, void *pkey, void *item)
75 {
76 hashtItem *htip;
77 hashtItem *last;
78
79 if (!(*htab))
80 *htab = newHashTable (DEFAULT_HTAB_SIZE);
81
82 if (key > (*htab)->size)
83 {
84 int i;
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;
90 }
91
92 /* update the key */
93 if ((*htab)->maxKey < key)
94 (*htab)->maxKey = key;
95
96 if ((*htab)->minKey > key)
97 (*htab)->minKey = key;
98
99 /* create the item */
100 htip = _newHashtItem (key, pkey, item);
101
102 /* if there is a clash then goto end of chain */
103 if ((last = (*htab)->table[key]))
104 {
105 while (last->next)
106 last = last->next;
107 last->next = htip;
108 }
109 else
110 /* else just add it */
111 (*htab)->table[key] = htip;
112 (*htab)->nItems++;
113 }
114
115 /*-----------------------------------------------------------------*/
116 /* hTabAddItem - adds an item to the hash table */
117 /*-----------------------------------------------------------------*/
118 void
hTabAddItem(hTab ** htab,int key,void * item)119 hTabAddItem (hTab ** htab, int key, void *item)
120 {
121 hTabAddItemLong (htab, key, NULL, item);
122 }
123
124 /*-----------------------------------------------------------------*/
125 /* hTabDeleteItem - either delete an item */
126 /*-----------------------------------------------------------------*/
127 void
hTabDeleteItem(hTab ** htab,int key,const void * item,DELETE_ACTION action,int (* compareFunc)(const void *,const void *))128 hTabDeleteItem (hTab ** htab, int key,
129 const void *item, DELETE_ACTION action,
130 int (*compareFunc) (const void *, const void *))
131 {
132 hashtItem *htip, **htipp;
133
134 if (!(*htab))
135 return;
136
137 /* first check if anything exists in the slot */
138 if (!(*htab)->table[key])
139 return;
140
141 /* if delete chain */
142 if (action == DELETE_CHAIN)
143 (*htab)->table[key] = NULL;
144 else
145 {
146
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 */
150
151 htipp = &((*htab)->table[key]);
152 htip = (*htab)->table[key];
153 for (; htip; htip = htip->next)
154 {
155
156 if (compareFunc ? compareFunc (item, htip->item) :
157 (item == htip->item))
158 {
159 *htipp = htip->next;
160 break;
161 }
162
163 htipp = &(htip->next);
164 }
165
166 }
167
168 (*htab)->nItems--;
169
170 if (!(*htab)->nItems)
171 {
172 *htab = NULL;
173 }
174 }
175
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 /*-----------------------------------------------------------------*/
181 void
hTabDeleteAll(hTab * p)182 hTabDeleteAll (hTab * p)
183 {
184 if (p && p->table)
185 {
186 register int i;
187 register hashtItem *jc, *jn;
188 for (i = 0; i < p->size; i++)
189 {
190
191 if (!(jc = p->table[i]))
192 continue;
193 jn = jc->next;
194 while (jc)
195 {
196 Safe_free (jc);
197 if ((jc = jn))
198 jn = jc->next;
199 }
200 p->table[i] = NULL;
201 }
202 Safe_free (p->table);
203 }
204 }
205
206 /*-----------------------------------------------------------------*/
207 /* hTabClearAll - clear all entries in the table (does not free) */
208 /*-----------------------------------------------------------------*/
209 void
hTabClearAll(hTab * htab)210 hTabClearAll (hTab * htab)
211 {
212
213 if (!htab || !htab->table)
214 {
215 printf ("null table\n");
216 return;
217 }
218 memset (htab->table, 0, htab->size * sizeof (hashtItem *));
219
220 htab->minKey = htab->size;
221 htab->currKey = htab->nItems = htab->maxKey = 0;
222 }
223
224 static const hashtItem *
_findItem(hTab * htab,int key,void * item,int (* compareFunc)(void *,void *))225 _findItem (hTab * htab, int key, void *item, int (*compareFunc) (void *, void *))
226 {
227 hashtItem *htip;
228
229 for (htip = htab->table[key]; htip; htip = htip->next)
230 {
231 /* if a compare function is given use it */
232 if (compareFunc && compareFunc (item, htip->item))
233 break;
234 else if (item == htip->item)
235 break;
236 }
237 return htip;
238 }
239
240 static const hashtItem *
_findByKey(hTab * htab,int key,const void * pkey,int (* compare)(const void *,const void *))241 _findByKey (hTab * htab, int key, const void *pkey, int (*compare) (const void *, const void *))
242 {
243 hashtItem *htip;
244
245 assert (compare);
246
247 if (!htab)
248 return NULL;
249
250 for (htip = htab->table[key]; htip; htip = htip->next)
251 {
252 /* if a compare function is given use it */
253 if (compare && compare (pkey, htip->pkey))
254 {
255 break;
256 }
257 else
258 {
259 if (pkey == htip->pkey)
260 {
261 break;
262 }
263 }
264 }
265 return htip;
266 }
267
268 void *
hTabFindByKey(hTab * h,int key,const void * pkey,int (* compare)(const void *,const void *))269 hTabFindByKey (hTab * h, int key, const void *pkey, int (*compare) (const void *, const void *))
270 {
271 const hashtItem *item;
272
273 if ((item = _findByKey (h, key, pkey, compare)))
274 return item->item;
275 return NULL;
276 }
277
278 int
hTabDeleteByKey(hTab ** h,int key,const void * pkey,int (* compare)(const void *,const void *))279 hTabDeleteByKey (hTab ** h, int key, const void *pkey, int (*compare) (const void *, const void *))
280 {
281 hashtItem *htip, **htipp;
282 bool found = FALSE;
283
284 if (!(*h))
285 return 0;
286
287 /* first check if anything exists in the slot */
288 if (!(*h)->table[key])
289 return 0;
290
291 /* delete specific item */
292 /* if a compare function is given then use the compare */
293 /* function to find the item, else just compare the items */
294
295 htipp = &((*h)->table[key]);
296 htip = (*h)->table[key];
297 for (; htip; htip = htip->next)
298 {
299 if (
300 (compare && compare (pkey, htip->pkey)) ||
301 pkey == htip->pkey)
302 {
303 *htipp = htip->next;
304 found = TRUE;
305 break;
306 }
307 htipp = &(htip->next);
308 }
309
310 if (found == TRUE)
311 {
312 (*h)->nItems--;
313
314 if (!(*h)->nItems)
315 {
316 *h = NULL;
317 }
318 }
319
320 return 1;
321 }
322
323 /*-----------------------------------------------------------------*/
324 /* hTabIsInTable - will determine if an Item is in the hasht */
325 /*-----------------------------------------------------------------*/
326 int
hTabIsInTable(hTab * htab,int key,void * item,int (* compareFunc)(void *,void *))327 hTabIsInTable (hTab * htab, int key,
328 void *item, int (*compareFunc) (void *, void *))
329 {
330 if (_findItem (htab, key, item, compareFunc))
331 return 1;
332 return 0;
333 }
334
335 /*-----------------------------------------------------------------*/
336 /* hTabFirstItem - returns the first Item in the hTab */
337 /*-----------------------------------------------------------------*/
338 void *
hTabFirstItem(hTab * htab,int * k)339 hTabFirstItem (hTab * htab, int *k)
340 {
341 int key;
342
343 if (!htab)
344 return NULL;
345
346 for (key = htab->minKey; key <= htab->maxKey; key++)
347 {
348 if (htab->table[key])
349 {
350 htab->currItem = htab->table[key];
351 htab->currKey = key;
352 *k = key;
353 return htab->table[key]->item;
354 }
355 }
356 return NULL;
357 }
358
359 /*-----------------------------------------------------------------*/
360 /* hTabNextItem - returns the next item in the hTab */
361 /*-----------------------------------------------------------------*/
362 void *
hTabNextItem(hTab * htab,int * k)363 hTabNextItem (hTab * htab, int *k)
364 {
365 int key;
366
367 if (!htab)
368 return NULL;
369
370 /* if this chain not ended then */
371 if (htab->currItem->next)
372 {
373 *k = htab->currItem->key;
374 return (htab->currItem = htab->currItem->next)->item;
375 }
376
377 /* find the next chain which has something */
378 for (key = htab->currKey + 1; key <= htab->maxKey; key++)
379 {
380 if (htab->table[key])
381 {
382 htab->currItem = htab->table[key];
383 *k = htab->currKey = key;
384 return htab->table[key]->item;
385 }
386 }
387
388 return NULL;
389 }
390
391 /*-----------------------------------------------------------------*/
392 /* hTabFirstItemWK - returns the first Item in the hTab for a key */
393 /*-----------------------------------------------------------------*/
394 void *
hTabFirstItemWK(hTab * htab,int wk)395 hTabFirstItemWK (hTab * htab, int wk)
396 {
397
398 if (!htab)
399 return NULL;
400
401 if (wk < htab->minKey || wk > htab->maxKey)
402 return NULL;
403
404 htab->currItem = htab->table[wk];
405 htab->currKey = wk;
406
407 return (htab->table[wk] ? htab->table[wk]->item : NULL);
408 }
409
410 /*-----------------------------------------------------------------*/
411 /* hTabNextItem - returns the next item in the hTab for a key */
412 /*-----------------------------------------------------------------*/
413 void *
hTabNextItemWK(hTab * htab)414 hTabNextItemWK (hTab * htab)
415 {
416
417 if (!htab)
418 return NULL;
419
420 /* if this chain not ended then */
421 if (htab->currItem->next)
422 {
423 return (htab->currItem = htab->currItem->next)->item;
424 }
425
426 return NULL;
427 }
428
429 /*-----------------------------------------------------------------*/
430 /* hTabFromTable - hash Table from a hash table */
431 /*-----------------------------------------------------------------*/
432 hTab *
hTabFromTable(hTab * htab)433 hTabFromTable (hTab * htab)
434 {
435 hTab *nhtab;
436 hashtItem *htip;
437 int key;
438
439 if (!htab)
440 return NULL;
441
442 nhtab = newHashTable (htab->size);
443
444 for (key = htab->minKey; key <= htab->maxKey; key++)
445 {
446
447 for (htip = htab->table[key]; htip; htip = htip->next)
448 hTabAddItem (&nhtab, htip->key, htip->item);
449 }
450
451 return nhtab;
452 }
453
454 /*-----------------------------------------------------------------*/
455 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2 */
456 /*-----------------------------------------------------------------*/
457 int
isHtabsEqual(hTab * htab1,hTab * htab2,int (* compareFunc)(void *,void *))458 isHtabsEqual (hTab * htab1, hTab * htab2,
459 int (*compareFunc) (void *, void *))
460 {
461 void *item;
462 int key;
463
464 if (htab1 == htab2)
465 return 1;
466
467 if (htab1 == NULL || htab2 == NULL)
468 return 0;
469
470 /* if they are different sizes then */
471 if (htab1->nItems != htab2->nItems)
472 return 0;
473
474 /* now do an item by item check */
475 for (item = hTabFirstItem (htab1, &key); item;
476 item = hTabNextItem (htab1, &key))
477 if (!hTabIsInTable (htab2, key, item, compareFunc))
478 return 0;
479
480 return 1;
481 }
482
483
484 /*-----------------------------------------------------------------*/
485 /* hTabSearch - returns the first Item with the specified key */
486 /*-----------------------------------------------------------------*/
487 hashtItem *
hTabSearch(hTab * htab,int key)488 hTabSearch (hTab * htab, int key)
489 {
490 if (!htab)
491 return NULL;
492
493 if ((key < htab->minKey) || (key > htab->maxKey))
494 return NULL;
495
496 if (!htab->table[key])
497 return NULL;
498
499 return htab->table[key];
500 }
501
502 /*-----------------------------------------------------------------*/
503 /* hTabItemWithKey - returns the first item with the given key */
504 /*-----------------------------------------------------------------*/
505 void *
hTabItemWithKey(hTab * htab,int key)506 hTabItemWithKey (hTab * htab, int key)
507 {
508 hashtItem *htip;
509
510 if (!(htip = hTabSearch (htab, key)))
511 return NULL;
512
513 return htip->item;
514 }
515
516 /*-----------------------------------------------------------------*/
517 /* hTabMaxKey - return the maxKey of item in the hashTable */
518 /*-----------------------------------------------------------------*/
hTabMaxKey(hTab * htab)519 int hTabMaxKey (hTab *htab)
520 {
521 return (htab ? htab->maxKey : 0);
522 }
523
524 /*-----------------------------------------------------------------*/
525 /*hTabAddItemIfNotP - adds an item with nothing found with key */
526 /*-----------------------------------------------------------------*/
527 void
hTabAddItemIfNotP(hTab ** htab,int key,void * item)528 hTabAddItemIfNotP (hTab ** htab, int key, void *item)
529 {
530 if (!*htab)
531 {
532 hTabAddItem (htab, key, item);
533 return;
534 }
535
536 if (hTabItemWithKey (*htab, key))
537 return;
538
539 hTabAddItem (htab, key, item);
540 }
541
542 /** Simple implementation of a hash table which uses
543 string (key, value) pairs. If a key already exists in the
544 table, the newly added value will replace it.
545 This is used for the assembler token table. The replace existing
546 condition is used to implement inheritance.
547 */
548 static int
_compare(const void * s1,const void * s2)549 _compare (const void *s1, const void *s2)
550 {
551 return !strcmp (s1, s2);
552 }
553
554 static int
_hash(const char * sz)555 _hash (const char *sz)
556 {
557 /* Dumb for now */
558 return *sz;
559 }
560
561 void
shash_add(hTab ** h,const char * szKey,const char * szValue)562 shash_add (hTab ** h, const char *szKey, const char *szValue)
563 {
564 char *val;
565 int key = _hash (szKey);
566
567 /* Find value of the item */
568 val = (char *)hTabFindByKey(*h, key, szKey, _compare);
569 /* Delete any that currently exist */
570 hTabDeleteByKey(h, key, szKey, _compare);
571 /* Deallocate old value in not NULL */
572 if (val != NULL)
573 Safe_free(val);
574 /* Duplicate new value if not NULL */
575 if (szValue != NULL)
576 szValue = Safe_strdup(szValue);
577 /* Now add in ours */
578 hTabAddItemLong (h, key, Safe_strdup (szKey), (void *)szValue);
579 }
580
581 const char *
shash_find(hTab * h,const char * szKey)582 shash_find (hTab * h, const char *szKey)
583 {
584 int key = _hash (szKey);
585 return (char *) hTabFindByKey (h, key, szKey, _compare);
586 }
587