src/cx/array_list.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 array_list.h
 * @brief Array list implementation.
 * @author Mike Becker
 * @author Olaf Wintermann
 * @copyright 2-Clause BSD License
 */


#ifndef UCX_ARRAY_LIST_H
#define UCX_ARRAY_LIST_H

#include "list.h"

/**
 * The maximum item size in an array list that fits into
 * a stack buffer when swapped.
 */
CX_EXPORT extern const unsigned cx_array_swap_sbo_size;

/**
 * Declares a typed array with size and capacity.
 *
 * @param type the type of the elements
 * @param name the name of the array
 */
#define CX_ARRAY(type, name) \
    struct { \
        type *data; \
        size_t size; \
        size_t capacity; \
    } name

/**
 * Internal structure for arrays.
 *
 * A generalization of array structures declared with CX_ARRAY().
 */
typedef struct cx_array_s {
    /** The array data. */
    void *data;
    /** The number of elements. */
    size_t size;
    /** The maximum number of elements. */
    size_t capacity;
} CxArray;

/**
 * Initializes an array by allocating memory.
 *
 * Internal function - do not use manually.
 *
 * @param allocator the allocator for the array
 * @param array a pointer to the array structure
 * @param elem_size size of one element
 * @param capacity the initial maximum number of elements
 * @retval zero allocation was successful
 * @retval non-zero allocation failed
 */
CX_EXTERN CX_NONNULL
int cx_array_init_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity);

/**
 * Initializes an array by allocating memory.
 *
 * The size is set to zero.
 *
 * @attention If the array was already initialized, this will leak memory.
 * Use cx_array_reserve() to change the capacity of an initialized array.
 *
 * @param allocator (@c CxAllocator*) the allocator for the array
 * @param array the name of the array
 * @param capacity (@c size_t) the initial maximum number of elements
 * @retval zero allocation was successful
 * @retval non-zero allocation failed
 */
#define cx_array_init_a(allocator, array, capacity) cx_array_init_(allocator, (CxArray*)&(array), sizeof((array).data[0]), capacity)

/**
 * Initializes an array by allocating memory.
 *
 * The size is set to zero.
 *
 * @attention If the array was already initialized, this will leak memory.
 *
 * @param array the name of the array
 * @param capacity (@c size_t) the initial maximum number of elements
 * @retval zero allocation was successful
 * @retval non-zero allocation failed
 */
#define cx_array_init(array, capacity) cx_array_init_a(cxDefaultAllocator, array, capacity)

/**
 * Initializes an array with fixed size memory.
 *
 * Internal function - do not use manually.
 *
 * @param array a pointer to the array structure
 * @param data the fixed size array
 * @param capacity the capacity of the fixed size array
 * @param size the number of initialized elements in the fixed size array
 */
CX_EXTERN CX_NONNULL
void cx_array_init_fixed_(CxArray *array, const void *data, size_t capacity, size_t size);

/**
 * Initializes an array with fixed size memory.
 *
 * This is useful, for example, when you want to work with memory on the stack
 * and only want to move to the heap when the stack memory is not enough.
 *
 * With the @p num_initialized argument you can specify how many elements in the
 * fixed size array are already correctly initialized, which determines the
 * initial size of the array.
 *
 * The capacity is determined automatically by the compiler.
 *
 * @attention When you add elements to an array that was initialized with fixed
 * size memory, you MUST check the capacity before adding the element and invoke
 * cx_array_copy_to_new() when you intend to exceed the capacity.
 *
 * @attention When you pass a pointer to an array that does not have a fixed
 * size, the behavior is unspecified.
 *
 * @param array the name of the array to initialize
 * @param fixed_size_array (@c void*) the fixed size array
 * @param num_initialized (@c size_t) the number of already initialized elements in the fixed size array
 * @see cx_array_copy_to_new()
 */
#define cx_array_init_fixed(array, fixed_size_array, num_initialized) \
        cx_array_init_fixed_((CxArray*)&(array), fixed_size_array, cx_nmemb(fixed_size_array), num_initialized)

/**
 * Changes the capacity of an array.
 *
 * Internal function - do not use.
 *
 * @param allocator the allocator
 * @param array a pointer to the array structure
 * @param elem_size the size of one element
 * @param capacity the new capacity
 * @retval zero allocation was successful
 * @retval non-zero allocation failed
 */
CX_EXTERN CX_NONNULL
int cx_array_reserve_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity);

