src/cx/map.h

/*
 * 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

/** 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 map entry where the pointer to the key is @c NULL if allocation fails.
     */
    CxMapEntry (*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_EXTERN
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_EXTERN CX_NONNULL
void cxMapClear(CxMap *map);

/**
 * Returns the number of elements in this map.
 *
 * @param map the map
 * @return the number of stored elements
 */
CX_EXTERN CX_NONNULL
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_EXTERN CX_NODISCARD
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_EXTERN CX_NODISCARD
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_EXTERN CX_NODISCARD
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_EXTERN CX_NONNULL
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
 * @see cxMapEmplace()
 */
CX_EXTERN CX_NONNULL CX_NODISCARD
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
 * @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_EXTERN CX_NONNULL CX_NODISCARD
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_EXTERN CX_NONNULL_ARG(1)
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_EXTERN CX_NONNULL_ARG(1, 2, 3)
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_EXTERN CX_NONNULL_ARG(1, 2, 3, 4)
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_EXTERN CX_NONNULL_ARG(1, 2, 3, 4)
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_EXTERN CX_NONNULL_ARG(1, 2, 3, 4)
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_EXTERN CX_NONNULL_ARG(1, 2, 3, 4)
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_EXTERN CX_NONNULL_ARG(1, 2, 3)
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_EXTERN CX_NONNULL
int cxMapCloneShallow(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_EXTERN CX_NONNULL
int cxMapDifferenceShallow(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_EXTERN CX_NONNULL
int cxMapListDifferenceShallow(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_EXTERN CX_NONNULL
int cxMapIntersectionShallow(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_EXTERN CX_NONNULL
int cxMapListIntersectionShallow(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_EXTERN CX_NONNULL
int cxMapUnionShallow(CxMap *dst, const CxMap *src);

/**
 * Compares the entries of two maps.
 *
 * @param map the map
 * @param other the other map that the first map is compared to
 * @retval zero when both maps have the same key sets
 * and the values are pairwise equivalent
 * @retval negative when the first @p map has fewer keys than the @p other map
 * @retval positive when the first @p map has more keys than the @p other map
 * @retval non-zero (unspecified whether positive or negative) when the size
 * of both maps is equal but a key or a value is different
 */
CX_EXTERN CX_NONNULL
int cxMapCompare(const CxMap *map, const CxMap *other);

#endif // UCX_MAP_H