HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Dynamic array implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
arrayimplementationdynamic

Problem

I would like to use code below for general purpose dynamic array implementation in my future code. How does it look?

array.h:

```
#include

/* This file describes structures and functions
for general purpose dynamic array.
*/

struct array {
void data; / Points to where the data is */
int numElements; / Number of elements /
int sizeElem; / Size of a single elements /
int capacity; / Current total space in number of elements /
};

/ macros for accessing array internals /
#define array_index(ARRAY, INDEX) (void )((unsigned)((ARRAY)->data)+(INDEX((ARRAY)->sizeElem)))
#define array_len(ARRAY) (ARRAY)->numElements
#define array_cap(ARRAY) (ARRAY)->capacity

static inline void array_init(struct array *arr, int capacity, int sizeElem) {
arr->data = malloc(capacity * sizeElem);
arr->capacity = capacity;
arr->sizeElem = sizeElem;
arr->numElements = 0;
}

/ Add an element to array. Expand array if necessary. /
static inline void array_add(struct array arr, void data) {
if (arr->capacity numElements) {
int new_capacity = 2 * arr->capacity;
arr->data = realloc(arr->data, new_capacity * arr->sizeElem);
arr->capacity = new_capacity;
}
memcpy(array_index(arr,arr->numElements), data, arr->sizeElem);
arr->numElements++;
}

/ Macro for traversing array elements. /
#define array_for_each(TYPE, ELEM, ARRAY) \
for (TYPE ELEM=(ARRAY)->data; (ELEM - (TYPE )(ARRAY)->data) numElements; ELEM++)

/ Removes the element at given index and moves other elements if necessary. /
static inline void array_delete_index(struct array *arr, int index) {
int movables = arr->numElements - index - 1;
memcpy(array_index(arr, index),
(void *)((unsigned)array_index(arr, index) + arr->sizeElem),
movables * arr->sizeElem);
arr->numElements--;
}

/* If array capacity is too much compared to number of elements,
reduce array capacity
*/
static inline void arra

Solution

Some good practices:

Assert on NULL parameter

Whenever you have a function passing an array you should either do a runtime check to see if it's NULL or do an assert(array). To catch bugs where a NULL array is passed to the functions.

Check return values for alloc functions

You should always make sure you get a non-NULL result from any allocation, malloc, realloc and such to fail gracefully, or at least exit(1) with a nice out of memory message. Good for catching bugs where accidentally an uninitialized count value is passed to an allocating function.

Check for negative input

Since for instance your numElements is an int instead of size_t you should either change it, or at least check for negative values.

Deleting many values

I don't know how common a use case this would be, but since on each delete, you might move a large chunk of values. Adding a function that either takes a list of indices to delete and do it in one go, by simply refilling the array with those indices excluded. Otherwise iterating over and deleting values can be a huge operation depending on the size of the array.

Destroy function

I agree with this comment:

/* Probably useless macro */
#define array_free(ARRAY) free((ARRAY)->data)


This should be a function that both resets the numElements = 0, capacity = 0 and does the free(array->data) as well as array->data = NULL.

This ensures that any reuse of the array will still result in a reallocation and hence not writing to freed memory. However please note that array_add in this case must check that capacity > 0 and at least set it to 1, otherwise the realloc will be 0.

Code Snippets

/* Probably useless macro */
#define array_free(ARRAY) free((ARRAY)->data)

Context

StackExchange Code Review Q#82158, answer score: 2

Revisions (0)

No revisions yet.