Annotation of embedaddon/curl/lib/hash.c, revision 1.1
1.1 ! misho 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