array_list.h File Reference

Array list implementation. More...

#include "list.h"

Go to the source code of this file.

Data Structures
struct	cx_array_s
	Internal structure for arrays. More...

Macros
#define	CX_ARRAY(type, name)
	Declares a typed array with size and capacity.
#define	cx_array_init_a(allocator, array, capacity)
	Initializes an array by allocating memory.
#define	cx_array_init(array, capacity)
	Initializes an array by allocating memory.
#define	cx_array_init_fixed(array, fixed_size_array, num_initialized)
	Initializes an array with fixed size memory.
#define	cx_array_reserve_a(allocator, array, capacity)
	Changes the capacity of an array.
#define	cx_array_reserve(array, capacity)
	Changes the capacity of an array.
#define	cx_array_copy_to_new_a(allocator, array, capacity)
	Copies the array to a new memory region.
#define	cx_array_copy_to_new(array, capacity)
	Copies the array to a new memory region.
#define	cx_array_add_a(allocator, array, element)
	Appends an element to an array.
#define	cx_array_add(array, element)
	Appends an element to an array.
#define	cx_array_insert_a(allocator, array, index, element)
	Inserts an element into an array.
#define	cx_array_insert(array, index, element)
	Inserts an element into an array.
#define	cx_array_insert_array_a(allocator, array, index, other, n)
	Inserts data into an array.
#define	cx_array_insert_array(array, index, other, n)
	Inserts data into an array.
#define	cx_array_add_array_a(allocator, array, other, n)
	Appends data to an array.
#define	cx_array_add_array(array, other, n)
	Appends data to an array.
#define	cx_array_insert_sorted_a(allocator, array, element, cmp_func)
	Inserts an element into a sorted array.
#define	cx_array_insert_sorted(array, element, cmp_func)
	Inserts an element into a sorted array.
#define	cx_array_insert_sorted_array_a(allocator, array, sorted_data, n, cmp_func)
	Inserts sorted data into a sorted array.
#define	cx_array_insert_sorted_array(array, sorted_data, n, cmp_func)
	Inserts sorted data into a sorted array.
#define	cx_array_insert_unique_a(allocator, array, element, cmp_func)
	Inserts an element into a sorted array if it is not already contained.
#define	cx_array_insert_unique(array, element, cmp_func)
	Inserts an element into a sorted array if it is not already contained.
#define	cx_array_insert_unique_array_a(allocator, array, sorted_data, n, cmp_func)
	Inserts sorted data into a sorted array, skipping duplicates.
#define	cx_array_insert_unique_array(array, sorted_data, n, cmp_func)
	Inserts sorted data into a sorted array, skipping duplicates.
#define	cx_array_insert_sorted_ca(allocator, array, element, cmp_func, context)
	Inserts an element into a sorted array.
#define	cx_array_insert_sorted_c(array, element, cmp_func, context)
	Inserts an element into a sorted array.
#define	cx_array_insert_sorted_array_ca(allocator, array, sorted_data, n, cmp_func, context)
	Inserts sorted data into a sorted array.
#define	cx_array_insert_sorted_array_c(array, sorted_data, n, cmp_func, context)
	Inserts sorted data into a sorted array.
#define	cx_array_insert_unique_ca(allocator, array, element, cmp_func, context)
	Inserts an element into a sorted array if it is not already contained.
#define	cx_array_insert_unique_c(array, element, cmp_func, context)
	Inserts an element into a sorted array if it is not already contained.
#define	cx_array_insert_unique_array_ca(allocator, array, sorted_data, n, cmp_func, context)
	Inserts sorted data into a sorted array, skipping duplicates.
#define	cx_array_insert_unique_array_c(array, sorted_data, n, cmp_func, context)
	Inserts sorted data into a sorted array, skipping duplicates.
#define	cx_array_sort(array, fn)
	Sorts an array.
#define	cx_array_sort_c(array, fn, context)
	Sorts an array.
#define	cx_array_iterator(array)
	Creates an iterator over the elements of an array.
