libslack(map) - map module
#include <slack/std.h>
#include <slack/map.h>
typedef struct Map Map;
typedef struct Mapper Mapper;
typedef struct Mapping Mapping;
typedef list_release_t map_release_t;
typedef list_copy_t map_copy_t;
typedef list_cmp_t map_cmp_t;
typedef size_t map_hash_t(size_t table_size, const void *key);
typedef void map_action_t(void *key, void *item, void *data);
Map *map_create(map_release_t *destroy);
Map *map_create_sized(size_t size, map_release_t *destroy);
Map *map_create_with_hash(map_hash_t *hash, map_release_t *destroy);
Map *map_create_sized_with_hash(size_t size, map_hash_t *hash, map_release_t *destroy);
Map *map_create_with_locker(Locker *locker, map_release_t *destroy);
Map *map_create_with_locker_sized(Locker *locker, size_t size, map_release_t *destroy);
Map *map_create_with_locker_with_hash(Locker *locker, map_hash_t *hash, map_release_t *destroy);
Map *map_create_with_locker_sized_with_hash(Locker *locker, size_t size, map_hash_t *hash, map_release_t *destroy);
Map *map_create_generic(map_copy_t *copy, map_cmp_t *cmp, map_hash_t *hash, map_release_t *key_destroy, map_release_t *value_destroy);
Map *map_create_generic_sized(size_t size, map_copy_t *copy, map_cmp_t *cmp, map_hash_t *hash, map_release_t *key_destroy, map_release_t *value_destroy);
Map *map_create_generic_with_locker(Locker *locker, map_copy_t *copy, map_cmp_t *cmp, map_hash_t *hash, map_release_t *key_destroy, map_release_t *value_destroy);
Map *map_create_generic_with_locker_sized(Locker *locker, size_t size, map_copy_t *copy, map_cmp_t *cmp, map_hash_t *hash, map_release_t *key_destroy, map_release_t *value_destroy);
int map_rdlock(const Map *map);
int map_wrlock(const Map *map);
int map_unlock(const Map *map);
void map_release(Map *map);
void *map_destroy(Map **map);
int map_own(Map *map, map_release_t *destroy);
int map_own_unlocked(Map *map, map_release_t *destroy);
map_release_t *map_disown(Map *map);
map_release_t *map_disown_unlocked(Map *map);
int map_add(Map *map, const void *key, void *value);
int map_add_unlocked(Map *map, const void *key, void *value);
int map_put(Map *map, const void *key, void *value);
int map_put_unlocked(Map *map, const void *key, void *value);
int map_insert(Map *map, const void *key, void *value, int replace);
int map_insert_unlocked(Map *map, const void *key, void *value, int replace);
int map_remove(Map *map, const void *key);
int map_remove_unlocked(Map *map, const void *key);
void *map_get(Map *map, const void *key);
void *map_get_unlocked(const Map *map, const void *key);
Mapper *mapper_create(Map *map);
Mapper *mapper_create_rdlocked(Map *map);
Mapper *mapper_create_wrlocked(Map *map);
Mapper *mapper_create_unlocked(Map *map);
void mapper_release(Mapper *mapper);
void mapper_release_unlocked(Mapper *mapper);
void *mapper_destroy(Mapper **mapper);
void *mapper_destroy_unlocked(Mapper **mapper);
int mapper_has_next(Mapper *mapper);
void *mapper_next(Mapper *mapper);
const Mapping *mapper_next_mapping(Mapper *mapper);
void mapper_remove(Mapper *mapper);
int map_has_next(Map *map);
void map_break(Map *map);
void *map_next(Map *map);
const Mapping *map_next_mapping(Map *map);
void map_remove_current(Map *map);
const void *mapping_key(const Mapping *mapping);
const void *mapping_value(const Mapping *mapping);
List *map_keys(Map *map);
List *map_keys_unlocked(Map *map);
List *map_keys_with_locker(Locker *locker, Map *map);
List *map_keys_with_locker_unlocked(Locker *locker, Map *map);
List *map_values(Map *map);
List *map_values_unlocked(Map *map);
List *map_values_with_locker(Locker *locker, Map *map);
List *map_values_with_locker_unlocked(Locker *locker, Map *map);
void map_apply(Map *map, map_action_t *action, void *data);
void map_apply_rdlocked(Map *map, map_action_t *action, void *data);
void map_apply_wrlocked(Map *map, map_action_t *action, void *data);
void map_apply_unlocked(Map *map, map_action_t *action, void *data);
ssize_t map_size(Map *map);
ssize_t map_size_unlocked(const Map *map);This module provides functions for manipulating and iterating over a set of mappings from one object to another object, also known as hashes or associative arrays. Maps may own their items. Maps created with a non-null destroy function use that function to destroy an item when it is removed from the map and to destroy each item when the map itself it destroyed. Maps are hash tables with 11 buckets by default. They grow when necessary, approximately doubling in size each time up to a maximum size of 26,214,401 buckets.
Map *map_create(map_release_t *destroy)Creates a small Map with string keys and destroy as its item destructor. It is the caller's responsibility to deallocate the new map with map_release(3) or map_destroy(3). It is strongly recommended to use map_destroy(3), because it also sets the pointer variable to null. On success, returns the new map. On error, returns null with errno set appropriately.
Map *map_create_sized(size_t size, map_release_t *destroy)Equivalent to map_create(3) except that the initial number of buckets is approximately size. The actual size will be the first prime greater than or equal to size in a prebuilt sequence of primes between 11 and 26,214,401 that double at each step.
Map *map_create_with_hash(map_hash_t *hash, map_release_t *destroy)Equivalent to map_create(3) except that hash is used as the hash function. The arguments to hash are a size_t specifying the number of buckets, and a const void * specifying the key to hash. It must return a size_t between zero and the table size - 1.
Map *map_create_sized_with_hash(size_t size, map_hash_t *hash, map_release_t *destroy)Equivalent to map_create_sized(3) except that hash is used as the hash function. The arguments to hash are a size_t specifying the number of buckets, and a const void * specifying the key to hash. It must return a size_t between zero and the table size - 1.
Map *map_create_with_locker(Locker *locker, map_release_t *destroy)Equivalent to map_create(3) except that multiple threads accessing the new map will be synchronised by locker.
Map *map_create_with_locker_sized(Locker *locker, size_t size, map_release_t *destroy)Equivalent to map_create_sized(3) except that multiple threads accessing the new map will be synchronised by locker.
Map *map_create_with_locker_with_hash(Locker *locker, map_hash_t *hash, map_release_t *destroy)Equivalent to map_create_with_hash(3) except that multiple threads accessing the new map will be synchronised by locker.
Map *map_create_with_locker_sized_with_hash(Locker *locker, size_t size, map_hash_t *hash, map_release_t *destroy)Equivalent to map_create_sized_with_hash(3) except that multiple threads accessing the new map will be synchronised by locker.
Map *map_create_generic(map_copy_t *copy, map_cmp_t *cmp, map_hash_t *hash, map_release_t *key_destroy, map_release_t *value_destroy)Equivalent to map_create(3) except that the mapping keys can be of any type. copy is used to copy mapping keys. The argument to copy is the key to be copied. It must return a copy of its argument. cmp is used to compare mapping keys. The arguments to cmp are two keys to be compared. It must return < 0 if the first compares less than the second, 0 if they compare equal and > 0 if the first compares greater than the second. hash is the hash function. The arguments to hash are a size_t specifying the number of buckets, and a const void * specifying the key to hash. It must return a size_t between zero and the table size - 1. key_destroy is the destructor for mapping keys. value_destroy is the destructor for mapping values. On success, returns the new map. On error, returns null with errno set appropriately.
Map *map_create_generic_sized(size_t size, map_copy_t *copy, map_cmp_t *cmp, map_hash_t *hash, map_release_t *key_destroy, map_release_t *value_destroy)Equivalent to map_create_generic(3) except that the initial number of buckets is approximately size. The actual size will be the first prime greater than or equal to size in a prebuilt sequence of primes between 11 and 26,214,401 that double at each step.
Map *map_create_generic_with_locker(Locker *locker, map_copy_t *copy, map_cmp_t *cmp, map_hash_t *hash, map_release_t *key_destroy, map_release_t *value_destroy)Equivalent to map_create_generic(3) except that multiple threads accessing the new map will be synchronised by locker.
Map *map_create_generic_with_locker_sized(Locker *locker, size_t size, map_copy_t *copy, map_cmp_t *cmp, map_hash_t *hash, map_release_t *key_destroy, map_release_t *value_destroy)Equivalent to map_create_generic_sized(3) except that multiple threads accessing the new map will be synchronised by locker.
int map_rdlock(const Map *map)Claims a read lock on map (if map was created with a Locker). This is needed when multiple read-only map(3) module functions need to be called atomically. It is the client's responsibility to call map_unlock(3) after the atomic operation. The only functions that may be called on map between calls to map_rdlock(3) and map_unlock(3) are any read-only map(3) module functions whose name ends with _unlocked. On success, returns 0. On error, returns an error code.
int map_wrlock(const Map *map)Claims a write lock on map (if map was created with a Locker). This is needed when multiple read/write map(3) module functions need to be called atomically. It is the client's responsibility to subsequently call map_unlock(3). The only functions that may be called on map between calls to map_wrlock(3) and map_unlock(3) are any map(3) module functions whose name ends with _unlocked. On success, returns 0. On error, returns an error code.
int map_unlock(const Map *map)Unlocks a read or write lock on map obtained with map_rdlock(3) or map_wrlock(3) (if map was created with a locker). On success, returns 0. On error, returns an error code.
void map_release(Map *map)Releases (deallocates) map, destroying its items if necessary. On error, sets errno appropriately.
void *map_destroy(Map **map)Destroys (deallocates and sets to null) *map. Returns null. Note: maps shared by multiple threads must not be destroyed until after all threads have finished with it.
int map_own(Map *map, map_release_t *destroy)Causes map to take ownership of its items. The items will be destroyed using destroy when their mappings are removed from map or when map is destroyed. On success, returns 0. On error, returns -1 with errno set appropriately.
int map_own_unlocked(Map *map, map_release_t *destroy)Equivalent to map_own(3) except that map is not write-locked.
map_release_t *map_disown(Map *map)Causes map to relinquish ownership of its items. The items will not be destroyed when their mappings are removed from map or when map is destroyed. On success, returns the previous destroy function, if any. On error, returns null with errno set appropriately.
map_release_t *map_disown_unlocked(Map *map)Equivalent to map_disown(3) except that map is not write-locked.
int map_add(Map *map, const void *key, void *value)Adds the (key, value) mapping to map, if key is not already present. Note that key is copied but value is not. On success, returns 0. On error, returns -1 with errno set appropriately.
int map_add_unlocked(Map *map, const void *key, void *value)Equivalent to map_add(3) except that map is not write-locked.
int map_put(Map *map, const void *key, void *value)Adds the (key, value) mapping to map, replacing any existing (key, value) mapping. Note that key is copied but value is not. On success, returns 0. On error, returns -1 with errno set appropriately.
int map_put_unlocked(Map *map, const void *key, void *value)Equivalent to map_put(3) except that map is not write-locked.
int map_insert(Map *map, const void *key, void *value, int replace)Adds the (key, value) mapping to map, replacing any existing (key, value) mapping, if replace is non-zero. Note that key is copied but value is not. On success, returns 0. On error, or if key is already present and replace is zero, returns -1 with errno set appropriately.
int map_insert_unlocked(Map *map, const void *key, void *value, int replace)Equivalent to map_insert(3) except that map is not write-locked.
int map_remove(Map *map, const void *key)Removes (key, value) mapping from map if it is present. If map was created with a destroy function, then the value will be destroyed. On success, returns 0. On error, returns -1 with errno set appropriately.
int map_remove_unlocked(Map *map, const void *key)Equivalent to map_remove(3) except that map is not write-locked.
void *map_get(Map *map, const void *key)Returns the value associated with key in map, or null if there is none. On error, returns null with errno set appropriately.
void *map_get_unlocked(const Map *map, const void *key)Equivalent to map_get(3) except that map is not read-locked.
Mapper *mapper_create(Map *map)Creates an iterator for map. The iterator keeps map write-locked until it is released with mapper_release(3) or mapper_destroy(3). Note that the iterator itself is not locked, so it must not be shared between threads. On success, returns the iterator. On error, returns null with errno set appropriately.
Mapper *mapper_create_rdlocked(Map *map)Equivalent to mapper_create(3) except that map is read-locked rather than write-locked. Use this in preference to mapper_create(3) when no calls to mapper_remove(3) will be made during the iteration.
Mapper *mapper_create_wrlocked(Map *map)Equivalent to mapper_create(3) except that this function name makes the fact that map is write-locked explicit.
Mapper *mapper_create_unlocked(Map *map)Equivalent to mapper_create(3) except that map is not write-locked.
void mapper_release(Mapper *mapper)Releases (deallocates) mapper and unlocks the associated map.
void mapper_release_unlocked(Mapper *mapper)Equivalent to mapper_release(3) except that the associated map is not unlocked.
void *mapper_destroy(Mapper **mapper)Destroys (deallocates and sets to null) *mapper and unlocks the associated map. Returns null. On error, sets errno appropriately.
void *mapper_destroy_unlocked(Mapper **mapper)Equivalent to mapper_destroy(3) except that the associated map is not unlocked.
int mapper_has_next(Mapper *mapper)Returns whether or not there is another item in the map over which mapper is iterating. On error, returns -1 with errno set appropriately.
void *mapper_next(Mapper *mapper)Returns the next item in the map over which mapper is iterating. On error, returns null with errno set appropriately.
const Mapping *mapper_next_mapping(Mapper *mapper)Returns the next mapping (key, value) pair in the map over which mapper is iterating. On error, returns null with errno set appropriately.
void mapper_remove(Mapper *mapper)Removes the current item in the iteration mapper. The next item in the iteration is the item following the removed item, if any. This must be called after mapper_next(3). On error, sets errno appropriately.
int map_has_next(Map *map)Returns whether or not there is another item in map using an internal iterator. The first time this is called, a new internal Mapper will be created (Note: There can be only one at any time for a given map). When there are no more items, returns 0 and destroys the internal iterator. When it returns 1, use map_next(3) to retrieve the next item. On error, returns -1 with errno set appropriately.
Note: If an iteration using an internal iterator terminates before the end of the map, it is the caller's responsibility to call map_break(3). Failure to do so will cause the internal iterator to leak. It will also break the next call to map_has_next(3) which will continue where the current iteration stopped rather than starting at the beginning again. map_release(3) assumes that there is no internal iterator, so it is the caller's responsibility to complete the iteration, or call map_break(3) before releasing map with map_release(3) or map_destroy(3).
Note: The internal Mapper does not lock map so this function is not threadsafe. It can only be used with maps created in the current function (to guarantee that no other thread can access it). This practice should be observed even in single-threaded applications to avoid breaking iterator semantics (possible with nested function calls). If map is a parameter or a variable declared outside the function, it is best to create an explicit Mapper instead. If this function is used on such maps instead, it is the caller's responsibility to explicitly lock map first with map_wrlock(3) and explicitly unlock it with map_unlock(3). Do this even if you are writing single-threaded code, in case your function may one day be used in a multi-threaded application.
void map_break(Map *map)Unlocks map and destroys its internal iterator. Must be used only when an iteration using an internal iterator has terminated before reaching the end of map. On error, returns null with errno set appropriately.
void *map_next(Map *map)Returns the next item in map using its internal iterator. On error, returns null with errno set appropriately.
const Mapping *map_next_mapping(Map *map)Returns the next mapping (key, value) pair in map using its internal iterator. On error, returns -1 with errno set appropriately.
void map_remove_current(Map *map)Removes the current item in map using its internal iterator. The next item in the iteration is the item following the removed item, if any. This must be called after map_next(3).
const void *mapping_key(const Mapping *mapping)Returns the key in mapping. On error, returns null with errno set appropriately.
const void *mapping_value(const Mapping *mapping)Returns the value in mapping. On error, returns null with errno set appropriately.
List *map_keys(Map *map)Creates and returns a list of all of the keys contained in map. It is the caller's responsibility to deallocate the new list with list_release(3) or list_destroy(3). It is strongly recommended to use list_destroy(3), because it also sets the pointer variable to null. The keys in the new list are owned by map, so the list returned must not outlive map. On error, returns null with errno set appropriately.
List *map_keys_unlocked(Map *map)Equivalent to map_keys(3) except that map is not read-locked.
List *map_keys_with_locker(Locker *locker, Map *map)Equivalent to map_keys(3) except that multiple threads accessing the list returned will be synchronised by locker.
List *map_keys_with_locker_unlocked(Locker *locker, Map *map)Equivalent to map_keys_with_locker(3) except that map is not read-locked.
List *map_values(Map *map)Creates and returns a list of all of the values contained in map. It is the caller's responsibility to deallocate the new list with list_release(3) or list_destroy(3). It is strongly recommended to use list_destroy(3), because it also sets the pointer variable to null. The values in the list are not owned by the list, so it must not outlive the owner of the items in map. On error, returns null with errno set appropriately.
List *map_values_unlocked(Map *map)Equivalent to map_values(3) except that map is not read-locked.
List *map_values_with_locker(Locker *locker, Map *map)Equivalent to map_values(3) except that multiple threads accessing the list returned will be synchronised by locker.
List *map_values_with_locker_unlocked(Locker *locker, Map *map)Equivalent to map_values_with_locker(3) except that map is not read-locked.
void map_apply(Map *map, map_action_t *action, void *data)Invokes action for each of map's items. The arguments passed to action are the key, the item, and data. On error, sets errno appropriately.
void map_apply_rdlocked(Map *map, map_action_t *action, void *data)Equivalent to map_apply(3) except that map is read-locked rather than write-locked. Use this in preference to map_apply(3) when map and its items will not be modified during the iteration.
void map_apply_wrlocked(Map *map, map_action_t *action, void *data)Equivalent to map_apply(3) except that this function name makes the fact that map is write-locked explicit.
void map_apply_unlocked(Map *map, map_action_t *action, void *data)Equivalent to map_apply(3) except that map is not write-locked.
ssize_t map_size(Map *map)Returns the number of mappings in map. On error, returns -1 with errno set appropriately.
ssize_t map_size_unlocked(const Map *map)Equivalent to map_size(3) except that map is not read-locked.
On error, errno is set either by an underlying function, or as follows:
EINVALWhen arguments are null or out of range.
ENOENTWhen map_get(3) tries to get, or map_remove(3) tries to remove, a non-existent mapping.
MT-Disciplined
By default, Maps are not MT-Safe because most programs are single-threaded, and synchronisation doesn't come for free. Even in multi-threaded programs, not all Maps are necessarily shared between multiple threads.
When a Map is shared between multiple threads which need to be synchronised, the method of synchronisation must be carefully selected by the client code. There are tradeoffs between concurrency and overhead. The greater the concurrency, the greater the overhead. More locks give greater concurrency, but have greater overhead. Readers/Writer locks can give greater concurrency than Mutex, locks but have greater overhead. One lock for each Map may be required, or one lock for all (or a set of) Maps may be more appropriate.
Generally, the best synchronisation strategy for a given application can only be determined by testing/benchmarking the written application. It is important to be able to experiment with the synchronisation strategy at this stage of development without pain.
To facilitate this, Maps can be created with map_create_with_locker(3), which takes a Locker argument. The Locker specifies a lock and a set of functions for manipulating the lock. Each Map can have its own lock by creating a separate Locker for each Map. Multiple Maps can share the same lock by sharing the same Locker. Only the application developer can determine what is appropriate for each application on a case by case basis.
MT-Disciplined means that the application developer has a mechanism for specifying the synchronisation requirements to be applied to library code.
Create a map that doesn't own its items, populate it, and then iterate over its values with the internal iterator to print the values:
#include <slack/std.h>
#include <slack/map.h>
int main()
{
Map *map;
if (!(map = map_create(NULL)))
return EXIT_FAILURE;
map_add(map, "abc", "123");
map_add(map, "def", "456");
map_add(map, "ghi", "789");
while (map_has_next(map) == 1)
printf("%s\n", (char *)map_next(map));
map_destroy(&map);
return EXIT_SUCCESS;
}Create a map that does own its items, populate it, and then iterate over its items with an external iterator to print its keys and values:
#include <slack/std.h>
#include <slack/map.h>
int main()
{
Map *map;
Mapper *mapper;
if (!(map = map_create(free)))
return EXIT_FAILURE;
map_add(map, "abc", strdup("123"));
map_add(map, "def", strdup("456"));
map_add(map, "ghi", strdup("789"));
if (!(mapper = mapper_create(map)))
{
map_destroy(&map);
return EXIT_FAILURE;
}
while (mapper_has_next(mapper) == 1)
{
const Mapping *mapping = mapper_next_mapping(mapper);
printf("%s -> %s\n", (char *)mapping_key(mapping), (char *)mapping_value(mapping));
}
mapper_destroy(&mapper);
map_destroy(&map);
return EXIT_SUCCESS;
}The same, but with an apply function:
#include <slack/std.h>
#include <slack/map.h>
void action(void *key, void *item, void *data)
{
printf("%s -> %s\n", (char *)key, (char *)item);
}
int main()
{
Map *map;
if (!(map = map_create(free)))
return EXIT_FAILURE;
map_add(map, "abc", strdup("123"));
map_add(map, "def", strdup("456"));
map_add(map, "ghi", strdup("789"));
map_apply(map, action, NULL);
map_destroy(&map);
return EXIT_SUCCESS;
}The same, but with integer keys:
#include <slack/std.h>
#include <slack/map.h>
static void *int_copy(const void *key)
{
return (void *)key;
}
static int int_cmp(const void *a, const void *b)
{
return (int)a - (int)b;
}
static size_t int_hash(size_t size, const void *key)
{
return (int)key % size;
}
void action(void *key, void *item, void *data)
{
printf("%d -> %s\n", (int)key, (char *)item);
}
int main(int ac, char **av)
{
Map *map;
if (!(map = map_create_generic(int_copy, int_cmp, int_hash, NULL, free)))
return EXIT_FAILURE;
map_add(map, (void *)123, strdup("abc"));
map_add(map, (void *)456, strdup("def"));
map_add(map, (void *)789, strdup("ghi"));
map_apply(map, action, NULL);
map_destroy(&map);
return EXIT_SUCCESS;
}A null pointer can't be a key. Neither can zero when using integers as keys.
If you use an internal iterator in a loop that terminates before the end of the map, and fail to call map_break(3), the internal iterator will leak.
Uses malloc(3) directly. The type of memory used and the allocation strategy should be decoupled from this code.
libslack(3), list(3), mem(3), locker(3)
20230824 raf <raf@raf.org>