Array-List-int.h

#ifndef ARRAY_LIST_INT
#define ARRAY_LIST_INT

#include <stddef.h>
#include <stdbool.h>

////////////////////////////////////////////////////////////////////////////////

// AL_int x; creates an object handler called 'x' for an array list.
// The creation of an object handler for an array list must be followed by
// AL_int_create_empty() or AL_int_create_empty_with_initial_capacity() before
// the array list can be used.
typedef struct
{
    int* arr;
    size_t size;
    size_t capacity;
}
AL_int;

////////////////////////////////////////////////////////////////////////////////

extern const size_t AL_INT_MAX_CAPACITY;

// Allocates memory for the array list (which is handled by the object handler
// pointed to by 'ptr'), and sets the size and the capacity of the array list to
// 0 and 1, respectively.
// May cause the program to terminate due to 'out of memory'.
void AL_int_create_empty(AL_int* ptr);

// Allocates memory for the array list (which is handled by the object handler
// pointed to by 'ptr'), and sets the size and the capacity of the array list to
// 0 and 'initial_capacity', respectively.
// May cause the program to terminate due to 'out of memory'.
// 'initial_capacity' must be less than or equal to AL_INT_MAX_CAPACITY.
void AL_int_create_empty_with_initial_capacity(AL_int* ptr,
                                               size_t initial_capacity);

// Frees the memory taken up by the array list (which is handled by the object
// handler pointed to by 'ptr').
void AL_int_destroy(const AL_int* ptr);

////////////////////////////////////////////////////////////////////////////////

// Adds 'n' to the end of the array list (which is handled by the object handler
// pointed to by 'ptr').
// May cause the program to terminate due to 'capacity overflow' or 'out of
// memory'.
void AL_int_add(AL_int* ptr, int n);

// Adds 'n' at the index 'i' to the array list (which is handled by the object
// handler pointed to by 'ptr'), shifting elements as required.
// May cause the program to terminate due to 'index out of bounds', 'capacity
// overflow' or 'out of memory'.
void AL_int_add_at_index(AL_int* ptr, ptrdiff_t i, int n);

// Clears the array list (which is handled by the object handler pointed to by
// 'ptr'), and sets the size and the capacity of the array list to 0 and 1,
// respectively.
// May cause the program to terminate due to 'out of memory'.
void AL_int_clear(AL_int* ptr);

// Returns true if 'n' is present in the array list (which is handled by the
// object handler pointed to by 'ptr'), and returns false otherwise.
bool AL_int_contains(const AL_int* ptr, int n);

// Returns the element at the index 'i' in the array list (which is handled by
// the object handler pointed to by 'ptr').
// May cause the program to terminate due to 'index out of bounds'.
int AL_int_get(const AL_int* ptr, ptrdiff_t i);

// Returns the index of the first occurrence of 'n' at the range of indices
// ['i', 'j') in the array list (which is handled by the object handler pointed
// to by 'ptr'), and returns -1 if 'n' is not present at the range of indices in
// the array list.
ptrdiff_t AL_int_index_of(const AL_int* ptr, ptrdiff_t i, ptrdiff_t j, int n);

// Returns true if the array list (which is handled by the object handler
// pointed to by 'ptr') is empty (i.e. if the size of the array list is 0), and
// returns false otherwise.
bool AL_int_is_empty(const AL_int* ptr);

// Returns the index of the last occurrence of 'n' at the range of indices
// ['i', 'j') in the array list (which is handled by the object handler pointed
// to by 'ptr'), and returns -1 if 'n' is not present at the range of indices in
// the array list.
ptrdiff_t AL_int_last_index_of(const AL_int* ptr, ptrdiff_t i, ptrdiff_t j,
                               int n);

// Removes the element at the index 'i' from the array list (which is handled by
// the object handler pointed to by 'ptr'), shifting elements as required.
// May cause the program to terminate due to 'index out of bounds' or 'out of
// memory'.
void AL_int_remove(AL_int* ptr, ptrdiff_t i);

