Array List C implementation

Question

I want to show you my implementation of the array list in C. Is there something I can improve or fix?

Header

#ifndef ARRAY_LIST_H
#define ARRAY_LIST_H

#include <stdlib.h>

static const int AL_INITIAL_CAPACITY = 16;

struct array_list {
    int *array;
    size_t capacity;
    size_t count;
};

struct array_list *al_new(void);
int al_destroy(struct array_list **list);

int al_ensure_capacity(struct array_list *list, size_t capacity);

int al_push_back(struct array_list *list, int data);
int al_pop_back(struct array_list *list, int *data);
int al_push_front(struct array_list *list, int data);
int al_pop_front(struct array_list *list, int *data);

int al_is_valid_index(struct array_list *list, int index);
int al_get(struct array_list *list, int index, int *data);
int al_set(struct array_list *list, int index, int data);

int al_insert(struct array_list *list, int index, int data);
int al_delete(struct array_list *list, int index);

int al_find(struct array_list *list, int data);
int al_find_last(struct array_list *list, int data);
int al_contains(struct array_list *list, int data);

int al_is_empty(struct array_list *list);
int al_clear(struct array_list *list);

int al_delete_first(struct array_list *list, int data);
int al_delete_last(struct array_list *list, int data);

int al_print(struct array_list *list);

#endif //ARRAY_LIST_H

Source

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "array_list.h"

struct array_list *al_new(void) {
    struct array_list *list = malloc(sizeof(*list));
    if (list == NULL) {
        return NULL;
    }
    list->array = malloc(sizeof(*(list->array)) * AL_INITIAL_CAPACITY);
    list->capacity = AL_INITIAL_CAPACITY;
    list->count = 0;
    for (int i = 0; i < list->capacity; ++i) {
        list->array[i] = 0;
    }
    return list;
}

int al_destroy(struct array_list **list) {
    if (list == NULL || *list == NULL) {
        return -1;
    }
    free((*list)->array);
    (*list)->capacity = 0;
    (*list)->count = 0;
    free(*list);
    *list = NULL;
    return 0;
}

int al_ensure_capacity(struct array_list *list, size_t capacity) {
    if (list == NULL) {
        return -1;
    }
    size_t old_capacity = list->capacity;
    if (old_capacity < capacity) {
        list->capacity = (capacity + capacity / 2);
        list->array = realloc(list->array, sizeof(*(list->array)) * list->capacity);
        if (list->array == NULL) {
            return -1;
        }
        for (size_t i = old_capacity; i < list->capacity; ++i) {
            list->array[i] = 0;
        }
    }
    return 0;
}

int al_push_back(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    al_ensure_capacity(list, list->count + 1);
    list->array[list->count] = data;
    ++(list->count);
    return 0;
}

int al_pop_back(struct array_list *list, int *data) {
    if (list == NULL) {
        return -1;
    }
    *data = list->array[list->count - 1];
    list->array[list->count - 1] = 0;
    --(list->count);
    return 0;
}

int al_push_front(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    al_ensure_capacity(list, list->count + 1);
    memmove(&(list->array[1]), list->array, list->count * sizeof(*(list->array)));
    list->array[0] = data;
    ++(list->count);
    return 0;
}

int al_pop_front(struct array_list *list, int *data) {
    if (list == NULL) {
        return -1;
    }
    if (data != NULL) {
        *data = list->array[0];
    }
    memmove(list->array, list->array + 1, list->count * sizeof(*(list->array)));
    list->array[list->count] = 0;
    --(list->count);
    return 0;
}

int al_is_valid_index(struct array_list *list, int index) {
    if (list == NULL) {
        return -1;
    }
    return index >= 0 && index < list->count ? 0 : -1;
}

int al_get(struct array_list *list, int index, int *data) {
    if (list == NULL || !al_is_valid_index(list, index)) {
        return -1;
    }
    *data = list->array[index];
    return 0;
}

int al_set(struct array_list *list, int index, int data) {
    if (list == NULL || !al_is_valid_index(list, index)) {
        return -1;
    }
    list->array[index] = data;
    return 0;
}

int al_insert(struct array_list *list, int index, int data) {
    if (list == NULL || al_is_valid_index(list, index) < 0) {
        return -1;
    }
    al_ensure_capacity(list, list->count + 1);
    memmove(&(list->array[index + 1]),
            &(list->array[index]),
            (list->count - index) * sizeof(*(list->array)));
    list->array[index] = data;
    ++(list->count);
    return 0;
}

