List implementation in C

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

}

edited Jan 4 at 15:49

Reinderien

4,140822

asked Jan 4 at 10:24

Aidenhjj

1,3932517

$begingroup$
I wanted to suggest you add a main so that the code is self-contained and can be compiled and tested without further effort. It would also show a usage example. But you already have collected 7 (!!!) answers, so you probably don’t care to do so. :/
$endgroup$
– Cris Luengo
Jan 12 at 3:26

add a comment |

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

}

edited Jan 4 at 15:49

Reinderien

4,140822

asked Jan 4 at 10:24

Aidenhjj

1,3932517

$begingroup$
I wanted to suggest you add a main so that the code is self-contained and can be compiled and tested without further effort. It would also show a usage example. But you already have collected 7 (!!!) answers, so you probably don’t care to do so. :/
$endgroup$
– Cris Luengo
Jan 12 at 3:26

add a comment |

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

}

edited Jan 4 at 15:49

Reinderien

4,140822

asked Jan 4 at 10:24

Aidenhjj

1,3932517

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

}

beginner c reinventing-the-wheel

edited Jan 4 at 15:49

Reinderien

4,140822

asked Jan 4 at 10:24

Aidenhjj

1,3932517

edited Jan 4 at 15:49

Reinderien

4,140822

asked Jan 4 at 10:24

Aidenhjj

1,3932517

edited Jan 4 at 15:49

Reinderien

4,140822

edited Jan 4 at 15:49

Reinderien

4,140822

edited Jan 4 at 15:49

Reinderien

4,140822

asked Jan 4 at 10:24

Aidenhjj

1,3932517

asked Jan 4 at 10:24

Aidenhjj

1,3932517

asked Jan 4 at 10:24

Aidenhjj

1,3932517

$begingroup$
I wanted to suggest you add a main so that the code is self-contained and can be compiled and tested without further effort. It would also show a usage example. But you already have collected 7 (!!!) answers, so you probably don’t care to do so. :/
$endgroup$
– Cris Luengo
Jan 12 at 3:26

add a comment |

$begingroup$
I wanted to suggest you add a main so that the code is self-contained and can be compiled and tested without further effort. It would also show a usage example. But you already have collected 7 (!!!) answers, so you probably don’t care to do so. :/
$endgroup$
– Cris Luengo
Jan 12 at 3:26

I wanted to suggest you add a main so that the code is self-contained and can be compiled and tested without further effort. It would also show a usage example. But you already have collected 7 (!!!) answers, so you probably don’t care to do so. :/

– Cris Luengo
Jan 12 at 3:26

add a comment |

7 Answers
7

active

oldest

votes

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.

answered Jan 4 at 21:11

vnp

39k13098

$begingroup$
That should be malloc(sizeof list). You probably need more space than a single pointer...
$endgroup$
– Cris Luengo
Jan 12 at 3:29

add a comment |

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.

answered Jan 4 at 13:41

ratchet freak

11.9k1343

$begingroup$
Thanks for the tips. Re: "Don't printf in library functions" - can you expand on why? Should I be returning error codes or something?
$endgroup$
– Aidenhjj
Jan 4 at 16:34

$begingroup$
C error reporting is really up to you, but here I would specify that element_delete be in list_create, and if it's null, you should return null and set errno.
$endgroup$
– Neil Edelman
Jan 11 at 0:06

add a comment |

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.

answered Jan 4 at 16:02

Reinderien

4,140822

$begingroup$
"[restrict] requires more explanation than can reasonably go into this answer", no it really doesn't, restrict isn't voodo magic, it is a way for the programmer to tell the compiler "these pointers are un related, and point to different objects". What I said might have even been shorter than your own explanation that you couldn't explain it. Not to mention it can also hurt performance on certain platforms. For example, in CUDA, using restrict can cause register pressure and lower occupancy on SMs (though not always).
$endgroup$
– opa
Jan 4 at 16:45

$begingroup$
@opa I didn't say it was voodoo; I said it can (and not will) improve performance; and I recommended that the OP consider adding this, rather than unconditionally recommending that it be added. You say that the topic is trivially explained, but then contradict this by saying that the behaviour is complex and platform-dependent. So I maintain my recommendation that the OP do further reading.
$endgroup$
– Reinderien
Jan 4 at 16:51

