List implementation in C

Question

I tried to implement a Python-esque list in C. Having not really used C in anger, I'd like some pointers on style and error handling in particular.

Header

#ifndef __TYPE_LIST_H__
#define __TYPE_LIST_H__

/*  Generic list implementation for holding a set of pointers to a type
    (has to be consistently handled by the element_match and element_delete 
    functions)
*/

typedef struct list_s list_t;

#include <stdbool.h>
#include <stdint.h>

extern const uint16_t default_capacity;

list_t* list_create(
    uint16_t    initial_capacity,
    bool        (*element_match )(const void* a, const void* b),
    void        (*element_delete)(void* element));

void list_delete(list_t* list);

bool    list_append(list_t* list, void* element);
void*   list_pop(list_t* list);
bool    list_remove(list_t* list, void* element);
int16_t list_index(list_t* list, void* element);
bool    list_contains(list_t* list, void* element);
bool    list_empty(list_t* list);

#endif

Source

#include <type/list.h>
#include <stdio.h>
#include <stdlib.h>

const uint16_t default_capacity = 256;

struct list_s
{
    uint16_t length;
    uint16_t capacity;
    void**   elements;
    bool     (*element_match )(const void* a, const void* b);
    void     (*element_delete)(void* element);
};

list_t* list_create(
    uint16_t    initial_capacity,
    bool        (*element_match )(const void* a, const void* b),
    void        (*element_delete)(void* element)) 
{
    list_t* list = (list_t*) malloc(sizeof(list_t));
    if (!list) return NULL;

    if (!initial_capacity) {
        initial_capacity = default_capacity;
    }

    list->elements = (void**) malloc(sizeof(void*) * initial_capacity);
    if (!list->elements) return NULL;

    list->length         = 0;
    list->capacity       = initial_capacity;
    list->element_match  = element_match;
    list->element_delete = element_delete;

    return list;
}

void list_delete(list_t* list) 
{
    if (!list) return;

    if (list->element_delete) {
        unsigned i;
        for (i = 0; i< list->length; i++) {
            list->element_delete(list->elements[i]);
        }
    }
    else {
        fprintf(stderr, "WARNING: no element_delete specified");
    }
    free(list);
}

bool list_append(list_t* list, void* element) 
{
    if (!list || !element)
        return false;
    if (list->length >= list->capacity) {
        // expand the elements array
        list->capacity *= 2;
        list->elements = realloc(list->elements, sizeof(void*) * list->capacity);
        if (!list->elements) {
            return false;
        }
    }
    list->length += 1;
    list->elements[list->length] = element;
    return true;
}

void* list_pop(list_t* list)
{
    if (!list || list_empty(list)) {
        return NULL;
    }
    void* element = list->elements[list->length];
    list->elements[list->length] = NULL;
    list->length -= 1;
    return element;
}

bool list_remove(list_t* list, void* element)
{
    if (!list || !list->element_match) {
        return false;
    }
    unsigned i;
    bool found = false;
    for (i = 0; i < list->length; i++) {
        if (!found && list->element_match(list->elements[i], element)) {
            found = true;
            list->length -= 1;
        }
        if (found) {
            // shift all subsequent elements back one
            list->elements[i] = list->elements[i + 1];
        }
    }
    return found;
}

int16_t list_index(list_t* list, void* element)
{
    int16_t i;
    for (i = 0; i < list->length; i++) {
        if (list->element_match(list->elements[i], element)) {
            return i;
        }
    }
    return -1;
}

bool list_contains(list_t* list, void* element) {
    return (list_index(list, element) != -1);
}

bool list_empty(list_t* list)
{
    return (list->length == 0);
}

Answer 1

• Do not cast what malloc returns.

• It is beneficial to take size of a variable, rather than a type.

      list_t* list = malloc(sizeof *list);
  

  is immune to possible changes in type of list.

  Along the same line, calloc is preferable when allocating arrays. First, the allocated memory is in known state, and second, multiplication size * number may overflow. Consider

      list->elements = calloc(initial_capacity, sizeof list->elements[0]);
  

• list_delete doesn't free(list->elements).

