Dynamic array C implementation

Question

I'm a C beginner. For a tiny personal project, I was in need of an "auto-growing" array and here it is the implementation. I'd like to get some feedback.

At the end there is a test function called in main. Assertions are used only for debug-testing purposes. INITIAL_CAPACITY is set to 0 to "stress test" the API.

resize_darray and enlarge_darray are not the same function because later I'd like to add a "shrink" function.

I have two concerns:

• Would it have been better if I used size_t for n and capacity? I used int mainly to avoid the compiler warning while comparing the result of size_darray with an int in e.g. a for loop iterating over the items.
• Is there a "better way" to shift items? memmove maybe?

There isn't an header file because I'd like to store this implementation in a single file (as snippet) for future reference. That's also why in resize_darray I use a void pointer: if I want to adapt the implementation to another type of data, I don't have to touch that function.

/*
 * Dynamic array.
 *
 * from Wikipedia: "...is a random access, variable-size list data structure
 * that allows elements to be added or removed... Dynamic arrays
 * overcome a limit of static arrays, which have a fixed capacity that needs to
 * be specified at allocation."
 *
 * Indexing                   O(1)
 * Insert/delete at beginning O(n)
 * Insert/delete at end       O(1) amortized
 * Insert/delete at middle    O(n)
 * Average space              O(n)
 *
 * https://en.wikipedia.org/wiki/Dynamic_array
 */


#include <assert.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

#define INITIAL_CAPACITY 0

typedef struct
{
        int capacity;
        int n;
        int *items;
} darray;

/*
 * resize_darray:  changes array total capacity to new_capacity and returns
 *                 true. On failure returns false and leaves array untouched.
 */
static bool resize_darray(darray *array, int new_capacity);

/*
 * enlarge_darray:  increases the total capacity of array by a factor of about
 *                  1.5 and returns true. On failure returns false and leaves
 *                  array untouched.
 *
 *                  The formula used to calculate new capacity is:
 *                  new_capacity = old_capacity + old_capacity / 2 + 1
 */
static bool enlarge_darray(darray *array);

/*
 * create_darray:  creates and returns (a pointer to) a new darray of capacity
 *                 INITIAL_CAPACITY. On failure returns NULL.
 */
darray *create_darray(void);

/*
 * size_darray:  returns the number of items stored in array.
 */
int size_darray(const darray *array);

/*
 * add_item_at:  inserts item in array at position index shifting other items to
 *               the right by one position and returns true. On failure returns
 *               false.
 *               If index is not a valid index for inserting in array, the
 *               behavior is undefined.
 */
bool add_item_at(darray *array, int index, int item);

/*
 * prepend_item:  inserts item at position 0. It is equivalent to:
 *                add_item_at(array, 0, item);
 */
bool prepend_item(darray *array, int item);

/*
 * append_item:  inserts item at the end of array. It is equivalent to:
 *               add_item_at(array, size_darray(array), item);
 */
bool append_item(darray *array, int item);

/*
 * get_item_at:  returns (but does not remove) the item at position index.
 *               If index is not a valid index for array, the behavior is
 *               undefined.
 */
int get_item_at(const darray *array, int index);

/*
 * remove_item_at:  removes and returns the item at position index shifting
 *                  other items to the left by one position.
 *                  If index is not a valid index for array, the behavior is
 *                  undefined.
 */
int remove_item_at(darray *array, int index);

/* replace_item_at:  replaces the item at position index with item and returns
 *                   the item previously at index.
 *                   If index is not a valid index for array, the behavior is
 *                   undefined.
 */
int replace_item_at(darray *array, int index, int item);

/*
 * free_darray:  frees memory occupied by array.
 */
void free_darray(darray *array);


static bool resize_darray(darray *array, int new_capacity)
{
        void *new_ptr = realloc(array->items,
                                sizeof(*(array->items)) * new_capacity);
        if (new_ptr != NULL) {
                array->items = new_ptr;
                array->capacity = new_capacity;
                return true;
        }
        return false;
}

static bool enlarge_darray(darray *array)
{
        return resize_darray(array, array->capacity + array->capacity / 2 + 1);
}

darray *create_darray(void)
{
        darray *new_darray = malloc(sizeof(*new_darray));
        if (new_darray == NULL) {
                return NULL;
        }

        new_darray->capacity = 0;
        new_darray->n = 0;
        new_darray->items = NULL;
        if ( ! resize_darray(new_darray, INITIAL_CAPACITY)) {
                free_darray(new_darray);
                return NULL;
        }

        return new_darray;
}

int size_darray(const darray *array)
{
        return array->n;
}

bool add_item_at(darray *array, int index, int item)
{
        assert(index >= 0 && index <= size_darray(array));

        if (size_darray(array) == array->capacity && ! enlarge_darray(array)) {
                return false;
        }

        array->n++;

        for (int i = size_darray(array) - 1; i > index; i--) {
                array->items[i] = array->items[i - 1];
        }
        array->items[index] = item;
        return true;
}

bool prepend_item(darray *array, int item)
{
        return add_item_at(array, 0, item);
}

bool append_item(darray *array, int item)
{
        return add_item_at(array, size_darray(array), item);
}

int get_item_at(const darray *array, int index)
{
        assert(index >= 0 && index < size_darray(array));

        return array->items[index];
}

int remove_item_at(darray *array, int index)
{
        assert(index >= 0 && index < size_darray(array));

        int item = get_item_at(array, index);

        for (int i = index + 1; i < size_darray(array); i++) {
                array->items[i - 1] = array->items[i];
        }
        array->n--;

        return item;
}