$begingroup$
I literally explained it, the explanation was trivial, the consequences of using it are not trivial, but then again, literally nothing low level is going to be trivial with respect to determining performance for all platforms, even using inlined constants and instructions can cause instruction cache misses critically lowering performance, but the actual explanation of such ideas is fairly simple. In the time you've spent providing excuses and avoiding explaining something important that could help OP, you could have written up a short explanation of restrict.
$endgroup$
– opa
Jan 4 at 16:57

1

$begingroup$
@opa but the subtleties around letting the compiler assume it are not that trivial.
$endgroup$
– ratchet freak
Jan 4 at 17:18

$begingroup$
I prefer the extern constant as it reduce compilation dependencies and avoiding macros is a good thing too.
$endgroup$
– Phil1970
Jan 11 at 2:08

add a comment |

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

edited Jan 7 at 15:03

answered Jan 7 at 0:28

chux

13.1k21344

add a comment |

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.

answered Jan 4 at 18:41

opa

27118

add a comment |

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.

answered Jan 4 at 21:18

Errorsatz

6837

add a comment |

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

edited Jan 11 at 20:15

answered Jan 11 at 1:15

Neil Edelman

282110

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210861%2flist-implementation-in-c%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

7 Answers
7

active

oldest

votes

7 Answers
7

active

oldest

votes

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.

answered Jan 4 at 21:11

vnp

39k13098

$begingroup$
That should be malloc(sizeof list). You probably need more space than a single pointer...
$endgroup$
– Cris Luengo
Jan 12 at 3:29

add a comment |

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.

answered Jan 4 at 21:11

vnp

39k13098

$begingroup$
That should be malloc(sizeof list). You probably need more space than a single pointer...
$endgroup$
– Cris Luengo
Jan 12 at 3:29

add a comment |

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.

answered Jan 4 at 21:11

vnp

39k13098

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.

answered Jan 4 at 21:11

vnp

39k13098

answered Jan 4 at 21:11

vnp

39k13098

answered Jan 4 at 21:11

vnp

39k13098

answered Jan 4 at 21:11

vnp

39k13098

$begingroup$
That should be malloc(sizeof list). You probably need more space than a single pointer...
$endgroup$
– Cris Luengo
Jan 12 at 3:29

add a comment |

$begingroup$
That should be malloc(sizeof list). You probably need more space than a single pointer...
$endgroup$
– Cris Luengo
Jan 12 at 3:29

That should be malloc(sizeof list). You probably need more space than a single pointer...

– Cris Luengo
Jan 12 at 3:29

add a comment |

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.

answered Jan 4 at 13:41

ratchet freak

11.9k1343

$begingroup$
Thanks for the tips. Re: "Don't printf in library functions" - can you expand on why? Should I be returning error codes or something?
$endgroup$
– Aidenhjj
Jan 4 at 16:34

$begingroup$
C error reporting is really up to you, but here I would specify that element_delete be in list_create, and if it's null, you should return null and set errno.
$endgroup$
– Neil Edelman
Jan 11 at 0:06

add a comment |

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.

answered Jan 4 at 13:41

ratchet freak

11.9k1343

$begingroup$
Thanks for the tips. Re: "Don't printf in library functions" - can you expand on why? Should I be returning error codes or something?
$endgroup$
– Aidenhjj
Jan 4 at 16:34

$begingroup$
C error reporting is really up to you, but here I would specify that element_delete be in list_create, and if it's null, you should return null and set errno.
$endgroup$
– Neil Edelman
Jan 11 at 0:06

add a comment |

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.

answered Jan 4 at 13:41

ratchet freak

11.9k1343

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.

answered Jan 4 at 13:41

ratchet freak

11.9k1343

answered Jan 4 at 13:41

ratchet freak

11.9k1343

answered Jan 4 at 13:41

ratchet freak

11.9k1343

answered Jan 4 at 13:41

ratchet freak

11.9k1343

