37727cd2c02fe22ce401f180e03782002f9615d9
   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.