#define	cx_array_iterator_ptr(array)
	Creates an iterator over the elements of an array containing pointers.
#define	cx_array_remove(array, index)
	Removes one element from the array.
#define	cx_array_remove_fast(array, index)
	Removes one element from the array.
#define	cx_array_remove_array(array, index, n)
	Removes multiple elements from the array.
#define	cx_array_remove_array_fast(array, index, n)
	Removes multiple elements from the array.
#define	cx_array_free(array)
	Deallocates an array.
#define	cx_array_free_a(allocator, array)
	Deallocates an array.

Typedefs
typedef struct cx_array_s	CxArray
	Internal structure for arrays.

Functions
int	cx_array_init_ (const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity)
	Initializes an array by allocating memory.
void	cx_array_init_fixed_ (CxArray *array, const void *data, size_t capacity, size_t size)
	Initializes an array with fixed size memory.
int	cx_array_reserve_ (const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity)
	Changes the capacity of an array.
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.
int	cx_array_insert_ (const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t index, const void *other, size_t n)
	Inserts data into an array.
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 sorted data into a sorted array.
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 sorted data into a sorted array.
void	cx_array_qsort_c (void *array, size_t nmemb, size_t size, cx_compare_func2 fn, void *context)
	An alternative to qsort_r() when that is not available on your platform.
void	cx_array_sort_ (CxArray *array, size_t elem_size, cx_compare_func fn)
	Sorts an array.
void	cx_array_sort_c_ (CxArray *array, size_t elem_size, cx_compare_func2 fn, void *context)
	Sorts an array.
CxIterator	cx_array_iterator_ (CxArray *array, size_t elem_size)
	Creates an iterator over the elements of an array.
CxIterator	cx_array_iterator_ptr_ (CxArray *array)
	Creates an iterator over the elements of an array containing pointers.
void	cx_array_remove_ (CxArray *array, size_t elem_size, size_t index, size_t n, bool fast)
	Removes elements from the array.
void	cx_array_free_ (const CxAllocator *allocator, CxArray *array)
	Deallocates an array.
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 the largest lower bound in a sorted array.
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 an item in a sorted array.
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 smallest upper bound in a sorted array.
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 the largest lower bound in a sorted array.
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 an item in a sorted array.
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)
	Searches the smallest upper bound in a sorted array.
void	cx_array_swap (void *arr, size_t elem_size, size_t idx1, size_t idx2)
	Swaps two array elements.
CxList *	cxArrayListCreate (const CxAllocator *allocator, size_t elem_size, size_t initial_capacity)
	Allocates an array list for storing elements with elem_size bytes each.

Variables
const unsigned	cx_array_swap_sbo_size
	The maximum item size in an array list that fits into a stack buffer when swapped.

Detailed Description

Array list implementation.

Author

Mike Becker

Olaf Wintermann

Copyright

2-Clause BSD License

Macro Definition Documentation

CX_ARRAY

#define CX_ARRAY	(		type,
			name )

Value:

    struct { \
        type *data; \
        size_t size; \
        size_t capacity; \
    } name

Declares a typed array with size and capacity.

Parameters

type	the type of the elements
name	the name of the array

cx_array_add

#define cx_array_add	(		array,
			element )

Value:

        cx_array_add_a(cxDefaultAllocator, array, element)

Appends an element to an array.

When the capacity is not enough to hold the new element, a re-allocation is attempted.

Parameters

array	the name of the array where the element shall be added
element	(void*) a pointer to the element that shall be added

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_add_a

#define cx_array_add_a	(		allocator,
			array,
			element )

Value:

        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.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the element shall be added
element	the element that shall be added

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_add_array

#define cx_array_add_array	(		array,
			other,
			n )

Value:

        cx_array_add_array_a(cxDefaultAllocator, array, other, n)

Appends data to an array.

When the capacity is not enough to hold the new elements, a re-allocation is attempted.

Parameters