// Removes the elements at the range of indices ['i', 'j') from the array list
// (which is handled by the object handler pointed to by 'ptr'), shifting
// elements as required.
// May cause the program to terminate due to 'index out of bounds' or 'out of
// memory'.
void AL_int_remove_range(AL_int* ptr, ptrdiff_t i, ptrdiff_t j);

// Assigns 'n' to the element at the index 'i' in the array list (which is
// handled by the object handler pointed to by 'ptr').
// May cause the program to terminate due to 'index out of bounds'.
void AL_int_set(AL_int* ptr, ptrdiff_t i, int n);

// Returns the size of the array list (which is handled by the object handler
// pointed to by 'ptr').
size_t AL_int_size(const AL_int* ptr);

// Copies the elements of the array list (which is handled by the object handler
// pointed to by 'ptr') to a malloc'ed array, and returns a pointer to its first
// element.
// May cause the program to terminate due to 'out of memory'.
int* AL_int_to_array(const AL_int* ptr);

////////////////////////////////////////////////////////////////////////////////

#endif

Array-List-int.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>
#include "Array-List-int.h"

////////////////////////////////////////////////////////////////////////////////

#define AL_INT_INDEX_OUT_OF_BOUNDS "Array List (int) - Index out of Bounds"
#define AL_INT_CAPACITY_OVERFLOW "Array List (int) Capacity Overflow"
#define AL_INT_OUT_OF_MEMORY "Array List (int) - Out of Memory"

// Terminates the program after sending a diagnostic message to stderr.
// 'cause' points to the first character of a null-terminated string describing
// the cause of termination.
// 'caller' points to the first character of a null-terminated string
// representing the name of the calling function.
static void AL_int_exit(const char* cause, const char* caller)
{
    fprintf(stderr, "%s\n\tat %s()\n", cause, caller);
    fprintf(stderr, "\nExiting due to failure\n");

    exit(EXIT_FAILURE);
}

////////////////////////////////////////////////////////////////////////////////

const size_t AL_INT_MAX_CAPACITY = ((unsigned long long) PTRDIFF_MAX <
    (unsigned long long) SIZE_MAX / (unsigned long long) sizeof (int)) ?
        (size_t) PTRDIFF_MAX : SIZE_MAX / sizeof (int);

// Increases the capacity of the array list (which is handled by the object
// handler pointed to by 'ptr').
// May cause the program to terminate due to 'capacity overflow' or 'out of
// memory'.
static void AL_int_expand(AL_int* ptr)
{
    if (ptr->capacity > AL_INT_MAX_CAPACITY / (size_t) 2)
    {
        if (ptr->capacity < AL_INT_MAX_CAPACITY)
            ptr->capacity = AL_INT_MAX_CAPACITY;
        else
            AL_int_exit(AL_INT_CAPACITY_OVERFLOW, __func__);
    }

    else
    {
        ptr->capacity = ptr->capacity * (size_t) 2;
    }

    ptr->arr = (int*) realloc((void*) ptr->arr, ptr->capacity * sizeof (int));
    if ((void*) ptr->arr == NULL)
        AL_int_exit(AL_INT_OUT_OF_MEMORY, __func__);
}

// Reduces the capacity of the array list (which is handled by the object
// handler pointed to by 'ptr').
// May cause the program to terminate due to 'out of memory'.
static void AL_int_shrink(AL_int* ptr)
{
    if (ptr->size == (size_t) 0)
        ptr->capacity = (size_t) 1;
    else
        ptr->capacity = ptr->size;

    ptr->arr = (int*) realloc((void*) ptr->arr, ptr->capacity * sizeof (int));
    if ((void*) ptr->arr == NULL)
        AL_int_exit(AL_INT_OUT_OF_MEMORY, __func__);
}

////////////////////////////////////////////////////////////////////////////////

