7. Hashmap

A hashmap(3m) object associates keys with data pointers. Large numbers of elements may be stored and retrieved efficiently.

Memory management of keys and data pointers is the resposibility of the user although del_fn function pointers (defined in allocator(3m)) may be specified with some hashmap functions to assist the user with this task.

7.1. Definitions

Hashmap Definitions 


  typedef unsigned long (*hash_fn)(const void *object, void *context);
  typedef int (*cmp_fn)(const void *object1, const void *object2, void *context);
  
  unsigned long hash_text(const void *text, void *context);
  unsigned long cmp_text(const void *text1, const void *text2, void *context);
The hash_text function is a suitable hash_fn for character strings. This function is actually a macro for either hash_str or hash_wcs that accept multi-byte or wide character strings depending on wheather or not USE_WCHAR is defined.

The cmp_text function is a suitable cmp_fn for character strings. This function is actually a macro for either cmp_str or cmp_wcs that accept multi-byte or wide character strings depending on wheather or not USE_WCHAR is defined.

7.2. Memory management functions

These functions should be used to create and destroy hashmap objects.

The hashmap_init function
Synopsis 

  #include <mba/hashmap.h>
  int hashmap_init(struct hashmap *h,
           unsigned int load_factor,
           hash_fn hash,
           cmp_fn cmp,
           void *context,
           struct allocator *al);
Description
The hashmap_init function initializes the memory at h as a hashmap with no elements. The load_factor parameter must be an integer between 1 and 100 indicating when the map should be resized. If a value of 0 is specified, the default value of 75 will be used meaning the map will be increased when 75 of every 100 spaces for elements are occupied.

If the hash parameter is not NULL it will be used to generate a hash value given a key and the specified context object. Given a set of keys the hash function should generate an even distribution of values. If the hash parameter is NULL a key's memory address will be used as it's hash value.

If the cmp parameter is not NULL it will used to compare two keys for equality. This function should return 0 if two keys are equal and non-zero if they are not. If the cmp parameter is NULL the memory addresses of the two keys will be compared.

The al parameter is an allocator(3m) from which all memory associated with this hashmap should be allocated. As with the allocator functions, a NULL allocator indicates the stdlib_allocator should be used.

The following example illustrates how to initialize a hashmap and use it to store the object data associated with the character string "name". 

  struct hashmap hm;
  struct foo data, *out;
  hashmap_init(&hm,
  	0,                             /* default load factor of 75 */
  	hash_text,                    /* default text hash function */
  	cmp_text,                  /* default text compare function */
  	NULL, /* hash_fn and cmp_fn function do not require context */
  	NULL);                          /* use the stdlib_allocator */
  hashmap_put(&hm, "name", &data);
  out = hashmap_get(&hm, "name");
  /* out now points to data */
Returns
The hashmap_init function returns 0 on success or -1 for failure in which case errno will be set to an appropriate value.

The hashmap_deinit function
Synopsis 

  #include <mba/hashmap.h>
  int hashmap_deinit(struct hashmap *h,
           del_fn key_del,
           del_fn data_del,
           void *context);
Description
The hashmap_deinit function deinitializes the hashmap h. If the key_del or data_del functions are not NULL they will be called with the context object and each key and/or data object in the map. Any memory associated with the hashmap will be released.
Returns
The hashmap_deinit function returns 0 on success or -1 for failure in which case errno will be set to an appropriate value.

The hashmap_new function
Synopsis 

  #include <mba/hashmap.h>
  struct hashmap *hashmap_new(hash_fn hash, cmp_fn cmp, void *context, struct allocator *al);
Description
The hashmap_new function allocates memory for a new hashmap object and initializes it with hashmap_init
Returns
The hashmap_new function returns a new struct hashmap * object that contains no elements or NULL if the operation failed in which case errno will be set to an appropriate value.

The hashmap_del function
Synopsis 

  #include <mba/hashmap.h>
  int hashmap_del(struct hashmap *h, del_fn key_del, del_fn data_del, void *context);
Description
The hashmap_del function deinitializes the hashmap h with the hashmap_deinit function and then releases the h object itself.
Returns
The hashmap_del function returns 0 on success or -1 for failure in which case errno will be set to an appropriate value.

The hashmap_clear function
Synopsis 

  #include <mba/hashmap.h>
  int hashmap_clear(struct hashmap *h, del_fn key_del, del_fn data_del, void *context);
Description
The hashmap_clear function clears all elements from the hashmap h. If the key_del or data_del functions are not NULL they will be called with the context object and each key and/or data object in the map.
Returns
The hashmap_clear function returns 0 on success or -1 for failure in which case errno will be set to an appropriate value.

The hashmap_clean function
Synopsis 

  #include <mba/hashmap.h>
  int hashmap_clean(struct hashmap *h);
Description
The hashmap_clean function will release excess memory allocated by the hashmap h. See the allocator_set_reclaim function.
Returns
The hashmap_clean function returns the number of unused elements released (possibly 0) or -1 if an error occured in which case errno will be set to an appropriate value.

7.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 with the key key. If an element with the same key already exists in the map, -1 will be returned and errno will be set to EEXIST. If another error occurs, -1 will be returned and errno will be set to an appropriate value.

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 with the key key.
Returns
The hashmap_get function returns the data pointer being retrieved or NULL if the element was not found. NULL 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 should adding or removing data cause the table to be resized, not all keys may be enumerated and some keys may be returned more than once. Therefore, to make multiple modifications during the enumeration it may be desirable to first create a snapshot of the keys in an array or list.

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>
  int hashmap_remove(struct hashmap *h, void **key, void **data);
Description
The hashmap_remove function removes the element associated with key from the hashmap h and stores pointers to the original key and data in the provided key and data parameters.

The following is an example of removing an element from a hashmap. 

  char *key = name;
  struct foo *data;
  hashmap_remove(hm, (void **)&key, (void **)&data);
  /* free data if necessary */
Returns
The hashmap_remove function returns 0 on success or -1 for failure in which case errno will be set to an appropriate value.

Copyright 2004 Michael B. Allen <mba2000 ioplex.com>