array.h File Reference

Dynamically allocated array implementation. More...

#include "ucx.h"
#include "allocator.h"

Go to the source code of this file.

Data Structures
struct	UcxArray
	UCX array type. More...

Macros
#define	ucx_array_util_set(array, capacity, elmsize, idx, data)
	Sets an element in an arbitrary user defined array. More...
#define	ucx_array_util_setptr(array, capacity, idx, ptr)
	Stores a pointer in an arbitrary user defined array. More...

Functions
int	ucx_array_util_set_a (UcxAllocator *alloc, void **array, size_t *capacity, size_t elmsize, size_t idx, void *data)
	Sets an element in an arbitrary user defined array. More...
int	ucx_array_util_setptr_a (UcxAllocator *alloc, void **array, size_t *capacity, size_t idx, void *ptr)
	Stores a pointer in an arbitrary user defined array. More...
UcxArray *	ucx_array_new (size_t capacity, size_t elemsize)
	Creates a new UCX array with the given capacity and element size. More...
UcxArray *	ucx_array_new_a (size_t capacity, size_t elemsize, UcxAllocator *allocator)
	Creates a new UCX array using the specified allocator. More...
void	ucx_array_init (UcxArray *array, size_t capacity, size_t elemsize)
	Initializes a UCX array structure with the given capacity and element size. More...
void	ucx_array_init_a (UcxArray *array, size_t capacity, size_t elemsize, UcxAllocator *allocator)
	Initializes a UCX array structure using the specified allocator. More...
int	ucx_array_clone (UcxArray *dest, UcxArray const *src)
	Creates an shallow copy of an array. More...
int	ucx_array_equals (UcxArray const *array1, UcxArray const *array2, cmp_func cmpfnc, void *data)
	Compares two UCX arrays element-wise by using a compare function. More...
void	ucx_array_destroy (UcxArray *array)
	Destroys the array. More...
void	ucx_array_free (UcxArray *array)
	Destroys and frees the array. More...
int	ucx_array_append_from (UcxArray *array, void *data, size_t count)
	Inserts elements at the end of the array. More...
int	ucx_array_prepend_from (UcxArray *array, void *data, size_t count)
	Inserts elements at the beginning of the array. More...
int	ucx_array_set_from (UcxArray *array, size_t index, void *data, size_t count)
	Sets elements starting at the specified index. More...
int	ucx_array_concat (UcxArray *array1, const UcxArray *array2)
	Concatenates two arrays. More...
void *	ucx_array_at (UcxArray const *array, size_t index)
	Returns a pointer to the array element at the specified index. More...
size_t	ucx_array_find (UcxArray const *array, void *elem, cmp_func cmpfnc, void *data)
	Returns the index of an element containing the specified data. More...
int	ucx_array_contains (UcxArray const *array, void *elem, cmp_func cmpfnc, void *data)
	Checks, if an array contains a specific element. More...
void	ucx_array_sort (UcxArray *array, cmp_func cmpfnc, void *data)
	Sorts a UcxArray with the best available sort algorithm. More...
void	ucx_array_remove (UcxArray *array, size_t index)
	Removes an element from the array. More...
void	ucx_array_remove_fast (UcxArray *array, size_t index)
	Removes an element from the array. More...
int	ucx_array_shrink (UcxArray *array)
	Shrinks the memory to exactly fit the contents. More...
int	ucx_array_resize (UcxArray *array, size_t capacity)
	Sets the capacity of the array. More...
int	ucx_array_reserve (UcxArray *array, size_t capacity)
	Resizes the array only, if the capacity is insufficient. More...
int	ucx_array_grow (UcxArray *array, size_t count)
	Resizes the capacity, if the specified number of elements would not fit. More...

Detailed Description

Dynamically allocated array implementation.

Author

Mike Becker

Olaf Wintermann

Macro Definition Documentation

ucx_array_util_set

#define ucx_array_util_set	(		array,
			capacity,
			elmsize,
			idx,
			data
	)

Value:

ucx_array_util_set_a(ucx_default_allocator(), (void**)(array), capacity, \
                         elmsize, idx, data)

