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 -------------------------------------------------------------------------*/
28 #include "SDCChasht.h"
31 #define DEFAULT_HTAB_SIZE 128
33 /*-----------------------------------------------------------------*/
34 /* newHashtItem - creates a new hashtable Item */
35 /*-----------------------------------------------------------------*/
36 hashtItem *newHashtItem (int key, void *item)
40 ALLOC(htip,sizeof(hashtItem));
48 /*-----------------------------------------------------------------*/
49 /* newHashTable - allocates a new hashtable of size */
50 /*-----------------------------------------------------------------*/
51 hTab *newHashTable (int size)
55 ALLOC(htab,sizeof(hTab));
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 *));
62 htab->minKey = htab->size = size ;
67 /*-----------------------------------------------------------------*/
68 /* hTabAddItem - adds an item to the hash table */
69 /*-----------------------------------------------------------------*/
70 void hTabAddItem (hTab **htab, int key, void *item )
76 *htab = newHashTable ( DEFAULT_HTAB_SIZE );
78 if (key > (*htab)->size ) {
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;
88 if ((*htab)->maxKey < key )
89 (*htab)->maxKey = key ;
91 if ((*htab)->minKey > key )
92 (*htab)->minKey = key ;
95 htip = newHashtItem (key,item);
97 /* if there is a clash then goto end of chain */
98 if ((last = (*htab)->table[key])) {
103 /* else just add it */
104 (*htab)->table[key] = htip ;
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 *))
115 hashtItem *htip, **htipp ;
120 /* first check if anything exists in the slot */
121 if (! (*htab)->table[key] )
124 /* if delete chain */
125 if ( action == DELETE_CHAIN )
126 (*htab)->table[key] = NULL ;
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 */
133 htipp = &((*htab)->table[key]);
134 htip = (*htab)->table[key];
135 for (; htip; htip = htip->next) {
137 if (compareFunc ? (*compareFunc)(item,htip->item) :
138 (item == htip->item) ) {
151 if (!(*htab)->nItems) {
156 /*-----------------------------------------------------------------*/
157 /* hTabDeleteAll - deletes all items in a hash table to reduce mem */
158 /* leaks written by */
159 /* "BESSIERE Jerome" <BESSIERE_Jerome@stna.dgac.fr> */
160 /*-----------------------------------------------------------------*/
161 void hTabDeleteAll(hTab * p)
165 register hashtItem *jc,*jn;
166 for (i=0;i<p->size;i++) {
168 if (!(jc = p->table[i])) continue;
172 if((jc=jn)) jn = jc->next;
180 /*-----------------------------------------------------------------*/
181 /* hTabClearAll - clear all entries inthe table (does not free) */
182 /*-----------------------------------------------------------------*/
183 void hTabClearAll (hTab *htab)
186 if (!htab || !htab->table) {
187 printf("null table\n");
190 memset(htab->table, 0, htab->size*sizeof(hashtItem *));
192 htab->minKey = htab->size;
193 htab->currKey = htab->nItems = htab->maxKey = 0;
196 /*-----------------------------------------------------------------*/
197 /* hTabIsInTable - will determine if an Item is in the hasht */
198 /*-----------------------------------------------------------------*/
199 int hTabIsInTable (hTab *htab, int key,
200 void *item , int (*compareFunc)(void *,void *))
204 for (htip = htab->table[key] ; htip ; htip = htip->next ) {
205 /* if a compare function is given use it */
206 if (compareFunc && (*compareFunc)(item,htip->item))
209 if (item == htip->item)
218 /*-----------------------------------------------------------------*/
219 /* hTabFirstItem - returns the first Item in the hTab */
220 /*-----------------------------------------------------------------*/
221 void *hTabFirstItem (hTab *htab, int *k)
228 for ( key = htab->minKey ; key <= htab->maxKey ; key++ ) {
229 if (htab->table[key]) {
230 htab->currItem = htab->table[key];
231 htab->currKey = key ;
233 return htab->table[key]->item;
239 /*-----------------------------------------------------------------*/
240 /* hTabNextItem - returns the next item in the hTab */
241 /*-----------------------------------------------------------------*/
242 void *hTabNextItem (hTab *htab, int *k)
249 /* if this chain not ended then */
250 if (htab->currItem->next) {
251 *k = htab->currItem->key ;
252 return (htab->currItem = htab->currItem->next)->item ;
255 /* find the next chain which has something */
256 for ( key = htab->currKey + 1; key <= htab->maxKey ; key++ ) {
257 if (htab->table[key]) {
258 htab->currItem = htab->table[key];
259 *k = htab->currKey = key ;
260 return htab->table[key]->item;
267 /*-----------------------------------------------------------------*/
268 /* hTabFirstItemWK - returns the first Item in the hTab for a key */
269 /*-----------------------------------------------------------------*/
270 void *hTabFirstItemWK (hTab *htab, int wk)
276 if (wk < htab->minKey || wk > htab->maxKey )
279 htab->currItem = htab->table[wk] ;
282 return (htab->table[wk] ? htab->table[wk]->item : NULL);
285 /*-----------------------------------------------------------------*/
286 /* hTabNextItem - returns the next item in the hTab for a key */
287 /*-----------------------------------------------------------------*/
288 void *hTabNextItemWK (hTab *htab )
294 /* if this chain not ended then */
295 if (htab->currItem->next) {
296 return (htab->currItem = htab->currItem->next)->item ;
302 /*-----------------------------------------------------------------*/
303 /* hTabFromTable - hash Table from a hash table */
304 /*-----------------------------------------------------------------*/
305 hTab *hTabFromTable (hTab *htab)
314 nhtab = newHashTable(htab->size);
316 for (key = htab->minKey; key <= htab->maxKey ; key++ ) {
318 for (htip = htab->table[key] ; htip ; htip = htip->next)
319 hTabAddItem (&nhtab, htip->key, htip->item);
325 /*-----------------------------------------------------------------*/
326 /* isHtabsEqual - returns 1 if all items in htab1 is found in htab2*/
327 /*-----------------------------------------------------------------*/
328 int isHtabsEqual (hTab *htab1, hTab *htab2,
329 int (*compareFunc)(void *,void *))
334 if ( htab1 == htab2 )
337 if (htab1 == NULL || htab2 == NULL )
340 /* if they are different sizes then */
341 if ( htab1->nItems != htab2->nItems)
344 /* now do an item by item check */
345 for ( item = hTabFirstItem (htab1,&key) ;item;
346 item = hTabNextItem (htab1,&key))
347 if (!hTabIsInTable (htab2, key, item, compareFunc))
354 /*-----------------------------------------------------------------*/
355 /* hTabSearch - returns the first Item with the specified key */
356 /*-----------------------------------------------------------------*/
357 hashtItem *hTabSearch (hTab *htab, int key )
362 if ((key < htab->minKey)||(key>htab->maxKey))
365 if (!htab->table[key])
368 return htab->table[key] ;
371 /*-----------------------------------------------------------------*/
372 /* hTabItemWithKey - returns the first item with the gievn key */
373 /*-----------------------------------------------------------------*/
374 void *hTabItemWithKey (hTab *htab, int key )
378 if (!(htip = hTabSearch(htab,key)))
384 /*-----------------------------------------------------------------*/
385 /*hTabAddItemIfNotP - adds an item with nothing found with key */
386 /*-----------------------------------------------------------------*/
387 void hTabAddItemIfNotP (hTab **htab, int key, void *item)
390 hTabAddItem (htab,key,item);
394 if (hTabItemWithKey(*htab,key))
397 hTabAddItem(htab,key,item);