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_reallocator_s
	Defines a reallocation mechanism for arrays. More...

Macros
#define	CX_ARRAY_DECLARE_SIZED(type, name, size_type)
	Declares variables for an array that can be used with the convenience macros.
#define	CX_ARRAY_DECLARE(type, name)   CX_ARRAY_DECLARE_SIZED(type, name, size_t)
	Declares variables for an array that can be used with the convenience macros.
#define	cx_array_initialize(array, capacity)
	Initializes an array with the given capacity.
#define	cx_array_initialize_a(allocator, array, capacity)
	Initializes an array with the given capacity using the specified allocator.
#define	cx_array_simple_copy_a(reallocator, array, index, src, count)
	Convenience macro that uses cx_array_copy() with a default layout and the specified reallocator.
#define	cx_array_simple_copy(array, index, src, count)    cx_array_simple_copy_a(NULL, array, index, src, count)
	Convenience macro that uses cx_array_copy() with a default layout and the default reallocator.
#define	cx_array_simple_reserve_a(reallocator, array, count)
	Convenience macro that uses cx_array_reserve() with a default layout and the specified reallocator.
#define	cx_array_simple_reserve(array, count)    cx_array_simple_reserve_a(NULL, array, count)
	Convenience macro that uses cx_array_reserve() with a default layout and the default reallocator.
#define	cx_array_add(target, size, capacity, elem_size, elem, reallocator)
	Adds an element to an array with the possibility of allocating more space.
#define	cx_array_simple_add_a(reallocator, array, elem)    cx_array_simple_copy_a(reallocator, array, array##_size, &(elem), 1)
	Convenience macro that uses cx_array_add() with a default layout and the specified reallocator.
#define	cx_array_simple_add(array, elem)    cx_array_simple_add_a(cx_array_default_reallocator, array, elem)
	Convenience macro that uses cx_array_add() with a default layout and the default reallocator.
#define	cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator)    cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator)
	Inserts an element into a sorted array.
#define	cx_array_simple_add_sorted_a(reallocator, array, elem, cmp_func)
	Convenience macro for cx_array_add_sorted() with a default layout and the specified reallocator.
#define	cx_array_simple_add_sorted(array, elem, cmp_func)    cx_array_simple_add_sorted_a(NULL, array, elem, cmp_func)
	Convenience macro for cx_array_add_sorted() with a default layout and the default reallocator.
#define	cx_array_simple_insert_sorted_a(reallocator, array, src, n, cmp_func)
	Convenience macro for cx_array_insert_sorted() with a default layout and the specified reallocator.
#define	cx_array_simple_insert_sorted(array, src, n, cmp_func)    cx_array_simple_insert_sorted_a(NULL, array, src, n, cmp_func)
	Convenience macro for cx_array_insert_sorted() with a default layout and the default reallocator.
#define	cxArrayListCreateSimple(elem_size, initial_capacity)    cxArrayListCreate(NULL, NULL, elem_size, initial_capacity)
	Allocates an array list for storing elements with elem_size bytes each.

Typedefs
typedef struct cx_array_reallocator_s	CxArrayReallocator
	Typedef for the array reallocator struct.

Functions
CxArrayReallocator	cx_array_reallocator (const struct cx_allocator_s *allocator, const void *stackmem)
	Creates a new array reallocator.
int	cx_array_reserve (void **array, void *size, void *capacity, unsigned width, size_t elem_size, size_t elem_count, CxArrayReallocator *reallocator)
	Reserves memory for additional elements.
int	cx_array_copy (void **target, void *size, void *capacity, unsigned width, size_t index, const void *src, size_t elem_size, size_t elem_count, CxArrayReallocator *reallocator)
	Copies elements from one array to another.
int	cx_array_insert_sorted (void **target, size_t *size, size_t *capacity, cx_compare_func cmp_func, const void *src, size_t elem_size, size_t elem_count, CxArrayReallocator *reallocator)
	Inserts a sorted array into another sorted 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.
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, cx_compare_func comparator, 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 stack buffer when swapped.
CxArrayReallocator *	cx_array_default_reallocator
	A default stdlib-based array reallocator.

Detailed Description

Array list implementation.

Author

Mike Becker

Olaf Wintermann

Copyright

2-Clause BSD License