/**
 * Changes the capacity of an array.
 *
 * If required, the size is reduced to fit into the new capacity.
 *
 * @param allocator (@c CxAllocator*) the allocator for the array
 * @param array the name of the array
 * @param capacity (@c size_t) the new maximum number of elements
 * @retval zero allocation was successful
 * @retval non-zero allocation failed
 */
#define cx_array_reserve_a(allocator, array, capacity) \
        cx_array_reserve_(allocator, (CxArray*)&(array), sizeof((array).data[0]), capacity)

/**
 * Changes the capacity of an array.
 *
 * If required, the size is reduced to fit into the new capacity.
 *
 * @param array the name of the array
 * @param capacity (@c size_t) the new maximum number of elements
 * @retval zero allocation was successful
 * @retval non-zero allocation failed
 */
#define cx_array_reserve(array, capacity) \
        cx_array_reserve_a(cxDefaultAllocator, array, capacity)

/**
 * Copies the array to a new memory region.
 *
 * Internal function - do not use.
 *
 * @param allocator the allocator for new new memory
 * @param array a pointer to the array structure
 * @param elem_size the size of one element
 * @param capacity the new capacity
 * @retval zero allocation was successful
 * @retval non-zero allocation failed
 */
CX_EXTERN CX_NONNULL
int cx_array_copy_to_new_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity);

/**
 * Copies the array to a new memory region.
 *
 * This is useful when you have initialized the array with a fixed size memory
 * using cx_array_init_fixed(), and now you want to increase the capacity.
 *
 * @attention When the original memory does not belong to stack memory, and
 * you do not have another reference to this memory, it will leak.
 *
 * @param allocator (@c CxAllocator*) the allocator for the new memory
 * @param array the name of the array
 * @param capacity (@c size_t) the new maximum number of elements
 * @retval zero allocation was successful
 * @retval non-zero allocation failed
 * @see cx_array_init_fixed()
 */
#define cx_array_copy_to_new_a(allocator, array, capacity) \
        cx_array_copy_to_new_(allocator, (CxArray*)&(array), sizeof((array).data[0]), capacity)

/**
 * Copies the array to a new memory region.
 *
 * This is useful when you have initialized the array with a fixed size memory
 * using cx_array_init_fixed(), and now you want to increase the capacity.
 *
 * @attention When the original memory does not belong to stack memory, and
 * you do not have another reference to this memory, it will leak.
 *
 * @param array the name of the array
 * @param capacity (@c size_t) the new maximum number of elements
 * @retval zero allocation was successful
 * @retval non-zero allocation failed
 * @see cx_array_init_fixed()
 */
#define cx_array_copy_to_new(array, capacity) \
        cx_array_copy_to_new_a(cxDefaultAllocator, array, capacity)