array	the name of the array where the elements shall be added
other	(void*) a pointer to an array of data that shall be added
n	(size_t) the number of elements that shall be added

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_add_array_a

#define cx_array_add_array_a	(		allocator,
			array,
			other,
			n )

Value:

        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.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the elements shall be added
other	(void*) a pointer to an array of data that shall be added
n	(size_t) the number of elements that shall be added

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_copy_to_new

#define cx_array_copy_to_new	(		array,
			capacity )

Value:

        cx_array_copy_to_new_a(cxDefaultAllocator, array, 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.

Parameters

array	the name of the array
capacity	(size_t) the new maximum number of elements

Return values

zero	allocation was successful
non-zero	allocation failed

See also

cx_array_init_fixed()

cx_array_copy_to_new_a

#define cx_array_copy_to_new_a	(		allocator,
			array,
			capacity )

Value:

        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.

Parameters

allocator	(CxAllocator*) the allocator for the new memory
array	the name of the array
capacity	(size_t) the new maximum number of elements

Return values

zero	allocation was successful
non-zero	allocation failed

See also

cx_array_init_fixed()

cx_array_free

#define cx_array_free

(

array

)

Value:

cx_array_free_(cxDefaultAllocator, (CxArray*)&(array))

Deallocates an array.

The structure is reset to zero and can be re-initialized with cx_array_inita().

Parameters

array

the name of the array

cx_array_free_a

#define cx_array_free_a	(		allocator,
			array )

Value:

cx_array_free_(allocator, (CxArray*)&(array))

Deallocates an array.

The structure is reset to zero and can be re-initialized with cx_array_init_a().

Parameters

allocator	(CxAllocator*) the allocator which was used to allocate the array
array	the name of the array

cx_array_init

#define cx_array_init	(		array,
			capacity )

Value:

cx_array_init_a(cxDefaultAllocator, array, capacity)

Initializes an array by allocating memory.

The size is set to zero.

Attention

If the array was already initialized, this will leak memory.

Parameters

array	the name of the array
capacity	(size_t) the initial maximum number of elements

Return values

zero	allocation was successful
non-zero	allocation failed

cx_array_init_a

#define cx_array_init_a	(		allocator,
			array,
			capacity )

Value:

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. Use cx_array_reserve() to change the capacity of an initialized array.

Parameters

allocator	(CxAllocator*) the allocator for the array
array	the name of the array
capacity	(size_t) the initial maximum number of elements

Return values

zero	allocation was successful
non-zero	allocation failed

cx_array_init_fixed

#define cx_array_init_fixed	(		array,
			fixed_size_array,
			num_initialized )

Value:

        cx_array_init_fixed_((CxArray*)&(array), fixed_size_array, cx_nmemb(fixed_size_array), num_initialized)

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 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.

When you pass a pointer to an array that does not have a fixed size, the behavior is unspecified.

Parameters

array	the name of the array to initialize
fixed_size_array	(void*) the fixed size array
num_initialized	(size_t) the number of already initialized elements in the fixed size array

See also

cx_array_copy_to_new()

cx_array_insert

#define cx_array_insert	(		array,
			index,
			element )

Value:

        cx_array_insert_a(cxDefaultAllocator, array, index, element)

Inserts an element into an array.

When the capacity is not enough to hold the new element, a re-allocation is attempted.

Parameters

array	the name of the array where the element shall be inserted
index	(size_t) the index where to insert the element
element	(void*) a pointer to the element that shall be inserted

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_a

#define cx_array_insert_a	(		allocator,
			array,
			index,
			element )

Value:

        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.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the element shall be inserted
index	(size_t) the index where to insert the element
element	the element that shall be inserted

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_array

#define cx_array_insert_array	(		array,
			index,
			other,
			n )

Value:

        cx_array_insert_array_a(cxDefaultAllocator, array, index, other, n)

Inserts data into an array.

When the capacity is not enough to hold the new elements, a re-allocation is attempted.

Parameters

