8
\$\begingroup\$

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 ?

\$\endgroup\$
  • 1
    \$\begingroup\$ What you have implemented is more commonly referred to as a vector in C/C++, not as an ArrayList from the Java world. \$\endgroup\$ – syb0rg Oct 1 '14 at 20:26
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How can I properly check if I have a valid ArrayList instance ? What I have so far is a macro that checks for a specific value of a new field I added to struct _arraylist. Since the struct declaration isn't available in the header, the ArrayList interface user cannot access any field directly (i.e he must use one of the wrapper functions). And I specifically didn't give any clue about this field .. \$\endgroup\$ – Amr Ayman Oct 4 '14 at 20:30
  • \$\begingroup\$ @AmrAyman, depends on your definition of valid, but I would say the minimum validation would be checking that the ArrayList pointer is not null and that ArrayList::data is also not null. You can also check that each array in data is not null: assert( list->data[i] != NULL ); \$\endgroup\$ – glampert Oct 4 '14 at 20:56
6
\$\begingroup\$

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]);
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I respect your interest. However, this is C, not C++. If it was C++, I would just use vectors to do that .. \$\endgroup\$ – Amr Ayman Oct 1 '14 at 20:08
  • \$\begingroup\$ @AmrAyman, check it \$\endgroup\$ – outoftime Oct 2 '14 at 14:03
  • \$\begingroup\$ That's impressive! But I want to have an arraylist not a linked list. Though your linked list implementation here is more advanced than the normal struct implementation, glampert solved the problem. \$\endgroup\$ – Amr Ayman Oct 2 '14 at 16:01
  • \$\begingroup\$ About the performance gain. There isn't really that much: My implementation relies on the heap, normally because it relies on an array; Yours rely heavily on recursion, and that's natural because you're relying on nodes. Also, freeing the list would be a lot slow relatively, because you'd either use recursion (which is really low on performance), or a fairly complicated while loop .. \$\endgroup\$ – Amr Ayman Oct 2 '14 at 17:02
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Well, you might not notice it, but that's exactly what I wanted to test. That pointers are stored and retrieved correctly through the function wrappers .. \$\endgroup\$ – Amr Ayman Oct 4 '14 at 20:19
  • \$\begingroup\$ Storing things as void * isn't really as bad as it seems. Think about it, void * simply stores a memory address, which I don't care about the type of the value stored at. In short, the array is only supposed to store memory addresses, and that's practically the only way that C would deal with various types in a single array .. \$\endgroup\$ – Amr Ayman Oct 4 '14 at 20:23
  • \$\begingroup\$ About realloc, I agree with you but I just couldn't find a better way to create a dynamic array. Anyway, I followed glampert's advice of wrapping a special function for that, the shrink_to_fit function .. \$\endgroup\$ – Amr Ayman Oct 4 '14 at 20:25
  • \$\begingroup\$ I imagined you were trying to save variable sized scalar data by storing it in a void* (various people have submitted code to do that). If you really wanted to store pointers, then a better test would be to store a number of different pointers in a known order and to check that you get them back in the same order - instead of saving the same pointer 100 times. The problem with storing pointers is that the object pointed to must be persistent for the lifetime of the existence of its address in the array. Despite the void* you of course cannot mix types within one array. \$\endgroup\$ – William Morris Oct 4 '14 at 23:33
  • 1
    \$\begingroup\$ Just a different way of doing the same thing, where the array follows on immediately after the end of the structure. That method has its own problems, so forget I mentioned it. \$\endgroup\$ – William Morris Oct 5 '14 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.