Ykhjuy

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.