array	the name of the array where the elements shall be inserted
index	(size_t) the index where to insert the other data
other	(void*) a pointer to an array of data that shall be inserted
n	(size_t) the number of elements that shall be inserted

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_array_a

#define cx_array_insert_array_a	(		allocator,
			array,
			index,
			other,
			n )

Value:

        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.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the elements shall be inserted
index	(size_t) the index where to insert the other data
other	(void*) a pointer to an array of data that shall be inserted
n	(size_t) the number of elements that shall be inserted

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_sorted

#define cx_array_insert_sorted	(		array,
			element,
			cmp_func )

Value:

        cx_array_insert_sorted_a(cxDefaultAllocator, array, element, cmp_func)

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 cmp_func, the behavior is undefined.

Parameters

array	the name of the array where the elements shall be inserted
element	the element that shall be inserted
cmp_func	(cx_compare_func) the compare function that establishes the order

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_sorted_a

#define cx_array_insert_sorted_a	(		allocator,
			array,
			element,
			cmp_func )

Value:

        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 cmp_func, the behavior is undefined.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the elements shall be inserted
element	the element that shall be inserted
cmp_func	(cx_compare_func) the compare function that establishes the order

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_sorted_array

#define cx_array_insert_sorted_array	(		array,
			sorted_data,
			n,
			cmp_func )

Value:

        cx_array_insert_sorted_array_a(cxDefaultAllocator, array, sorted_data, n, 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 cmp_func, the behavior is undefined.

Parameters

array	the name of the array where the elements shall be inserted
sorted_data	(void*) a pointer to an array of sorted data that shall be inserted
n	(size_t) the number of elements that shall be inserted
cmp_func	(cx_compare_func) the compare function that establishes the order

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_sorted_array_a

#define cx_array_insert_sorted_array_a	(		allocator,
			array,
			sorted_data,
			n,
			cmp_func )

Value:

        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 cmp_func, the behavior is undefined.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the elements shall be inserted
sorted_data	(void*) a pointer to an array of sorted data that shall be inserted
n	(size_t) the number of elements that shall be inserted
cmp_func	(cx_compare_func) the compare function that establishes the order

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_sorted_array_c

#define cx_array_insert_sorted_array_c	(		array,
			sorted_data,
			n,
			cmp_func,
			context )

Value:

        cx_array_insert_sorted_array_ca(cxDefaultAllocator, array, sorted_data, n, 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 cmp_func, the behavior is undefined.

Parameters

array	the name of the array where the elements shall be inserted
sorted_data	(void*) a pointer to an array of sorted data that shall be inserted
n	(size_t) the number of elements that shall be inserted
cmp_func	(cx_compare_func2) the compare function that establishes the order
context	(void*) additional context for the compare function

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_sorted_array_ca

#define cx_array_insert_sorted_array_ca	(		allocator,
			array,
			sorted_data,
			n,
			cmp_func,
			context )

Value:

        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 cmp_func, the behavior is undefined.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the elements shall be inserted
sorted_data	(void*) a pointer to an array of sorted data that shall be inserted
n	(size_t) the number of elements that shall be inserted
cmp_func	(cx_compare_func2) the compare function that establishes the order
context	(void*) additional context for the compare function

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_sorted_c

#define cx_array_insert_sorted_c	(		array,
			element,
			cmp_func,
			context )

Value:

        cx_array_insert_sorted_ca(cxDefaultAllocator, array, element, cmp_func, context)

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 cmp_func, the behavior is undefined.

Parameters

array	the name of the array where the elements shall be inserted
element	the element that shall be inserted
cmp_func	(cx_compare_func2) the compare function that establishes the order
context	(void*) additional context for the compare function

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_sorted_ca

#define cx_array_insert_sorted_ca	(		allocator,
			array,
			element,
			cmp_func,
			context )

Value:

        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 cmp_func, the behavior is undefined.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the elements shall be inserted
element	the element that shall be inserted
cmp_func	(cx_compare_func2) the compare function that establishes the order
context	(void*) additional context for the compare function

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_unique

