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). 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). 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 it's 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 it's internal
iterator. On error, returns -1
with errno
set appropriately.
void map_remove_current(Map *map)
Removes the current item in map
using it's 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). 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). 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:
EINVAL
When arguments are null
or out of range.
ENOENT
When 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 it's 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). The type of memory used and the allocation strategy need to be decoupled from this code.
libslack(3), list(3), mem(3), locker(3)
20100612 raf <raf@raf.org>