int al_delete(struct array_list *list, int index) {
    if (list == NULL || al_is_valid_index(list, index) < 0) {
        return -1;
    }
    memmove(&(list->array[index]),
            &(list->array[index + 1]),
            sizeof(*(list->array)) * list->count);
    list->array[list->count] = 0;
    --(list->count);
    return 0;
}

int al_find(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    for (int i = 0; i < list->count; ++i) {
        if (list->array[i] == data) {
            return data;
        }
    }
    return -1;
}

int al_find_last(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    for (int i = (int)list->count - 1; i >= 0; --i) {
        if (list->array[i] == data) {
            return data;
        }
    }
    return -1;
}

int al_contains(struct array_list *list, int data) {
    return al_find(list, data) ? 0 : -1;
}

int al_delete_first(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    int index = al_find(list, data);
    if (index >= 0) {
        al_delete(list, index);
    }
    return 0;
}

int al_delete_last(struct array_list *list, int data) {
    if (list == NULL) {
        return -1;
    }
    int index = al_find_last(list, data);
    if (index >= 0) {
        al_delete(list, index);
    }
    return 0;
}

int al_is_empty(struct array_list *list) {
    if (list == NULL) {
        return -1;
    }
    return list->count == 0 ? 0 : -1;
}

int al_clear(struct array_list *list) {
    if (list == NULL) {
        return -1;
    }
    for (int i = 0; i < list->count; ++i) {
        list->array[i] = 0;
    }
    list->count = 0;
    return 0;
}

int al_print(struct array_list *list) {
    if (list == NULL) {
        return -1;
    }
    if (list->count == 0) {
        printf("list is empty\n");
        return 0;
    }
    for (int i = 0; i < list->count; ++i) {
        printf("array list node %d: %d\n", i, list->array[i]);
    }
    return 0;
}

Answer 1

A definitely better than average effort.

No documentation

.h file deserves overall documentation. Consider users should be able to understand what these functions do without access to the .c file.

Bug: al_contains()

al_contains() returns 0 when data is not found or if data != 0.

Did OP want al_contains() to return the index when found?

Hide it

struct array_list definition not needed in .h file. Only its declaration needed. Research Information hiding

Unclear return

al_find() returns -1 when data not found, yet -1 is a valid data. Consider a different approach.

Use const

For functions that do not modify the state of the list:
Example:

//int al_is_valid_index(struct array_list *list, int index);
int al_is_valid_index(const struct array_list *list, int index);

Include first

In array_list.c,code #include "array_list.h" first to test that it does not rely on any <.h> files that it does not include itself.

Why 10?

Zero is a better choice for AL_INITIAL_CAPACITY.

Often the list are used, there are many empty ones. Zero is a natural choice.

If concerned about a lot of initial re-allocations, simply jump use to 10 when first needed.

Name space

Code uses al_... and array_list.... Use one,

static??

static const int AL_INITIAL_CAPACITY = 16; serves no purpose in the .h file.

Order?

With so many functions, consider alphabetizing the order in both .c and .h.

Mixed indexing types

Code using int and size_t for the array indexing and sizing type. Suggest size_t throughout.

Pedantic growth

Insure capacity + capacity / 2 does not overflow.

More functions

Consider:

A right-size function to reduce the allocation to the needed size.

With al_find() and al_find_last(), perhaps a find_next(... index) to pickup after al_find()?

Consider an apply function, one that applies a passed in function to every element of the array. I'd such this is a better way to print too and delete al_print().

int al_apply(struct array_list *list, void *state, int (*f)(void *state, size_t index, int data));

Consider al_sort(int (*cmp)(const void *e1, const void *e2)).

Answer 2

This is a problem:

        list->array = realloc(list->array, sizeof(*(list->array)) * list->capacity);

If the allocation fails, then we have overwritten list->array with a null pointer, leaving no way to access the memory it was pointing to. That's a memory leak. Don't overwrite any values until we know our reallocation was successful:

    size_t new_capacity = capacity + capacity / 2;
    int *new_mem = realloc(list->array, sizeof *list->array * new_capacity);
    if (!new_mem) { return false; }  /* using <stdbool.h> */
    list-array = new_mem;
    list->capacity = new_capacity;

Answer 3

Give Your Structures More Informative Names

This is a dequeue, not a list. The Java class named ArrayList doesn’t have push_front or pop_front operations, and these should change the underlying implementation. It’s also not a generic container, but a dequeue of int values. A user might later want a list (or dequeue) of some other type.

When I last wrote an implementation of one of these here, I named the type q_int_t and prefixed the functions manipulating it with q_int_.

Array Offsets are Never, Ever int

