hash.c 9.1 KB

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