source: UsbWattMeter/trunk/curl-7.47.1/lib/hash.c@ 164

Last change on this file since 164 was 164, checked in by coas-nagasima, 6 years ago

TOPPERS/ECNLサンプルアプリ「USB充電器電力計」を追加

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
  • Property svn:mime-type set to text/x-csrc
File size: 8.9 KB
RevLine 
[164]1/***************************************************************************
2 * _ _ ____ _
3 * Project ___| | | | _ \| |
4 * / __| | | | |_) | |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
7 *
8 * Copyright (C) 1998 - 2015, 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 "hash.h"
26#include "llist.h"
27#include "curl_memory.h"
28/* The last #include file should be: */
29#include "memdebug.h"
30
31static void
32hash_element_dtor(void *user, void *element)
33{
34 struct curl_hash *h = (struct curl_hash *) user;
35 struct curl_hash_element *e = (struct curl_hash_element *) element;
36
37 Curl_safefree(e->key);
38
39 if(e->ptr) {
40 h->dtor(e->ptr);
41 e->ptr = NULL;
42 }
43
44 e->key_len = 0;
45
46 free(e);
47}
48
49/* Initializes a hash structure.
50 * Return 1 on error, 0 is fine.
51 *
52 * @unittest: 1602
53 * @unittest: 1603
54 */
55int
56Curl_hash_init(struct curl_hash *h,
57 int slots,
58 hash_function hfunc,
59 comp_function comparator,
60 curl_hash_dtor dtor)
61{
62 int i;
63
64 if(!slots || !hfunc || !comparator ||!dtor) {
65 return 1; /* failure */
66 }
67
68 h->hash_func = hfunc;
69 h->comp_func = comparator;
70 h->dtor = dtor;
71 h->size = 0;
72 h->slots = slots;
73
74 h->table = malloc(slots * sizeof(struct curl_llist *));
75 if(h->table) {
76 for(i = 0; i < slots; ++i) {
77 h->table[i] = Curl_llist_alloc((curl_llist_dtor) hash_element_dtor);
78 if(!h->table[i]) {
79 while(i--) {
80 Curl_llist_destroy(h->table[i], NULL);
81 h->table[i] = NULL;
82 }
83 free(h->table);
84 h->table = NULL;
85 h->slots = 0;
86 return 1; /* failure */
87 }
88 }
89 return 0; /* fine */
90 }
91 else {
92 h->slots = 0;
93 return 1; /* failure */
94 }
95}
96
97static struct curl_hash_element *
98mk_hash_element(const void *key, size_t key_len, const void *p)
99{
100 struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element));
101
102 if(he) {
103 void *dupkey = malloc(key_len);
104 if(dupkey) {
105 /* copy the key */
106 memcpy(dupkey, key, key_len);
107
108 he->key = dupkey;
109 he->key_len = key_len;
110 he->ptr = (void *) p;
111 }
112 else {
113 /* failed to duplicate the key, free memory and fail */
114 free(he);
115 he = NULL;
116 }
117 }
118 return he;
119}
120
121#define FETCH_LIST(x,y,z) x->table[x->hash_func(y, z, x->slots)]
122
123/* Insert the data in the hash. If there already was a match in the hash,
124 * that data is replaced.
125 *
126 * @unittest: 1305
127 * @unittest: 1602
128 * @unittest: 1603
129 */
130void *
131Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p)
132{
133 struct curl_hash_element *he;
134 struct curl_llist_element *le;
135 struct curl_llist *l = FETCH_LIST (h, key, key_len);
136
137 for(le = l->head; le; le = le->next) {
138 he = (struct curl_hash_element *) le->ptr;
139 if(h->comp_func(he->key, he->key_len, key, key_len)) {
140 Curl_llist_remove(l, le, (void *)h);
141 --h->size;
142 break;
143 }
144 }
145
146 he = mk_hash_element(key, key_len, p);
147 if(he) {
148 if(Curl_llist_insert_next(l, l->tail, he)) {
149 ++h->size;
150 return p; /* return the new entry */
151 }
152 /*
153 * Couldn't insert it, destroy the 'he' element and the key again. We
154 * don't call hash_element_dtor() since that would also call the
155 * "destructor" for the actual data 'p'. When we fail, we shall not touch
156 * that data.
157 */
158 free(he->key);
159 free(he);
160 }
161
162 return NULL; /* failure */
163}
164
165/* Remove the identified hash entry.
166 * Returns non-zero on failure.
167 *
168 * @unittest: 1603
169 */
170int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len)
171{
172 struct curl_llist_element *le;
173 struct curl_hash_element *he;
174 struct curl_llist *l = FETCH_LIST(h, key, key_len);
175
176 for(le = l->head; le; le = le->next) {
177 he = le->ptr;
178 if(h->comp_func(he->key, he->key_len, key, key_len)) {
179 Curl_llist_remove(l, le, (void *) h);
180 --h->size;
181 return 0;
182 }
183 }
184 return 1;
185}
186
187/* Retrieves a hash element.
188 *
189 * @unittest: 1603
190 */
191void *
192Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len)
193{
194 struct curl_llist_element *le;
195 struct curl_hash_element *he;
196 struct curl_llist *l;
197
198 if(h) {
199 l = FETCH_LIST(h, key, key_len);
200 for(le = l->head; le; le = le->next) {
201 he = le->ptr;
202 if(h->comp_func(he->key, he->key_len, key, key_len)) {
203 return he->ptr;
204 }
205 }
206 }
207
208 return NULL;
209}
210
211#if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST)
212void
213Curl_hash_apply(curl_hash *h, void *user,
214 void (*cb)(void *user, void *ptr))
215{
216 struct curl_llist_element *le;
217 int i;
218
219 for(i = 0; i < h->slots; ++i) {
220 for(le = (h->table[i])->head;
221 le;
222 le = le->next) {
223 curl_hash_element *el = le->ptr;
224 cb(user, el->ptr);
225 }
226 }
227}
228#endif
229
230/* Destroys all the entries in the given hash and resets its attributes,
231 * prepping the given hash for [static|dynamic] deallocation.
232 *
233 * @unittest: 1305
234 * @unittest: 1602
235 * @unittest: 1603
236 */
237void
238Curl_hash_destroy(struct curl_hash *h)
239{
240 int i;
241
242 for(i = 0; i < h->slots; ++i) {
243 Curl_llist_destroy(h->table[i], (void *) h);
244 h->table[i] = NULL;
245 }
246
247 Curl_safefree(h->table);
248 h->size = 0;
249 h->slots = 0;
250}
251
252/* Removes all the entries in the given hash.
253 *
254 * @unittest: 1602
255 */
256void
257Curl_hash_clean(struct curl_hash *h)
258{
259 Curl_hash_clean_with_criterium(h, NULL, NULL);
260}
261
262/* Cleans all entries that pass the comp function criteria. */
263void
264Curl_hash_clean_with_criterium(struct curl_hash *h, void *user,
265 int (*comp)(void *, void *))
266{
267 struct curl_llist_element *le;
268 struct curl_llist_element *lnext;
269 struct curl_llist *list;
270 int i;
271
272 if(!h)
273 return;
274
275 for(i = 0; i < h->slots; ++i) {
276 list = h->table[i];
277 le = list->head; /* get first list entry */
278 while(le) {
279 struct curl_hash_element *he = le->ptr;
280 lnext = le->next;
281 /* ask the callback function if we shall remove this entry or not */
282 if(comp == NULL || comp(user, he->ptr)) {
283 Curl_llist_remove(list, le, (void *) h);
284 --h->size; /* one less entry in the hash now */
285 }
286 le = lnext;
287 }
288 }
289}
290
291size_t Curl_hash_str(void* key, size_t key_length, size_t slots_num)
292{
293 const char* key_str = (const char *) key;
294 const char *end = key_str + key_length;
295 unsigned long h = 5381;
296
297 while(key_str < end) {
298 h += h << 5;
299 h ^= (unsigned long) *key_str++;
300 }
301
302 return (h % slots_num);
303}
304
305size_t Curl_str_key_compare(void *k1, size_t key1_len,
306 void *k2, size_t key2_len)
307{
308 if((key1_len == key2_len) && !memcmp(k1, k2, key1_len))
309 return 1;
310
311 return 0;
312}
313
314void Curl_hash_start_iterate(struct curl_hash *hash,
315 struct curl_hash_iterator *iter)
316{
317 iter->hash = hash;
318 iter->slot_index = 0;
319 iter->current_element = NULL;
320}
321
322struct curl_hash_element *
323Curl_hash_next_element(struct curl_hash_iterator *iter)
324{
325 int i;
326 struct curl_hash *h = iter->hash;
327
328 /* Get the next element in the current list, if any */
329 if(iter->current_element)
330 iter->current_element = iter->current_element->next;
331
332 /* If we have reached the end of the list, find the next one */
333 if(!iter->current_element) {
334 for(i = iter->slot_index;i < h->slots;i++) {
335 if(h->table[i]->head) {
336 iter->current_element = h->table[i]->head;
337 iter->slot_index = i+1;
338 break;
339 }
340 }
341 }
342
343 if(iter->current_element) {
344 struct curl_hash_element *he = iter->current_element->ptr;
345 return he;
346 }
347 else {
348 iter->current_element = NULL;
349 return NULL;
350 }
351}
352
353#if 0 /* useful function for debugging hashes and their contents */
354void Curl_hash_print(struct curl_hash *h,
355 void (*func)(void *))
356{
357 struct curl_hash_iterator iter;
358 struct curl_hash_element *he;
359 int last_index = -1;
360
361 if(!h)
362 return;
363
364 fprintf(stderr, "=Hash dump=\n");
365
366 Curl_hash_start_iterate(h, &iter);
367
368 he = Curl_hash_next_element(&iter);
369 while(he) {
370 if(iter.slot_index != last_index) {
371 fprintf(stderr, "index %d:", iter.slot_index);
372 if(last_index >= 0) {
373 fprintf(stderr, "\n");
374 }
375 last_index = iter.slot_index;
376 }
377
378 if(func)
379 func(he->ptr);
380 else
381 fprintf(stderr, " [%p]", (void *)he->ptr);
382
383 he = Curl_hash_next_element(&iter);
384 }
385 fprintf(stderr, "\n");
386}
387#endif
Note: See TracBrowser for help on using the repository browser.