Sets an element in an arbitrary user defined array.

The data is copied from the specified data location.

If the capacity is insufficient, the array is automatically reallocated and the possibly new pointer is stored in the array argument.

On reallocation the capacity of the array is doubled until it is sufficient. The new capacity is stored back to capacity.

Parameters

array	a pointer to location of the array pointer
capacity	a pointer to the capacity
elmsize	the size of each element
idx	the index of the element to set
data	a pointer to the element data

Returns

zero on success or non-zero on error (errno will be set)

ucx_array_util_setptr

#define ucx_array_util_setptr	(		array,
			capacity,
			idx,
			ptr
	)

Value:

ucx_array_util_setptr_a(ucx_default_allocator(), (void**)(array), \
                            capacity, idx, ptr)

Stores a pointer in an arbitrary user defined array.

The element size of the array must be sizeof(void*).

If the capacity is insufficient, the array is automatically reallocated and the possibly new pointer is stored in the array argument.

On reallocation the capacity of the array is doubled until it is sufficient. The new capacity is stored back to capacity.

Parameters

array	a pointer to location of the array pointer
capacity	a pointer to the capacity
idx	the index of the element to set
ptr	the pointer to store

Returns

zero on success or non-zero on error (errno will be set)

Function Documentation

ucx_array_append_from()

int ucx_array_append_from	(	UcxArray *	array,
		void *	data,
		size_t	count
	)

Inserts elements at the end of the array.

This is an O(1) operation. The array will automatically grow, if the capacity is exceeded. If a pointer to data is provided, the data is copied into the array with memcpy(). Otherwise the new elements are completely zeroed.

Parameters

array	a pointer the array where to append the data
data	a pointer to the data to insert (may be NULL)
count	number of elements to copy from data (if data is NULL, zeroed elements are appended)

Returns

zero on success, non-zero if a reallocation was necessary but failed

See also

ucx_array_set_from()

ucx_array_append()

ucx_array_at()

void* ucx_array_at	(	UcxArray const *	array,
		size_t	index
	)

Returns a pointer to the array element at the specified index.

Parameters

array	the array to retrieve the element from
index	index of the element to return

Returns

a pointer to the element at the specified index or NULL, if the index is greater than the array size

ucx_array_clone()

int ucx_array_clone	(	UcxArray *	dest,
		UcxArray const *	src
	)

Creates an shallow copy of an array.

This function clones the specified array by using memcpy(). If the destination capacity is insufficient, an automatic reallocation is attempted.

Note: if the destination array is uninitialized, the behavior is undefined.

Parameters

dest	the array to copy to
src	the array to copy from

Returns

zero on success, non-zero on reallocation failure.

ucx_array_concat()

int ucx_array_concat	(	UcxArray *	array1,
		const UcxArray *	array2
	)

Concatenates two arrays.

The contents of the second array are appended to the first array in one single operation. The second array is otherwise left untouched.

The first array may grow automatically. If this fails, both arrays remain unmodified.

Parameters

array1	first array
array2	second array

Returns

zero on success, non-zero if reallocation was necessary but failed or the element size does not match

ucx_array_contains()

int ucx_array_contains	(	UcxArray const *	array,
		void *	elem,
		cmp_func	cmpfnc,
		void *	data
	)

Checks, if an array contains a specific element.

An element is found, if ucx_array_find() returns a value less than the size.

Parameters

array	the array where to search for the data
elem	the element data
cmpfnc	the compare function
data	additional data for the compare function

Returns

1, if and only if the array contains the specified element data

See also

ucx_array_find()

ucx_array_destroy()

void ucx_array_destroy

(

UcxArray *

array

)

Destroys the array.

The data is freed and both capacity and count are reset to zero. If the array structure itself has been dynamically allocated, it has to be freed separately.

Parameters

array

the array to destroy

ucx_array_equals()

int ucx_array_equals	(	UcxArray const *	array1,
		UcxArray const *	array2,
		cmp_func	cmpfnc,
		void *	data
	)