/**
 * Inserts data into an array.
 *
 * Internal function - do not use.
 *
 * @param allocator the allocator to use for a possible reallocation
 * @param array a pointer to the array structure
 * @param elem_size the size of one element
 * @param index the index where to insert the @p other data
 * @param other a pointer to an array of data that shall be inserted
 * @param n the number of elements that shall be inserted
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
CX_EXTERN CX_NONNULL_ARG(1, 2)
int cx_array_insert_(const CxAllocator *allocator, CxArray *array,
        size_t elem_size, size_t index, const void *other, size_t n);

/**
 * Appends an element to an array.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the element shall be added
 * @param element the element that shall be added
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_add_a(allocator, array, element) \
        cx_array_insert_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (array).size, (void*)&(element), 1)

/**
 * Appends an element to an array.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @param array the name of the array where the element shall be added
 * @param element (@c void*) a pointer to the element that shall be added
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_add(array, element) \
        cx_array_add_a(cxDefaultAllocator, array, element)

/**
 * Inserts an element into an array.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the element shall be inserted
 * @param index (@c size_t) the index where to insert the @p element
 * @param element the element that shall be inserted
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_a(allocator, array, index, element) \
        cx_array_insert_(allocator, (CxArray*)&(array), sizeof((array).data[0]), index, (void*)&(element), 1)

/**
 * Inserts an element into an array.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @param array the name of the array where the element shall be inserted
 * @param index (@c size_t) the index where to insert the @p element
 * @param element (@c void*) a pointer to the element that shall be inserted
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert(array, index, element) \
        cx_array_insert_a(cxDefaultAllocator, array, index, element)

/**
 * Inserts data into an array.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the elements shall be inserted
 * @param index (@c size_t) the index where to insert the @p other data
 * @param other (@c void*) a pointer to an array of data that shall be inserted
 * @param n (@c size_t) the number of elements that shall be inserted
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_array_a(allocator, array, index, other, n) \
        cx_array_insert_(allocator, (CxArray*)&(array), sizeof((array).data[0]), index, other, n)

/**
 * Inserts data into an array.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @param array the name of the array where the elements shall be inserted
 * @param index (@c size_t) the index where to insert the @p other data
 * @param other (@c void*) a pointer to an array of data that shall be inserted
 * @param n (@c size_t) the number of elements that shall be inserted
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_array(array, index, other, n) \
        cx_array_insert_array_a(cxDefaultAllocator, array, index, other, n)

/**
 * Appends data to an array.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the elements shall be added
 * @param other (@c void*) a pointer to an array of data that shall be added
 * @param n (@c size_t) the number of elements that shall be added
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_add_array_a(allocator, array, other, n) \
        cx_array_insert_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (array).size, other, n)

/**
 * Appends data to an array.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @param array the name of the array where the elements shall be added
 * @param other (@c void*) a pointer to an array of data that shall be added
 * @param n (@c size_t) the number of elements that shall be added
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_add_array(array, other, n) \
        cx_array_add_array_a(cxDefaultAllocator, array, other, n)

/**
 * Inserts sorted data into a sorted array.
 *
 * Internal function - do not use.
 *
 * @param allocator the allocator to use for a possible reallocation
 * @param array a pointer to the array structure
 * @param elem_size the size of one element
 * @param sorted_data a pointer to an array of data that shall be inserted
 * @param n the number of elements that shall be inserted
 * @param cmp_func the compare function
 * @param allow_duplicates @c false if duplicates shall be skipped during insertion
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
CX_EXTERN CX_NONNULL
int cx_array_insert_sorted_(const CxAllocator *allocator, CxArray *array,
        size_t elem_size, const void *sorted_data, size_t n,
        cx_compare_func cmp_func, bool allow_duplicates);

/**
 * Inserts an element into a sorted array.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the elements shall be inserted
 * @param element the element that shall be inserted
 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_sorted_a(allocator, array, element, cmp_func) \
        cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (void*)&(element), 1, cmp_func, true)

/**
 * Inserts an element into a sorted array.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param array the name of the array where the elements shall be inserted
 * @param element the element that shall be inserted
 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_sorted(array, element, cmp_func) \
        cx_array_insert_sorted_a(cxDefaultAllocator, array, element, cmp_func)

/**
 * Inserts sorted data into a sorted array.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the elements shall be inserted
 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
 * @param n (@c size_t) the number of elements that shall be inserted
 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_sorted_array_a(allocator, array, sorted_data, n, cmp_func) \
        cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), sorted_data, n, cmp_func, true)

/**
 * Inserts sorted data into a sorted array.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param array the name of the array where the elements shall be inserted
 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
 * @param n (@c size_t) the number of elements that shall be inserted
 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_sorted_array(array, sorted_data, n, cmp_func) \
        cx_array_insert_sorted_array_a(cxDefaultAllocator, array, sorted_data, n, cmp_func)

/**
 * Inserts an element into a sorted array if it is not already contained.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the elements shall be inserted
 * @param element the element that shall be inserted
 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_unique_a(allocator, array, element, cmp_func) \
        cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (void*)&(element), 1, cmp_func, false)

/**
 * Inserts an element into a sorted array if it is not already contained.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param array the name of the array where the elements shall be inserted
 * @param element the element that shall be inserted
 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_unique(array, element, cmp_func) \
        cx_array_insert_unique_a(cxDefaultAllocator, array, element, cmp_func)

/**
 * Inserts sorted data into a sorted array, skipping duplicates.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the elements shall be inserted
 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
 * @param n (@c size_t) the number of elements that shall be inserted
 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_unique_array_a(allocator, array, sorted_data, n, cmp_func) \
        cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), sorted_data, n, cmp_func, false)

/**
 * Inserts sorted data into a sorted array, skipping duplicates.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param array the name of the array where the elements shall be inserted
 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
 * @param n (@c size_t) the number of elements that shall be inserted
 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_unique_array(array, sorted_data, n, cmp_func) \
        cx_array_insert_unique_array_a(cxDefaultAllocator, array, sorted_data, n, cmp_func)

/**
 * Inserts sorted data into a sorted array.
 *
 * Internal function - do not use.
 *
 * @param allocator the allocator to use for a possible reallocation
 * @param array a pointer to the array structure
 * @param elem_size the size of one element
 * @param sorted_data a pointer to an array of data that shall be inserted
 * @param n the number of elements that shall be inserted
 * @param cmp_func the compare function
 * @param context additional context for the compare function
 * @param allow_duplicates @c false if duplicates shall be skipped during insertion
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
CX_EXTERN CX_NONNULL_ARG(1, 2, 4, 6)
int cx_array_insert_sorted_c_(const CxAllocator *allocator, CxArray *array,
        size_t elem_size, const void *sorted_data, size_t n,
        cx_compare_func2 cmp_func, void *context, bool allow_duplicates);

/**
 * Inserts an element into a sorted array.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the elements shall be inserted
 * @param element the element that shall be inserted
 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
 * @param context (@c void*) additional context for the compare function
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_sorted_ca(allocator, array, element, cmp_func) \
        cx_array_insert_sorted_c_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (void*)&(element), 1, cmp_func, context, true)

/**
 * Inserts an element into a sorted array.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param array the name of the array where the elements shall be inserted
 * @param element the element that shall be inserted
 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
 * @param context (@c void*) additional context for the compare function
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_sorted_c(array, element, cmp_func, context) \
        cx_array_insert_sorted_ca(cxDefaultAllocator, array, element, cmp_func, context)

/**
 * Inserts sorted data into a sorted array.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the elements shall be inserted
 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
 * @param n (@c size_t) the number of elements that shall be inserted
 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
 * @param context (@c void*) additional context for the compare function
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_sorted_array_ca(allocator, array, sorted_data, n, cmp_func, context) \
        cx_array_insert_sorted_c_(allocator, (CxArray*)&(array), sizeof((array).data[0]), sorted_data, n, cmp_func, context, true)

/**
 * Inserts sorted data into a sorted array.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param array the name of the array where the elements shall be inserted
 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
 * @param n (@c size_t) the number of elements that shall be inserted
 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
 * @param context (@c void*) additional context for the compare function
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_sorted_array_c(array, sorted_data, n, cmp_func, context) \
        cx_array_insert_sorted_array_ca(cxDefaultAllocator, array, sorted_data, n, cmp_func, context)

/**
 * Inserts an element into a sorted array if it is not already contained.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the elements shall be inserted
 * @param element the element that shall be inserted
 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
 * @param context (@c void*) additional context for the compare function
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_unique_ca(allocator, array, element, cmp_func, context) \
        cx_array_insert_sorted_c_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (void*)&(element), 1, cmp_func, context, false)

/**
 * Inserts an element into a sorted array if it is not already contained.
 *
 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
 *
 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param array the name of the array where the elements shall be inserted
 * @param element the element that shall be inserted
 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
 * @param context (@c void*) additional context for the compare function
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_unique_c(array, element, cmp_func, context) \
        cx_array_insert_unique_ca(cxDefaultAllocator, array, element, cmp_func, context)

/**
 * Inserts sorted data into a sorted array, skipping duplicates.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
 * @param array the name of the array where the elements shall be inserted
 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
 * @param n (@c size_t) the number of elements that shall be inserted
 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
 * @param context (@c void*) additional context for the compare function
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_unique_array_ca(allocator, array, sorted_data, n, cmp_func, context) \
        cx_array_insert_sorted_c_(allocator, (CxArray*)&(array), sizeof((array).data[0]), sorted_data, n, cmp_func, context, false)

/**
 * Inserts sorted data into a sorted array, skipping duplicates.
 *
 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
 *
 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
 *
 * @param array the name of the array where the elements shall be inserted
 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
 * @param n (@c size_t) the number of elements that shall be inserted
 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
 * @param context (@c void*) additional context for the compare function
 * @retval zero success
 * @retval non-zero a re-allocation was necessary but failed
 */
