4
\$\begingroup\$

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 #%i\n", 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);
}
\$\endgroup\$
1
  • \$\begingroup\$ struct KCR_Vec3 is not defined --> Compiler error. \$\endgroup\$ Jan 27, 2021 at 18:09

3 Answers 3

2
\$\begingroup\$
  • 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);
    
\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the feedback. I thought about the struct approach but that meant the consumer would have to cast every data retrieval, instead of just making it myDataType* myArray[]; myDataType element = myArray[5] . With the struct don't I have to do kcr_list* array; myDataType element = (myDataType) array->data[5]? That seems more cumbersome. Is your concern with macros abated if I use inline functions instead? \$\endgroup\$
    – KallDrexx
    Jan 27, 2021 at 1:05
  • \$\begingroup\$ also ++ to encoding the element size, that's a good thought! \$\endgroup\$
    – KallDrexx
    Jan 27, 2021 at 1:05
  • \$\begingroup\$ Ignore my first comment. I see what you are suggesting and makes perfect sense. \$\endgroup\$
    – KallDrexx
    Jan 27, 2021 at 1:19
1
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Thanks for the detailed review, it's extremely appreciated! Re List naming, I come from a C# background which has Array and List, the former is static sized while the latter is growable. That's why I gave it the list name, but I see why that can be confusing. I'll go with ArrayList to help with that. Re: malloc.h, is stdlib.h the proper way to include *alloc functions? Re: void* thanks, I was not aware of that. I assume char* is the standard way to use pointer arithmetic? Re: remove, I don't get your comment about that. Java ArrayList has remove by index \$\endgroup\$
    – KallDrexx
    Jan 27, 2021 at 1:25
  • \$\begingroup\$ Re: append returning a new pointer, I guess I can fix that with a char **list instead of char *list, which would allow me to reassign the pointer without a return, is that along the lines of what you are suggesting? Also does append(char** list, void* item); address the bad API comment, since that ends up with 2 different types? \$\endgroup\$
    – KallDrexx
    Jan 27, 2021 at 1:28
  • \$\begingroup\$ Yes, <stdlib.h> is the correct way to declare malloc and related functions. \$\endgroup\$ Jan 29, 2021 at 21:38
  • \$\begingroup\$ For pointer arithmetic, char * is the usual data type. But before you actually do pointer arithmetic on char *, you should think twice whether there is a cleaner way to express your ideas. Maybe a struct or some other data structure. \$\endgroup\$ Jan 29, 2021 at 21:40
  • \$\begingroup\$ Regarding Java's ArrayList.remove(index): Yes, that method exists, but it is slow if the list is large and you remove elements from the front. That's why I would only add that function to the API if it is actually necessary. \$\endgroup\$ Jan 29, 2021 at 21:42
1
\$\begingroup\$

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;
\$\endgroup\$
2
  • \$\begingroup\$ One question, why do you think initial capacity isn't needed. If you know you are going to append 100 items to the list, isn't it better to pass in the single 100 initial capacity for a single malloc, instead of several reallocs as you append new items? \$\endgroup\$
    – KallDrexx
    Jan 28, 2021 at 1:27
  • \$\begingroup\$ @KallDrexx Any competing approaches to code will have cases that favor one over the other. As a general usage collection code, the initial capacity feature lacks value. Cases that tend to know such things as initial capacity also tend to have a good idea of the max size needed. In that case, just allocate the array per the max size. Further the initial capacity parameter fragments memory sizes. Without it, the sizes allocated/reallocated follow a fixed pattern -easier for the system allocator to maintain. \$\endgroup\$ Jan 28, 2021 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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