hash.c 8.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369
  1. /***************************************************************************
  2. * _ _ ____ _
  3. * Project ___| | | | _ \| |
  4. * / __| | | | |_) | |
  5. * | (__| |_| | _ <| |___
  6. * \___|\___/|_| \_\_____|
  7. *
  8. * Copyright (C) 1998 - 2021, 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.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. #include "curl_setup.h"
  23. #include <curl/curl.h>
  24. #include "hash.h"
  25. #include "llist.h"
  26. #include "curl_memory.h"
  27. /* The last #include file should be: */
  28. #include "memdebug.h"
  29. static void
  30. hash_element_dtor(void *user, void *element)
  31. {
  32. struct Curl_hash *h = (struct Curl_hash *) user;
  33. struct Curl_hash_element *e = (struct Curl_hash_element *) element;
  34. if(e->ptr) {
  35. h->dtor(e->ptr);
  36. e->ptr = NULL;
  37. }
  38. e->key_len = 0;
  39. free(e);
  40. }
  41. /* Initializes a hash structure.
  42. * Return 1 on error, 0 is fine.
  43. *
  44. * @unittest: 1602
  45. * @unittest: 1603
  46. */
  47. void
  48. Curl_hash_init(struct Curl_hash *h,
  49. int slots,
  50. hash_function hfunc,
  51. comp_function comparator,
  52. Curl_hash_dtor dtor)
  53. {
  54. DEBUGASSERT(h);
  55. DEBUGASSERT(slots);
  56. DEBUGASSERT(hfunc);
  57. DEBUGASSERT(comparator);
  58. DEBUGASSERT(dtor);
  59. h->table = NULL;
  60. h->hash_func = hfunc;
  61. h->comp_func = comparator;
  62. h->dtor = dtor;
  63. h->size = 0;
  64. h->slots = slots;
  65. }
  66. static struct Curl_hash_element *
  67. mk_hash_element(const void *key, size_t key_len, const void *p)
  68. {
  69. /* allocate the struct plus memory after it to store the key */
  70. struct Curl_hash_element *he = malloc(sizeof(struct Curl_hash_element) +
  71. key_len);
  72. if(he) {
  73. /* copy the key */
  74. memcpy(he->key, key, key_len);
  75. he->key_len = key_len;
  76. he->ptr = (void *) p;
  77. }
  78. return he;
  79. }
  80. #define FETCH_LIST(x,y,z) &x->table[x->hash_func(y, z, x->slots)]
  81. /* Insert the data in the hash. If there already was a match in the hash, that
  82. * data is replaced. This function also "lazily" allocates the table if
  83. * needed, as it isn't done in the _init function (anymore).
  84. *
  85. * @unittest: 1305
  86. * @unittest: 1602
  87. * @unittest: 1603
  88. */
  89. void *
  90. Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
  91. {
  92. struct Curl_hash_element *he;
  93. struct Curl_llist_element *le;
  94. struct Curl_llist *l;
  95. DEBUGASSERT(h);
  96. DEBUGASSERT(h->slots);
  97. if(!h->table) {
  98. int i;
  99. h->table = malloc(h->slots * sizeof(struct Curl_llist));
  100. if(!h->table)
  101. return NULL; /* OOM */
  102. for(i = 0; i < h->slots; ++i)
  103. Curl_llist_init(&h->table[i], hash_element_dtor);
  104. }
  105. l = FETCH_LIST(h, key, key_len);
  106. for(le = l->head; le; le = le->next) {
  107. he = (struct Curl_hash_element *) le->ptr;
  108. if(h->comp_func(he->key, he->key_len, key, key_len)) {
  109. Curl_llist_remove(l, le, (void *)h);
  110. --h->size;
  111. break;
  112. }
  113. }
  114. he = mk_hash_element(key, key_len, p);
  115. if(he) {
  116. Curl_llist_insert_next(l, l->tail, he, &he->list);
  117. ++h->size;
  118. return p; /* return the new entry */
  119. }
  120. return NULL; /* failure */
  121. }
  122. /* Remove the identified hash entry.
  123. * Returns non-zero on failure.
  124. *
  125. * @unittest: 1603
  126. */
  127. int Curl_hash_delete(struct Curl_hash *h, void *key, size_t key_len)
  128. {
  129. struct Curl_llist_element *le;
  130. struct Curl_llist *l;
  131. DEBUGASSERT(h);
  132. DEBUGASSERT(h->slots);
  133. if(h->table) {
  134. l = FETCH_LIST(h, key, key_len);
  135. for(le = l->head; le; le = le->next) {
  136. struct Curl_hash_element *he = le->ptr;
  137. if(h->comp_func(he->key, he->key_len, key, key_len)) {
  138. Curl_llist_remove(l, le, (void *) h);
  139. --h->size;
  140. return 0;
  141. }
  142. }
  143. }
  144. return 1;
  145. }
  146. /* Retrieves a hash element.
  147. *
  148. * @unittest: 1603
  149. */
  150. void *
  151. Curl_hash_pick(struct Curl_hash *h, void *key, size_t key_len)
  152. {
  153. struct Curl_llist_element *le;
  154. struct Curl_llist *l;
  155. DEBUGASSERT(h);
  156. if(h->table) {
  157. DEBUGASSERT(h->slots);
  158. l = FETCH_LIST(h, key, key_len);
  159. for(le = l->head; le; le = le->next) {
  160. struct Curl_hash_element *he = le->ptr;
  161. if(h->comp_func(he->key, he->key_len, key, key_len)) {
  162. return he->ptr;
  163. }
  164. }
  165. }
  166. return NULL;
  167. }
  168. #if defined(DEBUGBUILD) && defined(AGGRESSIVE_TEST)
  169. void
  170. Curl_hash_apply(Curl_hash *h, void *user,
  171. void (*cb)(void *user, void *ptr))
  172. {
  173. struct Curl_llist_element *le;
  174. int i;
  175. for(i = 0; i < h->slots; ++i) {
  176. for(le = (h->table[i])->head;
  177. le;
  178. le = le->next) {
  179. Curl_hash_element *el = le->ptr;
  180. cb(user, el->ptr);
  181. }
  182. }
  183. }
  184. #endif
  185. /* Destroys all the entries in the given hash and resets its attributes,
  186. * prepping the given hash for [static|dynamic] deallocation.
  187. *
  188. * @unittest: 1305
  189. * @unittest: 1602
  190. * @unittest: 1603
  191. */
  192. void
  193. Curl_hash_destroy(struct Curl_hash *h)
  194. {
  195. if(h->table) {
  196. int i;
  197. for(i = 0; i < h->slots; ++i) {
  198. Curl_llist_destroy(&h->table[i], (void *) h);
  199. }
  200. Curl_safefree(h->table);
  201. }
  202. h->size = 0;
  203. h->slots = 0;
  204. }
  205. /* Removes all the entries in the given hash.
  206. *
  207. * @unittest: 1602
  208. */
  209. void
  210. Curl_hash_clean(struct Curl_hash *h)
  211. {
  212. Curl_hash_clean_with_criterium(h, NULL, NULL);
  213. }
  214. /* Cleans all entries that pass the comp function criteria. */
  215. void
  216. Curl_hash_clean_with_criterium(struct Curl_hash *h, void *user,
  217. int (*comp)(void *, void *))
  218. {
  219. struct Curl_llist_element *le;
  220. struct Curl_llist_element *lnext;
  221. struct Curl_llist *list;
  222. int i;
  223. if(!h || !h->table)
  224. return;
  225. for(i = 0; i < h->slots; ++i) {
  226. list = &h->table[i];
  227. le = list->head; /* get first list entry */
  228. while(le) {
  229. struct Curl_hash_element *he = le->ptr;
  230. lnext = le->next;
  231. /* ask the callback function if we shall remove this entry or not */
  232. if(!comp || comp(user, he->ptr)) {
  233. Curl_llist_remove(list, le, (void *) h);
  234. --h->size; /* one less entry in the hash now */
  235. }
  236. le = lnext;
  237. }
  238. }
  239. }
  240. size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num)
  241. {
  242. const char *key_str = (const char *) key;
  243. const char *end = key_str + key_length;
  244. size_t h = 5381;
  245. while(key_str < end) {
  246. h += h << 5;
  247. h ^= *key_str++;
  248. }
  249. return (h % slots_num);
  250. }
  251. size_t Curl_str_key_compare(void *k1, size_t key1_len,
  252. void *k2, size_t key2_len)
  253. {
  254. if((key1_len == key2_len) && !memcmp(k1, k2, key1_len))
  255. return 1;
  256. return 0;
  257. }
  258. void Curl_hash_start_iterate(struct Curl_hash *hash,
  259. struct Curl_hash_iterator *iter)
  260. {
  261. iter->hash = hash;
  262. iter->slot_index = 0;
  263. iter->current_element = NULL;
  264. }
  265. struct Curl_hash_element *
  266. Curl_hash_next_element(struct Curl_hash_iterator *iter)
  267. {
  268. struct Curl_hash *h = iter->hash;
  269. if(!h->table)
  270. return NULL; /* empty hash, nothing to return */
  271. /* Get the next element in the current list, if any */
  272. if(iter->current_element)
  273. iter->current_element = iter->current_element->next;
  274. /* If we have reached the end of the list, find the next one */
  275. if(!iter->current_element) {
  276. int i;
  277. for(i = iter->slot_index; i < h->slots; i++) {
  278. if(h->table[i].head) {
  279. iter->current_element = h->table[i].head;
  280. iter->slot_index = i + 1;
  281. break;
  282. }
  283. }
  284. }
  285. if(iter->current_element) {
  286. struct Curl_hash_element *he = iter->current_element->ptr;
  287. return he;
  288. }
  289. iter->current_element = NULL;
  290. return NULL;
  291. }
  292. #if 0 /* useful function for debugging hashes and their contents */
  293. void Curl_hash_print(struct Curl_hash *h,
  294. void (*func)(void *))
  295. {
  296. struct Curl_hash_iterator iter;
  297. struct Curl_hash_element *he;
  298. int last_index = -1;
  299. if(!h)
  300. return;
  301. fprintf(stderr, "=Hash dump=\n");
  302. Curl_hash_start_iterate(h, &iter);
  303. he = Curl_hash_next_element(&iter);
  304. while(he) {
  305. if(iter.slot_index != last_index) {
  306. fprintf(stderr, "index %d:", iter.slot_index);
  307. if(last_index >= 0) {
  308. fprintf(stderr, "\n");
  309. }
  310. last_index = iter.slot_index;
  311. }
  312. if(func)
  313. func(he->ptr);
  314. else
  315. fprintf(stderr, " [%p]", (void *)he->ptr);
  316. he = Curl_hash_next_element(&iter);
  317. }
  318. fprintf(stderr, "\n");
  319. }
  320. #endif