Compares two UCX arrays element-wise by using a compare function.

Elements of the two specified arrays are compared by using the specified compare function and the additional data. The type and content of this additional data depends on the cmp_func() used.

This function always returns zero, if the element sizes of the arrays do not match and performs no comparisons in this case.

Parameters

array1	the first array
array2	the second array
cmpfnc	the compare function
data	additional data for the compare function

Returns

1, if and only if the two arrays equal element-wise, 0 otherwise

ucx_array_find()

size_t ucx_array_find	(	UcxArray const *	array,
		void *	elem,
		cmp_func	cmpfnc,
		void *	data
	)

Returns the index of an element containing the specified data.

This function uses a cmp_func() to compare the data of each list element with the specified data. If no cmp_func is provided, memcmp() is used.

If the array contains the data more than once, the index of the first occurrence is returned. If the array does not contain the data, the size of array is returned.

Parameters

array	the array where to search for the data
elem	the element data
cmpfnc	the compare function
data	additional data for the compare function

Returns

the index of the element containing the specified data or the size of the array, if the data is not found in this array

ucx_array_free()

void ucx_array_free

(

UcxArray *

array

)

Destroys and frees the array.

Parameters

array

the array to free

ucx_array_grow()

int ucx_array_grow	(	UcxArray *	array,
		size_t	count
	)

Resizes the capacity, if the specified number of elements would not fit.

A call to ucx_array_grow(array, count) is effectively the same as ucx_array_reserve(array, array->size+count).

Parameters

array	a pointer to the array
count	the number of elements that should additionally fit into the array

Returns

zero on success, non-zero if reallocation failed

ucx_array_init()

void ucx_array_init	(	UcxArray *	array,
		size_t	capacity,
		size_t	elemsize
	)

Initializes a UCX array structure with the given capacity and element size.

The structure must be uninitialized as the data pointer will be overwritten.

Parameters

array	the structure to initialize
capacity	the initial capacity
elemsize	the element size

ucx_array_init_a()

void ucx_array_init_a	(	UcxArray *	array,
		size_t	capacity,
		size_t	elemsize,
		UcxAllocator *	allocator
	)

Initializes a UCX array structure using the specified allocator.

The structure must be uninitialized as the data pointer will be overwritten.

Parameters

array	the structure to initialize
capacity	the initial capacity
elemsize	the element size
allocator	the allocator to use

ucx_array_new()

UcxArray* ucx_array_new	(	size_t	capacity,
		size_t	elemsize
	)

Creates a new UCX array with the given capacity and element size.

Parameters

capacity	the initial capacity
elemsize	the element size

Returns

a pointer to a new UCX array structure

ucx_array_new_a()

UcxArray* ucx_array_new_a	(	size_t	capacity,
		size_t	elemsize,
		UcxAllocator *	allocator
	)

Creates a new UCX array using the specified allocator.

Parameters

capacity	the initial capacity
elemsize	the element size
allocator	the allocator to use

Returns

a pointer to new UCX array structure

ucx_array_prepend_from()

int ucx_array_prepend_from	(	UcxArray *	array,
		void *	data,
		size_t	count
	)

Inserts elements at the beginning of the array.

This is an expensive operation, because the contents must be moved. If there is no particular reason to prepend data, you should use ucx_array_append_from() instead.

Parameters

array	a pointer the array where to prepend the data
data	a pointer to the data to insert (may be NULL)
count	number of elements to copy from data (if data is NULL, zeroed elements are inserted)

Returns

zero on success, non-zero if a reallocation was necessary but failed

See also

ucx_array_append_from()

ucx_array_set_from()

ucx_array_prepend()

ucx_array_remove()

void ucx_array_remove	(	UcxArray *	array,
		size_t	index
	)

Removes an element from the array.

This is in general an expensive operation, because several elements may be moved. If the order of the elements is not relevant, use ucx_array_remove_fast() instead.

Parameters

array	pointer to the array from which the element shall be removed
index	the index of the element to remove

ucx_array_remove_fast()

