trAvis - MANAGER

Edit File: api-hashmap.txt

hashmap API =========== The hashmap API is a generic implementation of hash-based key-value mappings. Data Structures --------------- `struct hashmap`:: The hash table structure. + The `size` member keeps track of the total number of entries. The `cmpfn` member is a function used to compare two entries for equality. The `table` and `tablesize` members store the hash table and its size, respectively. `struct hashmap_entry`:: An opaque structure representing an entry in the hash table, which must be used as first member of user data structures. Ideally it should be followed by an int-sized member to prevent unused memory on 64-bit systems due to alignment. + The `hash` member is the entry's hash code and the `next` member points to the next entry in case of collisions (i.e. if multiple entries map to the same bucket). `struct hashmap_iter`:: An iterator structure, to be used with hashmap_iter_* functions. Types ----- `int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`:: User-supplied function to test two hashmap entries for equality. Shall return 0 if the entries are equal. + This function is always called with non-NULL `entry` / `entry_or_key` parameters that have the same hash code. When looking up an entry, the `key` and `keydata` parameters to hashmap_get and hashmap_remove are always passed as second and third argument, respectively. Otherwise, `keydata` is NULL. Functions --------- `unsigned int strhash(const char *buf)`:: `unsigned int strihash(const char *buf)`:: `unsigned int memhash(const void *buf, size_t len)`:: `unsigned int memihash(const void *buf, size_t len)`:: Ready-to-use hash functions for strings, using the FNV-1 algorithm (see http://www.isthe.com/chongo/tech/comp/fnv). + `strhash` and `strihash` take 0-terminated strings, while `memhash` and `memihash` operate on arbitrary-length memory. + `strihash` and `memihash` are case insensitive versions. `void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)`:: Initializes a hashmap structure. + `map` is the hashmap to initialize. + The `equals_function` can be specified to compare two entries for equality. If NULL, entries are considered equal if their hash codes are equal. + If the total number of entries is known in advance, the `initial_size` parameter may be used to preallocate a sufficiently large table and thus prevent expensive resizing. If 0, the table is dynamically resized. `void hashmap_free(struct hashmap *map, int free_entries)`:: Frees a hashmap structure and allocated memory. + `map` is the hashmap to free. + If `free_entries` is true, each hashmap_entry in the map is freed as well (using stdlib's free()). `void hashmap_entry_init(void *entry, int hash)`:: Initializes a hashmap_entry structure. + `entry` points to the entry to initialize. + `hash` is the hash code of the entry. `void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`:: Returns the hashmap entry for the specified key, or NULL if not found. + `map` is the hashmap structure. + `key` is a hashmap_entry structure (or user data structure that starts with hashmap_entry) that has at least been initialized with the proper hash code (via `hashmap_entry_init`). + If an entry with matching hash code is found, `key` and `keydata` are passed to `hashmap_cmp_fn` to decide whether the entry matches the key. `void *hashmap_get_from_hash(const struct hashmap *map, unsigned int hash, const void *keydata)`:: Returns the hashmap entry for the specified hash code and key data, or NULL if not found. + `map` is the hashmap structure. + `hash` is the hash code of the entry to look up. + If an entry with matching hash code is found, `keydata` is passed to `hashmap_cmp_fn` to decide whether the entry matches the key. The `entry_or_key` parameter points to a bogus hashmap_entry structure that should not be used in the comparison. `void *hashmap_get_next(const struct hashmap *map, const void *entry)`:: Returns the next equal hashmap entry, or NULL if not found. This can be used to iterate over duplicate entries (see `hashmap_add`). + `map` is the hashmap structure. + `entry` is the hashmap_entry to start the search from, obtained via a previous call to `hashmap_get` or `hashmap_get_next`. `void hashmap_add(struct hashmap *map, void *entry)`:: Adds a hashmap entry. This allows to add duplicate entries (i.e. separate values with the same key according to hashmap_cmp_fn). + `map` is the hashmap structure. + `entry` is the entry to add. `void *hashmap_put(struct hashmap *map, void *entry)`:: Adds or replaces a hashmap entry. If the hashmap contains duplicate entries equal to the specified entry, only one of them will be replaced. + `map` is the hashmap structure. + `entry` is the entry to add or replace. + Returns the replaced entry, or NULL if not found (i.e. the entry was added). `void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`:: Removes a hashmap entry matching the specified key. If the hashmap contains duplicate entries equal to the specified key, only one of them will be removed. + `map` is the hashmap structure. + `key` is a hashmap_entry structure (or user data structure that starts with hashmap_entry) that has at least been initialized with the proper hash code (via `hashmap_entry_init`). + If an entry with matching hash code is found, `key` and `keydata` are passed to `hashmap_cmp_fn` to decide whether the entry matches the key. + Returns the removed entry, or NULL if not found. `void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`:: `void *hashmap_iter_next(struct hashmap_iter *iter)`:: `void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`:: Used to iterate over all entries of a hashmap. + `hashmap_iter_init` initializes a `hashmap_iter` structure. + `hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no more entries. + `hashmap_iter_first` is a combination of both (i.e. initializes the iterator and returns the first entry, if any). Usage example ------------- Here's a simple usage example that maps long keys to double values. [source,c] ------------ struct hashmap map; struct long2double { struct hashmap_entry ent; /* must be the first member! */ long key; double value; }; static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused) { return !(e1->key == e2->key); } void long2double_init(void) { hashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0); } void long2double_free(void) { hashmap_free(&map, 1); } static struct long2double *find_entry(long key) { struct long2double k; hashmap_entry_init(&k, memhash(&key, sizeof(long))); k.key = key; return hashmap_get(&map, &k, NULL); } double get_value(long key) { struct long2double *e = find_entry(key); return e ? e->value : 0; } void set_value(long key, double value) { struct long2double *e = find_entry(key); if (!e) { e = malloc(sizeof(struct long2double)); hashmap_entry_init(e, memhash(&key, sizeof(long))); e->key = key; hashmap_add(&map, e); } e->value = value; } ------------ Using variable-sized keys ------------------------- The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary `hashmap_entry` structure as key to find the correct entry. If the key data is variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable to create a full-fledged entry structure on the heap and copy all the key data into the structure. In this case, the `keydata` parameter can be used to pass variable-sized key data directly to the comparison function, and the `key` parameter can be a stripped-down, fixed size entry structure allocated on the stack. See test-hashmap.c for an example using arbitrary-length strings as keys.