Implementing an ArrayList

Question

I implemented ArrayList functionality in C as follows:

#include <stdlib.h>
#include <assert.h>
#include "ArrayList.h"

struct _arraylist {
    size_t size;
    void ** data;
};

struct _arraylist *arraylist_create() {
    /* Allocate Memory */
    struct _arraylist *list = malloc(sizeof(struct _arraylist));
    assert(list != NULL);
    list->size = 0;
    list->data = calloc(2, sizeof(void *));
    assert(list->data != NULL);
    list->data[0] = NULL;
    return list;
}

void arraylist_setdata(struct _arraylist *list, void ** data, int max, int clear_data) {
    /* Sets the internal array of the arraylist */
    clear_data ? arraylist_clear(list) : NULL;
    list->data = data;
    list->size = max;
}

void arraylist_add(struct _arraylist *list, void *elem) {
    /* Adds one element of generic pointer type to the internal array */
    void ** new_data = realloc(list->data, arraylist_getsizeof(list));
    assert(new_data != NULL);
    new_data[list->size] = elem;
    arraylist_setdata(list, new_data, list->size + 1, 0);
}

void *arraylist_get(struct _arraylist *list, int index) {
    /* Gets an member of the array at an index */
    return list->data[index];
}

size_t arraylist_getsizeof(struct _arraylist *list) {
    /* Returns the size of the internal array in memory */
    return sizeof(*list->data);
}
size_t arraylist_getsize(struct _arraylist *list) {
    /* Returns the number of elements in the arraylist */
    return list->size;
}

void arraylist_remove(struct _arraylist *list, int index, int freeit) {
    /* Removes one element at and index */
    if (index > list->size - 1)
        return;
    if (list->size == 1) {
        arraylist_clear(list);
        return;
    }
    if (freeit)
        free(arraylist_get(list, index));
    for ( int i = index; i < list->size; ++i ) {
        if (i == list->size - 1)
            list->data[i] = NULL;
        else
            list->data[i] = list->data[i + 1];
    }
    void ** new_data = realloc(list->data, arraylist_getsizeof(list));
    --list->size;
    assert(new_data != NULL);
    arraylist_setdata(list, new_data, list->size, 0);
}

void arraylist_clear(struct _arraylist *list) {
    /* Clears the internal array */
    list->size = 0;
    free(list->data);
    list->data = NULL;
}

void arraylist_deallocate(struct _arraylist *list) {
    /* De-allocates the arraylist from memory
    No usage of the arraylist is allowed after this function call */
    if (list->data != NULL)
        free(list->data);
    free(list);
}

int arraylist_getindex(struct _arraylist *list, void *elem) {
    /* Looks for elem in list and returns the index or -1 if not found */
    for(int i = 0; i < list->size; ++i)
        if (elem == arraylist_get(list, i))
            return i;
    return -1;
}

I'm testing it like this:

#include <stdio.h>
#include "ArrayList.h"

int main(int argc, char const *argv[])
{
    ArrayList *list = arraylist_create();
    int i;
    for(i = 0; i < 100; ++i)
        arraylist_add(list, &i);
    for(i = 0; i < 100; ++i)
        printf("i: %d\n", *(int *)arraylist_get(list, i));
    for(i = 0; i < 100; ++i)
        arraylist_remove(list, i, 0);
    arraylist_deallocate(list);
    return 0;
}

It works fine, though realloc sometimes crash the program. Can I improve this ?

Answer 1

First, a word on naming:

The name you've chosen for your type, _arraylist is a bad name for a library interface type. Names starting with _ are not pleasant to work with in user code. They are commonly used inside library internals. Better names would be ArrayList or array_list.

Actually, in your usage example, you have ArrayList. Does this mean that in the header, which is not included here, you have something like this?

typedef _arraylist ArrayList;

If you did define an opaque type in the header, like above, that would be a good practice. But then you should not use any reference to _arraylist in your code. Use always the typedef'd name to avoid confusion.

The function name prefix should also follow exactly the name of the type, so for ArrayList all functions should be prefixed the ArrayList_, e.g.:

ArrayList * ArrayList_create();

Also, I would suggest that you avoid tightlypacked names, like in arraylist_getsize(). Adding an underscore to separate words makes them a lot more readable. E.g.: ArrayList_get_size().

Problems with memory:

Lets look at arraylist_create():

struct _arraylist *arraylist_create() {
    struct _arraylist *list = malloc(sizeof(struct _arraylist));
    assert(list != NULL);
    list->size = 0;
    list->data = calloc(2, sizeof(void *));
    assert(list->data != NULL);
    list->data[0] = NULL;
    return list;
}

First thing unusual here is the assertions. Assertions are not the proper way to handle a memory allocation failure. Plus, they are commonly disabled on release builds, so on release, if you'd happen to run out of memory, the program would just crash silently. You should probably return a NULL in this case (maybe also log to stderr) and let the caller handle this error as he/she sees fit.

Second problem here is with calloc(). You are allocating 2 void pointers, however, size is set to zero. I don't really get the point of this. Since your structure is more like and array of arrays then a list, what you should do is allocate the array of pointers with some predefined default size, then allocate the individual arrays as needed. Growing the array of pointers on demand. How arraylist_create() should look like:

ArrayList * ArrayList_create() {
    ArrayList *list = malloc(sizeof *list);
    if (list == NULL) {
        return NULL;
    }

    list->size = 0;
    list->data = calloc(INITIAL_BASE_ARRAY_SIZE, sizeof(void *));
    if (list->data == NULL) {
        free(list); // Don't leek memory here!
        return NULL;
    }

    return list;
}

