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 -------------------------------------------------------------------------*/
27 #define DEFAULT_HTAB_SIZE 128
29 /*-----------------------------------------------------------------*/
30 /* newHashtItem - creates a new hashtable Item */
31 /*-----------------------------------------------------------------*/
32 hashtItem *newHashtItem (int key, void *item)
36 ALLOC(htip,sizeof(hashtItem));
44 /*-----------------------------------------------------------------*/
45 /* newHashTable - allocates a new hashtable of size */
46 /*-----------------------------------------------------------------*/
47 hTab *newHashTable (int size)
51 ALLOC(htab,sizeof(hTab));
53 if (!(htab->table = GC_malloc((size +1)* sizeof(hashtItem *)))) {
54 fprintf(stderr,"out of virtual memory %s %d\n",
55 __FILE__,(size +1)* sizeof(hashtItem *));
58 htab->minKey = htab->size = size ;
63 /*-----------------------------------------------------------------*/
64 /* hTabAddItem - adds an item to the hash table */
65 /*-----------------------------------------------------------------*/
66 void hTabAddItem (hTab **htab, int key, void *item )
72 *htab = newHashTable ( DEFAULT_HTAB_SIZE );
74 if (key > (*htab)->size ) {
76 (*htab)->table = GC_realloc ((*htab)->table,
77 (key*2 + 2)*sizeof(hashtItem *));
78 for ( i = (*htab)->size +1; i <= (key*2 + 1); i++ )
79 (*htab)->table[i] = NULL ;
80 (*htab)->size = key*2 + 1;
84 if ((*htab)->maxKey < key )
85 (*htab)->maxKey = key ;
87 if ((*htab)->minKey > key )
88 (*htab)->minKey = key ;
91 htip = newHashtItem (key,item);
93 /* if there is a clash then goto end of chain */
94 if ((last = (*htab)->table[key])) {
99 /* else just add it */
100 (*htab)->table[key] = htip ;
104 /*-----------------------------------------------------------------*/
105 /* hTabDeleteItem - either delete an item */
106 /*-----------------------------------------------------------------*/
107 void hTabDeleteItem (hTab **htab, int key ,
108 void *item, int action ,
109 int (*compareFunc)(void *,void *))
111 hashtItem *htip, **htipp ;
116 /* first check if anything exists in the slot */
117 if (! (*htab)->table[key] )
120 /* if delete chain */
121 if ( action == DELETE_CHAIN )
122 (*htab)->table[key] = NULL ;
125 /* delete specific item */
126 /* if a compare function is given then use the compare */
127 /* function to find the item, else just compare the items */
129 htipp = &((*htab)->table[key]);
130 htip = (*htab)->table[key];
131 for (; htip; htip = htip->next) {
133 if (compareFunc ? (*compareFunc)(item,htip->item) :
134 (item == htip->item) ) {
147 if (!(*htab)->nItems) {
152 /*-----------------------------------------------------------------*/
153 /* hTabDeleteAll - deletes all items in a hash table to reduce mem */
154 /* leaks written by */
155 /* "BESSIERE Jerome" <BESSIERE_Jerome@stna.dgac.fr> */
156 /*-----------------------------------------------------------------*/
157 void hTabDeleteAll(hTab * p)
161 register hashtItem *jc,*jn;
162 for (i=0;i<p->size;i++) {
164 if (!(jc = p->table[i])) continue;
168 if((jc=jn)) jn = jc->next;
176 /*-----------------------------------------------------------------*/
177 /* hTabClearAll - clear all entries inthe table (does not free) */
178 /*-----------------------------------------------------------------*/
179 void hTabClearAll (hTab *htab)
182 if (!htab || !htab->table) {
183 printf("null table\n");
186 memset(htab->table, 0, htab->size*sizeof(hashtItem *));
188 htab->minKey = htab->size;
189 htab->currKey = htab->nItems = htab->maxKey = 0;
192 /*-----------------------------------------------------------------*/
193 /* hTabIsInTable - will determine if an Item is in the hasht */
194 /*-----------------------------------------------------------------*/
195 int hTabIsInTable (hTab *htab, int key,
196 void *item , int (*compareFunc)(void *,void *))
200 for (htip = htab->table[key] ; htip ; htip = htip->next ) {
201 /* if a compare function is given use it */
202 if (compareFunc && (*compareFunc)(item,htip->item))
205 if (item == htip->item)
214 /*-----------------------------------------------------------------*/
215 /* hTabFirstItem - returns the first Item in the hTab */
216 /*-----------------------------------------------------------------*/
217 void *hTabFirstItem (hTab *htab, int *k)
224 for ( key = htab->minKey ; key <= htab->maxKey ; key++ ) {
225 if (htab->table[key]) {
226 htab->currItem = htab->table[key];
227 htab->currKey = key ;
229 return htab->table[key]->item;
235 /*-----------------------------------------------------------------*/
236 /* hTabNextItem - returns the next item in the hTab */
237 /*-----------------------------------------------------------------*/
238 void *hTabNextItem (hTab *htab, int *k)
245 /* if this chain not ended then */
246 if (htab->currItem->next) {
247 *k = htab->currItem->key ;
248 return (htab->currItem = htab->currItem->next)->item ;
251 /* find the next chain which has something */
252 for ( key = htab->currKey + 1; key <= htab->maxKey ; key++ ) {
253 if (htab->table[key]) {
254 htab->currItem = htab->table[key];
255 *k = htab->currKey = key ;
256 return htab->table[key]->item;
263 /*-----------------------------------------------------------------*/
264 /* hTabFirstItemWK - returns the first Item in the hTab for a key */
265 /*-----------------------------------------------------------------*/
266 void *hTabFirstItemWK (hTab *htab, int wk)
272 if (wk < htab->minKey || wk > htab->maxKey )
275 htab->currItem = htab->table[wk] ;
278 return (htab->table[wk] ? htab->table[wk]->item : NULL);
281 /*-----------------------------------------------------------------*/
282 /* hTabNextItem - returns the next item in the hTab for a key */
283 /*-----------------------------------------------------------------*/
284 void *hTabNextItemWK (hTab *htab )
290 /* if this chain not ended then */
291 if (htab->currItem->next) {
292 return (htab->currItem = htab->currItem->next)->item ;
298 /*-----------------------------------------------------------------*/
299 /* hTabFromTable - hash Table from a hash table */
300 /*-----------------------------------------------------------------*/
301 hTab *hTabFromTable (hTab *htab)
310 nhtab = newHashTable(htab->size);
312 for (key = htab->minKey; key <= htab->maxKey ; key++ ) {
314 for (htip = htab->table[key] ; htip ; htip = htip->next)
315 hTabAddItem (&nhtab, htip->key, htip->item);
321 /*-----------------------------------------------------------------*/
322 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2*/
323 /*-----------------------------------------------------------------*/
324 int isHtabsEqual (hTab *htab1, hTab *htab2,
325 int (*compareFunc)(void *,void *))
330 if ( htab1 == htab2 )
333 if (htab1 == NULL || htab2 == NULL )
336 /* if they are different sizes then */
337 if ( htab1->nItems != htab2->nItems)
340 /* now do an item by item check */
341 for ( item = hTabFirstItem (htab1,&key) ;item;
342 item = hTabNextItem (htab1,&key))
343 if (!hTabIsInTable (htab2, key, item, compareFunc))
350 /*-----------------------------------------------------------------*/
351 /* hTabSearch - returns the first Item with the specified key */
352 /*-----------------------------------------------------------------*/
353 hashtItem *hTabSearch (hTab *htab, int key )
358 if ((key < htab->minKey)||(key>htab->maxKey))
361 if (!htab->table[key])
364 return htab->table[key] ;
367 /*-----------------------------------------------------------------*/
368 /* hTabItemWithKey - returns the first item with the gievn key */
369 /*-----------------------------------------------------------------*/
370 void *hTabItemWithKey (hTab *htab, int key )
374 if (!(htip = hTabSearch(htab,key)))
380 /*-----------------------------------------------------------------*/
381 /*hTabAddItemIfNotP - adds an item with nothing found with key */
382 /*-----------------------------------------------------------------*/
383 void hTabAddItemIfNotP (hTab **htab, int key, void *item)
386 hTabAddItem (htab,key,item);
390 if (hTabItemWithKey(*htab,key))
393 hTabAddItem(htab,key,item);