• list->elements[0] is never initialized. This would cause problems with list_delete. Similarly, list_delete does not touch the last element. Along the same line, list->elements[list->length] gives an impression of out of bounds access.

  An idiomatic way would be to assign the pointer first, and only then increment the length, e.g.

      list->elements[list->length++] = element;
  

• list_remove is unnecessarily complicated. Consider breaking it up, e.g.

      i = list_index(list, element)
  
      if (i == -1) {
          return false;
      }
  
      while (i < list_length - 1) {
          list->elements[i] = list->elements[i+1];
      }
  

  I also recommend to factor the last loop out into a list_shift method.

Answer 2

Surprising name

default_capacity is in the public .h file

In a header for list_this and list_that, finding default_capacity is not good and a name-space collision headache. Suggest list_default_capacity instead.

0 allocation

Be careful about allocating 0 memory (possible with default_capacity == 0 and list_create(0, ...)). Receiving NULL in that case does not certainly indicate an out-of-memory condition.

// list->elements = (void**) malloc(sizeof(void*) * initial_capacity);
// if (!list->elements) return NULL;

list->elements = malloc(sizeof list->elements[0] * initial_capacity);
if (list->elements == NULL && initial_capacity == 0) {
  return NULL;
}

default_capacity not needed

With generic list code, I'd expect the ability to create a 0 length list and not have 0 indicate "use a default value".

Answer 3

You error on missing function pointers when you try and use them. You should error out when you create the list.

Don't printf in library functions, even to stderr.

uint16_t only allows 65k elements, this is really tiny for a list.

You don't allow NULL elements. Sometimes you want NULL elements in your list, it's a big reason why one would use a list of pointers instead of a list by value.

There is no way to index into the list or iterate over it.

Answer 4

Consider using restrict

...on your pointer arguments. If you aren't familiar with this keyword, it requires more explanation than can reasonably go into this answer, so you'll have to do some reading, but - in short, it can help with performance.

Use a define instead of a variable

This:

extern const uint16_t default_capacity;

isn't terrible, but it hinders the compiler's capability to optimize based on known constants. Advanced compilers with "whole program optimization" that have an optimization stage between object compilation and link can figure this out, but older or naively configured compilers won't. Using a #define in your header will fix this.

Answer 5

What I see:

Like this answer states you should not be printing as an recoverable error. If your program needs to crash, then you can print, but printing when execution of the program should continue will unexpectedly fill the output stream with stderr symbols that the end user has no easy control of stopping. Instead, use return codes and possibly provide your own error function that returns the proper string of characters that need to be printed based upon the error code. That way they can choose to check the error code, do nothing, fix the problem, or crash on their own volition.

I'm not sure why you chose uint16_t as your list size type, but incase there are actually situations in which you want to do this, I would suggest instead using

typedef uint16_t list_size_t;

so you could potentially do something like:

#if defined MY_UINT64_DEFINED_VAR
typedef uint64_t list_size_t;
#elif defined MY_UINT32_DEFINED_VAR
typedef uint32_t list_size_t;
#elif defined MY_UINT16_DEFINED_VAR
typedef uint16_t list_size_t;
#endif

provided you can find a compiler variable or find the size of int or some other compile time definition to figure out the size type you want your system to use.

You also need to be able to iterate through list elements. I suggest using a function like:

void* list_get(list_size_t index)

which would then return the pointer to the element at the given index.

Another thing you might want to consider is namespace conflicts with:

typedef struct list_s list_t 

Because of the lack of namespaces in C, such names can conflict with other names within the same scope and lead to a whole bunch of odd errors that may or may not be hard to track down. list_t is such a generic name, I'm not sure it is appropriate to use directly here, you may want to not pollute the namespace with list_t, and instead keep it as struct list_s. However there is another solution to this problem that also solves other potential namespace conflicts.

