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

C - Generic ArrayList / Dynamic Array Implementations

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

Problem

As a small project to refresh my C and data-structure knowledge, I decided to write a generic ArrayList (as in Java). This is my most current version:

ArrayList.h:

```
#ifndef ARRAYLIST_H
#define ARRAYLIST_H

struct ArrayList;

// ArrayList_create: {{{
// Creates a new ArrayList in memory and returns a pointer to it.
//
// @param element_size The size of a single element to be stored in the
// ArrayList
// @require element_size != 0
//
// @return A pointer to the created ArrayList.
// NULL if something went wrong with the allocation }}}
struct ArrayList *ArrayList_create(size_t element_size);

// ArrayList_destroy: {{{
// Takes a pointer to an ArrayList and destroys it and its associated data.
// All data pointers previously acquired through ArrayList_get become invalid.
//
// @param list The ArrayList to destroy }}}
void ArrayList_destroy(struct ArrayList *list);

// ArrayList_getSize: {{{
// Get the current number of elements stored in @param list.
//
// @param list ArrayList to get the size from
// @require list != NULL
//
// @return The number of elements currently stored in @param list }}}
size_t ArrayList_getSize(const struct ArrayList *list);

// ArrayList_isEmpty: {{{
// Returns whether ArrayList @param list is empty.
//
// @param list ArrayList to check emptiness on
// @require list != NULL
//
// @return Non-zero when empty, zero otherwise }}}
int ArrayList_isEmpty(const struct ArrayList *list);

// ArrayList_trimToSize: {{{
// Trims the capacity of @param list to be the list's current size.
//
// @param list ArrayList to trim capacity from
// @require list != NULL
//
// @return Non-zero on successful trim, zero otherwise }}}
int ArrayList_trimToSize(struct ArrayList *list);

// ArrayList_append: {{{
// Appends @param element to @param list. The element gets copied.
//
// @param list ArrayList to append @para

Solution

Infinite loop bug

This code sequence demonstrates an infinite loop in your code:

void test(void)
{
    uint32_t elem = 5;
    struct ArrayList *arr = ArrayList_create(sizeof(elem));

    ArrayList_append(arr, &elem);
    ArrayList_trimToSize(arr);
    ArrayList_append(arr, &elem);
    ArrayList_destroy(arr);
}


The problem is with ArrayList_ensureCapacity() in this code:

while(list->capacity capacity + (list->capacity >> 1);
    // ...
  }


If list->capacity is 0 or 1 here, then the loop will never terminate because the capacity remains the same on each iteration. Although capacity starts at 10, it can be reduced to 0 or 1 after a call to ArrayList_trimToSize(), as with the example above.
Bug in remove

This line in ArrayList_remove() is wrong:

memmove(dest, source, len);


It should be:

memmove(dest, source, len * list->elem_size);


Otherwise, you are moving the wrong number of bytes. Your tests did not catch this bug because you used a 4 byte value to test but only used numbers such as 12 which occupied the first byte. So it just happened to work even though you moved 1 byte instead of 4 bytes. If you had used numbers such as 0x11111111, you would have caught the problem.
Concern about get function

I would suggest changing your get function to return a copy of the element rather than a pointer to it. Something like this:

void ArrayList_get(const struct ArrayList *list, size_t index, void *ret);


The danger in returning a pointer is that the pointer's lifetime could end unexpectedly. Any call to append, add, trim, or destroy could invalidate the pointer since each of those calls could reallocate the array. You've only documented that the destroy function will do so, but the other three could as well.

Code Snippets

void test(void)
{
    uint32_t elem = 5;
    struct ArrayList *arr = ArrayList_create(sizeof(elem));

    ArrayList_append(arr, &elem);
    ArrayList_trimToSize(arr);
    ArrayList_append(arr, &elem);
    ArrayList_destroy(arr);
}
while(list->capacity < capacity) {
    // Increase by factor 1.5
    const size_t new_capacity = list->capacity + (list->capacity >> 1);
    // ...
  }
memmove(dest, source, len);
memmove(dest, source, len * list->elem_size);
void ArrayList_get(const struct ArrayList *list, size_t index, void *ret);

Context

StackExchange Code Review Q#160434, answer score: 5

Revisions (0)

No revisions yet.