3
\$\begingroup\$

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

array.h:

#include <stdlib.h>

/* 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 <= arr->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) < (ARRAY)->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 array_free_capacity(struct array *arr) {
    if (arr->capacity > 2*arr->numElements) {
        int new_capacity = arr->capacity / 2;
        arr->data = realloc(arr->data, new_capacity * arr->sizeElem);
        arr->capacity = new_capacity;
    }
}

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

/* Search for an element and return an index if found. Otherwise, return -1
   Comparison function should return 0 if two items should be considered equal.
*/
static inline int array_search(struct array *arr, void *target, int (*cmp)(void *first, void *second)) {
    for(int i=0; i<arr->numElements; i++) {
        if(cmp(array_index(arr, i), target) == 0) return i;
    }
    return -1;
}

/* Returns a pointer to the element at given index, if it doesn't
    exist, return NULL
*/
static inline void *array_get_index(struct array *arr, int index) {
    if (index > (arr->numElements - 1)) return NULL;
    return array_index(arr, index);
}

How the code is used:

First you initialize the array with a data type and the initial array capacity, measured in the number of elements that the array can hold.

After that, the functions in array.h can be used to add, remove, traverse the array, and more.

Example:

struct task {
    char *task_name;
    int task_id;
};

struct array my_tasks;
/* Define an dynamic array of struct tasks */
array_init(&my_tasks, 2, sizeof(struct task));
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.