$begingroup$
Thanks for the tips. Re: "Don't printf in library functions" - can you expand on why? Should I be returning error codes or something?
$endgroup$
– Aidenhjj
Jan 4 at 16:34

$begingroup$
C error reporting is really up to you, but here I would specify that element_delete be in list_create, and if it's null, you should return null and set errno.
$endgroup$
– Neil Edelman
Jan 11 at 0:06

add a comment |

$begingroup$
Thanks for the tips. Re: "Don't printf in library functions" - can you expand on why? Should I be returning error codes or something?
$endgroup$
– Aidenhjj
Jan 4 at 16:34

$begingroup$
C error reporting is really up to you, but here I would specify that element_delete be in list_create, and if it's null, you should return null and set errno.
$endgroup$
– Neil Edelman
Jan 11 at 0:06

Thanks for the tips. Re: "Don't printf in library functions" - can you expand on why? Should I be returning error codes or something?

– Aidenhjj
Jan 4 at 16:34

C error reporting is really up to you, but here I would specify that element_delete be in list_create, and if it's null, you should return null and set errno.

– Neil Edelman
Jan 11 at 0:06

add a comment |

Consider using `restrict`

Use a `define` instead of a variable

This:

extern const uint16_t default_capacity;

answered Jan 4 at 16:02

Reinderien

4,140822

$begingroup$
"[restrict] requires more explanation than can reasonably go into this answer", no it really doesn't, restrict isn't voodo magic, it is a way for the programmer to tell the compiler "these pointers are un related, and point to different objects". What I said might have even been shorter than your own explanation that you couldn't explain it. Not to mention it can also hurt performance on certain platforms. For example, in CUDA, using restrict can cause register pressure and lower occupancy on SMs (though not always).
$endgroup$
– opa
Jan 4 at 16:45

$begingroup$
@opa I didn't say it was voodoo; I said it can (and not will) improve performance; and I recommended that the OP consider adding this, rather than unconditionally recommending that it be added. You say that the topic is trivially explained, but then contradict this by saying that the behaviour is complex and platform-dependent. So I maintain my recommendation that the OP do further reading.
$endgroup$
– Reinderien
Jan 4 at 16:51

$begingroup$
I literally explained it, the explanation was trivial, the consequences of using it are not trivial, but then again, literally nothing low level is going to be trivial with respect to determining performance for all platforms, even using inlined constants and instructions can cause instruction cache misses critically lowering performance, but the actual explanation of such ideas is fairly simple. In the time you've spent providing excuses and avoiding explaining something important that could help OP, you could have written up a short explanation of restrict.
$endgroup$
– opa
Jan 4 at 16:57

1

$begingroup$
@opa but the subtleties around letting the compiler assume it are not that trivial.
$endgroup$
– ratchet freak
Jan 4 at 17:18

$begingroup$
I prefer the extern constant as it reduce compilation dependencies and avoiding macros is a good thing too.
$endgroup$
– Phil1970
Jan 11 at 2:08

add a comment |

Consider using `restrict`

Use a `define` instead of a variable

This:

extern const uint16_t default_capacity;

answered Jan 4 at 16:02

Reinderien

4,140822

$begingroup$
"[restrict] requires more explanation than can reasonably go into this answer", no it really doesn't, restrict isn't voodo magic, it is a way for the programmer to tell the compiler "these pointers are un related, and point to different objects". What I said might have even been shorter than your own explanation that you couldn't explain it. Not to mention it can also hurt performance on certain platforms. For example, in CUDA, using restrict can cause register pressure and lower occupancy on SMs (though not always).
$endgroup$
– opa
Jan 4 at 16:45

$begingroup$
@opa I didn't say it was voodoo; I said it can (and not will) improve performance; and I recommended that the OP consider adding this, rather than unconditionally recommending that it be added. You say that the topic is trivially explained, but then contradict this by saying that the behaviour is complex and platform-dependent. So I maintain my recommendation that the OP do further reading.
$endgroup$
– Reinderien
Jan 4 at 16:51

