ucx/cx/collection.h

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2023 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 collection.h
 * @brief Common definitions for various collection implementations.
 * @author Mike Becker
 * @author Olaf Wintermann
 * @copyright 2-Clause BSD License
 */

#ifndef UCX_COLLECTION_H
#define UCX_COLLECTION_H

#include "allocator.h"
#include "iterator.h"
#include "compare.h"

#ifdef __cplusplus
extern "C" {
#endif

/**
 * Special constant used for creating collections that are storing pointers.
 */
#define CX_STORE_POINTERS 0

/**
 * Base attributes of a collection.
 */
struct cx_collection_s {
    /**
     * The allocator to use.
     */
    const CxAllocator *allocator;
    /**
     * The size of each element.
     */
    size_t elem_size;
    /**
     * The number of currently stored elements.
     */
    size_t size;
    /**
     * A two-argument comparator function for the elements.
     */
    cx_compare_func simple_cmp;
    /**
     * A three-argument comparator function for the elements.
     * If specified, this function has precedence over the @c simple_cmp function.
     */
    cx_compare_func2 advanced_cmp;
    /**
     * A pointer to custom data for the @c advanced_cmp function
     */
    void *cmp_data;
    /**
     * An optional simple destructor for the collection's elements.
     *
     * @attention Read the documentation of the particular collection implementation
     * whether this destructor shall only destroy the contents or also free the memory.
     */
    cx_destructor_func simple_destructor;
    /**
     * An optional advanced destructor for the collection's elements.
     *
     * @attention Read the documentation of the particular collection implementation
     * whether this destructor shall only destroy the contents or also free the memory.
     */
    cx_destructor_func2 advanced_destructor;
    /**
     * The pointer to additional data that is passed to the advanced destructor.
     */
    void *destructor_data;
    /**
     * Indicates if this list is supposed to store pointers
     * instead of copies of the actual objects.
     */
    bool store_pointer;
    /**
     * Indicates if this collection is guaranteed to be sorted.
     * Note that the elements can still be sorted, even when the collection is not aware of that.
     */
    bool sorted;
};

/**
 * Use this macro to declare common members for a collection structure.
 *
 * @par Example Use
 * @code
 * struct MyCustomSet {
 *     CX_COLLECTION_BASE;
 *     MySetElements *data;
 * }
 * @endcode
 */
#define CX_COLLECTION_BASE struct cx_collection_s collection

/**
 * Returns the number of elements currently stored.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @return (@c size_t) the number of currently stored elements
 */
#define cxCollectionSize(c) ((c)->collection.size)

/**
 * Returns the size of one element.
 *
 * If #cxCollectionStoresPointers() returns true, this is the size of a pointer.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @return (@c size_t) the size of one element in bytes
 */
#define cxCollectionElementSize(c) ((c)->collection.elem_size)

/**
 * Indicates whether this collection only stores pointers instead of the actual data.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @retval true if this collection stores only pointers to data
 * @retval false if this collection stores the actual element's data
 */
#define cxCollectionStoresPointers(c) ((c)->collection.store_pointer)


/**
 * Convenience macro for adding indirection to an element if the collection is storing pointers.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param elem the pointer that shall be taken the address from, if the collection is storing pointers
 * @return if the collection is storing pointers, takes the address of @p elem, otherwise returns @p elem
 */
#define cx_ref(c, elem) (cxCollectionStoresPointers(c) ? ((void*)&(elem)) : (elem))

/**
 * Convenience macro for dereferencing an element if the collection is storing pointers.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param elem a pointer to the collection element
 * @return if the collection is storing pointers, dereferences @p elem, otherwise returns @p elem
 */
#define cx_deref(c, elem) (cxCollectionStoresPointers(c) ? *((void**)(elem)) : (elem))

/**
 * Indicates whether the collection can guarantee that the stored elements are currently sorted.
 *
 * This may return @c false even when the elements are sorted.
 * It is totally up to the implementation of the collection when to check if the elements are sorted.
 * It is usually a good practice to establish this property as an invariant that does not need
 * to be re-checked on certain operations.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @retval true if the elements are currently sorted wrt. the collection's compare function
 * @retval false if the order of elements is unknown
 */
#define cxCollectionSorted(c) ((c)->collection.sorted || (c)->collection.size == 0)

/**
 * Sets a simple compare function for a collection.
 *
 * Erases a possible advanced compare function.
 * If you want to set both, because you want to access the simple function
 * in your advanced function, you must set the simple function first.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param func (@c cx_compare_func) the compare function
 */
#define cxSetCompareFunc(c, func) \
    (c)->collection.simple_cmp = (cx_compare_func)(func); \
    (c)->collection.advanced_cmp = NULL

/**
 * Sets an advanced compare function that supports custom data for a collection.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param func (@c cx_compare_func2) the compare function
 * @param data (@c void*) the pointer to custom data that is passed to the compare function
 */
#define cxSetAdvancedCompareFunc(c, func, data) \
    (c)->collection.advanced_cmp = (cx_compare_func2) func; \
    (c)->collection.cmp_data = data

/**
 * Invokes the simple comparator function for two elements.
 *
 * Usually only used by collection implementations. There should be no need
 * to invoke this macro manually.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param left (@c void*) pointer to data
 * @param right (@c void*) pointer to data
 */
#define cx_invoke_simple_compare_func(c, left, right) \
    (c)->collection.simple_cmp(left, right)

/**
 * Invokes the advanced comparator function for two elements.
 *
 * Usually only used by collection implementations. There should be no need
 * to invoke this macro manually.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param left (@c void*) pointer to data
 * @param right (@c void*) pointer to data
 */
#define cx_invoke_advanced_compare_func(c, left, right) \
    (c)->collection.advanced_cmp(left, right, (c)->collection.cmp_data)


/**
 * Invokes the configured comparator function for two elements.
 *
 * Usually only used by collection implementations. There should be no need
 * to invoke this macro manually.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param left (@c void*) pointer to data
 * @param right (@c void*) pointer to data
 */
#define cx_invoke_compare_func(c, left, right) \
    (((c)->collection.advanced_cmp) ? \
    cx_invoke_advanced_compare_func(c,left,right) : \
    cx_invoke_simple_compare_func(c,left,right))

/**
 * Sets a simple destructor function for this collection.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param destr (@c cx_destructor_func) the destructor function
 */
#define cxSetDestructor(c, destr) \
    (c)->collection.simple_destructor = (cx_destructor_func) destr

/**
 * Sets an advanced destructor function for this collection.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param destr (@c cx_destructor_func2) the destructor function
 * @param data (@c void*) the additional data the advanced destructor is invoked with
 */
#define cxSetAdvancedDestructor(c, destr, data) \
    (c)->collection.advanced_destructor = (cx_destructor_func2) destr; \
    (c)->collection.destructor_data = data

/**
 * Invokes the simple destructor function for a specific element.
 *
 * Usually only used by collection implementations. There should be no need
 * to invoke this macro manually.
 *
 * When the collection stores pointers, those pointers are directly passed
 * to the destructor. Otherwise, a pointer to the element is passed.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param e the element (the type is @c void* or @c void** depending on context)
 */
#define cx_invoke_simple_destructor(c, e) \
    (c)->collection.simple_destructor((c)->collection.store_pointer ? (*((void **) (e))) : (e))

/**
 * Invokes the advanced destructor function for a specific element.
 *
 * Usually only used by collection implementations. There should be no need
 * to invoke this macro manually.
 *
 * When the collection stores pointers, those pointers are directly passed
 * to the destructor. Otherwise, a pointer to the element is passed.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param e the element (the type is @c void* or @c void** depending on context)
 */
#define cx_invoke_advanced_destructor(c, e) \
    (c)->collection.advanced_destructor((c)->collection.destructor_data, \
    (c)->collection.store_pointer ? (*((void **) (e))) : (e))


/**
 * Invokes all available destructor functions for a specific element.
 *
 * Usually only used by collection implementations. There should be no need
 * to invoke this macro manually.
 *
 * When the collection stores pointers, those pointers are directly passed
 * to the destructor. Otherwise, a pointer to the element is passed.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param e the element (the type is @c void* or @c void** depending on context)
 */
#define cx_invoke_destructor(c, e) \
    if ((c)->collection.simple_destructor) cx_invoke_simple_destructor(c,e); \
    if ((c)->collection.advanced_destructor) cx_invoke_advanced_destructor(c,e)

#ifdef __cplusplus
} // extern "C"
#endif

#endif // UCX_COLLECTION_H