#define cx_array_insert_unique	(		array,
			element,
			cmp_func )

Value:

        cx_array_insert_unique_a(cxDefaultAllocator, array, element, 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 cmp_func, the behavior is undefined.

Parameters

array	the name of the array where the elements shall be inserted
element	the element that shall be inserted
cmp_func	(cx_compare_func) the compare function that establishes the order

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_unique_a

#define cx_array_insert_unique_a	(		allocator,
			array,
			element,
			cmp_func )

Value:

        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 cmp_func, the behavior is undefined.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the elements shall be inserted
element	the element that shall be inserted
cmp_func	(cx_compare_func) the compare function that establishes the order

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_unique_array

#define cx_array_insert_unique_array	(		array,
			sorted_data,
			n,
			cmp_func )

Value:

        cx_array_insert_unique_array_a(cxDefaultAllocator, array, sorted_data, n, 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 cmp_func, the behavior is undefined.

Parameters

array	the name of the array where the elements shall be inserted
sorted_data	(void*) a pointer to an array of sorted data that shall be inserted
n	(size_t) the number of elements that shall be inserted
cmp_func	(cx_compare_func) the compare function that establishes the order

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_unique_array_a

#define cx_array_insert_unique_array_a	(		allocator,
			array,
			sorted_data,
			n,
			cmp_func )

Value:

        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 cmp_func, the behavior is undefined.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the elements shall be inserted
sorted_data	(void*) a pointer to an array of sorted data that shall be inserted
n	(size_t) the number of elements that shall be inserted
cmp_func	(cx_compare_func) the compare function that establishes the order

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_unique_array_c

#define cx_array_insert_unique_array_c	(		array,
			sorted_data,
			n,
			cmp_func,
			context )

Value:

        cx_array_insert_unique_array_ca(cxDefaultAllocator, array, sorted_data, n, 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 cmp_func, the behavior is undefined.

Parameters

array	the name of the array where the elements shall be inserted
sorted_data	(void*) a pointer to an array of sorted data that shall be inserted
n	(size_t) the number of elements that shall be inserted
cmp_func	(cx_compare_func2) the compare function that establishes the order
context	(void*) additional context for the compare function

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_unique_array_ca

#define cx_array_insert_unique_array_ca	(		allocator,
			array,
			sorted_data,
			n,
			cmp_func,
			context )

Value:

        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 cmp_func, the behavior is undefined.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the elements shall be inserted
sorted_data	(void*) a pointer to an array of sorted data that shall be inserted
n	(size_t) the number of elements that shall be inserted
cmp_func	(cx_compare_func2) the compare function that establishes the order
context	(void*) additional context for the compare function

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_unique_c

#define cx_array_insert_unique_c	(		array,
			element,
			cmp_func,
			context )

Value:

        cx_array_insert_unique_ca(cxDefaultAllocator, array, element, 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 cmp_func, the behavior is undefined.

Parameters

array	the name of the array where the elements shall be inserted
element	the element that shall be inserted
cmp_func	(cx_compare_func2) the compare function that establishes the order
context	(void*) additional context for the compare function

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_unique_ca

#define cx_array_insert_unique_ca	(		allocator,
			array,
			element,
			cmp_func,
			context )

Value:

        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 cmp_func, the behavior is undefined.

Parameters

allocator	(CxAllocator*) the allocator to use for a possible reallocation
array	the name of the array where the elements shall be inserted
element	the element that shall be inserted
cmp_func	(cx_compare_func2) the compare function that establishes the order
context	(void*) additional context for the compare function

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_iterator

#define cx_array_iterator

(

array

)

Value:

        cx_array_iterator_((CxArray*)&(array), sizeof((array).data[0]))

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.

Parameters

array

the name of the array

Returns

an iterator over the elements

See also

cx_array_iterator_ptr()

cx_array_iterator_ptr

#define cx_array_iterator_ptr

(

array

)

Value:

        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.

Parameters

array

the name of the array