$begingroup$
I literally explained it, the explanation was trivial, the consequences of using it are not trivial, but then again, literally nothing low level is going to be trivial with respect to determining performance for all platforms, even using inlined constants and instructions can cause instruction cache misses critically lowering performance, but the actual explanation of such ideas is fairly simple. In the time you've spent providing excuses and avoiding explaining something important that could help OP, you could have written up a short explanation of restrict.
$endgroup$
– opa
Jan 4 at 16:57

1

$begingroup$
@opa but the subtleties around letting the compiler assume it are not that trivial.
$endgroup$
– ratchet freak
Jan 4 at 17:18

$begingroup$
I prefer the extern constant as it reduce compilation dependencies and avoiding macros is a good thing too.
$endgroup$
– Phil1970
Jan 11 at 2:08

add a comment |

Consider using `restrict`

Use a `define` instead of a variable

This:

extern const uint16_t default_capacity;

answered Jan 4 at 16:02

Reinderien

4,140822

Consider using `restrict`

Use a `define` instead of a variable

This:

extern const uint16_t default_capacity;

answered Jan 4 at 16:02

Reinderien

4,140822

answered Jan 4 at 16:02

Reinderien

4,140822

answered Jan 4 at 16:02

Reinderien

4,140822

answered Jan 4 at 16:02

Reinderien

4,140822

$begingroup$
"[restrict] requires more explanation than can reasonably go into this answer", no it really doesn't, restrict isn't voodo magic, it is a way for the programmer to tell the compiler "these pointers are un related, and point to different objects". What I said might have even been shorter than your own explanation that you couldn't explain it. Not to mention it can also hurt performance on certain platforms. For example, in CUDA, using restrict can cause register pressure and lower occupancy on SMs (though not always).
$endgroup$
– opa
Jan 4 at 16:45

$begingroup$
@opa I didn't say it was voodoo; I said it can (and not will) improve performance; and I recommended that the OP consider adding this, rather than unconditionally recommending that it be added. You say that the topic is trivially explained, but then contradict this by saying that the behaviour is complex and platform-dependent. So I maintain my recommendation that the OP do further reading.
$endgroup$
– Reinderien
Jan 4 at 16:51

$begingroup$
I literally explained it, the explanation was trivial, the consequences of using it are not trivial, but then again, literally nothing low level is going to be trivial with respect to determining performance for all platforms, even using inlined constants and instructions can cause instruction cache misses critically lowering performance, but the actual explanation of such ideas is fairly simple. In the time you've spent providing excuses and avoiding explaining something important that could help OP, you could have written up a short explanation of restrict.
$endgroup$
– opa
Jan 4 at 16:57

1

$begingroup$
@opa but the subtleties around letting the compiler assume it are not that trivial.
$endgroup$
– ratchet freak
Jan 4 at 17:18

$begingroup$
I prefer the extern constant as it reduce compilation dependencies and avoiding macros is a good thing too.
$endgroup$
– Phil1970
Jan 11 at 2:08

add a comment |

$begingroup$
"[restrict] requires more explanation than can reasonably go into this answer", no it really doesn't, restrict isn't voodo magic, it is a way for the programmer to tell the compiler "these pointers are un related, and point to different objects". What I said might have even been shorter than your own explanation that you couldn't explain it. Not to mention it can also hurt performance on certain platforms. For example, in CUDA, using restrict can cause register pressure and lower occupancy on SMs (though not always).
$endgroup$
– opa
Jan 4 at 16:45

$begingroup$
@opa I didn't say it was voodoo; I said it can (and not will) improve performance; and I recommended that the OP consider adding this, rather than unconditionally recommending that it be added. You say that the topic is trivially explained, but then contradict this by saying that the behaviour is complex and platform-dependent. So I maintain my recommendation that the OP do further reading.
$endgroup$
– Reinderien
Jan 4 at 16:51

$begingroup$
I literally explained it, the explanation was trivial, the consequences of using it are not trivial, but then again, literally nothing low level is going to be trivial with respect to determining performance for all platforms, even using inlined constants and instructions can cause instruction cache misses critically lowering performance, but the actual explanation of such ideas is fairly simple. In the time you've spent providing excuses and avoiding explaining something important that could help OP, you could have written up a short explanation of restrict.
$endgroup$
– opa
Jan 4 at 16:57

1

