1 #include "system.h"
2 #include "hash.h"
3 #include "util.h"
4
5 #include <stdlib.h>
6 #include <stdio.h>
7 #include <stdarg.h>
8 #include <string.h>
9
10 /* This is the guts of it right here. This is how we convert from a string
11 * into a number. This will always return a number < BUCKETS, since we
12 * modulo it
13 */
14
15 u_int32_t
hash(const char * const str)16 hash(const char * const str)
17 {
18 register const char *s_key = str;
19 register u_int32_t i_key = strlen(s_key);
20 register u_int32_t h_key = 0;
21
22 while(i_key--) {
23 h_key += *s_key++;
24 h_key += (h_key << 10);
25 h_key ^= (h_key >> 6);
26 }
27 h_key += (h_key << 3);
28 h_key ^= (h_key >> 11);
29 lj_debug(3, "[%s] belongs in bucket [%d]\n", str,
30 (h_key += (h_key << 15)) % BUCKETS);
31 return (h_key += (h_key << 15)) % BUCKETS;
32 }
33
34 /* The rest is fairly simple. In create_hash we allocate the memory, and
35 * initialize all the pointers to NULL.
36 */
37
38 int
create_hash(hashtable ** ht)39 create_hash(hashtable ** ht)
40 {
41 int i;
42
43 *ht = (hashtable *) lj_malloc(sizeof(hashtable));
44 for(i = 0; i < BUCKETS; i++) {
45 (*ht)->bucket[i] = (keypair *) NULL;
46 }
47 (*ht)->i_bucket = 0;
48 (*ht)->p_next = (keypair *) NULL;
49 return 0;
50 }
51
52 /* Here we just free all of the keypairs, then free the hash itself */
53
54 int
delete_hash(hashtable * ht)55 delete_hash(hashtable * ht)
56 {
57 keypair *i_pair = (keypair *) NULL;
58
59 reset(ht);
60 lj_debug(3, "Freeing keypairs...");
61 while((i_pair = next(ht))) {
62 del(ht, i_pair->key);
63 }
64 lj_debug(3, "Freeing hashtable [%p]", ht);
65 lj_free(ht);
66 lj_debug(3, "success");
67 return 0;
68 }
69
70 /* Putting is fairly simple we simply insert into the ordered linked list
71 * that is located in the bucket that hash() tells us to use.
72 */
73
74 int
put(hashtable * ht,const char * const key,const char * const value)75 put(hashtable * ht, const char * const key, const char * const value)
76 {
77 keypair *p_prev, *p_next, *p_new, **pp_head;
78 int bucket = hash(key);
79
80 if (!ht || !key || !value)
81 {
82 lj_debug(1, "No keypair to insert");
83 return 1;
84 }
85
86 p_prev = p_next = p_new = (keypair *) NULL;
87
88 p_new = (keypair *) lj_malloc(sizeof(keypair));
89 lj_debug(3, "New keypair [%p]\n", p_new);
90 p_new->key = strdup(key);
91 lj_debug(3, "\tkey [%p/%s]\n", p_new->key, p_new->key);
92 p_new->value = strdup(value);
93 lj_debug(3, "\tvalue [%p/%s]\n", p_new->value, p_new->value);
94 pp_head = &(ht->bucket[bucket]);
95 p_next = *pp_head;
96 while(p_next && (strcmp(p_new->key, p_next->key) > 0)) {
97 p_prev = p_next;
98 p_next = p_prev->p_next;
99 }
100
101 p_new->p_prev = p_prev;
102 if(p_prev) {
103 p_prev->p_next = p_new;
104 } else {
105 *pp_head = p_new;
106 }
107
108 p_new->p_next = p_next;
109 if(p_next) {
110 p_next->p_prev = p_new;
111 }
112 lj_debug(3, "\tp_prev [%p/%s]\n\tp_next[%p/%s]\n",
113 p_prev, p_prev ? p_prev->key : "(nil)",
114 p_next, p_next ? p_next->key : "(nil)");
115
116
117 return 0;
118 }
119
120 /* Deleting is similarly straight forward. We just look in the bucket, and
121 * search until we find the proper item.
122 *
123 * Note: if there is no such key, it will still return 0.
124 */
125
126 int
del(hashtable * ht,char * key)127 del(hashtable * ht, char *key)
128 {
129 keypair *p_this, *p_prev, *p_next;
130 char *value;
131 int bucket = hash(key);
132
133 p_this = p_prev = p_next = (keypair *) NULL;
134
135 if(!(p_this = get(ht, &value, key)))
136 return 0;
137 lj_free(value);
138 p_prev = p_this->p_prev;
139 p_next = p_this->p_next;
140
141 lj_debug(3, "Deleting [%p/%s]\n", p_this, p_this->key);
142
143 lj_debug(3, "Adjusting pointers...");
144 if(p_prev) {
145 p_prev->p_next = p_next;
146 lj_debug(3, "p_prev[%p]->p_next[%p]\n", p_prev, p_prev->p_next);
147 } else if(p_this) {
148 ht->bucket[bucket] = p_this->p_next;
149 lj_debug(3, "bucket[%d]->[%p]\n", bucket, ht->bucket[bucket]);
150 }
151
152 if(p_next) {
153 p_next->p_prev = p_prev;
154 lj_debug(3, "p_next[%p]->p_prev[%p]", p_next, p_next->p_prev);
155 }
156 /*
157 * Most doubly linked lists have tail pointers. We don't, so we don't
158 * have to worry about that like we do with the head pointer.
159 */
160
161 lj_debug(3, "Freeing key [%p/%s]\n", p_this->key, p_this->key);
162 lj_free(p_this->key);
163 lj_debug(3, "Freeing value [%p/%s]\n", p_this->value, p_this->value);
164 lj_free(p_this->value);
165 lj_debug(3, "Freeing keypair [%p]\n", p_this);
166 lj_free(p_this);
167 return 0;
168 }
169
170 /* Getting is practically the same as deleting */
171
172 keypair *
getp(const hashtable * const ht,char ** value,const char * const key,...)173 getp(const hashtable * const ht, char **value, const char * const key, ...)
174 {
175 keypair *p_this = NULL;
176 char *buff = NULL;
177 int bucket;
178 va_list ap;
179
180 va_start(ap, key);
181 vasprintf(&buff, key, ap);
182 va_end(ap);
183 bucket = hash(buff);
184 p_this = ht->bucket[bucket];
185 while (p_this && p_this->p_next && strcmp(buff, p_this->key)) {
186 p_this = p_this->p_next;
187 }
188 if (!p_this || strcmp(p_this->key, buff)) {
189 free(buff);
190 *value = NULL;
191 return NULL;
192 }
193 lj_debug(3, "get(\"%s\") returning [%p][%s]->[%s]\n",
194 buff, p_this, p_this->key, p_this->value);
195 free(buff);
196 *value = strdup(p_this->value);
197 return p_this;
198 }
199
200 keypair *
get(const hashtable * const ht,char ** value,const char * const key)201 get(const hashtable * const ht, char **value, const char * const key)
202 {
203 return getp(ht, value, "%s", key);
204 }
205
206 keypair *
getpi(const hashtable * const ht,int * value,const char * const key,...)207 getpi(const hashtable * const ht, int *value, const char * const key, ...)
208 {
209 char *buff = NULL, *values = NULL;
210 keypair *kp;
211 va_list ap;
212
213 va_start(ap, key);
214 vasprintf(&buff, key, ap);
215 va_end(ap);
216
217 kp = get(ht, &values, buff);
218 free(buff);
219 if (values)
220 {
221 *value = atoi(values);
222 lj_free(values);
223 }
224 else
225 *value = 0;
226 return kp;
227 }
228
229 keypair *
geti(const hashtable * const ht,int * value,const char * const key)230 geti(const hashtable * const ht, int *value, const char * const key)
231 {
232 return getpi(ht, value, "%s", key);
233 }
234
235 /* The iterator is also very simple. It just has some more bookkeeping to
236 * handle. Remember that p_current is a pointer to a pointer.
237 */
238
239 keypair *
next(hashtable * ht)240 next(hashtable * ht)
241 {
242 keypair *p_next;
243
244 p_next = ht->p_next;
245
246 lj_debug(3, "ni_bucket=[%d]\np_next=[%p/%s]\n",
247 ht->i_bucket, p_next, p_next ? p_next->key : "");
248 if(p_next)
249 ht->p_next = p_next->p_next;
250 while(!ht->p_next && (ht->i_bucket < BUCKETS)) {
251 /* Here we are setting the pointer to the next item */
252 ht->i_bucket++;
253 ht->p_next = ht->bucket[ht->i_bucket];
254 }
255 lj_debug(3, "ht->p_next=[%p/%s] in bucket [%d]\n",
256 ht->p_next, ht->p_next ? (ht->p_next)->key : "", ht->i_bucket);
257 if(!p_next && ht->p_next)
258 p_next = next(ht);
259 return p_next;
260 }
261
262 /* The reset function just sets i_bucket and p_current back to 0 */
263 int
reset(hashtable * ht)264 reset(hashtable * ht)
265 {
266 ht->i_bucket = 0;
267 ht->p_next = ht->bucket[0];
268 return 0;
269 }
270
271 void
dumphash(const hashtable * const ht)272 dumphash(const hashtable * const ht)
273 {
274 int i;
275 keypair *p_next;
276
277 for(i = 0; i < BUCKETS; i++) {
278 if((p_next = ht->bucket[i])) {
279 printf("Bucket [%d]:\n", i);
280 while(p_next) {
281 printf("\tKeypair at [%p]\n\t key [%p][%s]\n\t value [%p][%s]\n",
282 p_next, p_next->key, p_next->key,
283 p_next->value, p_next->value);
284 printf("\t p_prev [%p][%s]\n\t p_next [%p][%s]\n",
285 p_next->p_prev,
286 p_next->p_prev ? (p_next->p_prev)->key : "(nil)",
287 p_next->p_next,
288 p_next->p_next ? (p_next->p_next)->key : "(nil)");
289 p_next = p_next->p_next;
290 }
291 }
292 }
293 }
294