1: /***************************************************************************
2: * _ _ ____ _
3: * Project ___| | | | _ \| |
4: * / __| | | | |_) | |
5: * | (__| |_| | _ <| |___
6: * \___|\___/|_| \_\_____|
7: *
8: * Copyright (C) 1998 - 2018, Daniel Stenberg, <daniel@haxx.se>, et al.
9: *
10: * This software is licensed as described in the file COPYING, which
11: * you should have received as part of this distribution. The terms
12: * are also available at https://curl.haxx.se/docs/copyright.html.
13: *
14: * You may opt to use, copy, modify, merge, publish, distribute and/or sell
15: * copies of the Software, and permit persons to whom the Software is
16: * furnished to do so, under the terms of the COPYING file.
17: *
18: * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
19: * KIND, either express or implied.
20: *
21: ***************************************************************************/
22:
23: #include "curl_setup.h"
24:
25: #include <curl/curl.h>
26:
27: #include "hash.h"
28: #include "llist.h"
29: #include "curl_memory.h"
30:
31: /* The last #include file should be: */
32: #include "memdebug.h"
33:
34: static void
35: hash_element_dtor(void *user, void *element)
36: {
37: struct curl_hash *h = (struct curl_hash *) user;
38: struct curl_hash_element *e = (struct curl_hash_element *) element;
39:
40: if(e->ptr) {
41: h->dtor(e->ptr);
42: e->ptr = NULL;
43: }
44:
45: e->key_len = 0;
46:
47: free(e);
48: }
49:
50: /* Initializes a hash structure.
51: * Return 1 on error, 0 is fine.
52: *
53: * @unittest: 1602
54: * @unittest: 1603
55: */
56: int
57: Curl_hash_init(struct curl_hash *h,
58: int slots,
59: hash_function hfunc,
60: comp_function comparator,
61: curl_hash_dtor dtor)
62: {
63: if(!slots || !hfunc || !comparator ||!dtor) {
64: return 1; /* failure */
65: }
66:
67: h->hash_func = hfunc;
68: h->comp_func = comparator;
69: h->dtor = dtor;
70: h->size = 0;
71: h->slots = slots;
72:
73: h->table = malloc(slots * sizeof(struct curl_llist));
74: if(h->table) {
75: int i;
76: for(i = 0; i < slots; ++i)
77: Curl_llist_init(&h->table[i], (curl_llist_dtor) hash_element_dtor);
78: return 0; /* fine */
79: }
80: h->slots = 0;
81: return 1; /* failure */
82: }
83:
84: static struct curl_hash_element *
85: mk_hash_element(const void *key, size_t key_len, const void *p)
86: {
87: /* allocate the struct plus memory after it to store the key */
88: struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element) +
89: key_len);
90: if(he) {
91: /* copy the key */
92: memcpy(he->key, key, key_len);
93: he->key_len = key_len;
94: he->ptr = (void *) p;
95: }
96: return he;
97: }
98:
99: #define FETCH_LIST(x,y,z) &x->table[x->hash_func(y, z, x->slots)]
100:
101: /* Insert the data in the hash. If there already was a match in the hash,
102: * that data is replaced.
103: *
104: * @unittest: 1305
105: * @unittest: 1602
106: * @unittest: 1603
107: */
108: void *
109: Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p)
110: {
111: struct curl_hash_element *he;
112: struct curl_llist_element *le;
113: struct curl_llist *l = FETCH_LIST(h, key, key_len);
114:
115: for(le = l->head; le; le = le->next) {
116: he = (struct curl_hash_element *) le->ptr;
117: if(h->comp_func(he->key, he->key_len, key, key_len)) {
118: Curl_llist_remove(l, le, (void *)h);
119: --h->size;
120: break;
121: }
122: }
123:
124: he = mk_hash_element(key, key_len, p);
125: if(he) {
126: Curl_llist_insert_next(l, l->tail, he, &he->list);
127: ++h->size;
128: return p; /* return the new entry */
129: }
130:
131: return NULL; /* failure */
132: }
133:
134: /* Remove the identified hash entry.
135: * Returns non-zero on failure.
136: *
137: * @unittest: 1603
138: */
139: int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len)
140: {
141: struct curl_llist_element *le;
142: struct curl_llist *l = FETCH_LIST(h, key, key_len);
143:
144: for(le = l->head; le; le = le->next) {
145: struct curl_hash_element *he = le->ptr;
146: if(h->comp_func(he->key, he->key_len, key, key_len)) {
147: Curl_llist_remove(l, le, (void *) h);
148: --h->size;
149: return 0;
150: }
151: }
152: return 1;
153: }
154:
155: /* Retrieves a hash element.
156: *
157: * @unittest: 1603
158: */
159: void *
160: Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len)
161: {
162: struct curl_llist_element *le;
163: struct curl_llist *l;
164:
165: if(h) {
166: l = FETCH_LIST(h, key, key_len);
167: for(le = l->head; le; le = le->next) {
168: struct curl_hash_element *he = le->ptr;
169: if(h->comp_func(he->key, he->key_len, key, key_len)) {
170: return he->ptr;
171: }
172: }
173: }
174:
175: return NULL;
176: }
177:
178: #if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST)
179: void
180: Curl_hash_apply(curl_hash *h, void *user,
181: void (*cb)(void *user, void *ptr))
182: {
183: struct curl_llist_element *le;
184: int i;
185:
186: for(i = 0; i < h->slots; ++i) {
187: for(le = (h->table[i])->head;
188: le;
189: le = le->next) {
190: curl_hash_element *el = le->ptr;
191: cb(user, el->ptr);
192: }
193: }
194: }
195: #endif
196:
197: /* Destroys all the entries in the given hash and resets its attributes,
198: * prepping the given hash for [static|dynamic] deallocation.
199: *
200: * @unittest: 1305
201: * @unittest: 1602
202: * @unittest: 1603
203: */
204: void
205: Curl_hash_destroy(struct curl_hash *h)
206: {
207: int i;
208:
209: for(i = 0; i < h->slots; ++i) {
210: Curl_llist_destroy(&h->table[i], (void *) h);
211: }
212:
213: Curl_safefree(h->table);
214: h->size = 0;
215: h->slots = 0;
216: }
217:
218: /* Removes all the entries in the given hash.
219: *
220: * @unittest: 1602
221: */
222: void
223: Curl_hash_clean(struct curl_hash *h)
224: {
225: Curl_hash_clean_with_criterium(h, NULL, NULL);
226: }
227:
228: /* Cleans all entries that pass the comp function criteria. */
229: void
230: Curl_hash_clean_with_criterium(struct curl_hash *h, void *user,
231: int (*comp)(void *, void *))
232: {
233: struct curl_llist_element *le;
234: struct curl_llist_element *lnext;
235: struct curl_llist *list;
236: int i;
237:
238: if(!h)
239: return;
240:
241: for(i = 0; i < h->slots; ++i) {
242: list = &h->table[i];
243: le = list->head; /* get first list entry */
244: while(le) {
245: struct curl_hash_element *he = le->ptr;
246: lnext = le->next;
247: /* ask the callback function if we shall remove this entry or not */
248: if(comp == NULL || comp(user, he->ptr)) {
249: Curl_llist_remove(list, le, (void *) h);
250: --h->size; /* one less entry in the hash now */
251: }
252: le = lnext;
253: }
254: }
255: }
256:
257: size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num)
258: {
259: const char *key_str = (const char *) key;
260: const char *end = key_str + key_length;
261: size_t h = 5381;
262:
263: while(key_str < end) {
264: h += h << 5;
265: h ^= *key_str++;
266: }
267:
268: return (h % slots_num);
269: }
270:
271: size_t Curl_str_key_compare(void *k1, size_t key1_len,
272: void *k2, size_t key2_len)
273: {
274: if((key1_len == key2_len) && !memcmp(k1, k2, key1_len))
275: return 1;
276:
277: return 0;
278: }
279:
280: void Curl_hash_start_iterate(struct curl_hash *hash,
281: struct curl_hash_iterator *iter)
282: {
283: iter->hash = hash;
284: iter->slot_index = 0;
285: iter->current_element = NULL;
286: }
287:
288: struct curl_hash_element *
289: Curl_hash_next_element(struct curl_hash_iterator *iter)
290: {
291: struct curl_hash *h = iter->hash;
292:
293: /* Get the next element in the current list, if any */
294: if(iter->current_element)
295: iter->current_element = iter->current_element->next;
296:
297: /* If we have reached the end of the list, find the next one */
298: if(!iter->current_element) {
299: int i;
300: for(i = iter->slot_index; i < h->slots; i++) {
301: if(h->table[i].head) {
302: iter->current_element = h->table[i].head;
303: iter->slot_index = i + 1;
304: break;
305: }
306: }
307: }
308:
309: if(iter->current_element) {
310: struct curl_hash_element *he = iter->current_element->ptr;
311: return he;
312: }
313: iter->current_element = NULL;
314: return NULL;
315: }
316:
317: #if 0 /* useful function for debugging hashes and their contents */
318: void Curl_hash_print(struct curl_hash *h,
319: void (*func)(void *))
320: {
321: struct curl_hash_iterator iter;
322: struct curl_hash_element *he;
323: int last_index = -1;
324:
325: if(!h)
326: return;
327:
328: fprintf(stderr, "=Hash dump=\n");
329:
330: Curl_hash_start_iterate(h, &iter);
331:
332: he = Curl_hash_next_element(&iter);
333: while(he) {
334: if(iter.slot_index != last_index) {
335: fprintf(stderr, "index %d:", iter.slot_index);
336: if(last_index >= 0) {
337: fprintf(stderr, "\n");
338: }
339: last_index = iter.slot_index;
340: }
341:
342: if(func)
343: func(he->ptr);
344: else
345: fprintf(stderr, " [%p]", (void *)he->ptr);
346:
347: he = Curl_hash_next_element(&iter);
348: }
349: fprintf(stderr, "\n");
350: }
351: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / curl / lib