Macro Definition Documentation

cx_array_add

#define cx_array_add	(		target,
			size,
			capacity,
			elem_size,
			elem,
			reallocator )

Value:

    cx_array_copy((void**)(target), size, capacity, sizeof(*(size)), \
    *(size), elem, elem_size, 1, reallocator)

Adds an element to an array with the possibility of allocating more space.

The element elem is added to the end of the target array which contains size elements, already. The capacity must point to a variable denoting the current maximum number of elements the array can hold.

If the capacity is insufficient to hold the new element, an attempt to increase the capacity is made and the new capacity is written back.

The @ SIZE_TYPE is flexible and can be any unsigned integer type. It is important, however, that size and capacity are pointers to variables of the same type.

Parameters

target	(void**) a pointer to the target array
size	(SIZE_TYPE*) a pointer to the size of the target array
capacity	(SIZE_TYPE*) a pointer to the capacity of the target array
elem_size	(size_t) the size of one element
elem	(void*) a pointer to the element to add
reallocator	(CxArrayReallocator*) the array reallocator to use

Return values

zero	success
non-zero	failure

cx_array_add_sorted

#define cx_array_add_sorted	(		target,
			size,
			capacity,
			elem_size,
			elem,
			cmp_func,
			reallocator )    cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator)

Inserts an element into a sorted array.

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

If the capacity is insufficient to hold the new data, a reallocation attempt is made.

The @ SIZE_TYPE is flexible and can be any unsigned integer type. It is important, however, that size and capacity are pointers to variables of the same type.

Parameters

target	(void**) a pointer to the target array
size	(SIZE_TYPE*) a pointer to the size of the target array
capacity	(SIZE_TYPE*) a pointer to the capacity of the target array
elem_size	(size_t) the size of one element
elem	(void*) a pointer to the element to add
cmp_func	(cx_cmp_func) the compare function for the elements
reallocator	(CxArrayReallocator*) the array reallocator to use

Return values

zero	success
non-zero	failure

CX_ARRAY_DECLARE

#define CX_ARRAY_DECLARE	(		type,
			name )   CX_ARRAY_DECLARE_SIZED(type, name, size_t)

Declares variables for an array that can be used with the convenience macros.

The size and capacity variables will have size_t type. Use CX_ARRAY_DECLARE_SIZED() to specify a different type.

Examples

// int array
CX_ARRAY_DECLARE(int, myarray)
 
// initializing code
cx_array_initialize(myarray, 32); // reserve space for 32

Parameters

type	the type of the data
name	the name of the array

See also

cx_array_initialize()

cx_array_simple_add()

cx_array_simple_copy()

cx_array_simple_add_sorted()

cx_array_simple_insert_sorted()

CX_ARRAY_DECLARE_SIZED

#define CX_ARRAY_DECLARE_SIZED	(		type,
			name,
			size_type )

Value:

    type * name; \
 size_type name##_size; \
 size_type name##_capacity

Declares variables for an array that can be used with the convenience macros.

Examples

// integer array with at most 255 elements
CX_ARRAY_DECLARE_SIZED(int, myarray, uint8_t)
 
// array of MyObject* pointers where size and capacity are stored as unsigned int
CX_ARRAY_DECLARE_SIZED(MyObject*, objects, unsigned int)
 
// initializing code
cx_array_initialize(myarray, 16); // reserve space for 16
cx_array_initialize(objects, 100); // reserve space for 100

Parameters

type	the type of the data
name	the name of the array
size_type	the type of the size (should be uint8_t, uint16_t, uint32_t, or size_t)

See also

cx_array_initialize()

cx_array_simple_add()

cx_array_simple_copy()

cx_array_simple_add_sorted()

cx_array_simple_insert_sorted()

cx_array_initialize

#define cx_array_initialize	(		array,
			capacity )

Value:

        array##_capacity = capacity; \
        array##_size = 0; \
        array = malloc(sizeof(array[0]) * capacity)

Initializes an array with the given capacity.

The type of the capacity depends on the type used during declaration.

Examples

CX_ARRAY_DECLARE_SIZED(int, arr1, uint8_t)
CX_ARRAY_DECLARE(int, arr2) // size and capacity are implicitly size_t
 
