1 /***************************************************************************/
2 /* This code is part of WWW grabber called pavuk */
3 /* Copyright (c) 1997 - 2001 Stefan Ondrejicka */
4 /* Distributed under GPL 2 or later */
5 /***************************************************************************/
6
7 #include <stdlib.h>
8 #include <string.h>
9 #include <assert.h>
10
11 #include "config.h"
12 #include "dlhash.h"
13
dlhash_new(unsigned int size,dlkey_func key_func,dlhash_func hash_func,dlcomp_func comp_func)14 dlhash *dlhash_new(unsigned int size, dlkey_func key_func,
15 dlhash_func hash_func, dlcomp_func comp_func)
16 {
17 dlhash *retv = malloc(sizeof(dlhash));
18 assert(retv != NULL);
19
20 retv->size = size;
21 retv->key_func = key_func;
22 retv->hash_func = hash_func;
23 retv->comp_func = comp_func;
24 retv->free_func = NULL;
25 retv->keyfree_func = NULL;
26 retv->nodes = (dllist **) calloc(size, sizeof(dllist *));
27 assert(retv->nodes != NULL);
28 memset(retv->nodes, '\0', size * sizeof(dllist *));
29
30 return retv;
31 }
32
dlhash_set_free_func(dlhash * hash,dlfree_func free_func,dlkeyfree_func keyfree_func)33 void dlhash_set_free_func(dlhash * hash, dlfree_func free_func,
34 dlkeyfree_func keyfree_func)
35 {
36 hash->free_func = free_func;
37 hash->keyfree_func = keyfree_func;
38 }
39
dlhash_empty(dlhash * hash)40 void dlhash_empty(dlhash * hash)
41 {
42 unsigned int i = 0;
43
44 for(i = 0; i < hash->size; i++)
45 {
46 while(hash->nodes[i])
47 {
48 if(hash->free_func)
49 hash->free_func(hash->nodes[i]->data);
50 hash->nodes[i] = dllist_remove_entry(hash->nodes[i], hash->nodes[i]);
51 }
52 }
53 }
54
dlhash_free(dlhash * hash)55 void dlhash_free(dlhash * hash)
56 {
57 dlhash_empty(hash);
58 free(hash->nodes);
59 free(hash);
60 }
61
dlhash_insert(dlhash * hash,dllist_t key_data)62 void dlhash_insert(dlhash * hash, dllist_t key_data)
63 {
64 dllist_t key;
65 unsigned int key_class;
66
67 key = hash->key_func(key_data);
68 key_class = hash->hash_func(hash->size, key);
69
70 hash->nodes[key_class] = dllist_append(hash->nodes[key_class], key_data);
71
72 if(hash->keyfree_func)
73 hash->keyfree_func(key);
74 }
75
dlhash_remove(dlhash * hash,dllist_t key_data)76 void dlhash_remove(dlhash * hash, dllist_t key_data)
77 {
78 dllist_t key1, key2;
79 unsigned int key_class;
80 dllist *ptr;
81
82 key1 = hash->key_func(key_data);
83 key_class = hash->hash_func(hash->size, key1);
84
85 ptr = hash->nodes[key_class];
86 while(ptr)
87 {
88 key2 = hash->key_func(ptr->data);
89 if(hash->comp_func(key1, key2))
90 {
91 dllist *tptr;
92
93 if(hash->free_func)
94 hash->free_func(ptr->data);
95 tptr = ptr->next;
96 hash->nodes[key_class] =
97 dllist_remove_entry(hash->nodes[key_class], ptr);
98 ptr = tptr;
99 }
100 else
101 ptr = ptr->next;
102
103 if(hash->keyfree_func)
104 hash->keyfree_func(key2);
105 }
106
107 if(hash->keyfree_func)
108 hash->keyfree_func(key1);
109 }
110
dlhash_exclude(dlhash * hash,dllist_t key_data)111 void dlhash_exclude(dlhash * hash, dllist_t key_data)
112 {
113 dllist_t key1, key2;
114 unsigned int key_class;
115 dllist *ptr;
116
117 key1 = hash->key_func(key_data);
118 key_class = hash->hash_func(hash->size, key1);
119
120 ptr = hash->nodes[key_class];
121 while(ptr)
122 {
123 key2 = hash->key_func(ptr->data);
124
125 if(hash->comp_func(key1, key2))
126 {
127 dllist *tptr;
128
129 tptr = ptr->next;
130 hash->nodes[key_class] =
131 dllist_remove_entry(hash->nodes[key_class], ptr);
132 ptr = tptr;
133 }
134 else
135 ptr = ptr->next;
136
137 if(hash->keyfree_func)
138 hash->keyfree_func(key2);
139 }
140
141 if(hash->keyfree_func)
142 hash->keyfree_func(key1);
143 }
144
dlhash_get_class(dlhash * hash,dllist_t key_data)145 dllist *dlhash_get_class(dlhash * hash, dllist_t key_data)
146 {
147 dllist_t key;
148 unsigned int key_class;
149
150 key = hash->key_func(key_data);
151 key_class = hash->hash_func(hash->size, key);
152
153 if(hash->keyfree_func)
154 hash->keyfree_func(key);
155
156 return hash->nodes[key_class];
157 }
158
dlhash_exclude_exact(dlhash * hash,dllist_t key_data)159 void dlhash_exclude_exact(dlhash * hash, dllist_t key_data)
160 {
161 dllist_t key;
162 unsigned int key_class;
163 dllist *ptr;
164
165 key = hash->key_func(key_data);
166 key_class = hash->hash_func(hash->size, key);
167
168 if(hash->keyfree_func)
169 hash->keyfree_func(key);
170
171 if((ptr = dllist_find(hash->nodes[key_class], key_data)))
172 hash->nodes[key_class] = dllist_remove_entry(hash->nodes[key_class], ptr);
173 }
174
dlhash_find_by_key(dlhash * hash,dllist_t key1)175 dllist_t dlhash_find_by_key(dlhash * hash, dllist_t key1)
176 {
177 dllist_t key2;
178 dllist_t retv = 0;
179 unsigned int key_class;
180 dllist *ptr;
181
182 key_class = hash->hash_func(hash->size, key1);
183
184 ptr = hash->nodes[key_class];
185
186 while(ptr)
187 {
188 key2 = hash->key_func(ptr->data);
189
190 if(hash->comp_func(key1, key2))
191 {
192 retv = ptr->data;
193 if(hash->keyfree_func)
194 hash->keyfree_func(key2);
195 break;
196 }
197 ptr = ptr->next;
198
199 if(hash->keyfree_func)
200 hash->keyfree_func(key2);
201 }
202
203 return retv;
204 }
205
dlhash_find(dlhash * hash,dllist_t key_data)206 dllist_t dlhash_find(dlhash * hash, dllist_t key_data)
207 {
208 dllist_t key;
209 dllist_t retv = 0;
210
211 key = hash->key_func(key_data);
212
213 retv = dlhash_find_by_key(hash, key);
214
215 if(hash->keyfree_func)
216 hash->keyfree_func(key);
217
218 return retv;
219 }
220
dlhash_resize(dlhash * hash,unsigned int new_size)221 void dlhash_resize(dlhash * hash, unsigned int new_size)
222 {
223 unsigned int i, old_size;
224 dllist **old_nodes;
225
226 if(hash->size == new_size)
227 return;
228
229 old_nodes = hash->nodes;
230 old_size = hash->size;
231
232 hash->size = new_size;
233 hash->nodes = (dllist **) calloc(new_size, sizeof(dllist *));
234 assert(hash->nodes != NULL);
235 memset(hash->nodes, '\0', new_size * sizeof(dllist *));
236
237 for(i = 0; i < old_size; i++)
238 {
239 while(old_nodes[i])
240 {
241 dlhash_insert(hash, old_nodes[i]->data);
242 old_nodes[i] = dllist_remove_entry(old_nodes[i], old_nodes[i]);
243 }
244 }
245 free(old_nodes);
246 }
247