1 /*
2 ** HASH: Simple hash table implementation.
3 ** Copyright (C) 2002 Michael W. Shaffer <mwshaffer@angrypot.com>
4 **
5 ** This program is free software; you can redistribute it and/or modify
6 ** it under the terms of the GNU General Public License as published by
7 ** the Free Software Foundation; either version 2 of the License, or
8 ** (at your option) any later version.
9 **
10 ** This program is distributed in the hope that it will be useful,
11 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
12 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 ** GNU General Public License for more details.
14 **
15 ** You should have received a copy of the GNU General Public License
16 ** along with this program (see the file COPYING). If not, write to:
17 **
18 ** The Free Software Foundation, Inc.
19 ** 59 Temple Place, Suite 330,
20 ** Boston, MA 02111-1307 USA
21 */
22
23 #include <stdlib.h>
24 #include "primes.h"
25 #include "list.h"
26 #include "hash.h"
27
28 /* Peter J. Wienberger's hash */
hash_pjw(char * value)29 static unsigned long hash_pjw (char *value)
30 {
31 unsigned long h = 0;
32 unsigned long g = 0;
33
34 while (*value) {
35 h = (h << 4) + *(value++);
36 if ((g = h & 0xF0000000))
37 h ^= g >> 24;
38 h &= ~g;
39 }
40 return h;
41 }
42
hash_table_init(struct hash_table * h)43 void hash_table_init (struct hash_table *h)
44 {
45 int i = 0;
46
47 if (!h)
48 return;
49
50 if (h->size < 1)
51 h->size = 100;
52
53 h->size = find_prime (h->size);
54 h->tbl = (struct list *) malloc (h->size * (sizeof (struct list)));
55 if (!h->tbl)
56 return;
57 memset (h->tbl, 0, (h->size * sizeof (struct list)));
58
59 for (i = 0 ; i < h->size ; i++) {
60 list_init (&(h->tbl[i]));
61 }
62
63 return;
64 }
65
hash_table_free(struct hash_table * h)66 void hash_table_free (struct hash_table *h)
67 {
68 int i = 0;
69 struct datum *d = NULL;
70 struct list_item *curr = NULL;
71
72 if (!h)
73 return;
74
75 for (i = 0 ; i < h->size ; i++) {
76 for (curr = h->tbl[i].head ; curr ; curr = curr->next) {
77 if (curr->data) {
78 d = (struct datum *) curr->data;
79 if (d->key)
80 free (d->key);
81 if (d->val)
82 free (d->val);
83 }
84 }
85 list_free (&(h->tbl[i]));
86 }
87
88 if (h->tbl)
89 free (h->tbl);
90
91 h->size = 0;
92 h->tbl = NULL;
93
94 return;
95 }
96
hash_table_insert(struct hash_table * h,struct datum * d)97 struct datum *hash_table_insert (struct hash_table *h, struct datum *d)
98 {
99 int slot = 0;
100 struct datum *new = NULL;
101 struct list_item *item = NULL;
102
103 if (!(d && h && (h->size > 0) && h->tbl))
104 return NULL;
105
106 new = (struct datum *) malloc (sizeof (struct datum));
107 if (!new)
108 goto ERROR;
109 memset (new, 0, (sizeof (struct datum)));
110
111 new->ksize = d->ksize;
112 new->key = (void *) malloc (new->ksize + 1);
113 if (!new->key)
114 goto ERROR;
115 memset (new->key, 0, (new->ksize + 1));
116 memcpy (new->key, d->key, new->ksize);
117
118 new->vsize = d->vsize;
119 new->val = (void *) malloc (new->vsize + 1);
120 if (!new->val)
121 goto ERROR;
122 memset (new->val, 0, (new->vsize + 1));
123 memcpy (new->val, d->val, new->vsize);
124
125 slot = (int) (hash_pjw (d->key) % h->size);
126 item = list_insert (&(h->tbl[slot]), (void *) new, sizeof (struct datum));
127 goto EXIT;
128
129 ERROR:
130 if (new && (new->key))
131 free (new->key);
132 if (new && (new->val))
133 free (new->val);
134 EXIT:
135 if (new)
136 free (new);
137 return (struct datum *) item->data;
138 }
139
hash_table_search(struct hash_table * h,struct datum * k)140 struct datum *hash_table_search (struct hash_table *h, struct datum *k)
141 {
142 int slot = 0;
143 struct list_item *curr = NULL;
144 struct datum *d = NULL;
145
146 if (!(k && h && (h->size > 0) && h->tbl))
147 goto EXIT;
148
149 slot = (int) (hash_pjw (k->key) % h->size);
150 for (curr = h->tbl[slot].head ; curr ; curr = curr->next) {
151 d = (struct datum *) curr->data;
152 if (d->ksize == k->ksize){
153 if (!memcmp (d->key, k->key, d->ksize))
154 goto EXIT;
155 }
156 }
157 d = NULL;
158
159 EXIT:
160 return d;
161 }
162
hash_table_search2(struct hash_table * h,struct datum * k)163 static struct list_item *hash_table_search2 (struct hash_table *h, struct datum *k)
164 {
165 int slot = 0;
166 struct list_item *curr = NULL;
167 struct datum *d = NULL;
168
169 if (!(k && h && (h->size > 0) && h->tbl))
170 goto EXIT;
171
172 slot = (int) (hash_pjw (k->key) % h->size);
173 for (curr = h->tbl[slot].head ; curr ; curr = curr->next) {
174 d = (struct datum *) curr->data;
175 if (d->ksize == k->ksize){
176 if (!memcmp (d->key, k->key, d->ksize))
177 goto EXIT;
178 }
179 }
180 curr = NULL;
181
182 EXIT:
183 return curr;
184 }
185
hash_table_delete(struct hash_table * h,struct datum * k)186 void hash_table_delete (struct hash_table *h, struct datum *k)
187 {
188 struct datum *d = NULL;
189 struct list_item *l = NULL;
190
191 if (!(k && h && (h->size > 0) && h->tbl))
192 return;
193
194 if ((l = hash_table_search2 (h, k))) {
195 d = (struct datum *) l->data;
196 if (d->key)
197 free (d->key);
198 if (d->val)
199 free (d->val);
200 list_delete ((struct list_item *) l);
201 }
202
203 return;
204 }
205
206