4 * Hash table handling for strings
6 * © 1994-1998 Straylight
9 /*----- Licensing note ----------------------------------------------------*
11 * This file is part of Straylight's Dynamic Linking System (SDLS)
13 * SDLS is free software; you can redistribute it and/or modify
14 * it under the terms of the GNU General Public License as published by
15 * the Free Software Foundation; either version 2, or (at your option)
18 * SDLS is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 * GNU General Public License for more details.
23 * You should have received a copy of the GNU General Public License
24 * along with SDLS. If not, write to the Free Software Foundation,
25 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
32 #include "hashtable.h"
35 /*----- Constants ---------------------------------------------------------*/
37 #define hash__SIZE 512 /* A respectable size table */
38 /* Note: must be power of 2 */
40 /*----- Some good ol' data structures -------------------------------------*/
42 typedef struct hash__link
44 struct hash__link *next; /* Link in hash table bucket */
45 struct hash__link *left; /* Link in ordinal tree */
46 struct hash__link *right; /* Link in ordinal tree */
47 unsigned int ord; /* Ordinal value */
48 char string[1]; /* String (unsized array) */
52 typedef struct hash__table
54 hash__link *tbl[hash__SIZE]; /* The actual hash table */
55 hash__link *root; /* The ordinal tree root */
59 /*----- Private code ------------------------------------------------------*/
61 #define hash__hash(s) (crc32(0,s,strlen(s),1) & (hash__SIZE - 1))
63 static int hash__addToTree(hash__link **root,hash__link *l)
67 if ((*root)->ord > l->ord)
68 return (hash__addToTree(&(*root)->left,l));
69 else if ((*root)->ord < l->ord || l->ord == 0xFFFFFFFF)
70 return (hash__addToTree(&(*root)->right,l));
81 static void hash__traverse(hash__link *l,
82 void (*func)(char *string,
89 hash__traverse(l->left,func,handle);
90 func(l->string,l->ord,handle);
91 hash__traverse(l->right,func,handle);
95 static void hash__dump(char *string,unsigned int ord,void *handle)
98 printf(" ** %s (%08x)\n",string,ord);
101 /*----- Public code -------------------------------------------------------*/
103 hashtable hash_create(void)
105 return (calloc(1,sizeof(hash__table)));
108 int hash_find(hashtable h,char *string)
110 int sh=hash__hash(string);
112 for (l=h->tbl[sh];l;l=l->next)
114 if (!strcmp(l->string,string))
120 int hash_add(hashtable h,char *string)
122 return (hash_addWithOrd(h,string,0xFFFFFFFF));
125 int hash_addWithOrd(hashtable h,char *string,unsigned int ord)
127 int sh=hash__hash(string);
129 if (hash_find(h,string))
131 if (l=malloc(sizeof(hash__link)+strlen(string)),!l)
133 strcpy(l->string,string);
138 if (hash__addToTree(&h->root,l))
141 hash__addToTree(&h->root,l);
146 void hash_delete(hashtable h)
151 for (i=0;i<hash__SIZE;i++)
153 for (l=h->tbl[i];l;l=n)
162 int hash_subset(hashtable super,
164 void (*proc)(char *p))
169 for (i=0;i<hash__SIZE;i++)
171 for (l=sub->tbl[i];l;l=l->next)
173 if (!hash_find(super,l->string))
183 void hash_dump(hashtable h)
185 hash_enumOrdered(h,hash__dump,0);
187 void hash_enumerate(hashtable h,
188 void (*func)(char *string,void *handle),
193 for (i=0;i<hash__SIZE;i++)
195 for (l=h->tbl[i];l;l=l->next)
196 func(l->string,handle);
200 void hash_enumOrdered(hashtable h,
201 void (*func)(char *string,
206 hash__traverse(h->root,func,handle);
209 int hash_count(hashtable h)
214 for (i=0;i<hash__SIZE;i++)
216 for (l=h->tbl[i];l;l=l->next)