/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
/**
* @file map.h
* @brief Interface for map implementations.
* @author Mike Becker
* @author Olaf Wintermann
* @copyright 2-Clause BSD License
*/
#ifndef UCX_MAP_H
#define UCX_MAP_H
#include "common.h"
#include "collection.h"
#include "string.h"
#include "hash_key.h"
#ifndef UCX_LIST_H
// forward-declare CxList
typedef struct cx_list_s CxList;
#endif
#ifdef __cplusplus
extern "C" {
#endif
/** Type for the UCX map. */
typedef struct cx_map_s CxMap;
/** Type for a map entry. */
typedef struct cx_map_entry_s CxMapEntry;
/** Type for a map iterator. */
typedef struct cx_map_iterator_s CxMapIterator;
/** Type for map class definitions. */
typedef struct cx_map_class_s cx_map_class;
/** Structure for the UCX map. */
struct cx_map_s {
/**
* Base attributes.
*/
CX_COLLECTION_BASE;
/** The map class definition. */
cx_map_class *cl;
};
/**
* A map entry.
*/
struct cx_map_entry_s {
/**
* A pointer to the key.
*/
const CxHashKey *key;
/**
* A pointer to the value.
*/
void *value;
};
/**
* The type of iterator for a map.
*/
enum cx_map_iterator_type {
/**
* Iterates over key/value pairs.
*/
CX_MAP_ITERATOR_PAIRS,
/**
* Iterates over keys only.
*/
CX_MAP_ITERATOR_KEYS,
/**
* Iterates over values only.
*/
CX_MAP_ITERATOR_VALUES
};
/**
* Internal iterator struct - use CxMapIterator.
*/
struct cx_map_iterator_s {
/**
* Inherited common data for all iterators.
*/
CX_ITERATOR_BASE;
/**
* Handle for the source map.
*/
CxMap *map;
/**
* Handle for the current element.
*
* @attention Depends on the map implementation, do not assume a type (better: do not use!).
*/
void *elem;
/**
* Reserved memory for a map entry.
*
* If a map implementation uses an incompatible layout, the iterator needs something
* to point to during iteration which @em is compatible.
*/
CxMapEntry entry;
/**
* Field for storing the current slot number.
*
* (Used internally)
*/
size_t slot;
/**
* Counts the elements successfully.
* It usually does not denote a stable index within the map as it would be for arrays.
*/
size_t index;
/**
* The size of a value stored in this map.
*/
size_t elem_size;
/**
* May contain the total number of elements, if known.
* Set to @c SIZE_MAX when the total number is unknown during iteration.
*
* @remark The UCX implementations of #CxMap always know the number of elements they store.
*/
size_t elem_count;
/**
* The type of this iterator.
*/
enum cx_map_iterator_type type;
};
/**
* The class definition for arbitrary maps.
*/
struct cx_map_class_s {
/**
* Deallocates the entire memory.
*/
void (*deallocate)(struct cx_map_s *map);
/**
* Removes all elements.
*/
void (*clear)(struct cx_map_s *map);
/**
* Add or overwrite an element.
* If the @p value is @c NULL, the implementation
* shall only allocate memory instead of adding an existing value to the map.
* Returns a pointer to the allocated memory or @c NULL if allocation fails.
*/
void *(*put)(CxMap *map, CxHashKey key, void *value);
/**
* Returns an element.
*/
void *(*get)(const CxMap *map, CxHashKey key);
/**
* Removes an element.
*
* Implementations SHALL check if @p targetbuf is set and copy the elements
* to the buffer without invoking any destructor.
* When @p targetbuf is not set, the destructors SHALL be invoked.
*
* The function SHALL return zero when the @p key was found and
* non-zero, otherwise.
*/
int (*remove)(CxMap *map, CxHashKey key, void *targetbuf);
/**
* Creates an iterator for this map.
*/
CxMapIterator (*iterator)(const CxMap *map, enum cx_map_iterator_type type);
};
/**
* A shared instance of an empty map.
*
* Writing to that map is not allowed.
*
* You can use this as a placeholder for initializing CxMap pointers
* for which you do not want to reserve memory right from the beginning.
*/
CX_EXPORT extern CxMap *const cxEmptyMap;
/**
* Deallocates the memory of the specified map.
*
* Also calls the content destructor functions for each element, if specified.
*
* @param map the map to be freed
*/
CX_EXPORT void cxMapFree(CxMap *map);
/**
* Clears a map by removing all elements.
*
* Also calls the content destructor functions for each element, if specified.
*
* @param map the map to be cleared
*/
cx_attr_nonnull
CX_EXPORT void cxMapClear(CxMap *map);
/**
* Returns the number of elements in this map.
*
* @param map the map
* @return the number of stored elements
*/
cx_attr_nonnull
CX_EXPORT size_t cxMapSize(const CxMap *map);
/**
* Creates a value iterator for a map.
*
* When the map is storing pointers, those pointers are returned.
* Otherwise, the iterator iterates over pointers to the memory within the map where the
* respective elements are stored.
*
* @note An iterator iterates over all elements successively. Therefore, the order
* highly depends on the map implementation and may change arbitrarily when the contents change.
*
* @param map the map to create the iterator for (can be @c NULL)
* @return an iterator for the currently stored values
*/
cx_attr_nodiscard
CX_EXPORT CxMapIterator cxMapIteratorValues(const CxMap *map);
/**
* Creates a key iterator for a map.
*
* The elements of the iterator are keys of type CxHashKey, and the pointer returned
* during iterator shall be treated as @c const @c CxHashKey* .
*
* @note An iterator iterates over all elements successively. Therefore, the order
* highly depends on the map implementation and may change arbitrarily when the contents change.
*
* @param map the map to create the iterator for (can be @c NULL)
* @return an iterator for the currently stored keys
*/
cx_attr_nodiscard
CX_EXPORT CxMapIterator cxMapIteratorKeys(const CxMap *map);
/**
* Creates an iterator for a map.
*
* The elements of the iterator are key/value pairs of type CxMapEntry, and the pointer returned
* during iterator shall be treated as @c const @c CxMapEntry* .
*
* @note An iterator iterates over all elements successively. Therefore, the order
* highly depends on the map implementation and may change arbitrarily when the contents change.
*
* @param map the map to create the iterator for (can be @c NULL)
* @return an iterator for the currently stored entries
* @see cxMapIteratorKeys()
* @see cxMapIteratorValues()
*/
cx_attr_nodiscard
CX_EXPORT CxMapIterator cxMapIterator(const CxMap *map);
/**
* Puts a key/value-pair into the map.
*
* A possible existing value will be overwritten.
* If destructor functions are specified, they are called for
* the overwritten element.
*
* If this map is storing pointers, the @p value pointer is written
* to the map. Otherwise, the memory is copied from @p value with
* memcpy().
*
* The @p key is always copied.
*
* @param map the map
* @param key the key
* @param value the value
* @retval zero success
* @retval non-zero value on memory allocation failure
* @see cxMapPut()
*/
cx_attr_nonnull
CX_EXPORT int cx_map_put(CxMap *map, CxHashKey key, void *value);
/**
* Puts a key/value-pair into the map.
*
* A possible existing value will be overwritten.
* If destructor functions are specified, they are called for
* the overwritten element.
*
* If this map is storing pointers, the @p value pointer is written
* to the map. Otherwise, the memory is copied from @p value with
* memcpy().
*
* The @p key is always copied.
*
* @param map (@c CxMap*) the map
* @param key (any supported key type) the key
* @param value (@c void*) the value
* @retval zero success
* @retval non-zero value on memory allocation failure
* @see CX_HASH_KEY()
*/
#define cxMapPut(map, key, value) cx_map_put(map, CX_HASH_KEY(key), value)
/**
* Allocates memory for a value in the map associated with the specified key.
*
* A possible existing value will be overwritten.
* If destructor functions are specified, they are called for
* the overwritten element.
*
* If the map is storing pointers, this function returns a @c void** pointer,
* meaning a pointer to that pointer.
*
* The @p key is always copied.
*
* @param map the map
* @param key the key
* @return the pointer to the allocated memory or @c NULL if allocation fails
* @retval zero success
* @retval non-zero value on memory allocation failure
* @see cxMapEmplace()
*/
cx_attr_nonnull
CX_EXPORT void *cx_map_emplace(CxMap *map, CxHashKey key);
/**
* Allocates memory for a value in the map associated with the specified key.
*
* A possible existing value will be overwritten.
* If destructor functions are specified, they are called for
* the overwritten element.
*
* If the map is storing pointers, this function returns a @c void** pointer,
* meaning a pointer to that pointer.
*
* The @p key is always copied.
*
* @param map (@c CxMap*) the map
* @param key (any supported key type) the key
* @return the pointer to the allocated memory or @c NULL if allocation fails
* @retval zero success
* @retval non-zero value on memory allocation failure
* @see CX_HASH_KEY()
*/
#define cxMapEmplace(map, key) cx_map_emplace(map, CX_HASH_KEY(key))
/**
* Retrieves a value by using a key.
*
* If this map is storing pointers, the stored pointer is returned.
* Otherwise, a pointer to the element within the map's memory
* is returned (which is valid as long as the element stays in the map).
*
* @param map the map
* @param key the key
* @return the value
* @see cxMapGet()
*/
cx_attr_nonnull cx_attr_nodiscard
CX_EXPORT void *cx_map_get(const CxMap *map, CxHashKey key);
/**
* Retrieves a value by using a key.
*
* If this map is storing pointers, the stored pointer is returned.
* Otherwise, a pointer to the element within the map's memory
* is returned (which is valid as long as the element stays in the map).
*
* @param map (@c CxMap*) the map
* @param key (any supported key type) the key
* @return (@c void*) the value or @c NULL when no value with that @p key exists
* @see CX_HASH_KEY()
*/
#define cxMapGet(map, key) cx_map_get(map, CX_HASH_KEY(key))
/**
* Checks if a map contains a specific key.
*
* @param map (@c CxMap*) the map
* @param key (any supported key type) the key
* @retval true if the key exists in the map
* @retval false if the key does not exist in the map
* @see CX_HASH_KEY()
*/
#define cxMapContains(map, key) (cxMapGet(map, key) != NULL)
/**
* Removes a key/value-pair from the map by using the key.
*
* Invokes the destructor functions, if any, on the removed element if and only if the
* @p targetbuf is @c NULL.
*
* @param map the map
* @param key the key
* @param targetbuf the optional buffer where the removed element shall be copied to
* @retval zero success
* @retval non-zero the key was not found
*
* @see cxMapRemove()
* @see cxMapRemoveAndGet()
*/
cx_attr_nonnull_arg(1)
CX_EXPORT int cx_map_remove(CxMap *map, CxHashKey key, void *targetbuf);
/**
* Removes a key/value-pair from the map by using the key.
*
* Always invokes the destructor functions, if any, on the removed element.
*
* @param map (@c CxMap*) the map
* @param key (any supported key type) the key
* @retval zero success
* @retval non-zero the key was not found
*
* @see cxMapRemoveAndGet()
* @see CX_HASH_KEY()
*/
#define cxMapRemove(map, key) cx_map_remove(map, CX_HASH_KEY(key), NULL)
/**
* Removes a key/value-pair from the map by using the key.
*
* This function will copy the contents of the removed element
* to the target buffer, which must be guaranteed to be large enough
* to hold the element (the map's element size).
* The destructor functions, if any, will @em not be called.
*
* If this map is storing pointers, the element is the pointer itself
* and not the object it points to.
*
* @param map (@c CxMap*) the map
* @param key (any supported key type) the key
* @param targetbuf (@c void*) the buffer where the element shall be copied to
* @retval zero success
* @retval non-zero the key was not found
*
* @see cxMapRemove()
* @see CX_HASH_KEY()
*/
#define cxMapRemoveAndGet(map, key, targetbuf) cx_map_remove(map, CX_HASH_KEY(key), targetbuf)
/**
* Performs a deep clone of one map into another.
*
* If the destination map already contains entries, the cloned entries
* are added to that map, possibly overwriting existing elements when
* the keys already exist.
*
* When elements in the destination map need to be replaced, any destructor
* function is called on the replaced elements before replacing them.
*
* @attention If the cloned elements need to be destroyed by a destructor
* function, you must make sure that the destination map also uses this
* destructor function.
*
* @param dst the destination map
* @param src the source map
* @param clone_func the clone function for the values
* @param clone_allocator the allocator that is passed to the clone function
* @param data optional additional data that is passed to the clone function
* @retval zero when all elements were successfully cloned
* @retval non-zero when an allocation error occurred
*/
cx_attr_nonnull_arg(1, 2, 3)
CX_EXPORT int cxMapClone(CxMap *dst, const CxMap *src,
cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
/**
* Clones entries of a map if their key is not present in another map.
*
* @param dst the destination map
* @param minuend the map to subtract the entries from
* @param subtrahend the map containing the elements to be subtracted
* @param clone_func the clone function for the values
* @param clone_allocator the allocator that is passed to the clone function
* @param data optional additional data that is passed to the clone function
* @retval zero when the elements were successfully cloned
* @retval non-zero when an allocation error occurred
*/
cx_attr_nonnull_arg(1, 2, 3, 4)
CX_EXPORT int cxMapDifference(CxMap *dst, const CxMap *minuend, const CxMap *subtrahend,
cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
/**
* Clones entries of a map if their key is not present in a list.
*
* Note that the list must contain keys of type @c CxKey
* (or pointers to such keys) and must use @c cx_hash_key_cmp
* as the compare function.
* Generic key types cannot be processed in this case.
*
* @param dst the destination map
* @param src the source map
* @param keys the list of @c CxKey items
* @param clone_func the clone function for the values
* @param clone_allocator the allocator that is passed to the clone function
* @param data optional additional data that is passed to the clone function
* @retval zero when the elements were successfully cloned
* @retval non-zero when an allocation error occurred
*/
cx_attr_nonnull_arg(1, 2, 3, 4)
CX_EXPORT int cxMapListDifference(CxMap *dst, const CxMap *src, const CxList *keys,
cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
/**
* Clones entries of a map only if their key is present in another map.
*
* @param dst the destination map
* @param src the map to clone the entries from
* @param other the map to check for existence of the keys
* @param clone_func the clone function for the values
* @param clone_allocator the allocator that is passed to the clone function
* @param data optional additional data that is passed to the clone function
* @retval zero when the elements were successfully cloned
* @retval non-zero when an allocation error occurred
*/
cx_attr_nonnull_arg(1, 2, 3, 4)
CX_EXPORT int cxMapIntersection(CxMap *dst, const CxMap *src, const CxMap *other,
cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
/**
* Clones entries of a map only if their key is present in a list.
*
* Note that the list must contain keys of type @c CxKey
* (or pointers to such keys) and must use @c cx_hash_key_cmp
* as the compare function.
* Generic key types cannot be processed in this case.
*
* @param dst the destination map
* @param src the source map
* @param keys the list of @c CxKey items
* @param clone_func the clone function for the values
* @param clone_allocator the allocator that is passed to the clone function
* @param data optional additional data that is passed to the clone function
* @retval zero when the elements were successfully cloned
* @retval non-zero when an allocation error occurred
*/
cx_attr_nonnull_arg(1, 2, 3, 4)
CX_EXPORT int cxMapListIntersection(CxMap *dst, const CxMap *src, const CxList *keys,
cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
/**
* Clones entries into a map if their key does not exist yet.
*
* If you want to calculate the union of two maps into a fresh new map,
* you can proceed as follows:
* 1. Clone the first map into a fresh, empty map.
* 2. Use this function to clone the second map into the result from step 1.
*
* @param dst the destination map
* @param src the map to clone the entries from
* @param clone_func the clone function for the values
* @param clone_allocator the allocator that is passed to the clone function
* @param data optional additional data that is passed to the clone function
* @retval zero when the elements were successfully cloned
* @retval non-zero when an allocation error occurred
*/
cx_attr_nonnull_arg(1, 2, 3)
CX_EXPORT int cxMapUnion(CxMap *dst, const CxMap *src,
cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
/**
* Performs a shallow clone of one map into another.
*
* This function uses the default allocator, if needed, and performs
* shallow clones with @c memcpy().
*
* If the destination map already contains entries, the cloned entries
* are added to that map, possibly overwriting existing elements when
* the keys already exist.
*
* When elements in the destination map need to be replaced, any destructor
* function is called on the replaced elements before replacing them.
*
* @attention If the cloned elements need to be destroyed by a destructor
* function, you must make sure that the destination map also uses this
* destructor function.
*
* @param dst the destination map
* @param src the source map
* @retval zero when all elements were successfully cloned
* @retval non-zero when an allocation error occurred
* @see cxMapClone()
*/
cx_attr_nonnull
CX_EXPORT int cxMapCloneSimple(CxMap *dst, const CxMap *src);
/**
* Clones entries of a map if their key is not present in another map.
*
* This function uses the default allocator, if needed, and performs
* shallow clones with @c memcpy().
*
* @param dst the destination map
* @param minuend the map to subtract the entries from
* @param subtrahend the map containing the elements to be subtracted
* @retval zero when the elements were successfully cloned
* @retval non-zero when an allocation error occurred
*/
cx_attr_nonnull
CX_EXPORT int cxMapDifferenceSimple(CxMap *dst, const CxMap *minuend, const CxMap *subtrahend);
/**
* Clones entries of a map if their key is not present in a list.
*
* This function uses the default allocator, if needed, and performs
* shallow clones with @c memcpy().
*
* Note that the list must contain keys of type @c CxKey
* (or pointers to such keys) and must use @c cx_hash_key_cmp
* as the compare function.
* Generic key types cannot be processed in this case.
*
* @param dst the destination map
* @param src the source map
* @param keys the list of @c CxKey items
* @retval zero when the elements were successfully cloned
* @retval non-zero when an allocation error occurred
* @see cxMapListDifference()
*/
cx_attr_nonnull
CX_EXPORT int cxMapListDifferenceSimple(CxMap *dst, const CxMap *src, const CxList *keys);
/**
* Clones entries of a map only if their key is present in another map.
*
* This function uses the default allocator, if needed, and performs
* shallow clones with @c memcpy().
*
* @param dst the destination map
* @param src the map to clone the entries from
* @param other the map to check for existence of the keys
* @retval zero when the elements were successfully cloned
* @retval non-zero when an allocation error occurred
*/
cx_attr_nonnull
CX_EXPORT int cxMapIntersectionSimple(CxMap *dst, const CxMap *src, const CxMap *other);
/**
* Clones entries of a map only if their key is present in a list.
*
* This function uses the default allocator, if needed, and performs
* shallow clones with @c memcpy().
*
* Note that the list must contain keys of type @c CxKey
* (or pointers to such keys) and must use @c cx_hash_key_cmp
* as the compare function.
* Generic key types cannot be processed in this case.
*
* @param dst the destination map
* @param src the source map
* @param keys the list of @c CxKey items
* @retval zero when the elements were successfully cloned
* @retval non-zero when an allocation error occurred
*/
cx_attr_nonnull
CX_EXPORT int cxMapListIntersectionSimple(CxMap *dst, const CxMap *src, const CxList *keys);
/**
* Clones entries into a map if their key does not exist yet.
*
* This function uses the default allocator, if needed, and performs
* shallow clones with @c memcpy().
*
* If you want to calculate the union of two maps into a fresh new map,
* you can proceed as follows:
* 1. Clone the first map into a fresh, empty map.
* 2. Use this function to clone the second map into the result from step 1.
*
* @param dst the destination map
* @param src the map to clone the entries from
* @retval zero when the elements were successfully cloned
* @retval non-zero when an allocation error occurred
*/
cx_attr_nonnull
CX_EXPORT int cxMapUnionSimple(CxMap *dst, const CxMap *src);
#ifdef __cplusplus
} // extern "C"
#endif
#endif // UCX_MAP_H