// Shifts (by copying) the elements of the array list (which is handled by the
// object handler pointed to by 'ptr') at the range of indices [l, ptr->size)
// left by 'offset' positions.
// It must be ensured that 'l' and 'offset' are valid.
static void AL_int_shift_left(const AL_int* ptr, ptrdiff_t l, ptrdiff_t offset)
{
    // for (ptrdiff_t k = l; k < (ptrdiff_t) ptr->size; ++k)
    //     (ptr->arr)[k - offset] = (ptr->arr)[k];

    memmove((void*) (ptr->arr + l - offset), (void*) (ptr->arr + l),
            (ptr->size - (size_t) l) * sizeof (int));
}

// Shifts (by copying) the elements of the array list (which is handled by the
// object handler pointed to by 'ptr') at the range of indices [l, ptr->size)
// right by 'offset' positions.
// It must be ensured that 'l' and 'offset' are valid, and that the capacity of
// the array list is large enough.
static void AL_int_shift_right(const AL_int* ptr, ptrdiff_t l, ptrdiff_t offset)
{
    // for (ptrdiff_t k = (ptrdiff_t) ptr->size - (ptrdiff_t) 1; k >= l; --k)
    //     (ptr->arr)[k + offset] = (ptr->arr)[k];

    memmove((void*) (ptr->arr + l + offset), (void*) (ptr->arr + l),
            (ptr->size - (size_t) l) * sizeof (int));
}

////////////////////////////////////////////////////////////////////////////////

void AL_int_create_empty(AL_int* ptr)
{
    ptr->arr = (int*) malloc(sizeof (int));
    if ((void*) ptr->arr == NULL)
        AL_int_exit(AL_INT_OUT_OF_MEMORY, __func__);

    ptr->size = (size_t) 0;
    ptr->capacity = (size_t) 1;
}

void AL_int_create_empty_with_initial_capacity(AL_int* ptr,
                                               size_t initial_capacity)
{
    ptr->arr = (int*) malloc(initial_capacity * sizeof (int));
    if ((void*) ptr->arr == NULL)
        AL_int_exit(AL_INT_OUT_OF_MEMORY, __func__);

    ptr->size = (size_t) 0;
    ptr->capacity = initial_capacity;
}

void AL_int_destroy(const AL_int* ptr)
{
    free((void*) ptr->arr);
}

////////////////////////////////////////////////////////////////////////////////

void AL_int_add(AL_int* ptr, int n)
{
    if (ptr->size == ptr->capacity)
        AL_int_expand(ptr);

    (ptr->arr)[(ptrdiff_t) ptr->size] = n;
    ++(ptr->size);
}

void AL_int_add_at_index(AL_int* ptr, ptrdiff_t i, int n)
{
    if ((i < (ptrdiff_t) 0) || (i > (ptrdiff_t) ptr->size))
        AL_int_exit(AL_INT_INDEX_OUT_OF_BOUNDS, __func__);

    if (ptr->size == ptr->capacity)
        AL_int_expand(ptr);

    AL_int_shift_right(ptr, i, (ptrdiff_t) 1);
    (ptr->arr)[i] = n;
    ++(ptr->size);
}

void AL_int_clear(AL_int* ptr)
{
    ptr->size = (size_t) 0;
    AL_int_shrink(ptr);
}

bool AL_int_contains(const AL_int* ptr, int n)
{
    for (ptrdiff_t i = (ptrdiff_t) 0; i < (ptrdiff_t) ptr->size; ++i)
        if ((ptr->arr)[i] == n)
            return true;

    return false;
}

int AL_int_get(const AL_int* ptr, ptrdiff_t i)
{
    if ((i < (ptrdiff_t) 0) || (i >= (ptrdiff_t) ptr->size))
        AL_int_exit(AL_INT_INDEX_OUT_OF_BOUNDS, __func__);

    return (ptr->arr)[i];
}

