1 /*
2 ** HASH TABLE CLASS
3 **
4 ** This HashTable class implements a simple hash table to keep
5 ** objects associated with key words.
6 **
7 ** Author:
8 ** JP John Punin
9 **
10 */
11
12 #include "wwwsys.h"
13 #include "HTUtils.h"
14 #include "HTString.h"
15 #include "HTHash.h"
16
17 /*
18 (
19 Creation and Deletion Methods
20 )
21
22 These methods create and deletes a Hash Table
23 */
24
HTHashtable_new(int size)25 PUBLIC HTHashtable * HTHashtable_new (int size)
26 {
27 HTHashtable *newHashtable;
28 int c = size > 0 ? size : HT_L_HASH_SIZE;
29 if ((newHashtable = (HTHashtable *) HT_CALLOC(1, sizeof (HTHashtable))) == NULL)
30 HT_OUTOFMEM("HTHashtable_new");
31
32 if((newHashtable->table = (void **) HT_CALLOC(c, sizeof (void *))) == NULL)
33 HT_OUTOFMEM("HTHashtable_new");
34
35 newHashtable->count = 0;
36 newHashtable->size = c;
37 return newHashtable;
38 }
39
HTHashtable_delete(HTHashtable * me)40 PUBLIC BOOL HTHashtable_delete (HTHashtable *me)
41 {
42 if (me) {
43 int i;
44 for(i = 0; i< me->size; i++) {
45 HTList * l = (HTList *)me->table[i];
46 if (l) {
47 HTList *cur = l;
48 keynode *kn;
49 while ((kn = (keynode *) HTList_nextObject(cur))) {
50 HT_FREE(kn->key);
51 HT_FREE(kn);
52 }
53 HTList_delete(l);
54 }
55 }
56 HT_FREE(me->table);
57 HT_FREE(me);
58 return YES;
59 }
60 return NO;
61 }
62
hash_number(const char * key,int size)63 PRIVATE int hash_number (const char *key, int size)
64 {
65 int hash = 0;
66
67 if (key) {
68 const char * ptr = key;
69 for(; *ptr; ptr++)
70 hash = (int) ((hash*3 + (*(unsigned char*)ptr)) % size);
71 }
72 return hash;
73 }
74
75 /*
76 (
77 Add an Element to a HashTable
78 )
79 */
80
HTHashtable_addObject(HTHashtable * me,const char * key,void * newObject)81 PUBLIC BOOL HTHashtable_addObject (HTHashtable *me, const char *key,
82 void *newObject)
83 {
84 if(me) {
85 int size = me->size;
86 int i = hash_number(key,size);
87 HTList *l = (HTList *)me->table[i];
88 keynode *kn;
89 if(!l)
90 l = me->table[i] = HTList_new();
91 if ((kn = (keynode *) HT_CALLOC(1, sizeof (keynode))) == NULL)
92 HT_OUTOFMEM("HTHashtable_addObject");
93 StrAllocCopy(kn->key,key);
94 kn->object = newObject;
95 HTList_addObject(l,kn);
96 me->count++;
97 return YES;
98 }
99 return NO;
100 }
101
102 /*
103 (
104 Remove an Element from the HashTable
105 )
106 */
107
HTHashtable_removeObject(HTHashtable * me,const char * key)108 PUBLIC BOOL HTHashtable_removeObject (HTHashtable *me, const char *key)
109 {
110 if(me) {
111 int size = me->size;
112 int i = hash_number(key,size);
113 HTList *l = (HTList *)me->table[i];
114 if(l) {
115 HTList *cur = l;
116 keynode *kn;
117 while ((kn = (keynode *) HTList_nextObject(cur))) {
118 if(!strcmp(key,kn->key)) {
119 HTList_removeObject(l,kn);
120 me->count--;
121 return YES;
122 }
123 }
124 }
125 }
126 return NO;
127 }
128
129 /*
130 (
131 Search for an Element in a Hash Table
132 )
133 */
134
HTHashtable_object(HTHashtable * me,const char * key)135 PUBLIC void *HTHashtable_object (HTHashtable * me, const char *key)
136 {
137 if(me) {
138 int size = me->size;
139 int i = hash_number(key,size);
140 HTList * l = (HTList *)me->table[i];
141 if (l) {
142 HTList *cur = l;
143 keynode *kn;
144 while ((kn = (keynode *) HTList_nextObject(cur))) {
145 if(!strcmp(key,kn->key))
146 return kn->object;
147 }
148 }
149 }
150 return NULL;
151 }
152
153 /*
154 (
155 Size of a Hash Table
156 )
157 */
158
HTHashtable_count(HTHashtable * me)159 PUBLIC int HTHashtable_count (HTHashtable *me)
160 {
161 if(me)
162 return me->count;
163 return -1;
164 }
165
166 /*
167 (
168 Walk all Elements in the HashTable
169 )
170 */
171
HTHashtable_walk(HTHashtable * me,int (* walkFunc)(HTHashtable *,char *,void *))172 PUBLIC BOOL HTHashtable_walk (HTHashtable *me,
173 int (*walkFunc)(HTHashtable *,char *, void *))
174 {
175 if(me) {
176 int i, j;
177 for(i = 0; i< me->size; i++) {
178 HTList *l = (HTList *)me->table[i];
179 if(l) {
180 HTList *cur = l;
181 keynode *kn, *nextkn;
182 for(kn = (keynode *)HTList_nextObject(cur); kn; kn = nextkn) {
183 j = walkFunc(me, kn->key, kn->object);
184 if(j == 0)
185 return YES;
186 nextkn = (keynode *)HTList_nextObject(cur);
187 if (j < 0) {
188 HTList_removeObject(l, kn);
189 me->count--;
190 }
191 }
192 }
193 }
194 return YES;
195 }
196 return NO;
197 }
198
199 /*
200 (
201 Extract in a dynamic array all keys of the Hash Table
202 )
203 */
204
HTHashtable_keys(HTHashtable * me)205 PUBLIC HTArray * HTHashtable_keys (HTHashtable *me)
206 {
207 if(me) {
208 HTArray *keys = HTArray_new(me->count);
209 int i;
210
211 for(i = 0; i< me->size; i++) {
212 HTList * l = (HTList *)me->table[i];
213 if (l) {
214 HTList *cur = l;
215 keynode *kn;
216 while ((kn = (keynode *) HTList_nextObject(cur))) {
217 char * nkey = NULL;
218 StrAllocCopy(nkey,kn->key);
219 HTArray_addObject(keys,nkey);
220 }
221 }
222 }
223 return keys;
224 }
225 return NULL;
226 }
227
228 /*
229 (
230 Print the keys of the Hash Table
231 )
232 */
233
HTHashtable_print(HTHashtable * me)234 PUBLIC void HTHashtable_print (HTHashtable *me)
235 {
236 HTArray *keys = HTHashtable_keys(me);
237 int i;
238 HTPrint("Printing Hash Table of size %d\n", HTArray_size(keys));
239 for(i = 0; i< HTArray_size(keys); i++) {
240 HTPrint("Key %d %s\n",i,HTArray_data(keys)[i]);
241 }
242 for(i = 0; i< HTArray_size(keys); i++) {
243 HT_FREE(HTArray_data(keys)[i]);
244 }
245 HTArray_delete(keys);
246 }
247
248