void ucx_array_remove_fast	(	UcxArray *	array,
		size_t	index
	)

Removes an element from the array.

This is an O(1) operation, but does not maintain the order of the elements. The last element in the array is moved to the location of the removed element.

Parameters

array	pointer to the array from which the element shall be removed
index	the index of the element to remove

ucx_array_reserve()

int ucx_array_reserve	(	UcxArray *	array,
		size_t	capacity
	)

Resizes the array only, if the capacity is insufficient.

If the requested capacity is smaller than the current capacity, this function does nothing.

Parameters

array	a pointer to the array
capacity	the guaranteed capacity

Returns

zero on success, non-zero if reallocation failed

ucx_array_resize()

int ucx_array_resize	(	UcxArray *	array,
		size_t	capacity
	)

Sets the capacity of the array.

If the new capacity is smaller than the size of the array, the elements are removed and the size is adjusted accordingly.

Parameters

array	a pointer to the array
capacity	the new capacity

Returns

zero on success, non-zero if reallocation failed

ucx_array_set_from()

int ucx_array_set_from	(	UcxArray *	array,
		size_t	index,
		void *	data,
		size_t	count
	)

Sets elements starting at the specified index.

If the any index is out of bounds, the array automatically grows. The pointer to the data may be NULL, in which case the elements are zeroed.

Parameters

array	a pointer the array where to set the data
index	the index of the element to set
data	a pointer to the data to insert (may be NULL)
count	number of elements to copy from data (if data is NULL, the memory in the array is zeroed)

Returns

zero on success, non-zero if a reallocation was necessary but failed

See also

ucx_array_append_from()

ucx_array_set()

ucx_array_shrink()

int ucx_array_shrink

(

UcxArray *

array

)

Shrinks the memory to exactly fit the contents.

After this operation, the capacity equals the size.

Parameters

array

a pointer to the array

Returns

zero on success, non-zero if reallocation failed

ucx_array_sort()

void ucx_array_sort	(	UcxArray *	array,
		cmp_func	cmpfnc,
		void *	data
	)

Sorts a UcxArray with the best available sort algorithm.

The qsort_r() function is used, if available (glibc, FreeBSD or MacOS). The order of arguments is automatically adjusted for the FreeBSD and MacOS version of qsort_r().

If qsort_r() is not available, a merge sort algorithm is used, which is guaranteed to use no more additional memory than for exactly one element.

Parameters

array	the array to sort
cmpfnc	the function that shall be used to compare the element data
data	additional data for the cmp_func() or NULL

ucx_array_util_set_a()

int ucx_array_util_set_a	(	UcxAllocator *	alloc,
		void **	array,
		size_t *	capacity,
		size_t	elmsize,
		size_t	idx,
		void *	data
	)

Sets an element in an arbitrary user defined array.

The data is copied from the specified data location.

If the capacity is insufficient, the array is automatically reallocated using the specified allocator and the possibly new pointer is stored in the array argument.

On reallocation the capacity of the array is doubled until it is sufficient. The new capacity is stored back to capacity.

Parameters

alloc	the allocator that shall be used to reallocate the array
array	a pointer to location of the array pointer
capacity	a pointer to the capacity
elmsize	the size of each element
idx	the index of the element to set
data	a pointer to the element data

Returns

zero on success or non-zero on error (errno will be set)

ucx_array_util_setptr_a()

int ucx_array_util_setptr_a	(	UcxAllocator *	alloc,
		void **	array,
		size_t *	capacity,
		size_t	idx,
		void *	ptr
	)

Stores a pointer in an arbitrary user defined array.

The element size of the array must be sizeof(void*).

If the capacity is insufficient, the array is automatically reallocated using the specified allocator and the possibly new pointer is stored in the array argument.

On reallocation the capacity of the array is doubled until it is sufficient. The new capacity is stored back to capacity.

Parameters

alloc	the allocator that shall be used to reallocate the array
array	a pointer to location of the array pointer
capacity	a pointer to the capacity
idx	the index of the element to set
ptr	the pointer to store

Returns

zero on success or non-zero on error (errno will be set)