ucx
UAP Common Extensions
Data Structures | Macros | Typedefs | Functions
map.h File Reference

Hash map implementation. More...

#include "ucx.h"
#include "string.h"
#include "allocator.h"
#include <stdio.h>

Go to the source code of this file.

Data Structures

struct  UcxMap
 Structure for the UCX map. More...
 
struct  UcxKey
 Structure for a key of a UcxMap. More...
 
struct  UcxMapElement
 Structure for an element of a UcxMap. More...
 
struct  UcxMapIterator
 Structure for an iterator over a UcxMap. More...
 

Macros

#define UCX_MAP_FOREACH(key, value, iter)   for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);)
 Loop statement for UCX maps. More...
 
#define ucx_map_sstr_put(map, key, value)   ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value)
 Shorthand for putting data with a sstr_t key into the map. More...
 
#define ucx_map_cstr_put(map, key, value)   ucx_map_put(map, ucx_key((void*)key, strlen(key)), (void*)value)
 Shorthand for putting data with a C string key into the map. More...
 
#define ucx_map_int_put(map, key, value)   ucx_map_put(map, ucx_key((void*)&key, sizeof(key)), (void*)value)
 Shorthand for putting data with an integer key into the map. More...
 
#define ucx_map_sstr_get(map, key)   ucx_map_get(map, ucx_key(key.ptr, key.length))
 Shorthand for getting data from the map with a sstr_t key. More...
 
#define ucx_map_cstr_get(map, key)   ucx_map_get(map, ucx_key((void*)key, strlen(key)))
 Shorthand for getting data from the map with a C string key. More...
 
#define ucx_map_int_get(map, key)   ucx_map_get(map, ucx_key((void*)&key, sizeof(int)))
 Shorthand for getting data from the map with an integer key. More...
 
#define ucx_map_sstr_remove(map, key)   ucx_map_remove(map, ucx_key(key.ptr, key.length))
 Shorthand for removing data from the map with a sstr_t key. More...
 
#define ucx_map_cstr_remove(map, key)   ucx_map_remove(map, ucx_key((void*)key, strlen(key)))
 Shorthand for removing data from the map with a C string key. More...
 
#define ucx_map_int_remove(map, key)   ucx_map_remove(map, ucx_key((void*)&key, sizeof(key)))
 Shorthand for removing data from the map with an integer key. More...
 

Typedefs

typedef struct UcxMap UcxMap
 Type for the UCX map. More...
 
typedef struct UcxKey UcxKey
 Type for a key of a UcxMap. More...
 
typedef struct UcxMapElement UcxMapElement
 Type for an element of a UcxMap. More...
 
typedef struct UcxMapIterator UcxMapIterator
 Type for an iterator over a UcxMap. More...
 

Functions

UcxMapucx_map_new (size_t size)
 Creates a new hash map with the specified size. More...
 
UcxMapucx_map_new_a (UcxAllocator *allocator, size_t size)
 Creates a new hash map with the specified size using a UcxAllocator. More...
 
void ucx_map_free (UcxMap *map)
 Frees a hash map. More...
 
void ucx_map_free_content (UcxMap *map, ucx_destructor destr)
 Frees the contents of a hash map. More...
 
void ucx_map_clear (UcxMap *map)
 Clears a hash map. More...
 
int ucx_map_copy (UcxMap *from, UcxMap *to, copy_func fnc, void *data)
 Copies contents from a map to another map using a copy function. More...
 
UcxMapucx_map_clone (UcxMap *map, copy_func fnc, void *data)
 Clones the map and rehashes if necessary. More...
 
int ucx_map_rehash (UcxMap *map)
 Increases size of the hash map, if necessary. More...
 
int ucx_map_put (UcxMap *map, UcxKey key, void *value)
 Puts a key/value-pair into the map. More...
 
void * ucx_map_get (UcxMap *map, UcxKey key)
 Retrieves a value by using a key. More...
 
void * ucx_map_remove (UcxMap *map, UcxKey key)
 Removes a key/value-pair from the map by using the key. More...
 
UcxKey ucx_key (void *data, size_t len)
 Creates a UcxKey based on the given data. More...
 
int ucx_hash (const char *data, size_t len)
 Computes a murmur hash-2. More...
 
UcxMapIterator ucx_map_iterator (UcxMap *map)
 Creates an iterator for a map. More...
 
int ucx_map_iter_next (UcxMapIterator *iterator, UcxKey *key, void **value)
 Proceeds to the next element of the map (if any). More...
 

Detailed Description

Hash map implementation.

This implementation uses murmur hash 2 and separate chaining with linked lists.

Author
Mike Becker
Olaf Wintermann

Macro Definition Documentation

#define ucx_map_cstr_get (   map,
  key 
)    ucx_map_get(map, ucx_key((void*)key, strlen(key)))

Shorthand for getting data from the map with a C string key.

Parameters
mapthe map
keythe key
Returns
the value
See also
ucx_map_get()
#define ucx_map_cstr_put (   map,
  key,
  value 
)    ucx_map_put(map, ucx_key((void*)key, strlen(key)), (void*)value)

Shorthand for putting data with a C string key into the map.

Parameters
mapthe map
keythe key
valuethe value
Returns
0 on success, non-zero value on failure
See also
ucx_map_put()
#define ucx_map_cstr_remove (   map,
  key 
)    ucx_map_remove(map, ucx_key((void*)key, strlen(key)))

Shorthand for removing data from the map with a C string key.

Parameters
mapthe map
keythe key
Returns
the removed value
See also
ucx_map_remove()
#define UCX_MAP_FOREACH (   key,
  value,
  iter 
)    for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);)

Loop statement for UCX maps.

The key variable is implicitly defined, but the value variable must be already declared as type information cannot be inferred.

Parameters
keythe variable name for the key
valuethe variable name for the value
itera UcxMapIterator
See also
ucx_map_iterator()
#define ucx_map_int_get (   map,
  key 
)    ucx_map_get(map, ucx_key((void*)&key, sizeof(int)))

Shorthand for getting data from the map with an integer key.

Parameters
mapthe map
keythe key
Returns
the value
See also
ucx_map_get()
#define ucx_map_int_put (   map,
  key,
  value 
)    ucx_map_put(map, ucx_key((void*)&key, sizeof(key)), (void*)value)

Shorthand for putting data with an integer key into the map.

Parameters
mapthe map
keythe key
valuethe value
Returns
0 on success, non-zero value on failure
See also
ucx_map_put()
#define ucx_map_int_remove (   map,
  key 
)    ucx_map_remove(map, ucx_key((void*)&key, sizeof(key)))

Shorthand for removing data from the map with an integer key.

Parameters
mapthe map
keythe key
Returns
the removed value
See also
ucx_map_remove()
#define ucx_map_sstr_get (   map,
  key 
)    ucx_map_get(map, ucx_key(key.ptr, key.length))

Shorthand for getting data from the map with a sstr_t key.

Parameters
mapthe map
keythe key
Returns
the value
See also
ucx_map_get()
#define ucx_map_sstr_put (   map,
  key,
  value 
)    ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value)

Shorthand for putting data with a sstr_t key into the map.

Parameters
mapthe map
keythe key
valuethe value
Returns
0 on success, non-zero value on failure
See also
ucx_map_put()
#define ucx_map_sstr_remove (   map,
  key 
)    ucx_map_remove(map, ucx_key(key.ptr, key.length))

Shorthand for removing data from the map with a sstr_t key.

Parameters
mapthe map
keythe key
Returns
the removed value
See also
ucx_map_remove()

Typedef Documentation

typedef struct UcxKey UcxKey

Type for a key of a UcxMap.

See also
UcxKey
typedef struct UcxMap UcxMap

Type for the UCX map.

See also
UcxMap
typedef struct UcxMapElement UcxMapElement

Type for an element of a UcxMap.

See also
UcxMapElement

Type for an iterator over a UcxMap.

See also
UcxMapIterator

Function Documentation

int ucx_hash ( const char *  data,
size_t  len 
)

Computes a murmur hash-2.

Parameters
datathe data to hash
lenthe length of the data
Returns
the murmur hash-2 of the data
UcxKey ucx_key ( void *  data,
size_t  len 
)

Creates a UcxKey based on the given data.

This function implicitly computes the hash.

Parameters
datathe data for the key
lenthe length of the data
Returns
a UcxKey with implicitly computed hash
See also
ucx_hash()
void ucx_map_clear ( UcxMap map)

Clears a hash map.

Note: the contents are not freed, use ucx_map_free_content() before calling this function to achieve that.

