5. Hashmap
A hashmap(3m) object associates keys with pointers to data
objects. Large numbers of elements may be stored and retrieved efficiently.
It is vital that the free_key_fn and free_data_fn
parameters are correct. If memory management of all keys and data is
handled externally from the hashmap both function pointers must be
NULL. There is only one appropriate pair of parameters for each
scenario. Choosing incorrectly will result in a memory leak or undefined
behavior.
Keys are only compared by their hash values. Keys that collide during a put
will first be remove and called with free_key_fn on the existing
key and free_data_fn on it's data pointer. For this reason hash
functions must be chosen carefully. Please note, the hash_string
function can return the same hash value for different strings in rare cases
(e.g. the two character strings 'X"' and 'WA' both hash to the value 2762).
5.1. Definitions
Hashmap Definitions
Synopsis
#include <mba/hashmap.h>
HASHMAP_SMALL 17
HASHMAP_MEDIUM 701
HASHMAP_LARGE 8191
struct hashmap;
unsigned int hash_string(const void *s);
5.2. Memory management functions
These functions should be used to create and destroy hashmap objects.
The hashmap_new function
Synopsis
#include <mba/hashmap.h>
struct hashmap *hashmap_new(unsigned int size,
unsigned int (*hash_fn)(const void *),
void (*free_key_fnsize)(void *),
void (*free_data_fn)(void *));
Description
Create a new hashmap. The maximum number of elements that can be stored in a hashmap is less than size * size. The macros HASHMAP_SMALL, HASHMAP_MEDIUM, and HASHMAP_LARGE are suitable size values (or choose 1/10th max elements and round up to prime number). The hash_fn parameter should be a pointer to a function that generates a unique integer value for each key to be stored in the hashmap. If the hash_fn parameter is NULL the key's address in memory will be used. The hash_string function is a suitable hash_fn for most strings. If the free_key_fn or free_data_fn parameters are not NULL they will be called with each key or data object that is removed from the map.
Returns
The hashmap_new function returns a new struct hashmap * object that contains no elements.
The hashmap_del function
Synopsis
#include <mba/hashmap.h>
void hashmap_del(struct hashmap *h);
Description
Delete a hashmap. If the free_key_fn or free_data_fn functions are not NULL they will be called for each remaining element.
5.3. Map functions
The hashmap_put function
Synopsis
#include <mba/hashmap.h>
int hashmap_put(struct hashmap *h, void *key, void *data);
Description
Put a data pointer into the map by key key. If an element with the same key hash value already exists in the map it will be removed in which case the free_key_fn and free_data_fn functions will be called with it provided they are not NULL.
Returns
The hashmap_put function returns -1 and sets errno on error or 0 if the element was successfully placed into the hashmap.
The hashmap_get function
Synopsis
#include <mba/hashmap.h>
void *hashmap_get(const struct hashmap *h, const void *key);
Description
Retrieve a data pointer from the map by it's key.
Returns
The hashmap_get function returns the data pointer being retrieved or NULL if the element was not found. A null pointer will also be returned if the h or key parameters are NULL but this function does not set errno to any value.
The hashmap_is_empty function
Synopsis
#include <mba/hashmap.h>
int hashmap_is_empty(struct hashmap *h);
Description
Returns 1 if the map is empty and 0 otherwise.
The hashmap_size function
Synopsis
#include <mba/hashmap.h>
unsigned int hashmap_size(struct hashmap *h);
Description
Returns the number of data pointers in the map.
Returns
The hashmap_size function returns the number of data pointers in the map. If h is NULL, zero is returned.
The hashmap_iterate function
Synopsis
#include <mba/hashmap.h>
void hashmap_iterate(void *h, iter_t *iter);
Description
Enumerate each key in the map. The hashmap_iterate function initializes the iter object to point to
the beginning of the map. With each call to hashmap_next, a key will be returned.
When all keys have been enumerated, hashmap_next will return NULL. Keys
are not returned in any particular order. Modifying the map during the enumeration is permitted however keys added may or may not returned in subsequent calls to hashmap_next.
The hashmap_next function
Synopsis
#include <mba/hashmap.h>
void *hashmap_next(void *h, iter_t *iter);
Returns
The hashmap_next function returns the next key in the map or NULL if all keys have been enumerated.
The hashmap_remove function
Synopsis
#include <mba/hashmap.h>
void *hashmap_remove(struct hashmap *h, const void *key);
Description
Remove a data pointer from the map by it's key. If the free_key_fn function is not NULL it will be called on the original key used to store the data pointer.
Returns
The hashmap_remove function returns the data pointer that was removed.
Copyright 2002 Michael B. Allen <mballen@erols.com>