$begingroup$
@opa but the subtleties around letting the compiler assume it are not that trivial.
$endgroup$
– ratchet freak
Jan 4 at 17:18

$begingroup$
I prefer the extern constant as it reduce compilation dependencies and avoiding macros is a good thing too.
$endgroup$
– Phil1970
Jan 11 at 2:08

"[restrict] requires more explanation than can reasonably go into this answer", no it really doesn't, restrict isn't voodo magic, it is a way for the programmer to tell the compiler "these pointers are un related, and point to different objects". What I said might have even been shorter than your own explanation that you couldn't explain it. Not to mention it can also hurt performance on certain platforms. For example, in CUDA, using restrict can cause register pressure and lower occupancy on SMs (though not always).

– opa
Jan 4 at 16:45

@opa I didn't say it was voodoo; I said it can (and not will) improve performance; and I recommended that the OP consider adding this, rather than unconditionally recommending that it be added. You say that the topic is trivially explained, but then contradict this by saying that the behaviour is complex and platform-dependent. So I maintain my recommendation that the OP do further reading.

– Reinderien
Jan 4 at 16:51

I literally explained it, the explanation was trivial, the consequences of using it are not trivial, but then again, literally nothing low level is going to be trivial with respect to determining performance for all platforms, even using inlined constants and instructions can cause instruction cache misses critically lowering performance, but the actual explanation of such ideas is fairly simple. In the time you've spent providing excuses and avoiding explaining something important that could help OP, you could have written up a short explanation of restrict.

– opa
Jan 4 at 16:57

@opa but the subtleties around letting the compiler assume it are not that trivial.

– ratchet freak
Jan 4 at 17:18

I prefer the extern constant as it reduce compilation dependencies and avoiding macros is a good thing too.

– Phil1970
Jan 11 at 2:08

add a comment |

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

edited Jan 7 at 15:03

answered Jan 7 at 0:28

chux

13.1k21344

add a comment |

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

edited Jan 7 at 15:03

answered Jan 7 at 0:28

chux

13.1k21344

add a comment |

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

edited Jan 7 at 15:03

answered Jan 7 at 0:28

chux

13.1k21344

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

edited Jan 7 at 15:03

answered Jan 7 at 0:28

chux

13.1k21344

edited Jan 7 at 15:03

answered Jan 7 at 0:28

chux

13.1k21344

answered Jan 7 at 0:28

chux

13.1k21344

answered Jan 7 at 0:28

chux

13.1k21344

add a comment |

What I see:

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

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

answered Jan 4 at 18:41

opa

27118

add a comment |

What I see:

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

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

answered Jan 4 at 18:41

opa

27118

add a comment |

What I see:

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

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

answered Jan 4 at 18:41

opa

27118

What I see:

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

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

answered Jan 4 at 18:41

opa

27118

answered Jan 4 at 18:41

opa

27118

answered Jan 4 at 18:41

opa

27118

answered Jan 4 at 18:41

opa

27118

add a comment |

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

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.

answered Jan 4 at 21:18

Errorsatz

6837

add a comment |

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

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.

answered Jan 4 at 21:18

Errorsatz

6837

add a comment |

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

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.

answered Jan 4 at 21:18

Errorsatz

6837

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

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.

answered Jan 4 at 21:18

Errorsatz

6837

answered Jan 4 at 21:18

Errorsatz

6837

answered Jan 4 at 21:18

Errorsatz

6837

answered Jan 4 at 21:18

Errorsatz

6837

add a comment |

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

edited Jan 11 at 20:15

answered Jan 11 at 1:15

Neil Edelman

282110

add a comment |

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

edited Jan 11 at 20:15

answered Jan 11 at 1:15

Neil Edelman

282110

add a comment |

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

edited Jan 11 at 20:15

answered Jan 11 at 1:15

Neil Edelman

282110

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

edited Jan 11 at 20:15

answered Jan 11 at 1:15

Neil Edelman

282110

edited Jan 11 at 20:15

answered Jan 11 at 1:15

Neil Edelman

282110

answered Jan 11 at 1:15

Neil Edelman

282110

answered Jan 11 at 1:15

Neil Edelman

282110

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Code Review Stack Exchange!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu