1 /* vi:ai:et:ts=8 sw=2
2 */
3 /*
4 * wzdftpd - a modular and cool ftp server
5 * Copyright (C) 2002-2004 Pierre Chifflier
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 *
21 * As a special exemption, Pierre Chifflier
22 * and other respective copyright holders give permission to link this program
23 * with OpenSSL, and distribute the resulting executable, without including
24 * the source code for OpenSSL in the source distribution.
25 */
26
27 /** \file hash.c
28 * \brief Hash tables implementation
29 */
30
31 #ifdef HAVE_CONFIG_H
32 # include "config.h"
33 #endif
34
35 #include <stdio.h>
36 #include <string.h>
37 #include <stdlib.h>
38
39 #include "hash.h"
40
41 typedef struct {
42 void *key;
43 void *data;
44 htrigger_function trigger; /* trigger function to be called on modification */
45 hfree free_key;
46 hfree free_element;
47 } CHTBL_Elmnt;
48
49
hash_str(const char * key)50 unsigned int hash_str(const char *key)
51 {
52 unsigned hashval;
53
54 for (hashval = 0; *key != '\0'; key++)
55 hashval = (*key * 7 + hashval) % 781;
56 /* hashval = *key + 31 * hashval;*/
57 return hashval;
58 }
59
60
chtbl_init(CHTBL * htab,unsigned int containers,unsigned int (* h)(const void *),int (* match)(const void *,const void *),void (* ffree)(void *))61 int chtbl_init(CHTBL *htab, unsigned int containers, unsigned int (*h)(const void*),
62 int (*match)(const void*, const void*),
63 void (*ffree)(void*))
64 {
65 unsigned int i;
66
67 if ((htab->table = (List*)malloc(containers * sizeof(List))) == NULL)
68 return -1;
69
70 htab->containers = containers;
71
72 for (i=0; i<containers; i++)
73 list_init(&htab->table[i], free);
74
75 htab->h = h;
76 htab->match = match;
77 htab->free = ffree;
78
79 htab->size = 0;
80
81 return 0;
82 }
83
chtbl_destroy(CHTBL * htab)84 void chtbl_destroy(CHTBL *htab)
85 {
86 unsigned int i;
87
88 for (i=0; i<htab->containers; i++)
89 {
90 CHTBL_Elmnt *data;
91 List * list;
92
93 list = &htab->table[i];
94
95 /* list_destroy(&htab->table[i]);*/
96
97 while (list_size(list) > 0) {
98 if (list_rem_next(list,0,(void**)&data)==0 && list->destroy != NULL) {
99 if (data->free_key) data->free_key(data->key);
100 if (data->free_element) data->free_element(data->data);
101 list->destroy(data);
102 }
103 }
104 }
105
106 free(htab->table);
107
108 memset(htab, 0, sizeof(CHTBL));
109 }
110
chtbl_insert(CHTBL * htab,const void * key,void * data,htrigger_function fcn,hfree free_key,hfree free_element)111 int chtbl_insert(CHTBL *htab, const void *key, void *data, htrigger_function fcn, hfree free_key, hfree free_element)
112 {
113 CHTBL_Elmnt *entry;
114 unsigned int index;
115 int ret;
116
117 /* already present ? */
118 if (chtbl_lookup(htab, key, NULL) == 0)
119 return 1;
120
121 index = htab->h(key) % htab->containers;
122
123 /* insertion */
124 entry = malloc(sizeof(CHTBL_Elmnt));
125 entry->key = (void*)key;
126 entry->data = data;
127 entry->trigger = fcn;
128 entry->free_key = free_key;
129 entry->free_element = free_element;
130
131 if ((ret = list_ins_next(&htab->table[index], NULL, entry)) == 0)
132 htab->size++;
133 else
134 free(entry);
135
136 return ret;
137 }
138
chtbl_remove(CHTBL * htab,const void * key)139 int chtbl_remove(CHTBL *htab, const void *key)
140 {
141 ListElmt *prec, *element;
142 CHTBL_Elmnt *entry;
143 unsigned int index;
144
145 index = htab->h(key) % htab->containers;
146
147 prec = NULL;
148 for (element = list_head(&htab->table[index]); element != NULL; element = list_next(element))
149 {
150 entry = list_data(element);
151 if (!entry) return -1;
152 if (htab->match(key, entry->key)==0) {
153 if (list_rem_next(&htab->table[index], prec, (void*)entry) == 0) {
154 htab->size--;
155 if (entry->free_key) entry->free_key(entry->key);
156 if (entry->free_element) entry->free_element(entry->data);
157 htab->table[index].destroy(entry);
158 return 0;
159 }
160 return -1;
161 }
162 prec = element;
163 }
164
165 return -1;
166 }
167
chtbl_lookup(const CHTBL * htab,const void * key,void ** data)168 int chtbl_lookup(const CHTBL *htab, const void *key, void **data)
169 {
170 ListElmt *element;
171 CHTBL_Elmnt *entry;
172 unsigned int index;
173
174 if (key == NULL) return -1;
175
176 index = htab->h(key) % htab->containers;
177
178 for (element=list_head(&htab->table[index]); element != NULL; element = list_next(element))
179 {
180 entry = list_data(element);
181 if (!entry) return -1;
182 if (htab->match(key, entry->key)==0) {
183 if (data) *data = entry->data;
184 return 0;
185 }
186 }
187
188 return 1;
189 }
190
chtbl_change(const CHTBL * htab,const void * key,void * data)191 int chtbl_change(const CHTBL *htab, const void *key, void *data)
192 {
193 ListElmt *element;
194 CHTBL_Elmnt *entry;
195 unsigned int index;
196 int ret;
197
198 index = htab->h(key) % htab->containers;
199
200 for (element=list_head(&htab->table[index]); element != NULL; element = list_next(element))
201 {
202 entry = list_data(element);
203 if (!entry) return -1;
204 if (htab->match(key, entry->key)==0) {
205 if (data) entry->data = data;
206 if (entry->trigger) {
207 ret = (entry->trigger)(entry->key,entry->data);
208 }
209 return 0;
210 }
211 }
212
213 return 1;
214 }
215
chtbl_insert_or_change(CHTBL * htab,const void * key,void * data,htrigger_function fcn,hfree free_key,hfree free_element)216 int chtbl_insert_or_change(CHTBL *htab, const void *key, void *data, htrigger_function fcn, hfree free_key, hfree free_element)
217 {
218 if(chtbl_insert(htab, key, data, fcn, free_key, free_element)) {
219 return chtbl_change(htab, key, data);
220 }
221 return 0;
222 }
223
chtbl_search(const CHTBL * htab,int (* match)(const void *,const void *),const void * arg,void ** data)224 int chtbl_search(const CHTBL *htab, int (*match)(const void *, const void*), const void *arg, void **data)
225 {
226 unsigned int i;
227 void * test_data;
228
229 for (i=0; i<htab->containers; i++)
230 {
231 CHTBL_Elmnt *tbl_elmnt;
232 List * list;
233 ListElmt * elmnt;
234
235 list = &htab->table[i];
236
237 for (elmnt=list_head(list); elmnt; elmnt=list_next(elmnt)) {
238 tbl_elmnt = list_data(elmnt);
239 if (!tbl_elmnt) continue;
240 test_data = tbl_elmnt->data;
241 if (test_data && (*match)(test_data, arg)) {
242 if (data) *data = test_data;
243 return 0;
244 }
245 }
246 }
247
248 return 1;
249 }
250
251 /** \brief insert into a sorted list a hash table element
252 */
_h_list_ins_sorted(List * list,const CHTBL_Elmnt * data,int (* sort)(const void *,const void *))253 static int _h_list_ins_sorted(List *list, const CHTBL_Elmnt *data, int (*sort)(const void *, const void *))
254 {
255 ListElmt *element;
256
257 /* head insertion */
258 if (list_size(list)==0)
259 return list_ins_next(list, NULL, data);
260
261 /* find last element matching sort function */
262 element = list->head;
263 if (sort(((CHTBL_Elmnt*)element->data)->key,data->key)>0) {
264 return list_ins_next(list, NULL, data);
265 }
266
267 while (element->next && element->next->data && sort(((CHTBL_Elmnt*)element->next->data)->key,data->key)<0) {
268 element = element->next;
269 }
270
271 return list_ins_next(list, element, data);
272 }
273
chtbl_extract(const CHTBL * htab,int (* match)(const void *,const void *),const void * arg,int (* sort)(const void *,const void *))274 List * chtbl_extract(const CHTBL *htab, int (*match)(const void *, const void *), const void *arg, int (*sort)(const void *, const void *))
275 {
276 unsigned int i;
277 List * return_list;
278
279 return_list = malloc(sizeof(List));
280 list_init(return_list,NULL);
281
282 if (sort) {
283 CHTBL_Elmnt *tbl_elmnt;
284 ListElmt * elmnt;
285
286 for (i=0; i<htab->containers; i++)
287 {
288 List * list;
289
290 list = &htab->table[i];
291
292 for (elmnt=list_head(list); elmnt; elmnt=list_next(elmnt)) {
293 tbl_elmnt = list_data(elmnt);
294 if (!tbl_elmnt) continue;
295 /* if we do not have a match function or if the element matches, insert ! */
296 if (!match || (!(*match)(tbl_elmnt->key, arg))) {
297 _h_list_ins_sorted(return_list,tbl_elmnt,sort);
298 }
299 } /* for (list) */
300 } /* for (hash table) */
301
302 /* second pass */
303 for (elmnt=list_head(return_list); elmnt; elmnt=list_next(elmnt)) {
304 tbl_elmnt = list_data(elmnt);
305 if (tbl_elmnt)
306 elmnt->data = tbl_elmnt->data;
307 }
308 }
309 else { /* unsorted insertion */
310 for (i=0; i<htab->containers; i++)
311 {
312 CHTBL_Elmnt *tbl_elmnt;
313 List * list;
314 ListElmt * elmnt;
315
316 list = &htab->table[i];
317
318 for (elmnt=list_head(list); elmnt; elmnt=list_next(elmnt)) {
319 tbl_elmnt = list_data(elmnt);
320 if (!tbl_elmnt) continue;
321 /* if we do not have a match function or if the element matches, insert ! */
322 if (!match || (!(*match)(tbl_elmnt->key, arg))) {
323 list_ins_next(return_list,list_tail(return_list),tbl_elmnt->data);
324 }
325 } /* for (list) */
326 } /* for (hash table) */
327 }
328
329 return return_list;
330 }
331
332