#define cx_array_insert_unique_array_c(array, sorted_data, n, cmp_func, context) \
        cx_array_insert_unique_array_ca(cxDefaultAllocator, array, sorted_data, n, cmp_func, context)

/**
 * An alternative to qsort_r() when that is not available on your platform.
 *
 * If it is available, qsort_r() is used directly.
 *
 * @param array the array that shall be sorted
 * @param nmemb the number of elements in the array
 * @param size the size of one element
 * @param fn the compare function
 * @param context the context for the compare function
 */
CX_EXTERN CX_NONNULL
void cx_array_qsort_c(void *array, size_t nmemb, size_t size,
        cx_compare_func2 fn, void *context);

/**
 * Sorts an array.
 *
 * Internal function - do not use.
 *
 * @param array a pointer to the array structure
 * @param elem_size the size of one element
 * @param fn the compare function
 */
CX_EXTERN CX_NONNULL
void cx_array_sort_(CxArray *array, size_t elem_size,
        cx_compare_func fn);

/**
 * Sorts an array.
 *
 * Internal function - do not use.
 *
 * @param array a pointer to the array structure
 * @param elem_size the size of one element
 * @param fn the compare function
 * @param context the context for the compare function
 */
CX_EXTERN CX_NONNULL
void cx_array_sort_c_(CxArray *array, size_t elem_size,
        cx_compare_func2 fn, void *context);

