Dynamic list in C99

• kcr_list_append(void *list, void *item, size_t itemSize) allows appending elements of different sizes. It does not seem to be a design intent. I strongly recommend to make the element size a property of the list.

• I do not endorse this kind of macros. The list metadata are completely dissociated from the list initialization (notice that ugly sizeof(int) * 2). Consider

    struct kcr_list {
        int length;
        int capacity;
        int element_size;
        char data[1];
    };
  
    void * kcr_list_create(int initialCapacity, size_t itemSize)
    {
        struct kcr_list * list = malloc(sizeof(struct kcr_list + initialCapacity * itemSize);
        return list->data;
    }
  

  Other functions (append and remove) may get a hold of the base structure pointer via something along the lines of container_of macro.

• It might be beneficial to let remove to shrink the capacity when the list becomes too short (with respect to capacity).

• A note on remove. If you don't care about the order (and I don't see a need to care), you may improve the efficiency by copying only one item -namely, last one - over the removed:

    lastSlot = list + (count - 1) * itemSize;
    memcpy(slotToRemove, lastSlot, itemSize);
  

One thing I needed for the code I'm writing was a resizable list collection that can grow as items are added to it.

Do you need something more like Java's ArrayList or like its LinkedList? Mentioning this difference would have been nice, instead I have to read the code to get the answer. That's more work on the reader's side. Remember, code is written and rewritten a few times, and read much more often, so it's good to optimize for reading speed.

list.h

