"Fossies" - the Fresh Open Source Software Archive 
Member "xorriso-1.5.4/libisofs/util_htable.c" (30 Jan 2021, 8616 Bytes) of package /linux/misc/xorriso-1.5.4.pl02.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "util_htable.c" see the
Fossies "Dox" file reference documentation.
1 /*
2 * Copyright (c) 2007 Vreixo Formoso
3 * Copyright (c) 2014 Thomas Schmitt
4 *
5 * This file is part of the libisofs project; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License version 2
7 * or later as published by the Free Software Foundation.
8 * See COPYING file for details.
9 */
10
11 #ifdef HAVE_CONFIG_H
12 #include "../config.h"
13 #endif
14
15 #include "util.h"
16 #include "libisofs.h"
17
18 #include <stdlib.h>
19 #include <string.h>
20
21 /*
22 * Hash table implementation
23 */
24
25 struct iso_hnode
26 {
27 void *key;
28 void *data;
29
30 /** next node for chaining */
31 struct iso_hnode *next;
32 };
33
34 struct iso_htable
35 {
36 struct iso_hnode **table;
37
38 size_t size; /**< number of items in table */
39 size_t cap; /**< number of slots in table */
40
41 hash_funtion_t hash;
42 compare_function_t compare;
43 };
44
45 static
46 struct iso_hnode *iso_hnode_new(void *key, void *data)
47 {
48 struct iso_hnode *node = malloc(sizeof(struct iso_hnode));
49 if (node == NULL)
50 return NULL;
51
52 node->data = data;
53 node->key = key;
54 node->next = NULL;
55 return node;
56 }
57
58 /**
59 * Put an element in a Hash Table. The element will be identified by
60 * the given key, that you should use to retrieve the element again.
61 *
62 * This function allow duplicates, i.e., two items with the same key. In those
63 * cases, the value returned by iso_htable_get() is undefined. If you don't
64 * want to allow duplicates, use iso_htable_put() instead;
65 *
66 * Both the key and data pointers will be stored internally, so you should
67 * free the objects they point to. Use iso_htable_remove() to delete an
68 * element from the table.
69 */
70 int iso_htable_add(IsoHTable *table, void *key, void *data)
71 {
72 struct iso_hnode *node;
73 struct iso_hnode *new;
74 unsigned int hash;
75
76 if (table == NULL || key == NULL) {
77 return ISO_NULL_POINTER;
78 }
79
80 new = iso_hnode_new(key, data);
81 if (new == NULL) {
82 return ISO_OUT_OF_MEM;
83 }
84
85 hash = table->hash(key) % table->cap;
86 node = table->table[hash];
87
88 table->size++;
89 new->next = node;
90 table->table[hash] = new;
91 return ISO_SUCCESS;
92 }
93
94 /**
95 * Like iso_htable_add(), but this doesn't allow dulpicates.
96 *
97 * @return
98 * 1 success, 0 if an item with the same key already exists, < 0 error
99 */
100 int iso_htable_put(IsoHTable *table, void *key, void *data)
101 {
102 struct iso_hnode *node;
103 struct iso_hnode *new;
104 unsigned int hash;
105
106 if (table == NULL || key == NULL) {
107 return ISO_NULL_POINTER;
108 }
109
110 hash = table->hash(key) % table->cap;
111 node = table->table[hash];
112
113 while (node) {
114 if (!table->compare(key, node->key)) {
115 return 0;
116 }
117 node = node->next;
118 }
119
120 new = iso_hnode_new(key, data);
121 if (new == NULL) {
122 return ISO_OUT_OF_MEM;
123 }
124
125 table->size++;
126 new->next = table->table[hash];
127 table->table[hash] = new;
128 return ISO_SUCCESS;
129 }
130
131 /**
132 * Retrieve an element from the given table.
133 *
134 * @param table
135 * Hash table
136 * @param key
137 * Key of the element that will be removed
138 * @param data
139 * Will be filled with the element found. Remains untouched if no
140 * element with the given key is found.
141 * @return
142 * 1 if found, 0 if not, < 0 on error
143 */
144 int iso_htable_get(IsoHTable *table, void *key, void **data)
145 {
146 struct iso_hnode *node;
147 unsigned int hash;
148
149 if (table == NULL || key == NULL) {
150 return ISO_NULL_POINTER;
151 }
152
153 hash = table->hash(key) % table->cap;
154 node = table->table[hash];
155 while (node) {
156 if (!table->compare(key, node->key)) {
157 if (data) {
158 *data = node->data;
159 }
160 return 1;
161 }
162 node = node->next;
163 }
164 return 0;
165 }
166
167 /**
168 * Remove an item with the given key from the table. In tables that allow
169 * duplicates, it is undefined the element that will be deleted.
170 *
171 * @param table
172 * Hash table
173 * @param key
174 * Key of the element that will be removed
175 * @param free_data
176 * Function that will be called passing as parameters both the key and
177 * the element that will be deleted. The user can use it to free the
178 * element. You can pass NULL if you don't want to delete the item itself.
179 * @return
180 * 1 success, 0 no element exists with the given key, < 0 error
181 */
182 int iso_htable_remove(IsoHTable *table, void *key, hfree_data_t free_data)
183 {
184 struct iso_hnode *node, *prev;
185 unsigned int hash;
186
187 if (table == NULL || key == NULL) {
188 return ISO_NULL_POINTER;
189 }
190
191 hash = table->hash(key) % table->cap;
192 node = table->table[hash];
193 prev = NULL;
194 while (node) {
195 if (!table->compare(key, node->key)) {
196 if (free_data)
197 free_data(node->key, node->data);
198 if (prev) {
199 prev->next = node->next;
200 } else {
201 table->table[hash] = node->next;
202 }
203 free(node);
204 table->size--;
205 return 1;
206 }
207 prev = node;
208 node = node->next;
209 }
210 return 0;
211 }
212
213 /**
214 * Like remove, but instead of checking for key equality using the compare
215 * function, it just compare the key pointers. If the table allows duplicates,
216 * and you provide different keys (i.e. different pointers) to elements
217 * with same key (i.e. same content), this function ensure the exact element
218 * is removed.
219 *
220 * It has the problem that you must provide the same key pointer, and not just
221 * a key whose contents are equal. Moreover, if you use the same key (same
222 * pointer) to identify several objects, what of those are removed is
223 * undefined.
224 *
225 * @param table
226 * Hash table
227 * @param key
228 * Key of the element that will be removed
229 * @param free_data
230 * Function that will be called passing as parameters both the key and
231 * the element that will be deleted. The user can use it to free the
232 * element. You can pass NULL if you don't want to delete the item itself.
233 * @return
234 * 1 success, 0 no element exists with the given key, < 0 error
235 */
236 int iso_htable_remove_ptr(IsoHTable *table, void *key, hfree_data_t free_data)
237 {
238 struct iso_hnode *node, *prev;
239 unsigned int hash;
240
241 if (table == NULL || key == NULL) {
242 return ISO_NULL_POINTER;
243 }
244
245 hash = table->hash(key) % table->cap;
246 node = table->table[hash];
247 prev = NULL;
248 while (node) {
249 if (key == node->key) {
250 if (free_data)
251 free_data(node->key, node->data);
252 if (prev) {
253 prev->next = node->next;
254 } else {
255 table->table[hash] = node->next;
256 }
257 free(node);
258 table->size--;
259 return 1;
260 }
261 prev = node;
262 node = node->next;
263 }
264 return 0;
265 }
266
267 /**
268 * Hash function suitable for keys that are char strings.
269 */
270 unsigned int iso_str_hash(const void *key)
271 {
272 int i, len;
273 const char *p = key;
274 unsigned int h = 2166136261u;
275
276 len = strlen(p);
277 for (i = 0; i < len; i++)
278 h = (h * 16777619 ) ^ p[i];
279
280 return h;
281 }
282
283 /**
284 * Destroy the given hash table.
285 *
286 * Note that you're responsible to actually destroy the elements by providing
287 * a valid free_data function. You can pass NULL if you only want to delete
288 * the hash structure.
289 */
290 void iso_htable_destroy(IsoHTable *table, hfree_data_t free_data)
291 {
292 size_t i;
293 struct iso_hnode *node, *tmp;
294
295 if (table == NULL) {
296 return;
297 }
298
299 for (i = 0; i < table->cap; ++i) {
300 node = table->table[i];
301 while (node) {
302 tmp = node->next;
303 if (free_data)
304 free_data(node->key, node->data);
305 free(node);
306 node = tmp;
307 }
308 }
309 free(table->table);
310 free(table);
311 }
312
313 /**
314 * Create a new hash table.
315 *
316 * @param size
317 * Number of slots in table.
318 * @param hash
319 * Function used to generate
320 */
321 int iso_htable_create(size_t size, hash_funtion_t hash,
322 compare_function_t compare, IsoHTable **table)
323 {
324 IsoHTable *t;
325
326 if (size <= 0)
327 return ISO_WRONG_ARG_VALUE;
328 if (table == NULL)
329 return ISO_NULL_POINTER;
330
331 t = malloc(sizeof(IsoHTable));
332 if (t == NULL) {
333 return ISO_OUT_OF_MEM;
334 }
335 t->table = calloc(size, sizeof(void*));
336 if (t->table == NULL) {
337 free(t);
338 return ISO_OUT_OF_MEM;
339 }
340 t->cap = size;
341 t->size = 0;
342 t->hash = hash;
343 t->compare = compare;
344
345 *table = t;
346 return ISO_SUCCESS;
347 }