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_next(const struct hashmap *map, const void *entry)`::
 122
 123         Returns the next equal hashmap entry, or NULL if not found. This can be
 124         used to iterate over duplicate entries (see `hashmap_add`).
 125 +
 126 `map` is the hashmap structure.
 127 +
 128 `entry` is the hashmap_entry to start the search from, obtained via a previous
 129 call to `hashmap_get` or `hashmap_get_next`.
 130
 131 `void hashmap_add(struct hashmap *map, void *entry)`::
 132
 133         Adds a hashmap entry. This allows to add duplicate entries (i.e.
 134         separate values with the same key according to hashmap_cmp_fn).
 135 +
 136 `map` is the hashmap structure.
 137 +
 138 `entry` is the entry to add.
 139
 140 `void *hashmap_put(struct hashmap *map, void *entry)`::
 141
 142         Adds or replaces a hashmap entry. If the hashmap contains duplicate
 143         entries equal to the specified entry, only one of them will be replaced.
 144 +
 145 `map` is the hashmap structure.
 146 +
 147 `entry` is the entry to add or replace.
 148 +
 149 Returns the replaced entry, or NULL if not found (i.e. the entry was added).
 150
 151 `void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`::
 152
 153         Removes a hashmap entry matching the specified key. If the hashmap
 154         contains duplicate entries equal to the specified key, only one of
 155         them will be removed.
 156 +
 157 `map` is the hashmap structure.
 158 +
 159 `key` is a hashmap_entry structure (or user data structure that starts with
 160 hashmap_entry) that has at least been initialized with the proper hash code
 161 (via `hashmap_entry_init`).
 162 +
 163 If an entry with matching hash code is found, `key` and `keydata` are
 164 passed to `hashmap_cmp_fn` to decide whether the entry matches the key.
 165 +
 166 Returns the removed entry, or NULL if not found.
 167
 168 `void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`::
 169 `void *hashmap_iter_next(struct hashmap_iter *iter)`::
 170 `void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`::
 171
 172         Used to iterate over all entries of a hashmap.
 173 +
 174 `hashmap_iter_init` initializes a `hashmap_iter` structure.
 175 +
 176 `hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no
 177 more entries.
 178 +
 179 `hashmap_iter_first` is a combination of both (i.e. initializes the iterator
 180 and returns the first entry, if any).
 181
 182 Usage example
 183 -------------
 184
 185 Here's a simple usage example that maps long keys to double values.
 186 ------------
 187 struct hashmap map;
 188
 189 struct long2double {
 190         struct hashmap_entry ent; /* must be the first member! */
 191         long key;
 192         double value;
 193 };
 194
 195 static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused)
 196 {
 197         return !(e1->key == e2->key);
 198 }
 199
 200 void long2double_init(void)
 201 {
 202         hashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0);
 203 }
 204
 205 void long2double_free(void)
 206 {
 207         hashmap_free(&map, 1);
 208 }
 209
 210 static struct long2double *find_entry(long key)
 211 {
 212         struct long2double k;
 213         hashmap_entry_init(&k, memhash(&key, sizeof(long)));
 214         k.key = key;
 215         return hashmap_get(&map, &k, NULL);
 216 }
 217
 218 double get_value(long key)
 219 {
 220         struct long2double *e = find_entry(key);
 221         return e ? e->value : 0;
 222 }
 223
 224 void set_value(long key, double value)
 225 {
 226         struct long2double *e = find_entry(key);
 227         if (!e) {
 228                 e = malloc(sizeof(struct long2double));
 229                 hashmap_entry_init(e, memhash(&key, sizeof(long)));
 230                 e->key = key;
 231                 hashmap_add(&map, e);
 232         }
 233         e->value = value;
 234 }
 235 ------------
 236
 237 Using variable-sized keys
 238 -------------------------
 239
 240 The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary
 241 `hashmap_entry` structure as key to find the correct entry. If the key data is
 242 variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable
 243 to create a full-fledged entry structure on the heap and copy all the key data
 244 into the structure.
 245
 246 In this case, the `keydata` parameter can be used to pass
 247 variable-sized key data directly to the comparison function, and the `key`
 248 parameter can be a stripped-down, fixed size entry structure allocated on the
 249 stack.
 250
 251 See test-hashmap.c for an example using arbitrary-length strings as keys.