tip/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 comparator function for the elements.
     */
    cx_compare_func cmpfunc;
    /**
     * The size of each element.
     */
    size_t elem_size;
    /**
     * The number of currently stored elements.
     */
    size_t size;
    /**
     * 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)

/**
 * 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 the compare function for a collection.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param func (@c cx_compare_func) the compare function that shall be used by @c c
 */
#define cxCollectionCompareFunc(c, func) (c)->collection.cmpfunc = (func)

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

/**
 * Sets a simple destructor function for this collection.
 *
 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
 * @param destr the destructor function
 */
#define cxDefineAdvancedDestructor(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