Returns

an iterator over the elements

See also

cx_array_iterator()

cx_array_remove

#define cx_array_remove	(		array,
			index )

Value:

        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, 1, false)

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.

Parameters

array	the name of the array
index	(size_t) the index of the element to remove

See also

cx_array_remove_fast()

cx_array_remove_array

#define cx_array_remove_array	(		array,
			index,
			n )

Value:

        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, n, false)

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
overflows the array, this function removes as many elements as it can.

Parameters

array	the name of the array
index	(size_t) the index of the first element to remove
n	(size_t) the number of elements to remove

See also

cx_array_remove_array_fast()

cx_array_remove_array_fast

#define cx_array_remove_array_fast	(		array,
			index,
			n )

Value:

        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, n, true)

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
overflows the array, this function removes as many elements as it can.

Parameters

array	the name of the array
index	(size_t) the index of the first element to remove
n	(size_t) the number of elements to remove

See also

cx_array_remove_array()

cx_array_remove_fast

#define cx_array_remove_fast	(		array,
			index )

Value:

        cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, 1, true)

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.

Parameters

array	the name of the array
index	(size_t) the index of the element to remove

See also

cx_array_remove()

cx_array_reserve

#define cx_array_reserve	(		array,
			capacity )

Value:

        cx_array_reserve_a(cxDefaultAllocator, array, capacity)

Changes the capacity of an array.

If required, the size is reduced to fit into the new capacity.

Parameters

array	the name of the array
capacity	(size_t) the new maximum number of elements

Return values

zero	allocation was successful
non-zero	allocation failed

cx_array_reserve_a

#define cx_array_reserve_a	(		allocator,
			array,
			capacity )

Value:

        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.

Parameters

allocator	(CxAllocator*) the allocator for the array
array	the name of the array
capacity	(size_t) the new maximum number of elements

Return values

zero	allocation was successful
non-zero	allocation failed

cx_array_sort

#define cx_array_sort	(		array,
			fn )

Value:

        cx_array_sort_((CxArray*)&(array), sizeof((array).data[0]), fn)

Sorts an array.

Parameters

array	the name of the array
fn	(cx_compare_func) the compare function

cx_array_sort_c

#define cx_array_sort_c	(		array,
			fn,
			context )

Value:

        cx_array_sort_c_((CxArray*)&(array), sizeof((array).data[0]), fn, context)

Sorts an array.

Parameters

array	the name of the array
fn	(cx_compare_func2) the compare function
context	(void*) the context for the compare function

Typedef Documentation

CxArray

typedef struct cx_array_s CxArray

Internal structure for arrays.

A generalization of array structures declared with CX_ARRAY().

Function Documentation

cx_array_binary_search()

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 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 cmp_func, the behavior is undefined.

Parameters

arr	the array to search
size	the size of the array
elem_size	the size of one element
elem	the element to find
cmp_func	the compare function

Returns

the index of the element in the array, or size if the element cannot be found

See also

cx_array_binary_search_inf()

cx_array_binary_search_sup()

cx_array_binary_search_c()

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 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 cmp_func, the behavior is undefined.

Parameters

arr	the array to search
size	the size of the array
elem_size	the size of one element
elem	the element to find
cmp_func	the compare function
context	the context for the compare function

Returns

the index of the element in the array, or size if the element cannot be found

See also

cx_array_binary_search_inf()

cx_array_binary_search_sup()

cx_array_binary_search_inf()

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 the largest lower bound in a sorted array.

In other words, this function returns the index of the largest element in arr that is less or equal to elem with respect to cmp_func. When no such element exists, size is returned.

When such an element exists more than once, the largest index of all those elements is returned.

If elem is contained in the array, this is identical to cx_array_binary_search().

If the array is not sorted with respect to the cmp_func, the behavior is undefined.

Parameters

arr	the array to search
size	the size of the array
elem_size	the size of one element
elem	the element to find
cmp_func	the compare function

Returns

the index of the largest lower bound, or size