Parameters
mapthe map to be cleared
See also
ucx_map_free_content()
UcxMap* ucx_map_clone ( UcxMap map,
copy_func  fnc,
void *  data 
)

Clones the map and rehashes if necessary.

Note: In contrast to ucx_map_rehash() the load factor is irrelevant. This function always ensures a new UcxMap.size of at least 2.5*UcxMap.count.

Parameters
mapthe map to clone
fncthe copy function to use or NULL if the new and the old map shall share the data pointers
dataadditional data for the copy function
Returns
the cloned map
See also
ucx_map_copy()
int ucx_map_copy ( UcxMap from,
UcxMap to,
copy_func  fnc,
void *  data 
)

Copies contents from a map to another map using a copy function.

Note: The destination map does not need to be empty. However, if it contains data with keys that are also present in the source map, the contents are overwritten.

Parameters
fromthe source map
tothe destination map
fncthe copy function or NULL if the pointer address shall be copied
dataadditional data for the copy function
Returns
0 on success or a non-zero value on memory allocation errors
void ucx_map_free ( UcxMap map)

Frees a hash map.

Note: the contents are not freed, use ucx_map_free_content() before calling this function to achieve that.

Parameters
mapthe map to be freed
See also
ucx_map_free_content()
void ucx_map_free_content ( UcxMap map,
ucx_destructor  destr 
)

Frees the contents of a hash map.

This is a convenience function that iterates over the map and passes all values to the specified destructor function (e.g. stdlib free()).

You must ensure, that it is valid to pass each value in the map to the same destructor function.

You should free or clear the map afterwards, as the contents will be invalid.

Parameters
mapfor which the contents shall be freed
destrpointer to the destructor function
See also
ucx_map_free()
ucx_map_clear()
void* ucx_map_get ( UcxMap map,
UcxKey  key 
)

Retrieves a value by using a key.

Parameters
mapthe map
keythe key
Returns
the value
int ucx_map_iter_next ( UcxMapIterator iterator,
UcxKey key,
void **  value 
)

Proceeds to the next element of the map (if any).

Subsequent calls on the same iterator proceed to the next element and store the key/value-pair into the memory specified as arguments of this function.

If no further elements are found, this function returns zero and leaves the last found key/value-pair in memory.

Parameters
iteratorthe iterator to use
keya pointer to the memory where to store the key
valuea pointer to the memory where to store the value
Returns
1, if another element was found, 0 if all elements has been processed
See also
ucx_map_iterator()
UcxMapIterator ucx_map_iterator ( UcxMap map)

Creates an iterator for a map.

Note: A UcxMapIterator iterates over all elements in all element lists successively. Therefore the order highly depends on the key hashes and may vary under different map sizes. So generally you may NOT rely on the iteration order.

Note: The iterator is NOT initialized. You need to call ucx_map_iter_next() at least once before accessing any information. However, it is not recommended to access the fields of a UcxMapIterator directly.

Parameters
mapthe map to create the iterator for
Returns
an iterator initialized on the first element of the first element list
See also
ucx_map_iter_next()
UcxMap* ucx_map_new ( size_t  size)

Creates a new hash map with the specified size.

Parameters
sizethe size of the hash map
Returns
a pointer to the new hash map
UcxMap* ucx_map_new_a ( UcxAllocator allocator,
size_t  size 
)

Creates a new hash map with the specified size using a UcxAllocator.

Parameters
allocatorthe allocator to use
sizethe size of the hash map
Returns
a pointer to the new hash map
int ucx_map_put ( UcxMap map,
UcxKey  key,
void *  value 
)

Puts a key/value-pair into the map.

Parameters
mapthe map
keythe key
valuethe value
Returns
0 on success, non-zero value on failure
int ucx_map_rehash ( UcxMap map)

Increases size of the hash map, if necessary.

The load value is 0.75*UcxMap.size. If the element count exceeds the load value, the map needs to be rehashed. Otherwise no action is performed and this function simply returns 0.

The rehashing process ensures, that the UcxMap.size is at least 2.5*UcxMap.count. So there is enough room for additional elements without the need of another soon rehashing.

You can use this function to dramatically increase access performance.

Parameters
mapthe map to rehash
Returns
1, if a memory allocation error occurred, 0 otherwise
void* ucx_map_remove ( UcxMap map,
UcxKey  key 
)

Removes a key/value-pair from the map by using the key.

Parameters
mapthe map
keythe key
Returns
the removed value