ucx
UAP Common Extensions
Data Structures | Macros | Functions
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...
 
UcxArrayucx_array_new (size_t capacity, size_t elemsize)
 Creates a new UCX array with the given capacity and element size. More...
 
UcxArrayucx_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)
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.
Definition: array.c:72
UcxAllocator * ucx_default_allocator()
Returns a pointer to the default allocator.
Definition: allocator.c:41

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
arraya pointer to location of the array pointer
capacitya pointer to the capacity
elmsizethe size of each element
idxthe index of the element to set
dataa 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:
capacity, idx, ptr)
UcxAllocator * ucx_default_allocator()
Returns a pointer to the default allocator.
Definition: allocator.c:41
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.
Definition: array.c:112

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
arraya pointer to location of the array pointer
capacitya pointer to the capacity
idxthe index of the element to set
ptrthe 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
arraya pointer the array where to append the data
dataa pointer to the data to insert (may be NULL)
countnumber 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
arraythe array to retrieve the element from
indexindex 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
destthe array to copy to
srcthe 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
array1first array
array2second 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
arraythe array where to search for the data
elemthe element data
cmpfncthe compare function
dataadditional 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
arraythe 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
array1the first array
array2the second array
cmpfncthe compare function
dataadditional 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
arraythe array where to search for the data
elemthe element data
cmpfncthe compare function
dataadditional 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
arraythe 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
arraya pointer to the array
countthe 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
arraythe structure to initialize
capacitythe initial capacity
elemsizethe 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
arraythe structure to initialize
capacitythe initial capacity
elemsizethe element size
allocatorthe 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
capacitythe initial capacity
elemsizethe 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
capacitythe initial capacity
elemsizethe element size
allocatorthe 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
arraya pointer the array where to prepend the data
dataa pointer to the data to insert (may be NULL)
countnumber 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
arraypointer to the array from which the element shall be removed
indexthe 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
arraypointer to the array from which the element shall be removed
indexthe 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
arraya pointer to the array
capacitythe 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
arraya pointer to the array
capacitythe 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
arraya pointer the array where to set the data
indexthe index of the element to set
dataa pointer to the data to insert (may be NULL)
countnumber 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
arraya 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
arraythe array to sort
cmpfncthe function that shall be used to compare the element data
dataadditional 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
allocthe allocator that shall be used to reallocate the array
arraya pointer to location of the array pointer
capacitya pointer to the capacity
elmsizethe size of each element
idxthe index of the element to set
dataa 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
allocthe allocator that shall be used to reallocate the array
arraya pointer to location of the array pointer
capacitya pointer to the capacity
idxthe index of the element to set
ptrthe pointer to store
Returns
zero on success or non-zero on error (errno will be set)