ptrdiff_t AL_int_index_of(const AL_int* ptr, ptrdiff_t i, ptrdiff_t j, int n)
{
    for (ptrdiff_t k = i; k < j; ++k)
        if ((ptr->arr)[k] == n)
            return k;

    return (ptrdiff_t) -1;
}

bool AL_int_is_empty(const AL_int* ptr)
{
    return ptr->size == (size_t) 0;
}

ptrdiff_t AL_int_last_index_of(const AL_int* ptr, ptrdiff_t i, ptrdiff_t j,
                               int n)
{
    for (ptrdiff_t k = j - (ptrdiff_t) 1; k >= i; --k)
        if ((ptr->arr)[k] == n)
            return k;

    return (ptrdiff_t) -1;
}

void AL_int_remove(AL_int* ptr, ptrdiff_t i)
{
    AL_int_remove_range(ptr, i, i + (ptrdiff_t) 1);
}

void AL_int_remove_range(AL_int* ptr, ptrdiff_t i, ptrdiff_t j)
{
    if ((i >= j) || (i < (ptrdiff_t) 0) || (j > (ptrdiff_t) ptr->size))
        AL_int_exit(AL_INT_INDEX_OUT_OF_BOUNDS, __func__);

    ptrdiff_t offset = j - i;

    AL_int_shift_left(ptr, j, offset);
    ptr->size -= (size_t) offset;

    if (ptr->size < ptr->capacity / 2)
        AL_int_shrink(ptr);
}

void AL_int_set(AL_int* ptr, ptrdiff_t i, int n)
{
    if ((i < (ptrdiff_t) 0) || (i >= (ptrdiff_t) ptr->size))
        AL_int_exit(AL_INT_INDEX_OUT_OF_BOUNDS, __func__);

    (ptr->arr)[i] = n;
}

size_t AL_int_size(const AL_int* ptr)
{
    return ptr->size;
}

int* AL_int_to_array(const AL_int* ptr)
{
    int* array = (int*) malloc(ptr->size * sizeof (int));
    if ((void*) ptr->arr == NULL)
        AL_int_exit(AL_INT_OUT_OF_MEMORY, __func__);

    for (ptrdiff_t i = (ptrdiff_t) 0; i < (ptrdiff_t) ptr->size; ++i)
        array[i] = (ptr->arr)[i];

    return array;
}

Test.c

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include "Array-List-int.h"

