Dynamic array C implementation

Question 1

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 inmain. Assertions are used only for debug-testing purposes.INITIAL_CAPACITY is set to0 to "stress test" the API.

resize_darray andenlarge_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 usedsize_t forn andcapacity? I usedint mainly to avoid the compiler warning while comparing the result ofsize_darray with anint 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 inresize_darray I use avoid 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 0typedef 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);}

Question 2

Soo basically this only works for integers? Couldn't you cast to void pointer and ask for the type size in bytes on creation to allow for arrays of any (one) type of data?

Question 3

I'd say you have to split your code into h-file and c-file - since currently is completely unclear what is the public API for your object and are internal structures and functions. PUBLIC API should be moved to h-file. Everything else left in the c-file

Question 4

@Zorgatone yes, this "snippet" works only for integers. Actually I never looked into "generics types" in C (I know only the "void trick" used inresize_darray). I understand that I have to ask for the type size on creation, but then? How do I perform the shift of items? (memmove?) How do I return a specific element? (pointer arithmetic?) Sorry for all these questions, I'm still a beginner, any suggestion will be appreciated =)

Question 5

@ArtemyVysotsky like I said, I like to store my "snippets" implementations in single files. You can assume that static functions are meant to be "private", all the rest is "public".

Question 6

Impressive first attempt.

Allocating size 0 may returnNULL 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

"Would it have been better if I used size_t" Yes. Considersize_t for storing the array size and indexing.int may be too narrow. Take care thatsize_t is someunsigned type. (Reviewfor (int i = size_darray(array) - 1; i > index; i--) { Letsize_darray() returnsize_t.
```
typedef struct {    // int capacity;    // int n;    size_t capacity, n;    int *items;} darray;
```

"Is there a "better way" to shift items? memmove"memmove() is deigned to be very efficient. A good replacement for thefor() 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

Good that initial coding attempt is to save typeint. Saving a generic type has pitfalls that are best handled after mastering the basics. (OP is very close here.)
I'd declarestatic functions after non-static functions in preparation for moving the non-static functions into a "darray.h" file.
free(NULL) is OK and recommendfree_darray() to follow that idiom. This is even more important should the code set functionality tolerate/detectdarray == NULL in other functions.
```
void free_darray(darray *array) {  // free(array->items);  if (array) free(array->items);  free(array);}
```
I found the index of 8 spaces excessive. As with suchstyle issues, best to follow your groups coding standard.

Style:() not needed

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

"... later I'd like to add a "shrink" function.". In that case,realloc() may shrink the array and surprisingly may returnNULL 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.
Pedantic code would detect overflow possibilities like inarray->capacity + array->capacity / 2 + 1.

Question 7

Some suggestions:

I suggest that the word "new" is understood to mean object creation and initialization. Rather thancreate_darray, considernew_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);
```
Next, if you can make it past all the hissing and snarling, I would suggest that you take advantage of C99'sflexible array member feature, otherwise known as thetrailing array hack.
Specifically, declare a struct that contains your bookkeeping information at the "front" of the struct, and a trailing array ofint (or whatever your stored type will be)[hereafter, "(OWYSTWB)"].
Then, allocate the struct pluscapacity * sizeof int (OWYSTWB), compute the address of thestart 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 nativea[i] array syntax to C, and lets you skip having to code anyelement_at functions.
Finally, I'd suggest changing yoursize function to alength function. To me,size suggestssizeof, which is memory footprint. As we all know, the "length" of an array issizeof(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 calledsize simply because of the likely confusion withsizeof.

Question 8

Thank you! I didn't know about "flexible array member", seems interesting, I'll definitely look into it!

chux 36.5k2 gold badges43 silver badges97 bronze badges · Accepted Answer · 2017-09-18 15:04:33Z

Impressive first attempt.

Allocating size 0 may returnNULL 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

"Would it have been better if I used size_t" Yes. Considersize_t for storing the array size and indexing.int may be too narrow. Take care thatsize_t is someunsigned type. (Reviewfor (int i = size_darray(array) - 1; i > index; i--) { Letsize_darray() returnsize_t.
```
typedef struct {    // int capacity;    // int n;    size_t capacity, n;    int *items;} darray;
```

"Is there a "better way" to shift items? memmove"memmove() is deigned to be very efficient. A good replacement for thefor() 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

Good that initial coding attempt is to save typeint. Saving a generic type has pitfalls that are best handled after mastering the basics. (OP is very close here.)
I'd declarestatic functions after non-static functions in preparation for moving the non-static functions into a "darray.h" file.
free(NULL) is OK and recommendfree_darray() to follow that idiom. This is even more important should the code set functionality tolerate/detectdarray == NULL in other functions.
```
void free_darray(darray *array) {  // free(array->items);  if (array) free(array->items);  free(array);}
```
I found the index of 8 spaces excessive. As with suchstyle issues, best to follow your groups coding standard.

Style:() not needed

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

"... later I'd like to add a "shrink" function.". In that case,realloc() may shrink the array and surprisingly may returnNULL 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.
Pedantic code would detect overflow possibilities like inarray->capacity + array->capacity / 2 + 1.

Movatterモバイル変換

Stack Exchange Network

Dynamic array C implementation

2 Answers2

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS