patterncMinor
C - Generic ArrayList / Dynamic Array Implementations
Viewed 0 times
genericimplementationsarraydynamicarraylist
Problem
As a small project to refresh my C and data-structure knowledge, I decided to write a generic
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
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:
The problem is with
If
Bug in remove
This line in
It should be:
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
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:
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.
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.