// initializing code
cx_array_initialize(arr1, 500); // error: maximum for uint8_t is 255
cx_array_initialize(arr2, 500); // OK

The memory for the array is allocated with stdlib malloc().

Parameters

array	the name of the array
capacity	the initial capacity

See also

cx_array_initialize_a()

CX_ARRAY_DECLARE_SIZED()

CX_ARRAY_DECLARE()

cx_array_initialize_a

#define cx_array_initialize_a	(		allocator,
			array,
			capacity )

Value:

        array##_capacity = capacity; \
        array##_size = 0; \
        array = cxMalloc(allocator, sizeof(array[0]) * capacity)

Initializes an array with the given capacity using the specified allocator.

Example

CX_ARRAY_DECLARE(int, myarray)
 
 
const CxAllocator *al = // ...
cx_array_initialize_a(al, myarray, 128);
// ...
cxFree(al, myarray); // don't forget to free with same allocator

The memory for the array is allocated with stdlib malloc().

Parameters

allocator	(CxAllocator*) the allocator
array	the name of the array
capacity	the initial capacity

See also

cx_array_initialize()

CX_ARRAY_DECLARE_SIZED()

CX_ARRAY_DECLARE()

cx_array_simple_add

#define cx_array_simple_add	(		array,
			elem )    cx_array_simple_add_a(cx_array_default_reallocator, array, elem)

Convenience macro that uses cx_array_add() with a default layout and the default reallocator.

Parameters

array	the name of the array (NOT a pointer or alias to the array)
elem	the element to add (NOT a pointer, address is automatically taken)

Return values

zero	success
non-zero	failure

See also

CX_ARRAY_DECLARE()

cx_array_simple_add_a()

cx_array_simple_add_a

#define cx_array_simple_add_a	(		reallocator,
			array,
			elem )    cx_array_simple_copy_a(reallocator, array, array##_size, &(elem), 1)

Convenience macro that uses cx_array_add() with a default layout and the specified reallocator.

Parameters

reallocator	(CxArrayReallocator*) the array reallocator to use
array	the name of the array (NOT a pointer or alias to the array)
elem	the element to add (NOT a pointer, address is automatically taken)

Return values

zero	success
non-zero	failure

See also

CX_ARRAY_DECLARE()

cx_array_simple_add()

cx_array_simple_add_sorted

#define cx_array_simple_add_sorted	(		array,
			elem,
			cmp_func )    cx_array_simple_add_sorted_a(NULL, array, elem, cmp_func)

Convenience macro for cx_array_add_sorted() with a default layout and the default reallocator.

Parameters

array	the name of the array (NOT a pointer or alias to the array)
elem	the element to add (NOT a pointer, address is automatically taken)
cmp_func	(cx_cmp_func) the compare function for the elements

Return values

zero	success
non-zero	failure

See also

CX_ARRAY_DECLARE()

cx_array_simple_add_sorted_a()

cx_array_simple_add_sorted_a

#define cx_array_simple_add_sorted_a	(		reallocator,
			array,
			elem,
			cmp_func )

Value:

    cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \
        sizeof((array)[0]), &(elem), cmp_func, reallocator)

Convenience macro for cx_array_add_sorted() with a default layout and the specified reallocator.

Parameters

reallocator	(CxArrayReallocator*) the array reallocator to use
array	the name of the array (NOT a pointer or alias to the array)
elem	the element to add (NOT a pointer, address is automatically taken)
cmp_func	(cx_cmp_func) the compare function for the elements

Return values

zero	success
non-zero	failure

See also

CX_ARRAY_DECLARE()

cx_array_simple_add_sorted()

cx_array_simple_copy

#define cx_array_simple_copy	(		array,
			index,
			src,
			count )    cx_array_simple_copy_a(NULL, array, index, src, count)

Convenience macro that uses cx_array_copy() with a default layout and the default reallocator.

Parameters

array	the name of the array (NOT a pointer or alias to the array)
index	(size_t) the index where the copied elements shall be placed
src	(void*) the source array
count	(size_t) the number of elements to copy

Return values

zero	success
non-zero	failure

See also

CX_ARRAY_DECLARE()

cx_array_simple_copy_a()

cx_array_simple_copy_a

#define cx_array_simple_copy_a	(		reallocator,
			array,
			index,
			src,
			count )