/**
 * Sorts an array.
 *
 * @param array the name of the array
 * @param fn (@c cx_compare_func) the compare function
 * @param context (@c void*) the context for the compare function
 */
#define cx_array_sort(array, fn) \
        cx_array_sort_((CxArray*)&(array), sizeof((array).data[0]), fn)

/**
 * Sorts an array.
 *
 * @param array the name of the array
 * @param fn (@c cx_compare_func2) the compare function
 * @param context (@c void*) the context for the compare function
 */
#define cx_array_sort_c(array, fn, context) \
        cx_array_sort_c_((CxArray*)&(array), sizeof((array).data[0]), fn, context)

/**
 * Creates an iterator over the elements of an array.
 *
 * Internal function - do not use.
 *
 * @param array a pointer to the array structure
 * @param elem_size the size of one element
 * @return an iterator over the elements
 */
CX_EXTERN CX_NODISCARD CX_NONNULL
CxIterator cx_array_iterator_(CxArray *array, size_t elem_size);

/**
 * Creates an iterator over the elements of an array.
 *
 * The iterator will yield pointers to the elements.
 *
 * This iterator cannot be used to remove elements
 * because it does not get a modifiable reference to the array's size.
 *
 * @param array the name of the array
 * @return an iterator over the elements
 * @see cx_array_iterator_ptr()
 */
#define cx_array_iterator(array) \
        cx_array_iterator_((CxArray*)&(array), sizeof((array).data[0]))

/**
 * Creates an iterator over the elements of an array containing pointers.
 *
 * Internal function - do not use.
 *
 * @param array the name of the array
 * @return an iterator over the elements
 */
CX_EXTERN CX_NODISCARD CX_NONNULL
CxIterator cx_array_iterator_ptr_(CxArray *array);

/**
 * Creates an iterator over the elements of an array containing pointers.
 *
 * The iterator will yield the elements themselves, which are supposed to
 * be pointers.
 *
 * This iterator cannot be used to remove elements
 * because it does not get a modifiable reference to the array's size.
 *
 * @param array the name of the array
 * @return an iterator over the elements
 * @see cx_array_iterator()
 */
#define cx_array_iterator_ptr(array) \
        cx_array_iterator_ptr_((CxArray*)&(array))


/**
 * Removes elements from the array.
 *
 * Internal function - do not use.
 *
 * @param array a pointer to the array structure
 * @param elem_size the size of one element
 * @param index the index of the first element to remove
 * @param n the number of elements to remove
 * @param fast indicates whether tail elements should be copied into the gap
 */
CX_EXTERN CX_NONNULL
void cx_array_remove_(CxArray *array, size_t elem_size, size_t index, size_t n, bool fast);

/**
 * Removes one element from the array.
 *
 * Tail elements are all moved by one. If you don't need a stable order
 * in the array, consider using cx_array_remove_fast().
 *
 * If the index is out of bounds, this function does nothing.
 *
 * @param array the name of the array
 * @param index (@c size_t) the index of the element to remove
 * @see cx_array_remove_fast()
 */
#define cx_array_remove(array, index) \
        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, 1, false)

/**
 * Removes one element from the array.
 *
 * The gap will be filled with a copy of the last element in the array.
 * This changes the order of elements. If you want a stable order,
 * use cx_array_remove() instead.
 *
 * If the index is out of bounds, this function does nothing.
 *
 * @param array the name of the array
 * @param index (@c size_t) the index of the element to remove
 * @see cx_array_remove()
 */