/**
 * Creates a new growable list

I prefer to end each sentence with a period. And to have an empty line between the main description and the @param. But that of course depends on the IDE and its highlighting capabilities. If it looks good already, just keep it.

 * @param initialCapacity how many items the list should initially have memory for
 * @param itemSize The size of each item

Be consistent in the spelling. how starts lowercase, The starts uppercase.

 * @return returns a pointer to the newly created list, or `NULL` if list creation failed

The @return returns is redundant. The a pointer to is redundant since that can be seen from the return type of the function.

void* kcr_list_create(int initialCapacity, size_t itemSize);

What if I pass -13 as the initialCapacity? Is that undefined behavior? I would have chosen size_t for the capacity as well. This avoids problems later when you multiply signed and unsigned numbers. I don't know whether compilers typically warn about this type combination, but a strict linter might do.

The return type void * is wrong. It must be some other pointer type, and even if that type is only used as a marker type. A void * can be implicitly converted to any other pointer without further warning, that's just too dangerous. Remember, C is the language that you should only use if you really want to shoot yourself in the foot. Using void * is a good way to achieve that.

/**
 * 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.

Spelling: it's "then", not "than". If you are unsure, just replace that word with a comma. Or reword the complete sentence:

Appends an item to the end of the list, enlarging the list if necessary.

This way, you also avoid the inconsistency in grammar. "Appends …" versus "will be resized".

 * @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

As already mentioned in another review, the itemSize is redundant here and must be hidden as an implementation detail in the list structure.

 * @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.

Typo: "accomodate" => "accommodate"

I find it inconvenient to always have to re-assign the list variables. This feels like Go's append function, which I find so inconvenient that I suggested a short-hand syntax for it.

I like to have a stable pointer that refers to "the list" over its complete lifetime.

void* kcr_list_append(void* list, void* item, size_t itemSize);

Here you have the ambiguity: There's 3 times void *. Two of them mean the same, the third is different. That's a sign of a bad API.

void kcr_list_remove(void* list, int index, size_t itemSize);

Do you really need this function? If so, would it be more efficient to offer both an ArrayList and a LinkedList, depending on what usage patterns are more likely?

int kcr_list_length(const void* list);

What should the return value of kcr_list_length("hello, world") be? Should the compiler be able to detect this obvious mistake?

list.c

#include <malloc.h>

From which century do you come? malloc.h has been obsolete since 1990, when C90 was standardized.

#include <mem.h>

I never heard of the header mem.h. You must be living in an exotic world, far from all standard implementations.

#include <math.h>

That sounds wrong. math.h is for floating-point arithmetics. That's not something you should need in memory management.

#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

Urgs. That's really ugly. If you really want to keep this confusing programming style, at least define a struct for the internal data, so that you can name the individual members instead of referring to them by index.

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);

Bad. Don't reuse variables for different purposes just because they happen to have the same underlying implementation data type. memory points to the start of the actually allocated memory, the first element must be named first_element or something similar.

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

Don't do that. Use an assertion instead of silently ignoring errors.

It took me several weeks to remove this pattern from NetBSD's make, somewhere in August 2020, if I remember correctly, only to see that almost all callers passed valid lists all the time. The very few exceptional usages were impossible to spot in the original code. This created an unnecessary ambiguity. Make your code as clear, precise and specific as possible.

        int newCapacity = capacity + (int) roundf((float) capacity * 1.25f);

That's crap. As I said, don't use floating point arithmetic where you need precise results. In an IEEE 754 implementation, float has 23 significant bits, which means that numbers above 16 million are approximated. Additionally, converting to floating pointer numbers and back to integers is completely unnecessary. If the capacity is small enough, a simple capacity * 5 / 4 has the same effect. If you want, you can account for overflow. Or just use a uint64_t for the intermediate result, that cannot practically overflow.

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

Again, don't hide errors. assert(list != NULL); assert(index >= 0);.

    if (index >= count) {
        return;
    }

And again.

        void* slotToRemove = list + itemSize * index;
        … slotToRemove + itemSize …

Standard C doesn't allow arithmetic with void pointers, that's a GNU extension, and a bad one. It makes for sloppy code.

Test Usage

int main() {

Missing prototype. Did you compile with all compiler warnings enabled? You really should, to catch trivial errors like this one. Write int main(void) instead.

    struct KCR_Vec3* vectors = kcr_list_create(5, sizeof(struct KCR_Vec3));

Compile error. Undeclared type KCR_Vec3. I'll try to continue the review nevertheless. Next time, please post complete and compilable code.

Instead of sizeof(struct KCR_Vec3), just write sizeof *vectors. That's more reliable, just in case you need to change the data type. Sure, both styles require some form of repetition, either repeating the type or the variable name, so this is only a minor issue.

        if (array == NULL) {
            fprintf(stderr, "Failed to add item #%i\n", x);
        }

That's unreliable code. You must not print an error message and continue as if nothing bad had happened. Either continue, or print and error message and take the error path.

The test code is unreliable. To see whether the test worked or not, you have to manually inspect its output. That's unnecessary work. Use a small test framework that does this work for you. The minimal approach is to use assert from the C Standard Library. A more advanced possibility is Greatest, which is really solid code worth reading.

Bug: Potential wrong alignment

The pointer returned by malloc() and friends meets the alignment needs for all standards types.

OP's code takes the address and offsets it by the size of 2 int. This is likely an agreeable alignment for many types, but not specified so. Consider a complex long double which may need an alignment of 16 and 2 int is 8.

A solution is to use a header struct based with a FAM which will add any required padding.

// #define RAW_LIST(list) ((int*) list) - 2
// #define FIRST_ELEMENT(list) ((int*) list) + 2

struct head {
  int len;
  int cap;
  max_align_t data[];
}

#define RAW_LIST(list) (((struct head*) list) - 1)
#define FIRST_ELEMENT(list) (((struct head*) list) + 1)

struct header *memory = malloc(sizeof *mmemory + itemSize*initialCapacity);

Use a final () around these macro definitions.

I'd use size_t rather than int.

The header also cleans up other code too. and makes it more flexible to add a uniform element size member.

Simplify interface

I see little value in the int initialCapacity parameter. 0 is fine.

Consider size of empty list

When a collection type is use a lot, the existence of many instances of empty lists is possible. Based on my experience, such collections are often empty.

Consider a pointer of NULL as empty and adjust code accordingly. It can save quite a bit of space.

This also allows clean initialization:

struct KCR_Vec3* vectors = 0;