Documentation/technical/api-hashmap.txt

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