#define cx_array_remove_fast(array, index) \
        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, 1, true)

/**
 * Removes multiple elements from the array.
 *
 * Tail elements are all moved to close the gap. If you don't need a stable
 * order in the array, consider using cx_array_remove_array_fast().
 *
 * If the index is out of bounds, this function does nothing.
 * If @n overflows the array, this function removes as many elements as it can.
 *
 * @param array the name of the array
 * @param index (@c size_t) the index of the first element to remove
 * @param n (@c size_t) the number of elements to remove
 * @see cx_array_remove_array_fast()
 */
#define cx_array_remove_array(array, index, n) \
        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, n, false)

/**
 * Removes multiple elements from the array.
 *
 * Tail elements are copied into the gap. If you have more tail elements
 * than the number of elements that are removed, this will change the order
 * of elements. If you want a stable order, use cx_array_remove_array() instead.
 *
 * If the index is out of bounds, this function does nothing.
 * If @n overflows the array, this function removes as many elements as it can.
 *
 * @param array the name of the array
 * @param index (@c size_t) the index of the first element to remove
 * @param n (@c size_t) the number of elements to remove
 * @see cx_array_remove_array()
 */
#define cx_array_remove_array_fast(array, index, n) \
        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, n, true)

/**
 * Deallocates an array.
 *
 * Internal function - do not use.
 *
 * @param allocator (@c CxAllocator*) the allocator which was used to allocate the array
 * @param array a pointer to the array structure
 */
CX_EXTERN CX_NONNULL
void cx_array_free_(const CxAllocator *allocator, CxArray *array);

/**
 * Deallocates an array.
 *
 * The structure is reset to zero and can be re-initialized with
 * cx_array_inita().
 *
 * @param array the name of the array
 */
#define cx_array_free(array) cx_array_free_(cxDefaultAllocator, (CxArray*)&(array))

/**
 * Deallocates an array.
 *
 * The structure is reset to zero and can be re-initialized with
 * cx_array_init_a().
 *
 * @param allocator (@c CxAllocator*) the allocator which was used to allocate the array
 * @param array the name of the array
 */
#define cx_array_free_a(allocator, array) cx_array_free_(allocator, (CxArray*)&(array))


/**
 * Searches the largest lower bound in a sorted array.
 *
 * In other words, this function returns the index of the largest element
 * in @p arr that is less or equal to @p elem with respect to @p cmp_func.
 * When no such element exists, @p size is returned.
 *
 * When such an element exists more than once, the largest index of all those
 * elements is returned.
 *
 * If @p elem is contained in the array, this is identical to
 * #cx_array_binary_search().
 *
 * If the array is not sorted with respect to the @p cmp_func, the behavior
 * is undefined.
 *
 * @param arr the array to search
 * @param size the size of the array
 * @param elem_size the size of one element
 * @param elem the element to find
 * @param cmp_func the compare function
 * @return the index of the largest lower bound, or @p size
 * @see cx_array_binary_search_sup()
 * @see cx_array_binary_search()
 */
CX_EXTERN CX_NONNULL
size_t cx_array_binary_search_inf(const void *arr, size_t size,
        size_t elem_size, const void *elem, cx_compare_func cmp_func);

/**
 * Searches an item in a sorted array.
 *
 * When such an element exists more than once, the largest index of all those
 * elements is returned.
 *
 * If the array is not sorted with respect to the @p cmp_func, the behavior
 * is undefined.
 *
 * @param arr the array to search
 * @param size the size of the array
 * @param elem_size the size of one element
 * @param elem the element to find
 * @param cmp_func the compare function
 * @return the index of the element in the array, or @p size if the element
 * cannot be found
 * @see cx_array_binary_search_inf()
 * @see cx_array_binary_search_sup()
 */
CX_EXTERN CX_NONNULL
size_t cx_array_binary_search(const void *arr, size_t size,
        size_t elem_size, const void *elem, cx_compare_func cmp_func);

/**
 * Searches the smallest upper bound in a sorted array.
 *
 * In other words, this function returns the index of the smallest element
 * in @p arr that is greater or equal to @p elem with respect to @p cmp_func.
 * When no such element exists, @p size is returned.
 *
 * When such an element exists more than once, the smallest index of all those
 * elements is returned.
 *
 * If @p elem is contained in the array, this is identical to
 * #cx_array_binary_search().
 *
 * If the array is not sorted with respect to the @p cmp_func, the behavior
 * is undefined.
 *
 * @param arr the array to search
 * @param size the size of the array
 * @param elem_size the size of one element
 * @param elem the element to find
 * @param cmp_func the compare function
 * @return the index of the smallest upper bound, or @p size
 * @see cx_array_binary_search_inf()
 * @see cx_array_binary_search()
 */
