diff -r 92e482410453 -r d345541018fa docs/api-2.1/map_8h.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/docs/api-2.1/map_8h.html Sat Feb 06 19:11:44 2021 +0100 @@ -0,0 +1,1689 @@ + + + + + + + +ucx: /home/mike/workspace/c/ucx/src/ucx/map.h File Reference + + + + + + + + + +
+
+ + + + + + + +
+
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 to publicly denote a key of a UcxMap. More...
 
struct  UcxMapKey
 Internal 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(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(&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(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(&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(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(&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 const *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 const *map, copy_func fnc, void *data)
 Clones the map and rehashes if necessary. More...
 
UcxMapucx_map_clone_a (UcxAllocator *allocator, UcxMap const *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 const *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 (const 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 const *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...
 
UcxMapucx_map_union (const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
 Returns the union of two maps. More...
 
UcxMapucx_map_union_a (UcxAllocator *allocator, const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
 Returns the union of two maps. More...
 
UcxMapucx_map_intersection (const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
 Returns the intersection of two maps. More...
 
UcxMapucx_map_intersection_a (UcxAllocator *allocator, const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
 Returns the intersection of two maps. More...
 
UcxMapucx_map_difference (const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
 Returns the difference of two maps. More...
 
UcxMapucx_map_difference_a (UcxAllocator *allocator, const UcxMap *first, const UcxMap *second, copy_func cpfnc, void *cpdata)
 Returns the difference of two maps. 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

+ +

◆ ucx_map_cstr_get

+ +
+
+ + + + + + + + + + + + + + + + + + +
#define ucx_map_cstr_get( map,
 key 
)   ucx_map_get(map, ucx_key(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()
+ +
+
+ +

◆ ucx_map_cstr_put

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
#define ucx_map_cstr_put( map,
 key,
 value 
)   ucx_map_put(map, ucx_key(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()
+ +
+
+ +

◆ ucx_map_cstr_remove

+ +
+
+ + + + + + + + + + + + + + + + + + +
#define ucx_map_cstr_remove( map,
 key 
)   ucx_map_remove(map, ucx_key(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()
+ +
+
+ +

◆ UCX_MAP_FOREACH

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
#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()
+ +
+
+ +

◆ ucx_map_int_get

+ +
+
+ + + + + + + + + + + + + + + + + + +
#define ucx_map_int_get( map,
 key 
)   ucx_map_get(map, ucx_key(&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()
+ +
+
+ +

◆ ucx_map_int_put

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
#define ucx_map_int_put( map,
 key,
 value 
)   ucx_map_put(map, ucx_key(&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()
+ +
+
+ +

◆ ucx_map_int_remove

+ +
+
+ + + + + + + + + + + + + + + + + + +
#define ucx_map_int_remove( map,
 key 
)   ucx_map_remove(map, ucx_key(&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()
+ +
+
+ +

◆ ucx_map_sstr_get

+ +
+
+ + + + + + + + + + + + + + + + + + +
#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()
+ +
+
+ +

◆ ucx_map_sstr_put

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
#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()
+ +
+
+ +

◆ ucx_map_sstr_remove

+ +
+
+ + + + + + + + + + + + + + + + + + +
#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

+ +

◆ UcxKey

+ +
+
+ + + + +
typedef struct UcxKey UcxKey
+
+ +

Type for a key of a UcxMap.

+
See also
UcxKey
+ +
+
+ +

◆ UcxMap

+ +
+
+ + + + +
typedef struct UcxMap UcxMap
+
+ +

Type for the UCX map.

+
See also
UcxMap
+ +
+
+ +

◆ UcxMapElement

+ +
+
+ + + + +
typedef struct UcxMapElement UcxMapElement
+
+ +

Type for an element of a UcxMap.

+
See also
UcxMapElement
+ +
+
+ +

◆ UcxMapIterator

+ +
+
+ + + + +
typedef struct UcxMapIterator UcxMapIterator
+
+ +

Type for an iterator over a UcxMap.

+
See also
UcxMapIterator
+ +
+
+

Function Documentation

+ +

◆ ucx_hash()

+ +
+
+ + + + + + + + + + + + + + + + + + +
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
+ +
+
+ +

◆ ucx_key()

+ +
+
+ + + + + + + + + + + + + + + + + + +
UcxKey ucx_key (const 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()
+ +
+
+ +

◆ ucx_map_clear()

+ +
+
+ + + + + + + + +
void ucx_map_clear (UcxMapmap)
+
+ +

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()
+ +
+
+ +

◆ ucx_map_clone()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
UcxMap* ucx_map_clone (UcxMap const * 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()
+ +
+
+ +

◆ ucx_map_clone_a()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
UcxMap* ucx_map_clone_a (UcxAllocatorallocator,
UcxMap const * 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
+ + + + + +
allocatorthe allocator to use for the cloned map
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()
+ +
+
+ +

◆ ucx_map_copy()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
int ucx_map_copy (UcxMap const * from,
UcxMapto,
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
+ +
+
+ +

◆ ucx_map_difference()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
UcxMap* ucx_map_difference (const UcxMapfirst,
const UcxMapsecond,
copy_func cpfnc,
void * cpdata 
)
+
+ +

Returns the difference of two maps.

+

The difference contains a copy of all elements of the first map for which the corresponding keys cannot be found in the second map.

+
Parameters
+ + + + + +
firstthe first source map
secondthe second source map
cpfnca function to copy the elements
cpdataadditional data for the copy function
+
+
+
Returns
a new list containing the difference
+ +
+
+ +

◆ ucx_map_difference_a()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
UcxMap* ucx_map_difference_a (UcxAllocatorallocator,
const UcxMapfirst,
const UcxMapsecond,
copy_func cpfnc,
void * cpdata 
)
+
+ +

Returns the difference of two maps.

+

The difference contains a copy of all elements of the first map for which the corresponding keys cannot be found in the second map.

+
Parameters
+ + + + + + +
allocatorthe allocator that shall be used by the new map
firstthe first source map
secondthe second source map
cpfnca function to copy the elements
cpdataadditional data for the copy function
+
+
+
Returns
a new list containing the difference
+ +
+
+ +

◆ ucx_map_free()

+ +
+
+ + + + + + + + +
void ucx_map_free (UcxMapmap)
+
+ +

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()
+ +
+
+ +

◆ ucx_map_free_content()

+ +
+
+ + + + + + + + + + + + + + + + + + +
void ucx_map_free_content (UcxMapmap,
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.

+

If no destructor is specified (NULL), the free() function of the map's own allocator is used.

+

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
destroptional pointer to a destructor function
+
+
+
See also
ucx_map_free()
+
+ucx_map_clear()
+ +
+
+ +

◆ ucx_map_get()

+ +
+
+ + + + + + + + + + + + + + + + + + +
void* ucx_map_get (UcxMap const * map,
UcxKey key 
)
+
+ +

Retrieves a value by using a key.

+
Parameters
+ + + +
mapthe map
keythe key
+
+
+
Returns
the value
+ +
+
+ +

◆ ucx_map_intersection()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
UcxMap* ucx_map_intersection (const UcxMapfirst,
const UcxMapsecond,
copy_func cpfnc,
void * cpdata 
)
+
+ +

Returns the intersection of two maps.

+

The intersection is defined as a copy of the first map with every element removed that has no valid key in the second map.

+
Parameters
+ + + + + +
firstthe first source map
secondthe second source map
cpfnca function to copy the elements
cpdataadditional data for the copy function
+
+
+
Returns
a new map containing the intersection
+ +
+
+ +

◆ ucx_map_intersection_a()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
UcxMap* ucx_map_intersection_a (UcxAllocatorallocator,
const UcxMapfirst,
const UcxMapsecond,
copy_func cpfnc,
void * cpdata 
)
+
+ +

Returns the intersection of two maps.

+

The intersection is defined as a copy of the first map with every element removed that has no valid key in the second map.

+
Parameters
+ + + + + + +
allocatorthe allocator that shall be used by the new map
firstthe first source map
secondthe second source map
cpfnca function to copy the elements
cpdataadditional data for the copy function
+
+
+
Returns
a new map containing the intersection
+ +
+
+ +

◆ ucx_map_iter_next()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
int ucx_map_iter_next (UcxMapIteratoriterator,
UcxKeykey,
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()
+ +
+
+ +

◆ ucx_map_iterator()

+ +
+
+ + + + + + + + +
UcxMapIterator ucx_map_iterator (UcxMap const * 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()
+ +
+
+ +

◆ ucx_map_new()

+ +
+
+ + + + + + + + +
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
+ +
+
+ +

◆ ucx_map_new_a()

+ +
+
+ + + + + + + + + + + + + + + + + + +
UcxMap* ucx_map_new_a (UcxAllocatorallocator,
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
+ +
+
+ +

◆ ucx_map_put()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
int ucx_map_put (UcxMapmap,
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
+ +
+
+ +

◆ ucx_map_rehash()

+ +
+
+ + + + + + + + +
int ucx_map_rehash (UcxMapmap)
+
+ +

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
+ +
+
+ +

◆ ucx_map_remove()

+ +
+
+ + + + + + + + + + + + + + + + + + +
void* ucx_map_remove (UcxMapmap,
UcxKey key 
)
+
+ +

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

+
Parameters
+ + + +
mapthe map
keythe key
+
+
+
Returns
the removed value
+ +
+
+ +

◆ ucx_map_union()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
UcxMap* ucx_map_union (const UcxMapfirst,
const UcxMapsecond,
copy_func cpfnc,
void * cpdata 
)
+
+ +

Returns the union of two maps.

+

The union is a fresh map which is filled by two successive calls of ucx_map_copy() on the two input maps.

+
Parameters
+ + + + + +
firstthe first source map
secondthe second source map
cpfnca function to copy the elements
cpdataadditional data for the copy function
+
+
+
Returns
a new map containing the union
+ +
+
+ +

◆ ucx_map_union_a()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
UcxMap* ucx_map_union_a (UcxAllocatorallocator,
const UcxMapfirst,
const UcxMapsecond,
copy_func cpfnc,
void * cpdata 
)
+
+ +

Returns the union of two maps.

+

The union is a fresh map which is filled by two successive calls of ucx_map_copy() on the two input maps.

+
Parameters
+ + + + + + +
allocatorthe allocator that shall be used by the new map
firstthe first source map
secondthe second source map
cpfnca function to copy the elements
cpdataadditional data for the copy function
+
+
+
Returns
a new map containing the union
+ +
+
+
+ + + +