int main(void)
{
    AL_int a1;
    AL_int_create_empty(&a1);

    printf("---------------------------------------------------------------\n");

    printf(AL_int_is_empty(&a1) ? "true\n" : "false\n");

    printf("---------------------------------------------------------------\n");

    AL_int_add(&a1, 10);
    AL_int_add(&a1, 20);
    AL_int_add(&a1, 30);

    printf("%d\n", AL_int_get(&a1, 1));

    printf("---------------------------------------------------------------\n");

    printf(AL_int_is_empty(&a1) ? "true\n" : "false\n");

    printf("%zu\n", AL_int_size(&a1));

    printf("---------------------------------------------------------------\n");

    for (size_t i = 0; i < AL_int_size(&a1); ++i)
    {
        printf("%d ", AL_int_get(&a1, i));
    }

    printf("\n");

    printf("---------------------------------------------------------------\n");

    AL_int_set(&a1, (ptrdiff_t) 2, 40);

    for (size_t i = 0; i < AL_int_size(&a1); ++i)
    {
        printf("%d ", AL_int_get(&a1, i));
    }

    printf("\n");

    printf("---------------------------------------------------------------\n");

    AL_int_add_at_index(&a1, (ptrdiff_t) 1, 50);

    for (size_t i = 0; i < AL_int_size(&a1); ++i)
    {
        printf("%d ", AL_int_get(&a1, i));
    }

    printf("\n");

    printf("---------------------------------------------------------------\n");

    AL_int_clear(&a1);

    printf("%zu\n", AL_int_size(&a1));

    printf("---------------------------------------------------------------\n");

    AL_int_add(&a1, 10);
    AL_int_add(&a1, 20);
    AL_int_add(&a1, 30);
    AL_int_add(&a1, 40);
    AL_int_add(&a1, 10);
    AL_int_add(&a1, 20);

    for (size_t i = 0; i < AL_int_size(&a1); ++i)
    {
        printf("%d ", AL_int_get(&a1, i));
    }

    printf("\n");

    printf(AL_int_contains(&a1, 30) ? "true\n" : "false\n");

    printf(AL_int_contains(&a1, 50) ? "true\n" : "false\n");

    printf("---------------------------------------------------------------\n");

    for (size_t i = 0; i < AL_int_size(&a1); ++i)
    {
        printf("%d ", AL_int_get(&a1, i));
    }

    printf("\n");

    printf("%td\n", AL_int_index_of(&a1, (ptrdiff_t) 0,
                                    (ptrdiff_t) AL_int_size(&a1), 10));

    printf("%td\n", AL_int_index_of(&a1, (ptrdiff_t) 0,
                                    (ptrdiff_t) AL_int_size(&a1), 30));

    printf("%td\n", AL_int_index_of(&a1, (ptrdiff_t) 0,
                                    (ptrdiff_t) AL_int_size(&a1), 50));

    printf("---------------------------------------------------------------\n");

    for (size_t i = 0; i < AL_int_size(&a1); ++i)
    {
        printf("%d ", AL_int_get(&a1, i));
    }

    printf("\n");

    printf("%td\n", AL_int_last_index_of(&a1, (ptrdiff_t) 0,
                                         (ptrdiff_t) AL_int_size(&a1), 10));

    printf("%td\n", AL_int_last_index_of(&a1, (ptrdiff_t) 0,
                                         (ptrdiff_t) AL_int_size(&a1), 30));

    printf("%td\n", AL_int_last_index_of(&a1, (ptrdiff_t) 0,
                                         (ptrdiff_t) AL_int_size(&a1), 50));

    printf("---------------------------------------------------------------\n");

    AL_int_remove(&a1, (ptrdiff_t) 3);

    for (size_t i = 0; i < AL_int_size(&a1); ++i)
    {
        printf("%d ", AL_int_get(&a1, i));
    }

    printf("\n");

    printf("---------------------------------------------------------------\n");

    AL_int_remove_range(&a1, (ptrdiff_t) 1, (ptrdiff_t) 3);

    int* array = AL_int_to_array(&a1);

    for (size_t i = 0; i < AL_int_size(&a1); ++i)
    {
        printf("%d ", array[i]);
    }

    printf("\n");

    printf("---------------------------------------------------------------\n");

    free((void*) array);

    AL_int_destroy(&a1);

    return 0;
}

• Later, I will add more functions such as AL_int_sort(), AL_int_index_of_binary_search(), etc.

• I thought about freeing all allocated memory before exiting in AL_int_exit(), but then I couldn't figure out a way to free the memory pertaining to other array lists, or even other data structures, used within the same program. So, in the end, I decided to simply let exit() handle the freeing up of memory.

• I made the initial capacity and the capacity after clearing equal to 1 in order to avoid dealing with malloc(0) and realloc(foo, 0).

• I thought about not casting the return values of malloc() and realloc(), but I always use a compiler which is good enough to warn me about a missing #include <stdlib.h>. Also, with explicit casts, my program also works as a C++ program.

• Instead of making a generic array list, I've made a basic array list of int's, as I'm still learning and will later delve into generic programming in C.

• I decided to keep the object handlers on the stack (similar to the object handlers of std::vector's from C++). So, I was forced to define AL_int in the header file, instead of only declaring it.

Finally, I want to ask a question.

If we have a pointer to const struct, then we cannot modify the members of the struct using that pointer. But, if a member happens to be a pointer, then we can modify the pointed-to item.

For eg., AL_int_set() will work even if ptr is declared to be a pointer-to-const.

How are such situations dealt with?