You may want to prefix all of your names with a sort of psuedo namespace specifier (which a lot of other C APIs do, like opengl, vulkan opencv's now defunct C api etc...)

I would recommend even doing this on macros as well, as they have the same problem (and this practice is also standard).

for example, lets say you decide to use "abc" as your pseudo namespace name. You would then change:

bool    list_append(list_t* list, void* element);

to:

bool    abc_list_append(abc_list_t* list, void* element);

yes, this is annoying, but if someone wants to use your library but wants multiple list types, or have multiple libraries called list but don't do the same thing, then they are out of luck. If you use a "pseudo namespace" then they can avoid many of these conflicts. If however, this is only supposed to be used internally in another project or is never going to be released to be used as its own library, you do not have to worry about name-spacing these components to other people, though you may still find conflicts on your own.

Answer 6

In addition to list_get, as opa mentioned, and list_size / list_length to go with it, I would include a version of list_remove that takes an index instead of an element to compare to, for the fairly common scenario where you want to see if an element is in the list, possibly do something with it, and then delete it.

int player_index = list_index(entity_list, "player");
if(player_index == -1) 
{
    handle_no_player();
}
else
{
    handle_player();
    list_remove_at(entity_list, player_index);
}

Also, since you're using a function pointer for equality comparison anyway, it would be easy to include a version that takes a predicate:

bool is_on_fire(void *entity) { return ((game_entity*)entity)->on_fire; }
int first_on_fire = list_index(entity_list, &is_on_fire);

As the name first_on_fire indicates, the third issue is that if this is representing a general list rather than a set (meaning there can be duplicate elements), then you need a version of list_index that takes a starting index to search from, so that it's possible to find the second / third / nth instance of a given element.

list_pop is an ambiguous name, since it's not apparent whether it works like a stack or a queue. list_pop_back would be more clear.

A function that inserts into the middle of a list could be useful as well.

Answer 7

Probably pedantic, but your code could be more robust to errors without significant changes. In your constructor, you could fail-fast the element_delete and not worry about it in your destructor. Instead of going though serially and initialising one by one in create_list, consider setting values to the default first before calling malloc; then you're always in a valid state.

/* The newly created list or a null pointer and errno is set, (probably, it
 depends what standard you're using for it to be guaranteed.) */
list_t* list_create(
    const uint16_t    initial_capacity,
    const bool        (*element_match )(const void* a, const void* b),
    const void        (*element_delete)(void* element)) 
{
    list_t* list;

    /* Pre-conditions. */
    if(!element_delete || !initial_capacity) {
        errno = EDOM;
        return NULL;
    }

    list = malloc(sizeof *list);
    if (!list) return NULL; /* The malloc will (probably) set the errno. */
    list->length         = 0;
    list->capacity       = initial_capacity;
    list->elements       = NULL;
    list->element_match  = element_match;
    list->element_delete = element_delete;

    /* This could fail, so it's after initialisation. */
    list->elements = malloc(sizeof *list->elements * initial_capacity);
    if (!list->elements) {
        list_delete(list);
        return NULL;
    }

    return list;
}

/* If the list has been initialised, this will work regardless. */
void list_delete(const list_t* list) 
{
    unsigned i;
    if (!list) return;
    for (i = 0; i < list->length; i++) {
        list->element_delete(list->elements[i]);
    }
    free(list->elements);
    free(list);
}

(I haven't tested this. You will need to #include <errno.h>.)

Answer 8

For anyone curious, here's my code with the comments taken on board:

Header

#ifndef __TYPE_LIST_H__
#define __TYPE_LIST_H__

/*  Generic list implementation for holding a set of pointers to a type
    (has to be consistently handled by the element_match and element_delete 
    functions)
*/

typedef struct sdlui_list_s sdlui_list_t;

#include <stdbool.h>
#include <stdint.h>

sdlui_list_t* sdlui_list_create(
    uint32_t initial_capacity,
    bool     (*element_match )(const void* a, const void* b),
    void     (*element_delete)(void* element));

void sdlui_list_delete(sdlui_list_t* list);

bool     sdlui_list_append     (sdlui_list_t* list, void* element);
bool     sdlui_list_pop_back   (sdlui_list_t* list, void* ret);
bool     sdlui_list_get        (sdlui_list_t* list, uint32_t index, void* ret);
bool     sdlui_list_remove     (sdlui_list_t* list, void* element);
bool     sdlui_list_remove_at  (sdlui_list_t* list, uint32_t index);
void     sdlui_list_shift      (sdlui_list_t* list, int64_t start_index);
int64_t  sdlui_list_index      (sdlui_list_t* list, void* element);
int64_t  sdlui_list_index_from (sdlui_list_t* list, void* element,
                                                                int64_t start_index);
bool     sdlui_list_contains   (sdlui_list_t* list, void* element);
bool     sdlui_list_empty      (sdlui_list_t* list);
uint32_t sdlui_list_length     (sdlui_list_t* list);

#endif

Source

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>

#include <type/list.h>

struct sdlui_list_s
{
    uint32_t length;
    uint32_t capacity;
    void**   elements;
    bool     (*element_match )(const void* a, const void* b);
    void     (*element_delete)(void* element);
};

sdlui_list_t* sdlui_list_create(
    uint32_t initial_capacity,
    bool     (*element_match )(const void* a, const void* b),
    void     (*element_delete)(void* element))
{
    sdlui_list_t* list;

    if (!element_delete || !initial_capacity) {
        errno = EDOM;
        return NULL;
    }
    list = (sdlui_list_t*) malloc(sizeof(sdlui_list_t));
    if (!list) return NULL;

    list->length         = 0;
    list->capacity       = initial_capacity;
    list->element_match  = element_match;
    list->element_delete = element_delete;

    list->elements = (void**) malloc(sizeof(list->elements[0]) * initial_capacity);
    if (!list->elements) {
        sdlui_list_delete(list);
        return NULL;
    }
    return list;
}

void sdlui_list_delete(sdlui_list_t* list)
{
    unsigned i;
    for (i = 0; i< list->length; i++) {
        list->element_delete(list->elements[i]);
    }
    free(list->elements);
    free(list);
}

bool sdlui_list_append(sdlui_list_t* list, void* element)
{
    if (!list)
        return false;
    if (list->length >= list->capacity) {
        // expand the elements array
        list->capacity *= 2;
        list->elements = realloc(list->elements, sizeof(void*) * list->capacity);
        if (!list->elements) {
            return false;
        }
    }
    list->elements[list->length++] = element;
    return true;
}

bool sdlui_list_get(sdlui_list_t* list, uint32_t index, void* ret) {
    if (!list || index > list->length) {
        return false;
    }
    ret = list->elements[index];
    return true;
}

bool sdlui_list_pop_back(sdlui_list_t* list, void* ret)
{
    if (!list || sdlui_list_empty(list)) {
        return false;
    }
    ret = list->elements[list->length];
    list->elements[list->length] = NULL;
    list->length--;
    return true;
}

bool sdlui_list_remove(sdlui_list_t* list, void* element)
{
    int64_t i = sdlui_list_index(list, element);

    if (i == -1) {
        return false;
    }

    sdlui_list_shift(list, i);
    list->length--;
    return true;
}

bool sdlui_list_remove_at(sdlui_list_t* list, uint32_t index)
{
    if (list->length == 0) {
        return false;
    }
    sdlui_list_shift(list, index);
    list->length--;
    return true;
}

void sdlui_list_shift(sdlui_list_t* list, int64_t start_index)
{
    while ((uint32_t)start_index < list->length - 1) {
        list->elements[start_index] = list->elements[start_index+1];
        start_index++;
    }
}

int64_t sdlui_list_index(sdlui_list_t* list, void* element)
{
    return sdlui_list_index_from(list, element, 0);
}

int64_t  sdlui_list_index_from (sdlui_list_t* list, void* element,
                                                                int64_t start_index)
{
    if (!list->element_match || list->length < (uint32_t) start_index) {
        /* No way to compare */
        return -1;
    }
    uint32_t i;
    for (i = start_index; i < list->length; i++) {
        if (list->element_match(list->elements[i], element)) {
            return i;
        }
    }
    return -1;
}


bool sdlui_list_contains(sdlui_list_t* list, void* element) {
    return (sdlui_list_index(list, element) != -1);
}

bool sdlui_list_empty(sdlui_list_t* list)
{
    if (!list) {
        return false;
    }
    else {
        return (list->length == 0);
    }
}

uint32_t sdlui_list_length(sdlui_list_t* list) {
    return list->length;
}