See also

cx_array_binary_search_sup()

cx_array_binary_search()

cx_array_binary_search_inf_c()

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 the largest lower bound in a sorted array.

In other words, this function returns the index of the largest element in arr that is less or equal to elem with respect to cmp_func. When no such element exists, size is returned.

When such an element exists more than once, the largest index of all those elements is returned.

If elem is contained in the array, this is identical to cx_array_binary_search().

If the array is not sorted with respect to the cmp_func, the behavior is undefined.

Parameters

arr	the array to search
size	the size of the array
elem_size	the size of one element
elem	the element to find
cmp_func	the compare function
context	the context for the compare function

Returns

the index of the largest lower bound, or size

See also

cx_array_binary_search_sup()

cx_array_binary_search()

cx_array_binary_search_sup()

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 smallest upper bound in a sorted array.

In other words, this function returns the index of the smallest element in arr that is greater or equal to elem with respect to cmp_func. When no such element exists, size is returned.

When such an element exists more than once, the smallest index of all those elements is returned.

If elem is contained in the array, this is identical to cx_array_binary_search().

If the array is not sorted with respect to the cmp_func, the behavior is undefined.

Parameters

arr	the array to search
size	the size of the array
elem_size	the size of one element
elem	the element to find
cmp_func	the compare function

Returns

the index of the smallest upper bound, or size

See also

cx_array_binary_search_inf()

cx_array_binary_search()

cx_array_binary_search_sup_c()

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 )

Searches the smallest upper bound in a sorted array.

In other words, this function returns the index of the smallest element in arr that is greater or equal to elem with respect to cmp_func. When no such element exists, size is returned.

When such an element exists more than once, the smallest index of all those elements is returned.

If elem is contained in the array, this is identical to cx_array_binary_search().

If the array is not sorted with respect to the cmp_func, the behavior is undefined.

Parameters

arr	the array to search
size	the size of the array
elem_size	the size of one element
elem	the element to find
cmp_func	the compare function
context	the context for the compare function

Returns

the index of the smallest upper bound, or size

See also

cx_array_binary_search_inf()

cx_array_binary_search()

cx_array_copy_to_new_()

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.

Internal function - do not use.

Parameters

allocator	the allocator for new new memory
array	a pointer to the array structure
elem_size	the size of one element
capacity	the new capacity

Return values

zero	allocation was successful
non-zero	allocation failed

cx_array_free_()

void cx_array_free_	(	const CxAllocator *	allocator,
		CxArray *	array )

Deallocates an array.

Internal function - do not use.

Parameters

allocator	(CxAllocator*) the allocator which was used to allocate the array
array	a pointer to the array structure

cx_array_init_()

int cx_array_init_	(	const CxAllocator *	allocator,
		CxArray *	array,
		size_t	elem_size,
		size_t	capacity )

Initializes an array by allocating memory.

Internal function - do not use manually.

Parameters

allocator	the allocator for the array
array	a pointer to the array structure
elem_size	size of one element
capacity	the initial maximum number of elements

Return values

zero	allocation was successful
non-zero	allocation failed

cx_array_init_fixed_()

void cx_array_init_fixed_	(	CxArray *	array,
		const void *	data,
		size_t	capacity,
		size_t	size )

Initializes an array with fixed size memory.

Internal function - do not use manually.

Parameters

array	a pointer to the array structure
data	the fixed size array
capacity	the capacity of the fixed size array
size	the number of initialized elements in the fixed size array

cx_array_insert_()

int cx_array_insert_	(	const CxAllocator *	allocator,
		CxArray *	array,
		size_t	elem_size,
		size_t	index,
		const void *	other,
		size_t	n )

Inserts data into an array.

Internal function - do not use.

Parameters

allocator	the allocator to use for a possible reallocation
array	a pointer to the array structure
elem_size	the size of one element
index	the index where to insert the other data
other	a pointer to an array of data that shall be inserted
n	the number of elements that shall be inserted

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_sorted_()

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 sorted data into a sorted array.

