Mfrhtyj

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

}

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.

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.

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.

• 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.

  
  

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.