1hashmap API 2=========== 3 4The hashmap API is a generic implementation of hash-based key-value mappings. 5 6Data Structures 7--------------- 8 9`struct hashmap`:: 10 11 The hash table structure. 12+ 13The `size` member keeps track of the total number of entries. The `cmpfn` 14member is a function used to compare two entries for equality. The `table` and 15`tablesize` members store the hash table and its size, respectively. 16 17`struct hashmap_entry`:: 18 19 An opaque structure representing an entry in the hash table, which must 20 be used as first member of user data structures. Ideally it should be 21 followed by an int-sized member to prevent unused memory on 64-bit 22 systems due to alignment. 23+ 24The `hash` member is the entry's hash code and the `next` member points to the 25next entry in case of collisions (i.e. if multiple entries map to the same 26bucket). 27 28`struct hashmap_iter`:: 29 30 An iterator structure, to be used with hashmap_iter_* functions. 31 32Types 33----- 34 35`int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`:: 36 37 User-supplied function to test two hashmap entries for equality. Shall 38 return 0 if the entries are equal. 39+ 40This function is always called with non-NULL `entry` / `entry_or_key` 41parameters that have the same hash code. When looking up an entry, the `key` 42and `keydata` parameters to hashmap_get and hashmap_remove are always passed 43as second and third argument, respectively. Otherwise, `keydata` is NULL. 44 45Functions 46--------- 47 48`unsigned int strhash(const char *buf)`:: 49`unsigned int strihash(const char *buf)`:: 50`unsigned int memhash(const void *buf, size_t len)`:: 51`unsigned int memihash(const void *buf, size_t len)`:: 52 53 Ready-to-use hash functions for strings, using the FNV-1 algorithm (see 54 http://www.isthe.com/chongo/tech/comp/fnv). 55+ 56`strhash` and `strihash` take 0-terminated strings, while `memhash` and 57`memihash` operate on arbitrary-length memory. 58+ 59`strihash` and `memihash` are case insensitive versions. 60 61`unsigned int sha1hash(const unsigned char *sha1)`:: 62 63 Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code 64 for use in hash tables. Cryptographic hashes are supposed to have 65 uniform distribution, so in contrast to `memhash()`, this just copies 66 the first `sizeof(int)` bytes without shuffling any bits. Note that 67 the results will be different on big-endian and little-endian 68 platforms, so they should not be stored or transferred over the net. 69 70`void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)`:: 71 72 Initializes a hashmap structure. 73+ 74`map` is the hashmap to initialize. 75+ 76The `equals_function` can be specified to compare two entries for equality. 77If NULL, entries are considered equal if their hash codes are equal. 78+ 79If the total number of entries is known in advance, the `initial_size` 80parameter may be used to preallocate a sufficiently large table and thus 81prevent expensive resizing. If 0, the table is dynamically resized. 82 83`void hashmap_free(struct hashmap *map, int free_entries)`:: 84 85 Frees a hashmap structure and allocated memory. 86+ 87`map` is the hashmap to free. 88+ 89If `free_entries` is true, each hashmap_entry in the map is freed as well 90(using stdlib's free()). 91 92`void hashmap_entry_init(void *entry, unsigned int hash)`:: 93 94 Initializes a hashmap_entry structure. 95+ 96`entry` points to the entry to initialize. 97+ 98`hash` is the hash code of the entry. 99 100`void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`:: 101 102 Returns the hashmap entry for the specified key, or NULL if not found. 103+ 104`map` is the hashmap structure. 105+ 106`key` is a hashmap_entry structure (or user data structure that starts with 107hashmap_entry) that has at least been initialized with the proper hash code 108(via `hashmap_entry_init`). 109+ 110If an entry with matching hash code is found, `key` and `keydata` are passed 111to `hashmap_cmp_fn` to decide whether the entry matches the key. 112 113`void *hashmap_get_next(const struct hashmap *map, const void *entry)`:: 114 115 Returns the next equal hashmap entry, or NULL if not found. This can be 116 used to iterate over duplicate entries (see `hashmap_add`). 117+ 118`map` is the hashmap structure. 119+ 120`entry` is the hashmap_entry to start the search from, obtained via a previous 121call to `hashmap_get` or `hashmap_get_next`. 122 123`void hashmap_add(struct hashmap *map, void *entry)`:: 124 125 Adds a hashmap entry. This allows to add duplicate entries (i.e. 126 separate values with the same key according to hashmap_cmp_fn). 127+ 128`map` is the hashmap structure. 129+ 130`entry` is the entry to add. 131 132`void *hashmap_put(struct hashmap *map, void *entry)`:: 133 134 Adds or replaces a hashmap entry. If the hashmap contains duplicate 135 entries equal to the specified entry, only one of them will be replaced. 136+ 137`map` is the hashmap structure. 138+ 139`entry` is the entry to add or replace. 140+ 141Returns the replaced entry, or NULL if not found (i.e. the entry was added). 142 143`void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`:: 144 145 Removes a hashmap entry matching the specified key. If the hashmap 146 contains duplicate entries equal to the specified key, only one of 147 them will be removed. 148+ 149`map` is the hashmap structure. 150+ 151`key` is a hashmap_entry structure (or user data structure that starts with 152hashmap_entry) that has at least been initialized with the proper hash code 153(via `hashmap_entry_init`). 154+ 155If an entry with matching hash code is found, `key` and `keydata` are 156passed to `hashmap_cmp_fn` to decide whether the entry matches the key. 157+ 158Returns the removed entry, or NULL if not found. 159 160`void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`:: 161`void *hashmap_iter_next(struct hashmap_iter *iter)`:: 162`void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`:: 163 164 Used to iterate over all entries of a hashmap. 165+ 166`hashmap_iter_init` initializes a `hashmap_iter` structure. 167+ 168`hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no 169more entries. 170+ 171`hashmap_iter_first` is a combination of both (i.e. initializes the iterator 172and returns the first entry, if any). 173 174Usage example 175------------- 176 177Here's a simple usage example that maps long keys to double values. 178------------ 179struct hashmap map; 180 181struct long2double { 182 struct hashmap_entry ent; /* must be the first member! */ 183 long key; 184 double value; 185}; 186 187static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused) 188{ 189 return !(e1->key == e2->key); 190} 191 192void long2double_init(void) 193{ 194 hashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0); 195} 196 197void long2double_free(void) 198{ 199 hashmap_free(&map, 1); 200} 201 202static struct long2double *find_entry(long key) 203{ 204 struct long2double k; 205 hashmap_entry_init(&k, memhash(&key, sizeof(long))); 206 k.key = key; 207 return hashmap_get(&map, &k, NULL); 208} 209 210double get_value(long key) 211{ 212 struct long2double *e = find_entry(key); 213 return e ? e->value : 0; 214} 215 216void set_value(long key, double value) 217{ 218 struct long2double *e = find_entry(key); 219 if (!e) { 220 e = malloc(sizeof(struct long2double)); 221 hashmap_entry_init(e, memhash(&key, sizeof(long))); 222 e->key = key; 223 hashmap_add(&map, e); 224 } 225 e->value = value; 226} 227------------ 228 229Using variable-sized keys 230------------------------- 231 232The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary 233`hashmap_entry` structure as key to find the correct entry. If the key data is 234variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable 235to create a full-fledged entry structure on the heap and copy all the key data 236into the structure. 237 238In this case, the `keydata` parameter can be used to pass 239variable-sized key data directly to the comparison function, and the `key` 240parameter can be a stripped-down, fixed size entry structure allocated on the 241stack. 242 243See test-hashmap.c for an example using arbitrary-length strings as keys.