Value:

    cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \
        sizeof(array##_size), index, src, sizeof((array)[0]), count, \
        reallocator)

Convenience macro that uses cx_array_copy() with a default layout and the specified reallocator.

Parameters

reallocator	(CxArrayReallocator*) the array reallocator to use
array	the name of the array (NOT a pointer or alias to the array)
index	(size_t) the index where the copied elements shall be placed
src	(void*) the source array
count	(size_t) the number of elements to copy

Return values

zero	success
non-zero	failure

See also

CX_ARRAY_DECLARE()

cx_array_simple_copy()

cx_array_simple_insert_sorted

#define cx_array_simple_insert_sorted	(		array,
			src,
			n,
			cmp_func )    cx_array_simple_insert_sorted_a(NULL, array, src, n, cmp_func)

Convenience macro for cx_array_insert_sorted() with a default layout and the default reallocator.

Parameters

array	the name of the array (NOT a pointer or alias to the array)
src	(void*) pointer to the source array
n	(size_t) number of elements in the source array
cmp_func	(cx_cmp_func) the compare function for the elements

Return values

zero	success
non-zero	failure

See also

CX_ARRAY_DECLARE()

cx_array_simple_insert_sorted_a()

cx_array_simple_insert_sorted_a

#define cx_array_simple_insert_sorted_a	(		reallocator,
			array,
			src,
			n,
			cmp_func )

Value:

    cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \
        cmp_func, src, sizeof((array)[0]), n, reallocator)

Convenience macro for cx_array_insert_sorted() with a default layout and the specified reallocator.

Parameters

reallocator	(CxArrayReallocator*) the array reallocator to use
array	the name of the array (NOT a pointer or alias to the array)
src	(void*) pointer to the source array
n	(size_t) number of elements in the source array
cmp_func	(cx_cmp_func) the compare function for the elements

Return values

zero	success
non-zero	failure

See also

CX_ARRAY_DECLARE()

cx_array_simple_insert_sorted()

cx_array_simple_reserve

#define cx_array_simple_reserve	(		array,
			count )    cx_array_simple_reserve_a(NULL, array, count)

Convenience macro that uses cx_array_reserve() with a default layout and the default reallocator.

Parameters

array	the name of the array (NOT a pointer or alias to the array)
count	(size_t) the number of expected additional elements

Return values

zero	success
non-zero	failure

See also

CX_ARRAY_DECLARE()

cx_array_simple_reserve_a()

cx_array_simple_reserve_a

#define cx_array_simple_reserve_a	(		reallocator,
			array,
			count )