int replace_item_at(darray *array, int index, int item)
{
        assert(index >= 0 && index < size_darray(array));

        int old_item = get_item_at(array, index);
        array->items[index] = item;
        return old_item;
}

void free_darray(darray *array)
{
        free(array->items);
        free(array);
}


static void test_darray(darray *array, int test_size)
{
        /* array must be empty for this test */
        assert(size_darray(array) == 0);

        for (int i = 0; i < test_size; i++) {
                append_item(array, i);
        }
        assert(size_darray(array) == test_size);
        for (int i = 0; i < test_size; i++) {
                assert(get_item_at(array, i) == i);
        }

        for (int i = 0; i < test_size; i++) {

                int rnd_i = rand() % test_size;

                add_item_at(array, rnd_i, i);
                assert(size_darray(array) == test_size + 1);
                assert(replace_item_at(array, rnd_i, -1) == i);
                assert(size_darray(array) == test_size + 1);
                assert(remove_item_at(array, rnd_i) == -1);
        }
        assert(size_darray(array) == test_size);

        for (int i = 0; i < test_size; i++) {
                assert(remove_item_at(array, 0) == i);
        }
        assert(size_darray(array) == 0);

        for (int i = 0; i < test_size; i++) {
                prepend_item(array, i);
        }
        assert(size_darray(array) == test_size);
        for (int i = test_size - 1; i >= 0; i--) {
                assert(remove_item_at(array, 0) == i);
        }
        assert(size_darray(array) == 0);
}

int main(void)
{
        srand(time(NULL));

        darray *arr = create_darray();

        test_darray(arr, 0);
        test_darray(arr, 1);
        test_darray(arr, 100);
        test_darray(arr, 1000);

        free_darray(arr);
}

Answer 1

Impressive first attempt.

---

1. Allocating size 0 may return NULL and that is not an out-of-memory (OOM) indication.

   void *new_ptr = realloc(array->items, sizeof(*(array->items)) * new_capacity);
   // if (new_ptr != NULL) {
   if (new_ptr != NULL || new_capacity == 0) { // OK
   

2. "Would it have been better if I used size_t" Yes. Consider size_t for storing the array size and indexing. int may be too narrow. Take care that size_t is some unsigned type. (Review for (int i = size_darray(array) - 1; i > index; i--) { Let size_darray() return size_t.

   typedef struct {
       // int capacity;
       // int n;
       size_t capacity, n;
       int *items;
   } darray;
   

3. "Is there a "better way" to shift items? memmove" memmove() is deigned to be very efficient. A good replacement for the for() loops that shift data. Example:

   // for (int i = index + 1; i < size_darray(array); i++) {
   //  array->items[i - 1] = array->items[i];
   // }
   
   memmove(&array->items[index],  &array->items[index + 1], 
       sizeof (array->items[index]) * (array->n - index - 1));
   

Minor

10. Good that initial coding attempt is to save type int. Saving a generic type has pitfalls that are best handled after mastering the basics. (OP is very close here.)

11. I'd declare static functions after non-static functions in preparation for moving the non-static functions into a "darray.h" file.

12. free(NULL) is OK and recommend free_darray() to follow that idiom. This is even more important should the code set functionality tolerate/detect darray == NULL in other functions.

    void free_darray(darray *array) {
      // free(array->items);
      if (array) free(array->items);
      free(array);
    }
    

13. I found the index of 8 spaces excessive. As with such style issues, best to follow your groups coding standard.

14. Style: () not needed

    // darray *new_darray = malloc(sizeof(*new_darray));
    darray *new_darray = malloc(sizeof *new_darray);
    

15. "... later I'd like to add a "shrink" function.". In that case, realloc() may shrink the array and surprisingly may return NULL even when shrinking to a non-zero size. In that corner case code could choose to not return an error, but continue with the existing allocation.

16. Pedantic code would detect overflow possibilities like in array->capacity + array->capacity / 2 + 1.

Answer 2

Some suggestions:

1. I suggest that the word "new" is understood to mean object creation and initialization. Rather than create_darray, consider new_darray().

   Going one step farther, you might make this a preprocessor macro that returns a typed pointer. (In a post-int version, where arbitrary data can be handled.)

   Something like:

   #define new_darray(elt_type, count)  (((elt_type)*)darray_alloc(sizeof (elt_type), (count)))
   

   With a use-case like:

   int * pi = new_darray(int, 20);
   

2. Next, if you can make it past all the hissing and snarling, I would suggest that you take advantage of C99's flexible array member feature, otherwise known as the trailing array hack.

   Specifically, declare a struct that contains your bookkeeping information at the "front" of the struct, and a trailing array of int (or whatever your stored type will be)[hereafter, "(OWYSTWB)"].

   Then, allocate the struct plus capacity * sizeof int (OWYSTWB), compute the address of the start of the trailing array/flexible array member, and return that value to the user, and expect it in all user-facing function calls.

   It will have the effect of presenting to the end user as a pointer-to-int (OWYSTWB), which means you can use it like a ... dynamic array:

   int * pi = new_darray(int, 20);
   
   pi[0] = 1;
   pi[1] = 1; 
   
   for (n = 2; n < 20; ++n) 
       pi[n] = pi[n-2] + pi[n-1];
   
   pi = enlarge_darray(pi);
   

   This returns the native a[i] array syntax to C, and lets you skip having to code any element_at functions.

3. Finally, I'd suggest changing your size function to a length function. To me, size suggests sizeof, which is memory footprint. As we all know, the "length" of an array is sizeof(array) / sizeof(array[0]).

   You have two numbers to track: used elements and capacity. In fact, you might want to convert to simply tracking capacity, and let the user deal with managing the used elements.

   Regardless, neither of those should be called size simply because of the likely confusion with sizeof.