/* * libslack - https://libslack.org * * Copyright (C) 1999-2004, 2010, 2020-2023 raf * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, see . * * 20230824 raf */ /* =head1 NAME I - map module =head1 SYNOPSIS #include #include 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); =head1 DESCRIPTION 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. Is may own their items. Is created with a non-C 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. Is are hash tables with C<11> buckets by default. They grow when necessary, approximately doubling in size each time up to a maximum size of C<26,214,401> buckets. =over 4 =cut */ #ifndef _BSD_SOURCE #define _BSD_SOURCE /* For snprintf() on OpenBSD-4.7 */ #endif #ifndef _DEFAULT_SOURCE #define _DEFAULT_SOURCE /* New name for _BSD_SOURCE */ #endif #include "config.h" #include "std.h" #include "map.h" #include "mem.h" #include "err.h" #include "locker.h" struct Map { size_t size; /* number of buckets */ size_t items; /* number of items */ List **chain; /* array of hash buckets */ map_hash_t *hash; /* hash function */ map_copy_t *copy; /* key copy function */ map_cmp_t *cmp; /* key comparison function */ map_release_t *key_destroy; /* destructor function for keys */ map_release_t *value_destroy; /* destructor function for items */ Mapper *mapper; /* built-in iterator */ Locker *locker; /* locking strategy for this object */ }; struct Mapping { void *key; /* a map key */ void *value; /* a map value */ map_release_t *key_destroy; /* destructor function for key */ map_release_t *value_destroy; /* destructor function for value */ }; struct Mapper { Map *map; /* the map being iterated over */ ssize_t chain_index; /* the index of the chain of the current item */ ssize_t item_index; /* the index of the current item */ ssize_t next_chain_index; /* the index of the chain of the next item */ ssize_t next_item_index; /* the index of the next item */ }; #ifndef TEST /* Increasing sequence of valid (i.e. prime) table sizes to choose from. */ static const size_t table_sizes[] = { 11, 23, 47, 101, 199, 401, 797, 1601, 3203, 6397, 12799, 25601, 51199, 102397, 204803, 409597, 819187, 1638431, 3276799, 6553621, 13107197, 26214401 }; static const size_t num_table_sizes = sizeof(table_sizes) / sizeof(table_sizes[0]); /* Average bucket length threshold that must be reached before a map grows */ static const double table_resize_factor = 2.0; #if 0 /* C JPW hash function. Returns a hash value (in the range 0..size-1) for C. */ static size_t hash(size_t size, const void *key) { unsigned char *k = key; size_t g, h = 0; while (*k) if ((g = (h <<= 4, h += *k++) & 0xf0000000)) h ^= (g >> 24) ^ g; return h % size; } #endif /* C Hash function from The Practice of Programming by Kernighan and Pike (p57). Returns a hash value (in the range 0..size-1) for C. */ static size_t hash(size_t size, const void *key) { const unsigned char *k = key; size_t h = 0; while (*k) h *= 31, h += *k++; return h % size; } /* C Creates a new mapping from C to C. C is the destructor function for C. On success, returns the new mapping. On error, returns C with C set appropriately. */ static Mapping *mapping_create(void *key, void *value, map_release_t *key_destroy, map_release_t *value_destroy) { Mapping *mapping; if (!(mapping = mem_new(Mapping))) /* XXX decouple */ return NULL; mapping->key = key; mapping->value = value; mapping->key_destroy = key_destroy; mapping->value_destroy = value_destroy; return mapping; } /* C Releases (deallocates) C, destroying its value if necessary. */ static void mapping_release(Mapping *mapping) { if (!mapping) return; if (mapping->key_destroy) mapping->key_destroy(mapping->key); if (mapping->value_destroy) mapping->value_destroy(mapping->value); mem_release(mapping); } /* =item C Creates a small I with string keys and C as its item destructor. It is the caller's responsibility to deallocate the new map with I or I. It is strongly recommended to use I, because it also sets the pointer variable to C. On success, returns the new map. On error, returns C with C set appropriately. =cut */ Map *map_create(map_release_t *destroy) { return map_create_sized_with_hash(table_sizes[0], (map_hash_t *)hash, destroy); } /* =item C Equivalent to I except that the initial number of buckets is approximately C. The actual size will be the first prime greater than or equal to C in a prebuilt sequence of primes between C<11> and C<26,214,401> that double at each step. =cut */ Map *map_create_sized(size_t size, map_release_t *destroy) { return map_create_sized_with_hash(size, (map_hash_t *)hash, destroy); } /* =item C Equivalent to I except that C is used as the hash function. The arguments to C are a I specifying the number of buckets, and a I specifying the key to hash. It must return a I between zero and the table size - 1. =cut */ Map *map_create_with_hash(map_hash_t *hash, map_release_t *destroy) { return map_create_sized_with_hash(table_sizes[0], hash, destroy); } /* =item C Equivalent to I except that C is used as the hash function. The arguments to C are a I specifying the number of buckets, and a I specifying the key to hash. It must return a I between zero and the table size - 1. =cut */ Map *map_create_sized_with_hash(size_t size, map_hash_t *hash, map_release_t *destroy) { return map_create_generic_sized(size, (map_copy_t *)mem_strdup, (map_cmp_t *)strcmp, hash, (map_release_t *)free, destroy); } /* =item C Equivalent to I except that multiple threads accessing the new map will be synchronised by C. =cut */ Map *map_create_with_locker(Locker *locker, map_release_t *destroy) { return map_create_with_locker_sized_with_hash(locker, table_sizes[0], (map_hash_t *)hash, destroy); } /* =item C Equivalent to I except that multiple threads accessing the new map will be synchronised by C. =cut */ Map *map_create_with_locker_sized(Locker *locker, size_t size, map_release_t *destroy) { return map_create_with_locker_sized_with_hash(locker, size, (map_hash_t *)hash, destroy); } /* =item C Equivalent to I except that multiple threads accessing the new map will be synchronised by C. =cut */ Map *map_create_with_locker_with_hash(Locker *locker, map_hash_t *hash, map_release_t *destroy) { return map_create_with_locker_sized_with_hash(locker, table_sizes[0], hash, destroy); } /* =item C Equivalent to I except that multiple threads accessing the new map will be synchronised by C. =cut */ Map *map_create_with_locker_sized_with_hash(Locker *locker, size_t size, map_hash_t *hash, map_release_t *destroy) { return map_create_generic_with_locker_sized(locker, size, (map_copy_t *)mem_strdup, (map_cmp_t *)strcmp, hash, (map_release_t *)free, destroy); } /* =item C Equivalent to I except that the mapping keys can be of any type. C is used to copy mapping keys. The argument to C is the key to be copied. It must return a copy of its argument. C is used to compare mapping keys. The arguments to C 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. C is the hash function. The arguments to C are a I specifying the number of buckets, and a I specifying the key to hash. It must return a I between zero and the table size - 1. C is the destructor for mapping keys. C is the destructor for mapping values. On success, returns the new map. On error, returns C with C set appropriately. =cut */ 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) { return map_create_generic_with_locker_sized(NULL, table_sizes[0], copy, cmp, hash, key_destroy, value_destroy); } /* =item C Equivalent to I except that the initial number of buckets is approximately C. The actual size will be the first prime greater than or equal to C in a prebuilt sequence of primes between C<11> and C<26,214,401> that double at each step. =cut */ 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) { return map_create_generic_with_locker_sized(NULL, size, copy, cmp, hash, key_destroy, value_destroy); } /* =item C Equivalent to I except that multiple threads accessing the new map will be synchronised by C. =cut */ 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) { return map_create_generic_with_locker_sized(locker, table_sizes[0], copy, cmp, hash, key_destroy, value_destroy); } /* =item C Equivalent to I except that multiple threads accessing the new map will be synchronised by C. =cut */ 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) { Map *map; size_t i; for (i = 0; i < num_table_sizes; ++i) { if (table_sizes[i] >= size) { size = table_sizes[i]; break; } } if (i == num_table_sizes) return set_errnull(EINVAL); if (!(map = mem_new(Map))) /* XXX decouple */ return NULL; if (!(map->chain = mem_create(size, List *))) { mem_release(map); return NULL; } map->size = size; map->items = 0; memset(map->chain, 0, map->size * sizeof(List *)); map->hash = hash; map->copy = copy; map->cmp = cmp; map->key_destroy = key_destroy; map->value_destroy = value_destroy; map->mapper = NULL; map->locker = locker; return map; } /* =item C Claims a read lock on C (if C was created with a I). This is needed when multiple read-only I module functions need to be called atomically. It is the client's responsibility to call I after the atomic operation. The only functions that may be called on C between calls to I and I are any read-only I module functions whose name ends with C<_unlocked>. On success, returns C<0>. On error, returns an error code. =cut */ #define map_rdlock(map) ((map) ? locker_rdlock((map)->locker) : EINVAL) #define map_wrlock(map) ((map) ? locker_wrlock((map)->locker) : EINVAL) #define map_unlock(map) ((map) ? locker_unlock((map)->locker) : EINVAL) int (map_rdlock)(const Map *map) { return map_rdlock(map); } /* =item C Claims a write lock on C (if C was created with a I). This is needed when multiple read/write I module functions need to be called atomically. It is the client's responsibility to subsequently call I. The only functions that may be called on C between calls to I and I are any I module functions whose name ends with C<_unlocked>. On success, returns C<0>. On error, returns an error code. =cut */ int (map_wrlock)(const Map *map) { return map_wrlock(map); } /* =item C Unlocks a read or write lock on C obtained with I or I (if C was created with a C). On success, returns C<0>. On error, returns an error code. =cut */ int (map_unlock)(const Map *map) { return map_unlock(map); } /* =item C Releases (deallocates) C, destroying its items if necessary. On error, sets C appropriately. =cut */ void map_release(Map *map) { size_t i; if (!map) return; for (i = 0; i < map->size; ++i) list_release(map->chain[i]); mem_release(map->chain); mem_release(map); } /* =item C Destroys (deallocates and sets to C) C<*map>. Returns C. B maps shared by multiple threads must not be destroyed until after all threads have finished with it. =cut */ void *map_destroy(Map **map) { if (map && *map) { map_release(*map); *map = NULL; } return NULL; } /* =item C Causes C to take ownership of its items. The items will be destroyed using C when their mappings are removed from C or when C is destroyed. On success, returns C<0>. On error, returns C<-1> with C set appropriately. =cut */ int map_own(Map *map, map_release_t *destroy) { int ret; int err; if (!map || !destroy) return set_errno(EINVAL); if ((err = map_wrlock(map))) return set_errno(err); ret = map_own_unlocked(map, destroy); if ((err = map_unlock(map))) return set_errno(err); return ret; } /* =item C Equivalent to I except that C is not write-locked. =cut */ int map_own_unlocked(Map *map, map_release_t *destroy) { ssize_t length; size_t c, i; if (!map || !destroy) return set_errno(EINVAL); if (destroy == map->value_destroy) return 0; map->value_destroy = destroy; for (c = 0; c < map->size; ++c) { List *chain = map->chain[c]; if (!chain) continue; if ((length = list_length_unlocked(chain)) == -1) return -1; for (i = 0; i < length; ++i) { Mapping *mapping = (Mapping *)list_item_unlocked(chain, i); mapping->value_destroy = destroy; } } return 0; } /* =item C Causes C to relinquish ownership of its items. The items will not be destroyed when their mappings are removed from C or when C is destroyed. On success, returns the previous destroy function, if any. On error, returns C with C set appropriately. =cut */ map_release_t *map_disown(Map *map) { map_release_t *ret; int err; if (!map) return (map_release_t *)set_errnullf(EINVAL); if ((err = map_wrlock(map))) return (map_release_t *)set_errnullf(err); ret = map_disown_unlocked(map); if ((err = map_unlock(map))) return (map_release_t *)set_errnullf(err); return ret; } /* =item C Equivalent to I except that C is not write-locked. =cut */ map_release_t *map_disown_unlocked(Map *map) { ssize_t length; size_t c, i; map_release_t *destroy; if (!map) return (map_release_t *)set_errnullf(EINVAL); if (!map->value_destroy) return NULL; destroy = map->value_destroy; map->value_destroy = NULL; for (c = 0; c < map->size; ++c) { List *chain = map->chain[c]; if (!chain) continue; if ((length = list_length_unlocked(chain)) == -1) return NULL; for (i = 0; i < length; ++i) { Mapping *mapping = (Mapping *)list_item_unlocked(chain, i); mapping->value_destroy = NULL; } } return destroy; } /* C Resizes C to use the next prime in a prebuilt sequence of primes between C<11> and C<26,214,401> that is greater than the current size. On success, returns C<0>. On error, returns C<-1> with C set appropriately. */ static int map_resize(Map *map) { size_t size = 0; size_t i; Mapper *mapper; Map *new_map; if (!map) return set_errno(EINVAL); for (i = 1; i < num_table_sizes; ++i) { if (table_sizes[i] > map->size) { size = table_sizes[i]; break; } } if (i == num_table_sizes || size == 0) return set_errno(EINVAL); if (!(new_map = map_create_generic_sized(size, map->copy, map->cmp, map->hash, map->key_destroy, map->value_destroy))) return -1; if (!(mapper = mapper_create_unlocked(map))) { map_release(new_map); return -1; } while (mapper_has_next(mapper) == 1) { const Mapping *mapping = mapper_next_mapping(mapper); if (map_add_unlocked(new_map, mapping->key, mapping->value) == -1) { mapper_release_unlocked(mapper); map_release(new_map); return -1; } } mapper_release_unlocked(mapper); errno = 0; if (map_disown_unlocked(map) == NULL && errno) { map_release(new_map); return -1; } for (i = 0; i < map->size; ++i) list_release(map->chain[i]); mem_release(map->chain); map->size = new_map->size; map->items = new_map->items; map->chain = new_map->chain; map->value_destroy = new_map->value_destroy; mem_release(new_map); return 0; } /* =item C Adds the C<(key, value)> mapping to C, if C is not already present. Note that C is copied but C is not. On success, returns C<0>. On error, returns C<-1> with C set appropriately. =cut */ int map_add(Map *map, const void *key, void *value) { return map_insert(map, key, value, 0); } /* =item C Equivalent to I except that C is not write-locked. =cut */ int map_add_unlocked(Map *map, const void *key, void *value) { return map_insert_unlocked(map, key, value, 0); } /* =item C Adds the C<(key, value)> mapping to C, replacing any existing C<(key, value)> mapping. Note that C is copied but C is not. On success, returns C<0>. On error, returns C<-1> with C set appropriately. =cut */ int map_put(Map *map, const void *key, void *value) { return map_insert(map, key, value, 1); } /* =item C Equivalent to I except that C is not write-locked. =cut */ int map_put_unlocked(Map *map, const void *key, void *value) { return map_insert_unlocked(map, key, value, 1); } /* =item C Adds the C<(key, value)> mapping to C, replacing any existing C<(key, value)> mapping, if C is non-zero. Note that C is copied but C is not. On success, returns C<0>. On error, or if C is already present and C is zero, returns C<-1> with C set appropriately. =cut */ int map_insert(Map *map, const void *key, void *value, int replace) { int ret; int err; if (!map || !key) return set_errno(EINVAL); if ((err = map_wrlock(map))) return set_errno(err); ret = map_insert_unlocked(map, key, value, replace); if ((err = map_unlock(map))) return set_errno(err); return ret; } /* =item C Equivalent to I except that C is not write-locked. =cut */ int map_insert_unlocked(Map *map, const void *key, void *value, int replace) { Mapping *mapping; List *chain; ssize_t length; size_t h, c; if (!map || !key) return set_errno(EINVAL); if ((double)map->items / (double)map->size >= (double)table_resize_factor) if (map_resize(map) == -1) return -1; if ((h = map->hash(map->size, key)) >= map->size) return set_errno(EINVAL); if (!map->chain[h] && !(map->chain[h] = list_create((map_release_t *)mapping_release))) return -1; chain = map->chain[h]; if ((length = list_length_unlocked(chain)) == -1) return -1; for (c = 0; c < length; ++c) { mapping = (Mapping *)list_item_unlocked(chain, c); if (!map->cmp(mapping->key, key)) { if (replace && list_remove_unlocked(chain, c)) break; return -1; } } if (!(mapping = mapping_create(map->copy(key), value, map->key_destroy, map->value_destroy))) return -1; if (!list_append_unlocked(chain, mapping)) { mapping_release(mapping); return -1; } ++map->items; return 0; } /* =item C Removes C<(key, value)> mapping from C if it is present. If C was created with a destroy function, then the value will be destroyed. On success, returns C<0>. On error, returns C<-1> with C set appropriately. =cut */ int map_remove(Map *map, const void *key) { int ret; int err; if (!map || !key) return set_errno(EINVAL); if ((err = map_wrlock(map))) return set_errno(err); ret = map_remove_unlocked(map, key); if ((err = map_unlock(map))) return set_errno(err); return ret; } /* =item C Equivalent to I except that C is not write-locked. =cut */ int map_remove_unlocked(Map *map, const void *key) { List *chain; ssize_t length; size_t h, c; if (!map || !key) return set_errno(EINVAL); if ((h = map->hash(map->size, key)) >= map->size) return set_errno(EINVAL); if (!(chain = map->chain[h])) return set_errno(ENOENT); if ((length = list_length_unlocked(chain)) == -1) return -1; for (c = 0; c < length; ++c) { Mapping *mapping = (Mapping *)list_item_unlocked(chain, c); if (!map->cmp(mapping->key, key)) { if (!list_remove_unlocked(chain, c)) return -1; --map->items; return 0; } } return set_errno(ENOENT); } /* =item C Returns the value associated with C in C, or C if there is none. On error, returns C with C set appropriately. =cut */ void *map_get(Map *map, const void *key) { void *ret; int err; if (!map || !key) return set_errnull(EINVAL); if ((err = map_rdlock(map))) return set_errnull(err); ret = map_get_unlocked(map, key); if ((err = map_unlock(map))) return set_errnull(err); return ret; } /* =item C Equivalent to I except that C is not read-locked. =cut */ void *map_get_unlocked(const Map *map, const void *key) { List *chain; ssize_t length; size_t h, c; if (!map || !key) return set_errnull(EINVAL); if ((h = map->hash(map->size, key)) >= map->size) return set_errnull(EINVAL); if (!(chain = map->chain[h])) return set_errnull(ENOENT); if ((length = list_length_unlocked(chain)) == -1) return NULL; for (c = 0; c < length; ++c) { Mapping *mapping = (Mapping *)list_item_unlocked(chain, c); if (!map->cmp(mapping->key, key)) return mapping->value; } return set_errnull(ENOENT); } /* =item C Creates an iterator for C. The iterator keeps C write-locked until it is released with I or I. Note that the iterator itself is not locked, so it must not be shared between threads. On success, returns the iterator. On error, returns C with C set appropriately. =cut */ Mapper *mapper_create(Map *map) { return mapper_create_wrlocked(map); } /* =item C Equivalent to I except that C is read-locked rather than write-locked. Use this in preference to I when no calls to I will be made during the iteration. =cut */ Mapper *mapper_create_rdlocked(Map *map) { int err; if (!map) return set_errnull(EINVAL); if ((err = map_rdlock(map))) return set_errnull(err); return mapper_create_unlocked(map); } /* =item C Equivalent to I except that this function name makes the fact that C is write-locked explicit. =cut */ Mapper *mapper_create_wrlocked(Map *map) { int err; if (!map) return set_errnull(EINVAL); if ((err = map_wrlock(map))) return set_errnull(err); return mapper_create_unlocked(map); } /* =item C Equivalent to I except that C is not write-locked. =cut */ Mapper *mapper_create_unlocked(Map *map) { Mapper *mapper; if (!map) return set_errnull(EINVAL); if (!(mapper = mem_new(Mapper))) /* XXX decouple */ return NULL; mapper->map = map; mapper->chain_index = -1; mapper->item_index = -1; mapper->next_chain_index = -1; mapper->next_item_index = -1; return mapper; } /* =item C Releases (deallocates) C and unlocks the associated map. =cut */ void mapper_release(Mapper *mapper) { int err; if (!mapper) return; if ((err = map_unlock(mapper->map))) { set_errno(err); return; } mem_release(mapper); } /* =item C Equivalent to I except that the associated map is not unlocked. =cut */ void mapper_release_unlocked(Mapper *mapper) { if (!mapper) return; mem_release(mapper); } /* =item C Destroys (deallocates and sets to C) C<*mapper> and unlocks the associated map. Returns C. On error, sets C appropriately. =cut */ void *mapper_destroy(Mapper **mapper) { if (mapper && *mapper) { mapper_release(*mapper); *mapper = NULL; } return NULL; } /* =item C Equivalent to I except that the associated map is not unlocked. =cut */ void *mapper_destroy_unlocked(Mapper **mapper) { if (mapper && *mapper) { mapper_release_unlocked(*mapper); *mapper = NULL; } return NULL; } /* =item C Returns whether or not there is another item in the map over which C is iterating. On error, returns C<-1> with C set appropriately. =cut */ int mapper_has_next(Mapper *mapper) { List *chain; ssize_t length; if (!mapper) return set_errno(EINVAL); /* Find the current/first chain */ mapper->next_chain_index = mapper->chain_index; mapper->next_item_index = mapper->item_index; if (mapper->next_chain_index == -1) ++mapper->next_chain_index; while (mapper->next_chain_index < mapper->map->size && !mapper->map->chain[mapper->next_chain_index]) ++mapper->next_chain_index; if (mapper->next_chain_index == mapper->map->size) return 0; chain = mapper->map->chain[mapper->next_chain_index]; /* Find the next item */ if ((length = list_length_unlocked(chain)) == -1) return -1; if (++mapper->next_item_index < length) return 1; do { ++mapper->next_chain_index; while (mapper->next_chain_index < mapper->map->size && !mapper->map->chain[mapper->next_chain_index]) ++mapper->next_chain_index; if (mapper->next_chain_index == mapper->map->size) return 0; chain = mapper->map->chain[mapper->next_chain_index]; if ((length = list_length_unlocked(chain)) == -1) return -1; } while (length == 0); mapper->next_item_index = 0; return 1; } /* =item C Returns the next item in the map over which C is iterating. On error, returns C with C set appropriately. =cut */ void *mapper_next(Mapper *mapper) { if (!mapper) return set_errnull(EINVAL); return mapper_next_mapping(mapper)->value; } /* =item C Returns the next mapping (key, value) pair in the map over which C is iterating. On error, returns C with C set appropriately. =cut */ const Mapping *mapper_next_mapping(Mapper *mapper) { if (!mapper) return set_errnull(EINVAL); mapper->chain_index = mapper->next_chain_index; mapper->item_index = mapper->next_item_index; return (Mapping *)list_item_unlocked(mapper->map->chain[mapper->chain_index], mapper->item_index); } /* =item C Removes the current item in the iteration C. The next item in the iteration is the item following the removed item, if any. This must be called after I. On error, sets C appropriately. =cut */ void mapper_remove(Mapper *mapper) { if (!mapper) { set_errno(EINVAL); return; } if (mapper->item_index == -1) { set_errno(EINVAL); return; } list_remove_unlocked(mapper->map->chain[mapper->chain_index], (size_t)mapper->item_index--); --mapper->map->items; } /* =item C Returns whether or not there is another item in C using an internal iterator. The first time this is called, a new internal I will be created (Note: There can be only one at any time for a given map). When there are no more items, returns C<0> and destroys the internal iterator. When it returns C<1>, use I to retrieve the next item. On error, returns C<-1> with C 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 I. Failure to do so will cause the internal iterator to leak. It will also break the next call to I which will continue where the current iteration stopped rather than starting at the beginning again. I assumes that there is no internal iterator, so it is the caller's responsibility to complete the iteration, or call I before releasing C with I or I. Note: The internal I does not lock C 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 C is a parameter or a variable declared outside the function, it is best to create an explicit I instead. If this function is used on such maps instead, it is the caller's responsibility to explicitly lock C first with I and explicitly unlock it with I. Do this even if you are writing single-threaded code, in case your function may one day be used in a multi-threaded application. =cut */ int map_has_next(Map *map) { int has; if (!map) return set_errno(EINVAL); if (!map->mapper && !(map->mapper = mapper_create_unlocked(map))) return -1; if ((has = mapper_has_next(map->mapper)) != 1) map_break(map); return has; } /* =item C Unlocks C and destroys its internal iterator. Must be used only when an iteration using an internal iterator has terminated before reaching the end of C. On error, returns C with C set appropriately. =cut */ void map_break(Map *map) { if (!map) { set_errno(EINVAL); return; } mapper_destroy_unlocked(&map->mapper); } /* =item C Returns the next item in C using its internal iterator. On error, returns C with C set appropriately. =cut */ void *map_next(Map *map) { if (!map || !map->mapper) return set_errnull(EINVAL); return mapper_next(map->mapper); } /* =item C Returns the next mapping (key, value) pair in C using its internal iterator. On error, returns C<-1> with C set appropriately. =cut */ const Mapping *map_next_mapping(Map *map) { if (!map || !map->mapper) return set_errnull(EINVAL); return mapper_next_mapping(map->mapper); } /* =item C Removes the current item in C using its internal iterator. The next item in the iteration is the item following the removed item, if any. This must be called after I. =cut */ void map_remove_current(Map *map) { if (!map || !map->mapper) { set_errno(EINVAL); return; } mapper_remove(map->mapper); } /* =item C Returns the key in C. On error, returns C with C set appropriately. =cut */ const void *mapping_key(const Mapping *mapping) { if (!mapping) return set_errnull(EINVAL); return mapping->key; } /* =item C Returns the value in C. On error, returns C with C set appropriately. =cut */ const void *mapping_value(const Mapping *mapping) { if (!mapping) return set_errnull(EINVAL); return mapping->value; } /* =item C Creates and returns a list of all of the keys contained in C. It is the caller's responsibility to deallocate the new list with I or I. It is strongly recommended to use I, because it also sets the pointer variable to C. The keys in the new list are owned by C, so the list returned must not outlive C. On error, returns C with C set appropriately. =cut */ List *map_keys(Map *map) { return map_keys_with_locker(NULL, map); } /* =item C Equivalent to I except that C is not read-locked. =cut */ List *map_keys_unlocked(Map *map) { return map_keys_with_locker_unlocked(NULL, map); } /* =item C Equivalent to I except that multiple threads accessing the list returned will be synchronised by C. =cut */ List *map_keys_with_locker(Locker *locker, Map *map) { List *keys; int err; if (!map) return set_errnull(EINVAL); if ((err = map_rdlock(map))) return set_errnull(err); keys = map_keys_with_locker_unlocked(locker, map); if ((err = map_unlock(map))) return set_errnull(err); return keys; } /* =item C Equivalent to I except that C is not read-locked. =cut */ List *map_keys_with_locker_unlocked(Locker *locker, Map *map) { Mapper *mapper; List *keys; if (!map) return set_errnull(EINVAL); if (!(keys = list_create_with_locker(locker, NULL))) return NULL; if (!(mapper = mapper_create_unlocked(map))) { list_release(keys); return NULL; } while (mapper_has_next(mapper) == 1) { const Mapping *mapping = mapper_next_mapping(mapper); if (!list_append(keys, mapping->key)) { list_destroy(&keys); break; } } mapper_release_unlocked(mapper); return keys; } /* =item C Creates and returns a list of all of the values contained in C. It is the caller's responsibility to deallocate the new list with I or I. It is strongly recommended to use I, because it also sets the pointer variable to C. The values in the list are not owned by the list, so it must not outlive the owner of the items in C. On error, returns C with C set appropriately. =cut */ List *map_values(Map *map) { return map_values_with_locker(NULL, map); } /* =item C Equivalent to I except that C is not read-locked. =cut */ List *map_values_unlocked(Map *map) { return map_values_with_locker_unlocked(NULL, map); } /* =item C Equivalent to I except that multiple threads accessing the list returned will be synchronised by C. =cut */ List *map_values_with_locker(Locker *locker, Map *map) { List *values; int err; if (!map) return set_errnull(EINVAL); if ((err = map_rdlock(map))) return set_errnull(err); values = map_values_with_locker_unlocked(locker, map); if ((err = map_unlock(map))) return set_errnull(err); return values; } /* =item C Equivalent to I except that C is not read-locked. =cut */ List *map_values_with_locker_unlocked(Locker *locker, Map *map) { Mapper *mapper; List *values; if (!map) return set_errnull(EINVAL); if (!(values = list_create_with_locker(locker, NULL))) return NULL; if (!(mapper = mapper_create_unlocked(map))) { list_release(values); return NULL; } while (mapper_has_next(mapper) == 1) { const Mapping *mapping = mapper_next_mapping(mapper); if (!list_append(values, mapping->value)) { list_destroy(&values); break; } } mapper_release_unlocked(mapper); return values; } /* =item C Invokes C for each of C's items. The arguments passed to C are the key, the item, and C. On error, sets C appropriately. =cut */ void map_apply(Map *map, map_action_t *action, void *data) { map_apply_wrlocked(map, action, data); } /* =item C Equivalent to I except that C is read-locked rather than write-locked. Use this in preference to I when C and its items will not be modified during the iteration. =cut */ void map_apply_rdlocked(Map *map, map_action_t *action, void *data) { int err; if (!map || !action) { set_errno(EINVAL); return; } if ((err = map_rdlock(map))) { set_errno(err); return; } map_apply_unlocked(map, action, data); if ((err = map_unlock(map))) { set_errno(err); return; } } /* =item C Equivalent to I except that this function name makes the fact that C is write-locked explicit. =cut */ void map_apply_wrlocked(Map *map, map_action_t *action, void *data) { int err; if (!map || !action) { set_errno(EINVAL); return; } if ((err = map_wrlock(map))) { set_errno(err); return; } map_apply_unlocked(map, action, data); if ((err = map_unlock(map))) { set_errno(err); return; } } /* =item C Equivalent to I except that C is not write-locked. =cut */ void map_apply_unlocked(Map *map, map_action_t *action, void *data) { Mapper *mapper; if (!map || !action) { set_errno(EINVAL); return; } if (!(mapper = mapper_create_unlocked(map))) return; while (mapper_has_next(mapper) == 1) { const Mapping *mapping = mapper_next_mapping(mapper); action(mapping->key, mapping->value, data); } mapper_release_unlocked(mapper); } /* =item C Returns the number of mappings in C. On error, returns C<-1> with C set appropriately. =cut */ ssize_t map_size(Map *map) { size_t size; int err; if (!map) return set_errno(EINVAL); if ((err = map_rdlock(map))) return set_errno(err); size = map->items; if ((err = map_unlock(map))) return set_errno(err); return size; } /* =item C Equivalent to I except that C is not read-locked. =cut */ ssize_t map_size_unlocked(const Map *map) { if (!map) return set_errno(EINVAL); return map->items; } /* =back =head1 ERRORS On error, C is set either by an underlying function, or as follows: =over 4 =item C When arguments are C or out of range. =item C When I tries to get, or I tries to remove, a non-existent mapping. =back =head1 MT-Level I By default, Is are not I because most programs are single-threaded, and synchronisation doesn't come for free. Even in multi-threaded programs, not all Is are necessarily shared between multiple threads. When a I 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 I may be required, or one lock for all (or a set of) Is 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, Is can be created with I, which takes a I argument. The I specifies a lock and a set of functions for manipulating the lock. Each I can have its own lock by creating a separate I for each I. Multiple Is can share the same lock by sharing the same I. Only the application developer can determine what is appropriate for each application on a case by case basis. I means that the application developer has a mechanism for specifying the synchronisation requirements to be applied to library code. =head1 EXAMPLES 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 #include 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 #include 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 #include 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 #include 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; } =head1 CAVEAT A C 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 I, the internal iterator will leak. =head1 BUGS Uses I directly. The type of memory used and the allocation strategy should be decoupled from this code. =head1 SEE ALSO I, I, I, I =head1 AUTHOR 20230824 raf =cut */ #endif #ifdef TEST #ifndef HAVE_SNPRINTF #include #endif #if 0 static void map_print(const char *name, Map *map) { size_t i, j; if (!map) { printf("%s = nil\n", name); return; } printf("%s =\n{\n", name); for (i = 0; i < map->size; ++i) { if (map->chain[i]) { List *chain = map->chain[i]; ssize_t length = list_length(chain); if (length == -1) printf(" !!! length == -1 !!!\n"); for (j = 0; j < length; ++j) { Mapping *mapping = (Mapping *)list_item(chain, j); printf(" [%d/%d] \"%s\" -> \"%s\"\n", i, j, (char *)mapping->key, (char *)mapping->value); } } } printf("}\n"); } #endif static void map_histogram(const char *name, Map *map) { size_t i; int *histogram; if (!map) { printf("%s = nil\n", name); return; } if (!(histogram = mem_create(map->items, int))) { printf("Failed to allocate histogram for map %s\n", name); return; } memset(histogram, 0, map->items * sizeof(int)); for (i = 0; i < map->size; ++i) { size_t length = list_length(map->chain[i]); if (length == -1) { printf(" length[%d] = -1\n", (int)i); continue; } ++histogram[length]; } printf("\nhistogram %s =\n{\n", name); for (i = 0; i < map->items; ++i) if (histogram[i]) printf(" %d chain%s of length %d\n", histogram[i], (histogram[i] == 1) ? "" : "s", (int)i); printf("}\n"); } static void test_hash(void) { FILE *words = fopen("/usr/dict/words", "r"); char word[BUFSIZ]; Map *map; size_t c; size_t min = 0xffffffff; size_t max = 0x00000000; int sum = 0; if (!words) { printf("Failed to open /usr/dict/words\n"); exit(EXIT_FAILURE); } if (!(map = map_create(free))) { printf("Failed to create map\n"); exit(EXIT_FAILURE); } while (fgets(word, BUFSIZ, words)) { char *eow = strchr(word, '\n'); if (eow) *eow = nul; map_add(map, word, mem_strdup(word)); } fclose(words); printf("%d entries into %d buckets:\n\n", (int)map->items, (int)map->size); for (c = 0; c < map->size; ++c) { size_t length; if (!map->chain[c]) continue; if ((length = list_length(map->chain[c])) == -1) { printf(" length[%d] == -1\n", (int)c); continue; } if (length > max) max = length; if (length < min) min = length; sum += length; } printf("avg = %g\n", (double)sum / (double)map->size); printf("min = %d\n", (int)min); printf("max = %d\n", (int)max); map_histogram("dict", map); map_release(map); exit(EXIT_SUCCESS); } static int sort_cmp(const char **a, const char **b) { return strcmp(*a, *b); } static void test_action(char *key, char *value, char *cat) { size_t len = strlen(cat); snprintf(cat + len, BUFSIZ, "%s%s=%s", (len) ? ", " : "", key, value); } typedef struct Point Point; struct Point { int x; int y; }; static Point *point_create(int x, int y) { Point *point = mem_create(1, Point); if (!point) return NULL; point->x = x; point->y = y; return point; } static Point *point_copy(Point *point) { return point_create(point->x, point->y); } static int point_cmp(Point *a, Point *b) { if (a->x > b->x) return 1; if (a->y > b->y) return 1; if (a->x == b->x && a->y == b->y) return 0; return -1; } static size_t point_hash(size_t size, Point *point) { return (point->x * 31 + point->y * 37) % size; } static void point_release(Point *point) { mem_release(point); } static int direct_copy(int key) { return key; } static int direct_cmp(int a, int b) { return a - b; } static size_t direct_hash(size_t size, int key) { return key % size; } #define RD 0 #define WR 1 Map *mtmap = NULL; Locker *locker = NULL; pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; #ifdef PTHREAD_RWLOCK_INITIALIZER pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER; #else pthread_rwlock_t rwlock; #endif int barrier[2]; int size[2]; const int lim = 1000; int debug = 0; int errors = 0; void *produce(void *arg) { int i; int test = *(int *)arg; for (i = 1; i <= lim; ++i) { if (debug) printf("p: add %d\n", i); if (map_add(mtmap, (void *)(long)i, (void *)(long)i) == -1) ++errors, printf("Test%d: map_add(mtmap, %d), failed (%s)\n", test, i, strerror(errno)); write(size[WR], "", 1); } write(barrier[WR], "", 1); return NULL; } void *consume(void *arg) { int i; int test = *(int *)arg; char ack; for (i = 1; i <= lim; ++i) { if (debug) printf("c: pop\n"); while (read(size[RD], &ack, 1) == -1 && errno == EINTR) {} if (map_remove(mtmap, (void *)(long)i) == -1) { ++errors, printf("Test%d: map_remove(mtmap, %d), failed\n", test, i); break; } if (debug) printf("c: remove %d\n", i); } if (i != lim + 1) ++errors, printf("Test%d: consumer read %d items, not %d\n", test, i - 1, lim); write(barrier[WR], "", 1); return NULL; } void *iterate_builtin(void *arg) { int i; int t = *(int *)arg; int broken = 0; if (debug) printf("i%d: loop\n", t); for (i = 0; i < lim / 10; ++i) { map_wrlock(mtmap); while (map_has_next(mtmap) == 1) { int val = (int)(long)map_next(mtmap); if (debug) printf("i%d: loop %d/%d val %d\n", t, i, lim / 10, val); if (!broken) { map_break(mtmap); broken = 1; break; } } map_unlock(mtmap); } write(barrier[WR], "", 1); return NULL; } void *iterate_rdlocked(void *arg) { int i; int t = *(int *)arg; if (debug) printf("j%d: loop\n", t); for (i = 0; i < lim / 10; ++i) { Mapper *mapper = mapper_create_rdlocked(mtmap); while (mapper_has_next(mapper) == 1) { int val = (int)(long)mapper_next(mapper); if (debug) printf("j%d: loop %d/%d val %d\n", t, i, lim / 10, val); } mapper_release(mapper); } write(barrier[WR], "", 1); return NULL; } void *iterate_wrlocked(void *arg) { int i; int t = *(int *)arg; if (debug) printf("k%d: loop\n", t); for (i = 0; i < lim / 10; ++i) { Mapper *mapper = mapper_create_wrlocked(mtmap); while (mapper_has_next(mapper) == 1) { int val = (int)(long)mapper_next(mapper); if (debug) printf("k%d: loop %d/%d val %d\n", t, i, lim / 10, val); } mapper_release(mapper); } write(barrier[WR], "", 1); return NULL; } pthread_mutex_t rand_mutex[1] = { PTHREAD_MUTEX_INITIALIZER }; void *reader(void *arg) { int i; int t = *(int *)arg; if (debug) printf("r%d: loop\n", t); for (i = 0; i < lim / 10; ++i) { int key, value, r; List *keys, *values; pthread_mutex_lock(rand_mutex); r = rand(); pthread_mutex_unlock(rand_mutex); map_rdlock(mtmap); key = 1 + (int)((double)(map_size_unlocked(mtmap) - 1) * r / (RAND_MAX + 1.0)); value = (int)(long)map_get_unlocked(mtmap, (void *)(long)key); map_unlock(mtmap); keys = map_keys(mtmap); values = map_values(mtmap); if (debug) printf("r%d: loop %d/%d key/val %d/%d, #keys %d, #values %d\n", t, i, lim / 10, key, value, (int)list_length(keys), (int)list_length(values)); list_destroy(&keys); list_destroy(&values); } write(barrier[WR], "", 1); return NULL; } void mt_test(int test, Locker *locker) { mtmap = map_create_generic_with_locker(locker, (map_copy_t *)direct_copy, (map_cmp_t *)direct_cmp, (map_hash_t *)direct_hash, NULL, NULL); if (!mtmap) ++errors, printf("Test%d: map_create_generic_with_locker(NULL) failed\n", test); else { static int iid[13] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }; pthread_attr_t attr; pthread_t id; int i; char ack; if (pipe(size) == -1 || pipe(barrier) == -1) { ++errors, printf("Test%d: failed to perform test: pipe() failed\n", test); return; } srand(getpid() ^ time(NULL)); pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED); pthread_create(&id, &attr, produce, &test); pthread_create(&id, &attr, consume, &test); pthread_create(&id, &attr, iterate_builtin, iid + 0); pthread_create(&id, &attr, iterate_builtin, iid + 1); pthread_create(&id, &attr, iterate_builtin, iid + 2); pthread_create(&id, &attr, iterate_builtin, iid + 3); pthread_create(&id, &attr, iterate_rdlocked, iid + 4); pthread_create(&id, &attr, iterate_rdlocked, iid + 5); pthread_create(&id, &attr, iterate_rdlocked, iid + 6); pthread_create(&id, &attr, iterate_wrlocked, iid + 7); pthread_create(&id, &attr, iterate_wrlocked, iid + 8); pthread_create(&id, &attr, iterate_wrlocked, iid + 9); pthread_create(&id, &attr, reader, iid + 10); pthread_create(&id, &attr, reader, iid + 11); pthread_create(&id, &attr, reader, iid + 12); pthread_attr_destroy(&attr); for (i = 0; i < 15; ++i) while (read(barrier[RD], &ack, 1) == -1 && errno == EINTR) {} map_destroy(&mtmap); if (mtmap) ++errors, printf("Test%d: map_destroy(&mtmap) failed\n", test); close(size[RD]); close(size[WR]); close(barrier[RD]); close(barrier[WR]); } } #define TEST_ACT(i, action) \ if (!(action)) \ ++errors, printf("Test%d: %s failed\n", (i), (#action)); #define TEST_INT_ACT(i, action) \ if ((action) == -1) \ ++errors, printf("Test%d: %s failed\n", (i), (#action)); #define TEST_EQ(i, action, value) \ if ((val = (action)) != (value)) \ ++errors, printf("Test%d: %s failed (returned %d, not %d)\n", (i), (#action), val, (value)); #define TEST_NEQ(i, action, value) \ if ((val = (action)) == (value)) \ ++errors, printf("Test%d: %s failed (returned %d)\n", (i), (#action), val); #define CHECK_ITEM(i, action, key, result) \ if (!(value = (char *)(action)) || strcmp(value, (result))) \ ++errors, printf("Test%d: %s failed (mapping \"%s\" is \"%s\", not \"%s\")\n", (i), (#action), (key), value, (result)); #define CHECK_LIST_ITEM(i, action, list, item, value) \ if (!list_item((list), (item)) || strcmp(list_item((list), (item)), (value))) \ ++errors, printf("Test%d: %s failed (item %d is \"%s\", not \"%s\")\n", (i), (#action), (item), (char *)list_item(list, (item)), (value)); #define CHECK_LIST(i, desc, list) \ if (list_length(list) != 4) \ ++errors, printf("Test%d: %s failed (%d items, not 4)\n", (i), (desc), (int)list_length(list)); \ else \ { \ TEST_ACT((i), list_sort((list), (list_cmp_t *)sort_cmp)); \ CHECK_LIST_ITEM((i), list_sort((list), sort_cmp), (list), 0, "abc") \ CHECK_LIST_ITEM((i), list_sort((list), sort_cmp), (list), 1, "def") \ CHECK_LIST_ITEM((i), list_sort((list), sort_cmp), (list), 2, "ghi") \ CHECK_LIST_ITEM((i), list_sort((list), sort_cmp), (list), 3, "jkl") \ } int main(int ac, char **av) { Map *map; Mapper *mapper; List *keys, *values; const void *ckey; const char *cvalue; char *value; char cat[BUFSIZ]; void *ptr; int val; if (ac == 2 && !strcmp(av[1], "help")) { printf("usage: %s [debug|hash]\n", *av); return EXIT_SUCCESS; } if (ac == 2 && !strcmp(av[1], "hash")) test_hash(); printf("Testing: %s\n", "map"); /* Test map_create, map_add, map_get */ TEST_ACT(1, map = map_create(NULL)) else { TEST_INT_ACT(2, map_add(map, "abc", "abc")) TEST_INT_ACT(3, map_add(map, "def", "def")) TEST_INT_ACT(4, map_add(map, "ghi", "ghi")) TEST_INT_ACT(5, map_add(map, "jkl", "jkl")) CHECK_ITEM(6, map_get(map, "abc"), "abc", "abc") CHECK_ITEM(7, map_get(map, "def"), "def", "def") CHECK_ITEM(8, map_get(map, "ghi"), "ghi", "ghi") CHECK_ITEM(9, map_get(map, "jkl"), "jkl", "jkl") if ((value = (char *)map_get(map, "zzz"))) ++errors, printf("Test10: map_get(\"zzz\") failed\n"); /* Test mapper_create, mapper_has_next, mapper_next, map_destroy */ TEST_ACT(11, mapper = mapper_create(map)) else { TEST_ACT(12, keys = list_create(NULL)) while (mapper_has_next(mapper) == 1) { void *item = mapper_next(mapper); TEST_ACT(13, item) else TEST_ACT(13, list_append(keys, item)) } mapper_destroy(&mapper); if (mapper) ++errors, printf("Test14: mapper_destroy(&mapper) failed (%p, not NULL)", (void *)mapper); CHECK_LIST(15, "mapper_has_next/mapper_next", keys) list_destroy(&keys); } /* Test mapper_next_mapping, mapping_key, mapping_value */ TEST_ACT(16, mapper = mapper_create(map)) else { TEST_ACT(16, keys = list_create(NULL)) TEST_ACT(16, values = list_create(NULL)) while (mapper_has_next(mapper) == 1) { const Mapping *mapping = mapper_next_mapping(mapper); if (!mapping) ++errors, printf("Test17: mapper_next_mapping() failed\n"); else { TEST_ACT(17, ckey = mapping_key((void *)mapping)) else TEST_ACT(17, list_append(keys, (void *)ckey)) TEST_ACT(17, cvalue = mapping_value(mapping)) else TEST_ACT(17, list_append(values, (void *)cvalue)) } } mapper_destroy(&mapper); if (mapper) ++errors, printf("Test18: mapper_destroy(&mapper) failed (%p, not NULL)", (void *)mapper); CHECK_LIST(19, "mapper_has_next/mapper_next_mapping", keys) list_destroy(&keys); CHECK_LIST(20, "mapper_has_next/mapper_next_mapping", values) list_destroy(&values); } /* Test map_has_next, map_next */ TEST_ACT(21, keys = list_create(NULL)) while (map_has_next(map) == 1) { void *item; TEST_ACT(22, item = map_next(map)) else TEST_ACT(22, list_append(keys, item)) } CHECK_LIST(23, "map_has_next/map_next", keys) list_destroy(&keys); /* Test map_next_mapping */ TEST_ACT(24, keys = list_create(NULL)) TEST_ACT(24, values = list_create(NULL)) while (map_has_next(map) == 1) { const Mapping *mapping; TEST_ACT(25, mapping = map_next_mapping(map)) else { TEST_ACT(25, ckey = mapping_key(mapping)) else TEST_ACT(25, list_append(keys, (void *)ckey)) TEST_ACT(25, cvalue = mapping_value(mapping)) else TEST_ACT(25, list_append(values, (void *)cvalue)) } } CHECK_LIST(26, "map_has_next/map_next_mapping", keys) list_destroy(&keys); CHECK_LIST(27, "map_has_next/map_next_mapping", values) list_destroy(&values); /* Test map_keys */ TEST_ACT(28, keys = map_keys(map)) else { CHECK_LIST(29, "map_keys", keys) list_destroy(&keys); } /* Test map_values */ TEST_ACT(30, values = map_values(map)) else { CHECK_LIST(31, "map_values", values) list_destroy(&values); } /* Test map_remove */ TEST_ACT(32, map_remove(map, "zzz") == -1) TEST_ACT(33, map_remove(map, "abc") != -1) TEST_ACT(34, map_remove(map, "def") != -1) TEST_ACT(35, map_remove(map, "ghi") != -1) TEST_ACT(36, map_remove(map, "jkl") != -1) map_destroy(&map); if (map) ++errors, printf("Test37: map_destroy(&map) failed (%p, not NULL)\n", (void *)map); } /* Test map_apply */ TEST_ACT(38, map = map_create(NULL)) else { TEST_ACT(39, map_add(map, "1", "7") == 0) TEST_ACT(40, map_add(map, "2", "6") == 0) TEST_ACT(41, map_add(map, "3", "5") == 0) TEST_ACT(42, map_add(map, "4", "4") == 0) TEST_ACT(43, map_add(map, "5", "3") == 0) TEST_ACT(44, map_add(map, "6", "2") == 0) TEST_ACT(45, map_add(map, "7", "1") == 0) CHECK_ITEM(46, map_get(map, "1"), "1", "7") CHECK_ITEM(47, map_get(map, "2"), "2", "6") CHECK_ITEM(48, map_get(map, "3"), "3", "5") CHECK_ITEM(49, map_get(map, "4"), "4", "4") CHECK_ITEM(50, map_get(map, "5"), "5", "3") CHECK_ITEM(51, map_get(map, "6"), "6", "2") CHECK_ITEM(52, map_get(map, "7"), "7", "1") cat[0] = nul; map_apply(map, (map_action_t *)test_action, cat); if (strcmp(cat, "7=1, 1=7, 2=6, 3=5, 4=4, 5=3, 6=2")) ++errors, printf("Test53: map_apply(cat) failed (cat = \"%s\", not \"%s\")\n", cat, "7=1, 1=7, 2=6, 3=5, 4=4, 5=3, 6=2"); map_destroy(&map); if (map) ++errors, printf("Test54: map_destroy(&map) failed (%p, not NULL)\n", (void *)map); } /* Test mapper_remove, map_size */ TEST_ACT(55, map = map_create(NULL)) else { TEST_ACT(56, map_add(map, "1", "7") == 0) TEST_ACT(57, map_add(map, "2", "6") == 0) TEST_ACT(58, map_add(map, "3", "5") == 0) TEST_ACT(59, map_add(map, "4", "4") == 0) TEST_ACT(60, map_add(map, "5", "3") == 0) TEST_ACT(61, map_add(map, "6", "2") == 0) TEST_ACT(62, map_add(map, "7", "1") == 0) TEST_ACT(63, mapper = mapper_create(map)) else { while (mapper_has_next(mapper) == 1) { void *item; TEST_ACT(64, item = mapper_next(mapper)) mapper_remove(mapper); } mapper_destroy(&mapper); if (mapper) ++errors, printf("Test65: mapper_destroy(&mapper) failed (%p, not NULL)\n", (void *)mapper); TEST_EQ(66, map_size(map), 0) } map_destroy(&map); if (map) ++errors, printf("Test67: map_destroy(&map) failed (%p, not NULL)\n", (void *)map); } /* Test map_remove_current */ TEST_ACT(68, map = map_create(NULL)) else { TEST_ACT(69, map_add(map, "1", "1") == 0) TEST_ACT(70, map_add(map, "2", "2") == 0) TEST_ACT(71, map_add(map, "3", "3") == 0) TEST_ACT(72, map_add(map, "4", "4") == 0) while (map_has_next(map) == 1) { void *item; TEST_ACT(73, item = map_next(map)) map_remove_current(map); } TEST_EQ(74, map_size(map), 0) mapper_destroy(&mapper); map_destroy(&map); } /* Test map_create_generic (Point -> char *) */ #define ADD_POINT(i, xpos, ypos, value, rc) \ point->x = (xpos); \ point->y = (ypos); \ TEST_ACT((i), map_add(map, point, (value)) == (rc)) #define GET_POINT(i, xpos, ypos, str) \ point->x = (xpos); \ point->y = (ypos); \ if (!(value = map_get(map, point))) \ ++errors, printf("Test%d: map_get(generic) failed\n", (i)); \ else if (strcmp(value, (str))) \ ++errors, printf("Test%d: map_get(generic) failed (\"%s\", not \"%s\")\n", (i), value, (str)); TEST_ACT(75, map = map_create_generic((map_copy_t *)point_copy, (map_cmp_t *)point_cmp, (map_hash_t *)point_hash, (map_release_t *)point_release, NULL)) else { Point *point = point_create(0, 0); ADD_POINT(76, 0, 0, "(0, 0)", 0) ADD_POINT(77, 1, 0, "(1, 0)", 0) ADD_POINT(78, 0, 1, "(0, 1)", 0) ADD_POINT(79, 1, 1, "(1, 1)", 0) ADD_POINT(80, -1, 0, "(-1, 0)", 0) ADD_POINT(81, 0, -1, "(0, -1)", 0) ADD_POINT(82, -1, -1, "(-1, -1)", 0) ADD_POINT(83, 2, 0, "(2, 0)", 0) ADD_POINT(84, 0, 2, "(0, 2)", 0) ADD_POINT(85, 2, 2, "(2, 2)", 0) ADD_POINT(86, -2, 0, "(-2, 0)", 0) ADD_POINT(87, 0, -2, "(0, -2)", 0) ADD_POINT(88, -2, -2, "(-2, -2)", 0) ADD_POINT(89, 0, 0, "(0, 0)", -1) TEST_EQ(90, map_size(map), 13) GET_POINT(91, 0, 0, "(0, 0)") GET_POINT(92, 1, 0, "(1, 0)") GET_POINT(93, 0, 1, "(0, 1)") GET_POINT(94, 1, 1, "(1, 1)") GET_POINT(95, -1, 0, "(-1, 0)") GET_POINT(96, 0, -1, "(0, -1)") GET_POINT(97, -1, -1, "(-1, -1)") GET_POINT(98, 2, 0, "(2, 0)") GET_POINT(99, 0, 2, "(0, 2)") GET_POINT(100, 2, 2, "(2, 2)") GET_POINT(101, -2, 0, "(-2, 0)") GET_POINT(102, 0, -2, "(0, -2)") GET_POINT(103, -2, -2, "(-2, -2)") point_release(point); map_destroy(&map); } /* Test map_create_generic (int -> int) and map growth */ TEST_ACT(104, map = map_create_generic((map_copy_t *)direct_copy, (map_cmp_t *)direct_cmp, (map_hash_t *)direct_hash, NULL, NULL)) else { TEST_ACT(105, map_add(map, (void *)1, (void *)1) == 0) TEST_ACT(106, map_add(map, (void *)2, (void *)2) == 0) TEST_ACT(107, map_add(map, (void *)3, (void *)3) == 0) TEST_ACT(108, map_add(map, (void *)4, (void *)4) == 0) TEST_ACT(109, map_add(map, (void *)5, (void *)5) == 0) TEST_ACT(110, map_add(map, (void *)6, (void *)6) == 0) TEST_ACT(111, map_add(map, (void *)7, (void *)7) == 0) TEST_ACT(112, map_add(map, (void *)8, (void *)8) == 0) TEST_ACT(113, map_add(map, (void *)9, (void *)9) == 0) TEST_ACT(114, map_add(map, (void *)10, (void *)10) == 0) TEST_ACT(115, map_add(map, (void *)11, (void *)11) == 0) TEST_ACT(116, map_add(map, (void *)12, (void *)12) == 0) TEST_ACT(117, map_add(map, (void *)13, (void *)13) == 0) TEST_ACT(118, map_add(map, (void *)14, (void *)14) == 0) TEST_ACT(119, map_add(map, (void *)15, (void *)15) == 0) TEST_ACT(120, map_add(map, (void *)16, (void *)16) == 0) TEST_ACT(121, map_add(map, (void *)17, (void *)17) == 0) TEST_ACT(122, map_add(map, (void *)18, (void *)18) == 0) TEST_ACT(123, map_add(map, (void *)19, (void *)19) == 0) TEST_ACT(124, map_add(map, (void *)20, (void *)20) == 0) TEST_ACT(125, map_add(map, (void *)21, (void *)21) == 0) TEST_ACT(126, map_add(map, (void *)22, (void *)22) == 0) TEST_ACT(127, map_add(map, (void *)23, (void *)23) == 0) TEST_ACT(128, map_add(map, (void *)24, (void *)24) == 0) TEST_ACT(129, map_add(map, (void *)25, (void *)25) == 0) TEST_ACT(130, map_add(map, (void *)25, (void *)25) != 0) TEST_EQ(130, map_size(map), 25) TEST_EQ(131, (int)(long)map_get(map, (void *)1), 1) TEST_EQ(132, (int)(long)map_get(map, (void *)2), 2) TEST_EQ(133, (int)(long)map_get(map, (void *)3), 3) TEST_EQ(134, (int)(long)map_get(map, (void *)4), 4) TEST_EQ(135, (int)(long)map_get(map, (void *)5), 5) TEST_EQ(136, (int)(long)map_get(map, (void *)6), 6) TEST_EQ(137, (int)(long)map_get(map, (void *)7), 7) TEST_EQ(138, (int)(long)map_get(map, (void *)8), 8) TEST_EQ(139, (int)(long)map_get(map, (void *)9), 9) TEST_EQ(140, (int)(long)map_get(map, (void *)10), 10) TEST_EQ(141, (int)(long)map_get(map, (void *)11), 11) TEST_EQ(142, (int)(long)map_get(map, (void *)12), 12) TEST_EQ(143, (int)(long)map_get(map, (void *)13), 13) TEST_EQ(144, (int)(long)map_get(map, (void *)14), 14) TEST_EQ(145, (int)(long)map_get(map, (void *)15), 15) TEST_EQ(146, (int)(long)map_get(map, (void *)16), 16) TEST_EQ(147, (int)(long)map_get(map, (void *)17), 17) TEST_EQ(148, (int)(long)map_get(map, (void *)18), 18) TEST_EQ(149, (int)(long)map_get(map, (void *)19), 19) TEST_EQ(150, (int)(long)map_get(map, (void *)20), 20) TEST_EQ(151, (int)(long)map_get(map, (void *)21), 21) TEST_EQ(152, (int)(long)map_get(map, (void *)22), 22) TEST_EQ(153, (int)(long)map_get(map, (void *)23), 23) TEST_EQ(154, (int)(long)map_get(map, (void *)24), 24) TEST_EQ(155, (int)(long)map_get(map, (void *)25), 25) map_destroy(&map); } /* Test MT Safety */ debug = ac == 2 && !strcmp(av[1], "debug"); if (debug) setbuf(stdout, NULL); #ifndef PTHREAD_RWLOCK_INITIALIZER pthread_rwlock_init(&rwlock, NULL); #endif if (debug) locker = locker_create_debug_rwlock(&rwlock); else locker = locker_create_rwlock(&rwlock); if (!locker) ++errors, printf("Test220: locker_create_rwlock() failed\n"); else { mt_test(220, locker); locker_destroy(&locker); } if (debug) locker = locker_create_debug_mutex(&mutex); else locker = locker_create_mutex(&mutex); if (!locker) ++errors, printf("Test221: locker_create_mutex() failed\n"); else { mt_test(221, locker); locker_destroy(&locker); } /* Test assumption: sizeof(int) <= sizeof(void *) */ if (sizeof(int) > sizeof(void *)) ++errors, printf("Test 222: assumption failed: sizeof(int) > sizeof(void *): int maps are limited to %d bytes\n", (int)sizeof(void *)); /* Test assumption: memset(&ptr, 0, sizeof(void *)) same as NULL */ memset(&ptr, 0, sizeof(void *)); if (ptr != NULL) ++errors, printf("Test223: assumption failed: memset(&ptr, 0, sizeof(void *)) not same as NULL\n"); if (errors) printf("%d/223 tests failed\n", errors); else printf("All tests passed\n"); return (errors == 0) ? EXIT_SUCCESS : EXIT_FAILURE; } #endif /* vi:set ts=4 sw=4: */