Internal function - do not use.

Parameters

allocator	the allocator to use for a possible reallocation
array	a pointer to the array structure
elem_size	the size of one element
sorted_data	a pointer to an array of data that shall be inserted
n	the number of elements that shall be inserted
cmp_func	the compare function
allow_duplicates	false if duplicates shall be skipped during insertion

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_insert_sorted_c_()

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 sorted data into a sorted array.

Internal function - do not use.

Parameters

allocator	the allocator to use for a possible reallocation
array	a pointer to the array structure
elem_size	the size of one element
sorted_data	a pointer to an array of data that shall be inserted
n	the number of elements that shall be inserted
cmp_func	the compare function
context	additional context for the compare function
allow_duplicates	false if duplicates shall be skipped during insertion

Return values

zero	success
non-zero	a re-allocation was necessary but failed

cx_array_iterator_()

CxIterator cx_array_iterator_	(	CxArray *	array,
		size_t	elem_size )

Creates an iterator over the elements of an array.

Internal function - do not use.

Parameters

array	a pointer to the array structure
elem_size	the size of one element

Returns

an iterator over the elements

cx_array_iterator_ptr_()

CxIterator cx_array_iterator_ptr_

(

CxArray *

array

)

Creates an iterator over the elements of an array containing pointers.

Internal function - do not use.

Parameters

array

the name of the array

Returns

an iterator over the elements

cx_array_qsort_c()

void cx_array_qsort_c	(	void *	array,
		size_t	nmemb,
		size_t	size,
		cx_compare_func2	fn,
		void *	context )

An alternative to qsort_r() when that is not available on your platform.

If it is available, qsort_r() is used directly.

Parameters

array	the array that shall be sorted
nmemb	the number of elements in the array
size	the size of one element
fn	the compare function
context	the context for the compare function

cx_array_remove_()

void cx_array_remove_	(	CxArray *	array,
		size_t	elem_size,
		size_t	index,
		size_t	n,
		bool	fast )

Removes elements from the array.

Internal function - do not use.

Parameters

array	a pointer to the array structure
elem_size	the size of one element
index	the index of the first element to remove
n	the number of elements to remove
fast	indicates whether tail elements should be copied into the gap

cx_array_reserve_()

int cx_array_reserve_	(	const CxAllocator *	allocator,
		CxArray *	array,
		size_t	elem_size,
		size_t	capacity )

Changes the capacity of an array.

Internal function - do not use.

Parameters

allocator	the allocator
array	a pointer to the array structure
elem_size	the size of one element
capacity	the new capacity

Return values

zero	allocation was successful
non-zero	allocation failed

cx_array_sort_()

void cx_array_sort_	(	CxArray *	array,
		size_t	elem_size,
		cx_compare_func	fn )

Sorts an array.

Internal function - do not use.

Parameters

array	a pointer to the array structure
elem_size	the size of one element
fn	the compare function

cx_array_sort_c_()

void cx_array_sort_c_	(	CxArray *	array,
		size_t	elem_size,
		cx_compare_func2	fn,
		void *	context )

Sorts an array.

Internal function - do not use.

Parameters

array	a pointer to the array structure
elem_size	the size of one element
fn	the compare function
context	the context for the compare function

cx_array_swap()

void cx_array_swap	(	void *	arr,
		size_t	elem_size,
		size_t	idx1,
		size_t	idx2 )

Swaps two array elements.

Parameters

arr	the array
elem_size	the element size
idx1	index of the first element
idx2	index of the second element

cxArrayListCreate()

CxList * cxArrayListCreate	(	const CxAllocator *	allocator,
		size_t	elem_size,
		size_t	initial_capacity )

Allocates an array list for storing elements with elem_size bytes each.

If 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().

Parameters

allocator	the allocator for allocating the list memory (if NULL, the cxDefaultAllocator will be used)
elem_size	the size of each element in bytes
initial_capacity	the initial number of elements the array can store

Returns

the created list