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 The hashmap_entry structure does not hold references to external resources,
 109 and it is safe to just discard it once you are done with it (i.e. if
 110 your structure was allocated with xmalloc(), you can just free(3) it,
 111 and if it is on stack, you can just let it go out of scope).
 112
 113 `void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`::
 114
 115         Returns the hashmap entry for the specified key, or NULL if not found.
 116 +
 117 `map` is the hashmap structure.
 118 +
 119 `key` is a hashmap_entry structure (or user data structure that starts with
 120 hashmap_entry) that has at least been initialized with the proper hash code
 121 (via `hashmap_entry_init`).
 122 +
 123 If an entry with matching hash code is found, `key` and `keydata` are passed
 124 to `hashmap_cmp_fn` to decide whether the entry matches the key.
 125
 126 `void *hashmap_get_from_hash(const struct hashmap *map, unsigned int hash, const void *keydata)`::
 127
 128         Returns the hashmap entry for the specified hash code and key data,
 129         or NULL if not found.
 130 +
 131 `map` is the hashmap structure.
 132 +
 133 `hash` is the hash code of the entry to look up.
 134 +
 135 If an entry with matching hash code is found, `keydata` is passed to
 136 `hashmap_cmp_fn` to decide whether the entry matches the key. The
 137 `entry_or_key` parameter points to a bogus hashmap_entry structure that
 138 should not be used in the comparison.
 139
 140 `void *hashmap_get_next(const struct hashmap *map, const void *entry)`::
 141
 142         Returns the next equal hashmap entry, or NULL if not found. This can be
 143         used to iterate over duplicate entries (see `hashmap_add`).
 144 +
 145 `map` is the hashmap structure.
 146 +
 147 `entry` is the hashmap_entry to start the search from, obtained via a previous
 148 call to `hashmap_get` or `hashmap_get_next`.
 149
 150 `void hashmap_add(struct hashmap *map, void *entry)`::
 151
 152         Adds a hashmap entry. This allows to add duplicate entries (i.e.
 153         separate values with the same key according to hashmap_cmp_fn).
 154 +
 155 `map` is the hashmap structure.
 156 +
 157 `entry` is the entry to add.
 158
 159 `void *hashmap_put(struct hashmap *map, void *entry)`::
 160
 161         Adds or replaces a hashmap entry. If the hashmap contains duplicate
 162         entries equal to the specified entry, only one of them will be replaced.
 163 +
 164 `map` is the hashmap structure.
 165 +
 166 `entry` is the entry to add or replace.
 167 +
 168 Returns the replaced entry, or NULL if not found (i.e. the entry was added).
 169
 170 `void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`::
 171
 172         Removes a hashmap entry matching the specified key. If the hashmap
 173         contains duplicate entries equal to the specified key, only one of
 174         them will be removed.
 175 +
 176 `map` is the hashmap structure.
 177 +
 178 `key` is a hashmap_entry structure (or user data structure that starts with
 179 hashmap_entry) that has at least been initialized with the proper hash code
 180 (via `hashmap_entry_init`).
 181 +
 182 If an entry with matching hash code is found, `key` and `keydata` are
 183 passed to `hashmap_cmp_fn` to decide whether the entry matches the key.
 184 +
 185 Returns the removed entry, or NULL if not found.
 186
 187 `void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`::
 188 `void *hashmap_iter_next(struct hashmap_iter *iter)`::
 189 `void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`::
 190
 191         Used to iterate over all entries of a hashmap. Note that it is
 192         not safe to add or remove entries to the hashmap while
 193         iterating.
 194 +
 195 `hashmap_iter_init` initializes a `hashmap_iter` structure.
 196 +
 197 `hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no
 198 more entries.
 199 +
 200 `hashmap_iter_first` is a combination of both (i.e. initializes the iterator
 201 and returns the first entry, if any).
 202
 203 `const char *strintern(const char *string)`::
 204 `const void *memintern(const void *data, size_t len)`::
 205
 206         Returns the unique, interned version of the specified string or data,
 207         similar to the `String.intern` API in Java and .NET, respectively.
 208         Interned strings remain valid for the entire lifetime of the process.
 209 +
 210 Can be used as `[x]strdup()` or `xmemdupz` replacement, except that interned
 211 strings / data must not be modified or freed.
 212 +
 213 Interned strings are best used for short strings with high probability of
 214 duplicates.
 215 +
 216 Uses a hashmap to store the pool of interned strings.
 217
 218 Usage example
 219 -------------
 220
 221 Here's a simple usage example that maps long keys to double values.
 222 ------------
 223 struct hashmap map;
 224
 225 struct long2double {
 226         struct hashmap_entry ent; /* must be the first member! */
 227         long key;
 228         double value;
 229 };
 230
 231 static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused)
 232 {
 233         return !(e1->key == e2->key);
 234 }
 235
 236 void long2double_init(void)
 237 {
 238         hashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0);
 239 }
 240
 241 void long2double_free(void)
 242 {
 243         hashmap_free(&map, 1);
 244 }
 245
 246 static struct long2double *find_entry(long key)
 247 {
 248         struct long2double k;
 249         hashmap_entry_init(&k, memhash(&key, sizeof(long)));
 250         k.key = key;
 251         return hashmap_get(&map, &k, NULL);
 252 }
 253
 254 double get_value(long key)
 255 {
 256         struct long2double *e = find_entry(key);
 257         return e ? e->value : 0;
 258 }
 259
 260 void set_value(long key, double value)
 261 {
 262         struct long2double *e = find_entry(key);
 263         if (!e) {
 264                 e = malloc(sizeof(struct long2double));
 265                 hashmap_entry_init(e, memhash(&key, sizeof(long)));
 266                 e->key = key;
 267                 hashmap_add(&map, e);
 268         }
 269         e->value = value;
 270 }
 271 ------------
 272
 273 Using variable-sized keys
 274 -------------------------
 275
 276 The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary
 277 `hashmap_entry` structure as key to find the correct entry. If the key data is
 278 variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable
 279 to create a full-fledged entry structure on the heap and copy all the key data
 280 into the structure.
 281
 282 In this case, the `keydata` parameter can be used to pass
 283 variable-sized key data directly to the comparison function, and the `key`
 284 parameter can be a stripped-down, fixed size entry structure allocated on the
 285 stack.
 286
 287 See test-hashmap.c for an example using arbitrary-length strings as keys.