Right now, you have

    for (int i = 0; i < list->capacity; ++i) {
        list->array[i] = 0;
    }

On most modern systems, int is a 32-bit signed value, and size_t is an unsigned value wider than that. So, your int index could—realistically—overflow. This is undefined behavior, which most compilers take as permission to break your code and insert serious bugs. A classic example is that 3U < -1.

Use size_t consistently for indices and offsets, or if you really, truly want signed values that can handle negative indices, ptrdiff_t.

Furthermore, if this code compiled without warning you that comparing an int to a size_t is a serious red flag, you need to turn on more compiler warnings. On GCC, Clang or ICX, I typically use a -std= option plus -Wall -Wextra -Wpedantic -Wconversion -Wdeprecated, where -Wconversion is what ought to enable the warning about this.

Consider a More Familiar Naming Scheme

If you take an existing, well-known implementation, such as the STL or the Java standard library, and give your interfaces similar names to that, it will be faster to learn.

You don’t currently do this: the name of the class is array_list, like Java ArrayList (although this is actually a dequeue rather than a list). But your API is a mix of names similar to Java.util.ArrayList<int>, and others similar to the STL’s std::dequeue<int>. You neither use Java’s .add and .ensureCapacity nor the STL’s .push_back and .reserve, but a mixture of both. I expect I’d sometimes get them mixed up.

Make the struct Keyword Optional

It’s standard in C (and automatic in most derivatives) to define a struct with

typedef struct array_list {
    int *array;
    size_t capacity;
    size_t count;
} array_list;

This, for example, lets fopen return a FILE* instead of a struct FILE*. If you feel that it would be too ambiguous whether an array_list is the name of a type, a variable, or a function that lists an array, the convention is to end type names with _t.

Don’t Force Heap Allocation

Currently, the only way to initialize one of these is to call al_new, which returns a pointer to a heap-allocated object (or possibly NULL—but let’s come back to that later). However, you might want to create one of these on the stack, inside another data structure, or in shared memory.

Since you always initialize the new object to the same constants, it would be better to have a constant initializer expression, such as, in C99:

#define AL_INITIALIZER ((struct array_list){NULL, 0, 0})

or in c89/C++

#define AL_INITIALIZER {NULL, 0, 0}

This lets you write code like this, regardless of how the storage is allocated:

struct array_list dequeue = AL_INITIALIZER;

You can keep around the al_new function as a wrapper for a heap-allocated list, but remember, C++ has a placement new operator that lets you initialize an object anywhere in memory.

If you ever want variants that clone, move, or fill a new list, a good interface might be to have them return a list object, which can be on the right-hand-side of an assignment statement, such as:

struct array_list copy_of_queue = al_clone(&original_queue);

Although, be careful: programmers coming from a higher-level language might expect that this will free any memory the object being overwritten held. In C, any such memory will leak unless freed manually.

Allow const Objects

Currently, the interface always requires that it be able to modify the object. The deleter even asks for a pointer to a pointer that it can modify to the modifiable object.

It’s useful (and safer) to be able to wipe the object to a valid empty state, but interfaces that could be implemented without modifying the object should take a const struct array_list* rather than an array_list*, and there should be a way to free the memory of a const struct array_list (even though this leaves it in an invalid state).

Fix Your Error Reporting

The big no-no here is having interfaces return int, with a magic value that could either be a valid result, or an error code, with absolutely no way to tell which it is. If you are assuming that no list will ever contain this magic number, you never check for that, nor warn that the seemingly-legit operation al_push_back( &some_al, -1 ); will cause logic errors.

If you genuinely want to pack both results into the same return value, one thing you could do is return a wider integral type, such as long long int for a container holding int values, static_assert( sizeof(long long int) > sizeof(int), "" ); and #define AL_NOT_FOUND LLONG_MIN. Then, AL_NOT_FOUND always means that the result was not found and can never be a valid result. You could even write a wrapper to check if a result is valid (that is, between INT_MIN and INT_MAX) and have more different error codes lower than INT_MIN than you would ever possibly need.

A somewhat more complex way would be to define an option type. The fact that the user must unpack the type to extract the value is in some ways a benefit, since the type system will catch a bug caused by propagating an error value.

Don’t Report Out-of-Memory in-Band

In most real-world, practical coding (and certainly for learning projects), running out of memory is not a recoverable error. You can’t even safely print an error message, because that might need dynamic memory. Not only that, but the way modern 64-bit OSes work, the system will thrash to a halt long, long before it reports that it is out of virtual memory to allocate. Or if you’ve put a limit on the memory the process can receive, you want it to halt if a memory leak reaches that point.

