1<!-- 2Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al. 3 4SPDX-License-Identifier: curl 5--> 6 7# `hash` 8 9 #include "hash.h" 10 11This is the internal module for doing hash tables. A hash table uses a hash 12function to compute an index. On each index there is a separate linked list of 13entries. 14 15Create a hash table. Add items. Retrieve items. Remove items. Destroy table. 16 17## `Curl_hash_init` 18 19~~~c 20void Curl_hash_init(struct Curl_hash *h, 21 size_t slots, 22 hash_function hfunc, 23 comp_function comparator, 24 Curl_hash_dtor dtor); 25~~~ 26 27The call initializes a `struct Curl_hash`. 28 29- `slots` is the number of entries to create in the hash table. Larger is 30 better (faster lookups) but also uses more memory. 31- `hfunc` is a function pointer to a function that returns a `size_t` value as 32 a checksum for an entry in this hash table. Ideally, it returns a unique 33 value for every entry ever added to the hash table, but hash collisions are 34 handled. 35- `comparator` is a function pointer to a function that compares two hash 36 table entries. It should return non-zero if the compared items are 37 identical. 38- `dtor` is a function pointer to a destructor called when an entry is removed 39 from the table 40 41## `Curl_hash_add` 42 43~~~c 44void * 45Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p) 46~~~ 47 48This call adds an entry to the hash. `key` points to the hash key and 49`key_len` is the length of the hash key. `p` is a custom pointer. 50 51If there already was a match in the hash, that data is replaced with this new 52entry. 53 54This function also lazily allocates the table if needed, as it is not done in 55the `Curl_hash_init` function. 56 57Returns NULL on error, otherwise it returns a pointer to `p`. 58 59## `Curl_hash_add2` 60 61~~~c 62void *Curl_hash_add2(struct Curl_hash *h, void *key, size_t key_len, void *p, 63 Curl_hash_elem_dtor dtor) 64~~~ 65 66This works like `Curl_hash_add` but has an extra argument: `dtor`, which is a 67destructor call for this specific entry. When this entry is removed, this 68function is called instead of the function stored for the whole hash table. 69 70## `Curl_hash_delete` 71 72~~~c 73int Curl_hash_delete(struct Curl_hash *h, void *key, size_t key_len); 74~~~ 75 76This function removes an entry from the hash table. If successful, it returns 77zero. If the entry was not found, it returns 1. 78 79## `Curl_hash_pick` 80 81~~~c 82void *Curl_hash_pick(struct Curl_hash *h, void *key, size_t key_len); 83~~~ 84 85If there is an entry in the hash that matches the given `key` with size of 86`key_len`, that its custom pointer is returned. The pointer that was called 87`p` when the entry was added. 88 89It returns NULL if there is no matching entry in the hash. 90 91## `Curl_hash_destroy` 92 93~~~c 94void Curl_hash_destroy(struct Curl_hash *h); 95~~~ 96 97This function destroys a hash and cleanups up all its related data. Calling it 98multiple times is fine. 99 100## `Curl_hash_clean` 101 102~~~c 103void Curl_hash_clean(struct Curl_hash *h); 104~~~ 105 106This function removes all the entries in the given hash. 107 108## `Curl_hash_clean_with_criterium` 109 110~~~c 111void 112Curl_hash_clean_with_criterium(struct Curl_hash *h, void *user, 113 int (*comp)(void *, void *)) 114~~~ 115 116This function removes all the entries in the given hash that matches the 117criterion. The provided `comp` function determines if the criteria is met by 118returning non-zero. 119 120## `Curl_hash_count` 121 122~~~c 123size_t Curl_hash_count(struct Curl_hash *h) 124~~~ 125 126Returns the number of entries stored in the hash. 127 128## `Curl_hash_start_iterate` 129 130~~~c 131void Curl_hash_start_iterate(struct Curl_hash *hash, 132 struct Curl_hash_iterator *iter): 133~~~ 134 135This function initializes a `struct Curl_hash_iterator` that `iter` points to. 136It can then be used to iterate over all the entries in the hash. 137 138## `Curl_hash_next_element` 139 140~~~c 141struct Curl_hash_element * 142Curl_hash_next_element(struct Curl_hash_iterator *iter); 143~~~ 144 145Given the iterator `iter`, this function returns a pointer to the next hash 146entry if there is one, or NULL if there is no more entries. 147 148Called repeatedly, it iterates over all the entries in the hash table. 149 150Note: it only guarantees functionality if the hash table remains untouched 151during its iteration. 152 153# `curl_off_t` dedicated hash functions 154 155## `Curl_hash_offt_init` 156 157~~~c 158void Curl_hash_offt_init(struct Curl_hash *h, 159 size_t slots, 160 Curl_hash_dtor dtor); 161~~~ 162 163Initializes a hash table for `curl_off_t` values. Pass in desired number of 164`slots` and `dtor` function. 165 166## `Curl_hash_offt_set` 167 168~~~c 169void *Curl_hash_offt_set(struct Curl_hash *h, curl_off_t id, void *elem); 170~~~ 171 172Associate a custom `elem` pointer with the given `id`. 173 174## `Curl_hash_offt_remove` 175 176~~~c 177int Curl_hash_offt_remove(struct Curl_hash *h, curl_off_t id); 178~~~ 179 180Remove the `id` from the hash. 181 182## `Curl_hash_offt_get` 183 184~~~c 185void *Curl_hash_offt_get(struct Curl_hash *h, curl_off_t id); 186~~~ 187 188Get the pointer associated with the specified `id`. 189