CX_EXTERN CX_NONNULL
size_t cx_array_binary_search_sup(const void *arr, size_t size,
        size_t elem_size, const void *elem, cx_compare_func cmp_func);


/**
 * Searches the largest lower bound in a sorted array.
 *
 * In other words, this function returns the index of the largest element
 * in @p arr that is less or equal to @p elem with respect to @p cmp_func.
 * When no such element exists, @p size is returned.
 *
 * When such an element exists more than once, the largest index of all those
 * elements is returned.
 *
 * If @p elem is contained in the array, this is identical to
 * #cx_array_binary_search().
 *
 * If the array is not sorted with respect to the @p cmp_func, the behavior
 * is undefined.
 *
 * @param arr the array to search
 * @param size the size of the array
 * @param elem_size the size of one element
 * @param elem the element to find
 * @param cmp_func the compare function
 * @param context the context for the compare function
 * @return the index of the largest lower bound, or @p size
 * @see cx_array_binary_search_sup()
 * @see cx_array_binary_search()
 */
CX_EXTERN CX_NONNULL
size_t cx_array_binary_search_inf_c(const void *arr, size_t size,
        size_t elem_size, const void *elem, cx_compare_func2 cmp_func, void *context);

/**
 * Searches an item in a sorted array.
 *
 * When such an element exists more than once, the largest index of all those
 * elements is returned.
 *
 * If the array is not sorted with respect to the @p cmp_func, the behavior
 * is undefined.
 *
 * @param arr the array to search
 * @param size the size of the array
 * @param elem_size the size of one element
 * @param elem the element to find
 * @param cmp_func the compare function
 * @param context the context for the compare function
 * @return the index of the element in the array, or @p size if the element
 * cannot be found
 * @see cx_array_binary_search_inf()
 * @see cx_array_binary_search_sup()
 */
CX_EXTERN CX_NONNULL
size_t cx_array_binary_search_c(const void *arr, size_t size,
        size_t elem_size, const void *elem, cx_compare_func2 cmp_func, void *context);

/**
 * Searches the smallest upper bound in a sorted array.
 *
 * In other words, this function returns the index of the smallest element
 * in @p arr that is greater or equal to @p elem with respect to @p cmp_func.
 * When no such element exists, @p size is returned.
 *
 * When such an element exists more than once, the smallest index of all those
 * elements is returned.
 *
 * If @p elem is contained in the array, this is identical to
 * #cx_array_binary_search().
 *
 * If the array is not sorted with respect to the @p cmp_func, the behavior
 * is undefined.
 *
 * @param arr the array to search
 * @param size the size of the array
 * @param elem_size the size of one element
 * @param elem the element to find
 * @param cmp_func the compare function
 * @param context the context for the compare function
 * @return the index of the smallest upper bound, or @p size
 * @see cx_array_binary_search_inf()
 * @see cx_array_binary_search()
 */
CX_EXTERN CX_NONNULL
size_t cx_array_binary_search_sup_c(const void *arr, size_t size,
        size_t elem_size, const void *elem, cx_compare_func2 cmp_func, void *context);

/**
 * Swaps two array elements.
 *
 * @param arr the array
 * @param elem_size the element size
 * @param idx1 index of the first element
 * @param idx2 index of the second element
 */
CX_EXTERN CX_NONNULL
void cx_array_swap(void *arr, size_t elem_size, size_t idx1, size_t idx2);

/**
 * Allocates an array list for storing elements with @p elem_size bytes each.
 *
 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
 * copies of the added elements, and the compare function will be automatically set
 * to cx_cmp_ptr().
 *
 * @param allocator the allocator for allocating the list memory
 * (if @c NULL, the cxDefaultAllocator will be used)
 * @param elem_size the size of each element in bytes
 * @param initial_capacity the initial number of elements the array can store
 * @return the created list
 */
CX_EXTERN CX_NODISCARD CX_MALLOC CX_DEALLOC(cxListFree, 1)
CxList *cxArrayListCreate(const CxAllocator *allocator,
        size_t elem_size, size_t initial_capacity);

#endif // UCX_ARRAY_LIST_H