So, a memory allocation failing should be a fatal error, and you should write a handler that aborts the process with a human-readable error message if it happens, and preserves the call stack for debugging. Maybe you really, truly are writing an app that needs to recover gracefully from exhausting all available memory. In that case, you know what kind of data the recovery needs, and it’s probably not to pass the error code back up the stack.

Either way, the caller shouldn’t have to test the return value for an error, again, because the interfaces should only return normally if the memory operations all succeeded.

Check for Capacity Overflow

Currently, one memory bug you do not check for is the capacity overflowing a size_t value and wrapping around. This isn’t likely to happen on a 64-bit system, but might on one where size_t is smaller. Either compare to SIZE_MAX - old_capacity, or check that the new capacity is greater than the old.

You could try setting the capacity to the maximum possible, SIZE_MAX/sizeof(array[0]), instead, but needing more than SIZE_MAX bytes of memory is a logic error. Most programs should report it if it happens and abort.

Consider Zeroing Out Newly-Allocated Memory

This is very easy to do with the initial allocation: just call calloc instead of malloc. For memory that doesn’t come from the heap, there’s memset.

If there are no bugs in your program, the contents of memory past the current end of your list should never matter. If, however, there is a bug that does read them, and those values are different every time the program runs, that will be a heisenbug that is very difficult to reproduce. If, on the other hand, you always initialize the unused elements to the same value, the contents of that memory will be deterministic and the bug will appear more consistently.

There is a trade-off, in that zeroing out a large amount of memory returned by realloc costs time (and might clobber your L1 cache).

Use Efficient Dequeue Operations

The classic way to implement a dequeue with both back and front insertion is to keep a pair of indices, for the current front and back of the array. You pop_front by incrementing the front index, leaving empty space at the end of the array. When pushing to the front, if there is such empty space, you can use it instead of shifting the entire array. You can shift if you run out of room at the back, or when you reallocate, or if the amount of free space at the front is above a threshold (to save the library from getting locked into moving the array on every single insertion when you alternate between pop_front and push_back with the array exactly at capacity).

Be Consistent about What Your Return Values Mean

The search API is hopelessly broken. You currently have both an al_find and al_contains, but both only return two possible values, and in neither case do those two possible values tell the caller whether or not the result was actually found.

Currently, you implement the contains check as

int al_contains(struct array_list *list, int data) {
    return al_find(list, data) ? 0 : -1;
}

Where al_find is defined to return -1 on failure, or the value being searched for on success. However, in C, 0 is the falsey value and -1 is truthy. So, al_contains is falsey whenever you search for a value other than 0, whether the list contains it or not.

What you actually want is for al_find and its backwards counterpart to return either the index of the element it found, or a pointer to it. If not found, it should return a special value, either the invalid index SIZE_MAX or the invalid pointer NULL, and possibly given a name like AL_NOT_FOUND. AL_CONTAINS should return a bool from stdbool.h and be implemented with return find(list, data) != AL_NOT_FOUND;. Both should accept a const struct array_list* as their first argument, since neither needs to modify the list.

With that interface, you could iterate between two positions you searched for in the list.

Other Functions You Might Want to Implement

• Serialization more flexible than printing to stdout
• Clone a list
• Move a list
• Swap two lists
• Transform a list by calling a function on each element
• Reduce a list, especially by taking the sum
• Find the next occurrence of an element in the list after (or before) a given position
• Element-wise binary operations on two lists

Answer 4

A few more points:

In al_new you could use calloc to zero list->array and avoid the explicit loop to do so.

I think you provide only false safety by making al_destroy take a pointer to the list pointer. You have no control over how many copies of the pointer the caller is keeping, and nulling the one they pass in doesn't change any others.

Bug in al_push_back, al_push_front and al_insert: if al_ensure_capacity fails, you are writing to a NULL pointer. Need to check the return value.

al_pop_back should check that data is not NULL before writing to it.

al_is_valid_index returns the opposite of normal C truthiness. I see that it matches the "0 means success" pattern of other functions, but this seems error prone. Someone is going to write if (al_is_valid_index(my_list)) { /*do stuff with index */ } and get surprised.

Actually, you make the mistake yourself in al_get, al_set and others.

All your al_is... functions seem to have the truthiness wrong. If you are going to consistently use 0 for success, consider having functions return an error_code enum with named values for SUCCESS, INVALID_ARGUMENT, NO_MEMORY etc.

al_is_empty returns the same for not-empty and NULL list. I'd suggest adding different return values. If not, it makes more sense to me that a NULL list is empty.