Another big memory issue is the constant re-allocations done by arraylist_add() and arraylist_remove().

Remove should not shrink the sequence. Keep that space around if the array grows again in the future. You can add an explicit way to let the user shrink the storage if necessary (a la std::vector::shrink_to_fit()).

Adding to the array can be made to run in amortised-constant time if you pre-allocate storage with a larger size then the requested. (Again inspired by the STL vector).

sizeof mistake:

This will not return what you expect:

size_t arraylist_getsizeof(struct _arraylist *list) {
    /* Returns the size of the internal array in memory */
    return sizeof(*list->data);
}

The sizeof operator always returns the size of the type it is applied to. It cannot infer the size of an array pointed by a pointer, because it is a compile-time operation. arraylist_getsizeof() will always return the same value, the size of a void pointer, which will be 4 or 8, depending on the architecture.

Use assertions to check for invariants:

You should assert that the *list parameter of every function is valid. This is a precondition of every function, they cannot work without a valid ArrayList instance, so you should assert that once the function enters.

Miscellaneous:

You don't need to check if the pointer is null before freeing it. In arraylist_deallocate() the if (list->data != NULL) check is uneeded.

arraylist_deallocate would be more symmetric with arraylist_create if named arraylist_destroy.

Answer 2

Lets talk about perfomance

What if you need to use your list very frequently?

Let's look closer at function arraylist_add; if I need a list with 1 million bytes, which is 1MB, it will reallocate your data struct member 1 million times.

It is lowest part of your list!

Suggestions

Allocate memory by chunks, e.g., C++ std::vector uses increasing size of appended chunks depending on current size of std::vector.

This will increase perfomance it few times in purpose of adding new elements.

Lets talk about code as is

Try to implement some elegant, but simple program flow.

Create value type (int) ArrayList, which will allocate memory by chuncks instead of reallocate full array, and add some list behaviour under the hood. I mean list of chunks, you still need to manage it.

Here is my solution with with example of using chuncks of data for each node instead of reallocating nodes. Different chunck size may be best for one of purposes: writing, reading long arrays; r\w short arrays; removing elements; etc.

#include <stdio.h>
#include <stdlib.h>

typedef struct ArrayList ArrayList;
typedef ArrayList* ArrayListPtr;

struct ArrayList {
    size_t capacity;
    size_t size;
    int *data;
    ArrayListPtr parent;
    ArrayListPtr child;
};

const size_t ARRAY_LIST_CHUNCK_SIZE = 64;

ArrayListPtr array_list_create_with_parent_and_chunck_size(ArrayListPtr parent,
                                                           size_t chunck_size) {
    ArrayListPtr result = (ArrayListPtr)calloc(sizeof(ArrayList), 1);
    result->parent = parent;
    result->capacity = chunck_size;
    result->data = (int*)malloc(sizeof(int) * chunck_size);
    return result;
}

ArrayListPtr array_list_create_with_parent(ArrayListPtr parent) {
    return array_list_create_with_parent_and_chunck_size(
        parent, ARRAY_LIST_CHUNCK_SIZE
    );
}

ArrayListPtr array_list_create() {
    return array_list_create_with_parent_and_chunck_size(
        NULL, ARRAY_LIST_CHUNCK_SIZE
    );
}

void array_list_push_back(ArrayListPtr list, int value) {
    if (list->size >= list->capacity) {
        if (!list->child) {
            list->child = array_list_create_with_parent(list);
        }
        array_list_push_back(list->child, value);
    } else {
        list->data[list->size++] = value;
    }
}

int* array_list_get_value_by_index(ArrayListPtr list, size_t index) {
    if (index >= list->capacity || index >= list->size) {
        if (list->child) {
            return array_list_get_value_by_index(list->child,
                                                 index - list->size);
        } else {
            return NULL;
        }
    }
    return list->data + index;
}

int main(int argc, char *argv[]) {
    ArrayListPtr list = array_list_create();
    for (int i = 0; i < 100*1000; ++i) {
        array_list_push_back(list, i);
    }
    size_t test[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,31,32,33,63,64,65,999,1000};
    for (int i = 0; i < sizeof(test) / sizeof(size_t); ++i) {
        int* result = array_list_get_value_by_index(list, test[i]);
        if (result) {
            printf("list[%ld] = %d\n", test[i], *result);
        } else {
            printf("Can't get value by index %ld\n", test[i]);
        }
    }
}

Answer 3

A problem not mentioned by others is that your test doesn't work. It appears to work but in reality it doesn't. When you add values to the list you are passing the address of the variable i:

arraylist_add(list, &i);

And arraylist_add just saves the value passed (as it should):

void arraylist_add(struct arraylist *list, void *elem) {
    ....
    new_data[list->size] = elem;

So once you have looped through i = 0..99 all you have in the list is the address of i 100 times. When you read the data back you again use loop variable i and modify its value from 0..99 and the value printed looks right. But you are really just seeing the value of the loop variable being modified by the loop.

If you don't believe me, print out any fixed array entry, e.g. 50, as in:

printf("i: %d\n", *(int *)arraylist_get(list, 50));

it will print 100 (or whatever the value of i currently is).

Instead you should be storing the real value:

arraylist_add(list, (void*) i);

and to print it out you need to cast the value to the type it was when it went in:

printf("i: %d\n", (int)arraylist_get(list, t));

There are many other problems with the code, as others have noted. The basic design of using your arraylist_setdata to do all modifications is wrong. Reallocating at each change is just bad - realloc is expensive. And the basic idea of a list storing things by pretending they are void* is confusing to me and seems a bad idea.