Tag: list

I’m experimenting with C after working in high level languages for the last 15+ years, and trying to feel comfortable with C code bases again.

One thing I needed for the code I’m writing was a resizable list collection that can grow as items are added to it. It seems to work under the basic case, so I’m wondering if I missed something in it.

list.h

#ifndef CRENDERER_LIST_H
#define CRENDERER_LIST_H

#include <stddef.h>

/**
 * Creates a new growable list
 * @param initialCapacity how many items the list should initially have memory for
 * @param itemSize The size of each item
 * @return returns a pointer to the newly created list, or `NULL` if list creation failed
 */
void* kcr_list_create(int initialCapacity, size_t itemSize);

/**
 * Appends a new item to the end of an existing list.  If the list does not have the capacity for the item than
 * the list will be resized to account for it.
 * @param list Existing list to append the item onto
 * @param item A pointer to the item to add to the list
 * @param itemSize The memory size of the item to add.  This must be the same as specified during creation
 * @return returns a pointer to the latest location of the list.  Consumers must always reference the list from
 * the value returned and not re-use the previous pointer, as when the list grows it may end up in a new spot
 * to accomodate the size it needed to grow into.
 *
 * Will return `NULL` if appending failed
 */
void* kcr_list_append(void* list, void* item, size_t itemSize);

/**
 * Removes the item from the list at the specified index
 * @param list list to remove the item from
 * @param index Index of the item to remove
 * @param itemSize The memory size of the items in the list
 */
void kcr_list_remove(void* list, int index, size_t itemSize);

/**
 * Gets the number of items that exist in the list
 * @param list The existing list
 * @return Number of items in the list
 */
int kcr_list_length(const void* list);

/**
 * Frees the list
 */
void kcr_list_free(void* list);

#endif //CRENDERER_LIST_H

list.c

#include <malloc.h>
#include <mem.h>
#include <math.h>
#include "list.h"

#define MIN_GROWTH 10
#define RAW_LIST(list) ((int*) list) - 2
#define LIST_LEN(list) (RAW_LIST(list))(0)
#define LIST_CAP(list) (RAW_LIST(list))(1)
#define FIRST_ELEMENT(list) ((int*) list) + 2

void* kcr_list_create(int initialCapacity, size_t itemSize) {
    int* memory = malloc(sizeof(int) * 2 + itemSize * initialCapacity);
    if (memory == NULL) {
        return NULL;
    }

    memory = FIRST_ELEMENT(memory);
    LIST_LEN(memory) = 0;
    LIST_CAP(memory) = initialCapacity;
    return memory;
}

void *kcr_list_append(void *list, void *item, size_t itemSize) {
    if (list == NULL) {
        return NULL;
    }

    int capacity = LIST_CAP(list);
    int count = LIST_LEN(list);
    if (count + 1 > capacity) {
        // Grow it by either 1.25x or by MIN_GROWTH items, whichever is larger.  Item Minimum allows to keep a bunch of
        // small growths reallocating.
        int newCapacity = capacity + (int) roundf((float) capacity * 1.25f);
        if (newCapacity < MIN_GROWTH) {
            newCapacity = capacity + MIN_GROWTH;
        }

        int* newList = realloc(RAW_LIST(list), sizeof(int) * 2 + itemSize * newCapacity);
        if (newList == NULL) {
            return NULL;
        }

        list = FIRST_ELEMENT(newList);
        LIST_CAP(list) = newCapacity;
    }

    void* slot = list + itemSize * count;
    memcpy(slot, item, itemSize);
    LIST_LEN(list) = count + 1;

    return list;
}

void kcr_list_remove(void *list, int index, size_t itemSize) {
    if (list == NULL || index < 0) {
        return;
    }

    int count = LIST_LEN(list);
    if (index >= count) {
        return;
    }

    if (index < count - 1) {
        // Not the last item, so shift everything after it over
        void* slotToRemove = list + itemSize * index;
        int itemsToShift = count - index - 1;
        memmove(slotToRemove, slotToRemove + itemSize, itemsToShift * itemSize);
    }

    LIST_LEN(list) = count - 1;
}

int kcr_list_length(const void *list) {
    if (list == NULL) {
        return 0;
    }

    return LIST_LEN(list);
}

void kcr_list_free(void *list) {
    if (list != NULL) {
        free(RAW_LIST(list));
    }
}

Test Usage

int main() {
    struct KCR_Vec3* vectors = kcr_list_create(5, sizeof(struct KCR_Vec3));
    for (int x = 0; x < 30; x++) {
        struct KCR_Vec3 vector = {(float) x, (float) x + 1, (float) x + 2};
        struct KCR_Vec3* array = kcr_list_append(vectors, &vector, sizeof(struct KCR_Vec3));
        if (array == NULL) {
            fprintf(stderr, "Failed to add item #%in", x);
        }

        vectors = array;
    }

    kcr_list_remove(vectors, 10, sizeof(struct KCR_Vec3));
    kcr_list_remove(vectors, 20, sizeof(struct KCR_Vec3));

    for (int x = 0; x < kcr_list_length(vectors); x++) {
        printf("Vector #%i: {%f, %f, %f}n", x, vectors(x).x, vectors(x).y, vectors(x).z);
    }

    kcr_list_free(vectors);
}
```