Value:

    cx_array_reserve((void**)&(array), &(array##_size), &(array##_capacity), \
        sizeof(array##_size), sizeof((array)[0]), count, \
        reallocator)

Convenience macro that uses cx_array_reserve() with a default layout and the specified reallocator.

Parameters

reallocator	(CxArrayReallocator*) the array reallocator to use
array	the name of the array (NOT a pointer or alias to the array)
count	(size_t) the number of expected additional elements

Return values

zero	success
non-zero	failure

See also

CX_ARRAY_DECLARE()

cx_array_simple_reserve()

cxArrayListCreateSimple

#define cxArrayListCreateSimple	(		elem_size,
			initial_capacity )    cxArrayListCreate(NULL, NULL, elem_size, initial_capacity)

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

The list will use the cxDefaultAllocator and NO compare function. If you want to call functions that need a compare function, you have to set it immediately after creation or use cxArrayListCreate().

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

elem_size	(size_t) the size of each element in bytes
initial_capacity	(size_t) the initial number of elements the array can store

Returns

the created list

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.

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

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

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_copy()

int cx_array_copy	(	void **	target,
		void *	size,
		void *	capacity,
		unsigned	width,
		size_t	index,
		const void *	src,
		size_t	elem_size,
		size_t	elem_count,
		CxArrayReallocator *	reallocator )

Copies elements from one array to another.

The elements are copied to the target array at the specified index, overwriting possible elements. The index does not need to be in range of the current array size. If the new index plus the number of elements added would extend the array's size, the remaining capacity is used.

If the capacity is also insufficient to hold the new data, a reallocation attempt is made with the specified reallocator. You can create your own reallocator by hand, use cx_array_default_reallocator, or use the convenience function cx_array_reallocator() to create a custom reallocator.

The width in bytes refers to the size and capacity. Both must have the same width. Supported are 0, 1, 2, and 4, as well as 8 if running on a 64 bit architecture. If set to zero, the native word width is used.

Parameters

target	a pointer to the target array
size	a pointer to the size of the target array
capacity	a pointer to the capacity of the target array
width	the width in bytes for the size and capacity or zero for default
index	the index where the copied elements shall be placed
src	the source array
elem_size	the size of one element
elem_count	the number of elements to copy
reallocator	the array reallocator to use (NULL defaults to cx_array_default_reallocator)

Return values

zero	success
non-zero	failure

See also

cx_array_reallocator()

cx_array_insert_sorted()

int cx_array_insert_sorted	(	void **	target,
		size_t *	size,
		size_t *	capacity,
		cx_compare_func	cmp_func,
		const void *	src,
		size_t	elem_size,
		size_t	elem_count,
		CxArrayReallocator *	reallocator )

Inserts a sorted array into another sorted array.

If either the target or the source array is not already sorted with respect to the specified cmp_func, the behavior is undefined.

If the capacity is insufficient to hold the new data, a reallocation attempt is made. You can create your own reallocator by hand, use cx_array_default_reallocator, or use the convenience function cx_array_reallocator() to create a custom reallocator.

Parameters

target	a pointer to the target array
size	a pointer to the size of the target array
capacity	a pointer to the capacity of the target array
cmp_func	the compare function for the elements
src	the source array
elem_size	the size of one element
elem_count	the number of elements to insert
reallocator	the array reallocator to use (NULL defaults to cx_array_default_reallocator)

Return values

zero	success
non-zero	failure

cx_array_reallocator()

CxArrayReallocator cx_array_reallocator	(	const struct cx_allocator_s *	allocator,
		const void *	stackmem )

Creates a new array reallocator.

When allocator is NULL, the stdlib default allocator will be used.

When stackmem is not NULL, the reallocator is supposed to be used only for the specific array that is initially located at stackmem. When reallocation is needed, the reallocator checks, if the array is still located at stackmem and copies the contents to the heap.

Note

Invoking this function with both arguments NULL will return a reallocator that behaves like cx_array_default_reallocator.

Parameters

allocator	the allocator this reallocator shall be based on
stackmem	the address of the array when the array is initially located on the stack or shall not reallocated in place

Returns

an array reallocator

cx_array_reserve()

int cx_array_reserve	(	void **	array,
		void *	size,
		void *	capacity,
		unsigned	width,
		size_t	elem_size,
		size_t	elem_count,
		CxArrayReallocator *	reallocator )

Reserves memory for additional elements.

This function checks if the capacity of the array is sufficient to hold at least size plus elem_count elements. If not, a reallocation is performed with the specified reallocator. You can create your own reallocator by hand, use cx_array_default_reallocator, or use the convenience function cx_array_reallocator() to create a custom reallocator.

This function can be useful to replace subsequent calls to cx_array_copy() with one single cx_array_reserve() and then - after guaranteeing a sufficient capacity - use simple memmove() or memcpy().

The width in bytes refers to the size and capacity. Both must have the same width. Supported are 0, 1, 2, and 4, as well as 8 if running on a 64 bit architecture. If set to zero, the native word width is used.

Parameters

array	a pointer to the target array
size	a pointer to the size of the array
capacity	a pointer to the capacity of the array
width	the width in bytes for the size and capacity or zero for default
elem_size	the size of one element
elem_count	the number of expected additional elements
reallocator	the array reallocator to use (NULL defaults to cx_array_default_reallocator)

Return values

zero	success
non-zero	failure

See also

cx_array_reallocator()

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 first element
idx2	index of second element

cxArrayListCreate()

CxList * cxArrayListCreate	(	const CxAllocator *	allocator,
		cx_compare_func	comparator,
		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(), if none is given.

Parameters

allocator	the allocator for allocating the list memory (if NULL, a default stdlib allocator will be used)
comparator	the comparator for the elements (if NULL, and the list is not storing pointers, sort and find functions will not work)
elem_size	the size of each element in bytes
initial_capacity	the initial number of elements the array can store

Returns

the created list