Generic linked list implemented in pure C

Question

Recently i added such generic list in github and i would like to get some feedback.

Here is a link to the code in github:

https://github.com/MartinChekurov/Generic-Linked-List

GenericList.c

#include "GenericList.h"

typedef struct GenListNode_t {

    void* data;
    struct GenListNode_t* pNext;

}GenListNode;

struct GenList_t {

    GenListNode* head;
    Compare cmp;
    unsigned int dataSize;
    unsigned int count;
};

static GenListError genListCopyNodeData(void* data, unsigned int dataSize, void* buf, unsigned int bufSize)
{
    unsigned int cSize = 0;
    if (!data || !buf) {
        return GEN_LIST_WRONG_PAR;
    }
    cSize = bufSize < dataSize ? bufSize : dataSize;
    memcpy(buf, data, cSize);
    return GEN_LIST_NO_ERR;
}

static GenListNode* genLisNewNode(void* data, unsigned int dataSize)
{
    GenListNode* node = NULL;
    if (!data) {
        return NULL;
    }
    node = malloc(sizeof(*node));
    if (!node) {
        return NULL;
    }
    memset(node, 0, sizeof(*node));
    node->data = malloc(dataSize);
    if (!node->data) {
        return NULL;
    }
    memcpy(node->data, data, dataSize);
    return node;
}

static GenListError genListDestroyNode(GenListNode* node)
{
    if (!node) {
        return GEN_LIST_WRONG_PAR;
    }
    free(node->data);
    free(node);
    return GEN_LIST_NO_ERR;
}

GenList* genListNew(unsigned int dataSize, Compare cmp)
{
    GenList* list = NULL;
    list = malloc(sizeof(*list));
    if (!list) {
        return NULL;
    }
    memset(list, 0, sizeof(*list));
    list->dataSize = dataSize;
    if (cmp) {
        list->cmp = cmp;
    }
    return list;
}

GenListError genListPushHead(GenList* list, void* data)
{
    GenListNode* node = NULL;
    if (!list || !data) {
        return GEN_LIST_WRONG_PAR;
    }
    if (list->count == UINT_MAX) {
        return GEN_LIST_FULL;
    }
    node = genLisNewNode(data, list->dataSize);
    if (!node) {
        return GEN_LIST_NO_MEMORY;
    }
    node->pNext = list->head;
    list->head = node;
    list->count++;
    return GEN_LIST_NO_ERR;
}

GenListError genListPopHead(GenList* list, void* buf, unsigned int size)
{
    GenListNode* node = NULL;
    GenListError status = GEN_LIST_NO_ERR;
    if (!list) {
        return GEN_LIST_WRONG_PAR;
    }
    if (list->head) {
        node = list->head;
        list->head = node->pNext;
        status = genListCopyNodeData(node->data, list->dataSize, buf, size);
        if (status != GEN_LIST_NO_ERR) {
            return status;
        }
        genListDestroyNode(node);
        if (list->count)
            list->count--;
    }
    return GEN_LIST_NO_ERR;
}

GenListError genListGetIndex(GenList* list, unsigned int index, void* buf, unsigned int size)
{
    GenListNode* node = NULL;
    unsigned int count = 0;
    if (!list) {
        return GEN_LIST_WRONG_PAR;
    }
    node = list->head;
    while(node && count < list->count) {
        if (count == index) {
            return genListCopyNodeData(node->data, list->dataSize, buf, size);
        }
        node = node->pNext;
        count++;
    }
    return GEN_LIST_ERROR;
}

GenListError genListSearchNode(GenList* list, void* data, void* buf, unsigned int size)
{
    GenListNode* node = NULL;
    GenListError status = GEN_LIST_NO_ERR;
    if (!list || !data || !buf) {
        return GEN_LIST_WRONG_PAR;
    }
    node = list->head;
    while(node) {
        if (list->cmp) {
            status = list->cmp(node->data, data);
            if (status == GEN_LIST_MATCH) {
                return genListCopyNodeData(node->data, list->dataSize, buf, size);
            }
        }
        node = node->pNext;
    }
    return GEN_LIST_ERROR;
}

GenListError genListDestroy(GenList* list)
{
    GenListNode* node = NULL;
    GenListError status = GEN_LIST_NO_ERR;
    if (!list) {
        return GEN_LIST_WRONG_PAR;
    }
    while(list->head) {
        node = list->head;
        list->head = node->pNext;
        status = genListDestroyNode(node);
        if (status != GEN_LIST_NO_ERR) {
            return status;
        }
    }
    free(list);
    return GEN_LIST_NO_ERR;
}

GenListError genListGetSize(GenList* list, unsigned int *size)
{
    if (!list || !size) {
        return GEN_LIST_WRONG_PAR;
    }
    *size = list->count;
    return GEN_LIST_NO_ERR;
}

GenericList.h

/*
*   Author: Martin Chekurov
*/

#ifndef GEN_LIST_H_
#define GEN_LIST_H_

#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef enum {

    GEN_LIST_NO_ERR,
    GEN_LIST_WRONG_PAR,
    GEN_LIST_NO_MEMORY,
    GEN_LIST_MATCH,
    GEN_LIST_NO_MATCH,
    GEN_LIST_FULL,
    GEN_LIST_ERROR

}GenListError;

typedef GenListError (*Compare)(void*, void*);
typedef struct GenList_t GenList;

GenList*     genListNew        (unsigned int dataSize, Compare cmp);
GenListError genListDestroy   (GenList* list);
GenListError genListPushHead  (GenList* list, void* data);
GenListError genListPopHead   (GenList* list, void* buf, unsigned int size);
GenListError genListSearchNode(GenList* list, void* data, void* buf, unsigned int size);
GenListError genListGetSize   (GenList* list, unsigned int *size);
GenListError genListGetIndex  (GenList* list, unsigned int index, void* buf, unsigned int size);

#endif

Test.c

#include"GenericList.h"
#include<stdio.h>

#define MAX_NODES (5)

GenListError compare(void* dataIn, void* dataOut)
{
    return *(int*)dataIn == *(int*)dataOut ? GEN_LIST_MATCH : GEN_LIST_NO_MATCH;
}

int main(void)
{
    GenListError status = GEN_LIST_NO_ERR;
    GenList* list = NULL;
    unsigned int buf[MAX_NODES] = {1, 2, 3, 4, 5};
    unsigned int i = 0, size = 0, value = 0;

    printf("\nInitialize the list.");
    list = genListNew(sizeof(int), compare);
    if (!list) {
        printf("\ngenListNew failed.");
        return 1;
    }
    printf("\nPush %d nodes:", MAX_NODES);
    for (i = 0 ; i < MAX_NODES ; i++) {
        printf("\nPush value: %d.", buf[i]);
        status = genListPushHead(list, &buf[i]);
        if (status != GEN_LIST_NO_ERR) {
            printf("\ngenListPushHead() error: %d", (int)status);
            return 1;
        }
    }
    for (i = 0 ; i < MAX_NODES ; i++) {
        printf("\nGet value on index %d.", i);
        status = genListGetIndex(list, i, &value, sizeof(int));
        if (status != GEN_LIST_NO_ERR) {
            printf("\ngenListGetIndex() error: %d", (int)status);
            return 1;
        }
        printf("\nGot value: %d.", value);
    }
    status = genListGetSize(list, &size);
    if (status != GEN_LIST_NO_ERR) {
        printf("\ngenListGetSize() error: %d", (int)status);
        return 1;
    }
    printf("\nPushed %d nodes.", size);
    for (i = 0 ; i < MAX_NODES ; i++) {
        printf("\nFind value: %d.", buf[i]);
        status = genListSearchNode(list, &buf[i], &value, sizeof(int));
        if (status != GEN_LIST_NO_ERR) {
            printf("\ngenListSearchNode() error: %d", (int)status);
            return 1;
        }
        printf("\nFound value: %d.", value);
    }
    for (i = 0 ; i < MAX_NODES ; i++) {
        printf("\nPop a value from the list.");
        status = genListPopHead(list, &value, sizeof(int));
        if (status != GEN_LIST_NO_ERR) {
            printf("\ngenListPopHead() error: %d", (int)status);
            return 1;
        }
        printf("\nPoped value: %d.", value);
        status = genListGetSize(list, &size);
        if (status != GEN_LIST_NO_ERR) {
            printf("\ngenListGetSize() error: %d", (int)status);
            return 1;
        }
        printf("\nValues left: %d.", size);
    }
    printf("\nDestroy the list.");
    status = genListDestroy(list);
    if (status != GEN_LIST_NO_ERR) {
        printf("\ngenListDestroy() error: %d", (int)status);
        return 1;
    }
    printf("\nDone.");
    getchar();
}

Answer 1

GenericList.h and GenericList.c

Generally this is excellent code as long as it is a stack you want. It seems that what is created is really a generic stack implemented on a linked list rather than a generic linked list. If it was truly a generic linked list there would also be an append function and the delete node function would have to be smart enough to reset the next pointer of the previous node to the node being deleted next node.

Good things are that GenericList.h has include guards, malloc() is used properly and the return value is tested, I don't see any memory leaks.

A possible issue with GenericList.h is that all the includes that are required by GenericList.c are included in GenericList.h and those include files are not needed by Test.c.

GenericList.c is well designed and implemented, all the functions are well designed and implemented.

Test.c

I realize that this is just a test file, but the same care that was given to GenericList.h and GenericList.c should be given to the test code as well.

The main() function is too complex (does too much) and should be broken up into multiple functions (each loop should probably be a function). As it stands it would be very difficult to expand the functionality of the test code if additional functionality was added to GenericList.h and GenericList.c.

Rather than return 0 or 1 for the program status, it would be better to include <stdlib.h> in main and utilize the EXIT_SUCCESS and EXIT_FAILURE symbolic constants.

One other issue I see in Test.c is that it can use some blank lines for vertical spacing between the tests, this wouldn't be necessary if the tests were functions.

Answer 2

High level comment: you have chosen your list to own its data (as you allocate/free the data behind list elements inside this code) but without compile-time checking of the type of the data being fed to it.

Now this is actually fine if the user code is very careful with the data pointers and size inputs. But that is an assumption that you might not want to make. Furthermore, constant allocation/deallocation is somewhat wasteful, and copying the underlying data around on every input/output operation isn't something I'd expect to be necessary most of the time. In short, it looks like a generic Java list, minus type checking.

C isn't the best language for this sort of thing, but there are better ways even in pure C. First, consider if your use-case could do with a list which doesn't actually contain anything other than the concept of things which are in a certain order. Instead of copying your data into the list elements, make a mapping between your data owned by some other object (typically an array) and the list elements. This is trivial if your list has a sane bound on the maximum number of elements, not so much otherwise. If your list isn't used to pass things around between different parts of the code (i.e. your list type doesn't show up in high level interfaces), then I would recommend going with this "light" variant. Incidentally, this is how lists are usually implemented in baremetal code because it means you can get rid of dynamic allocation.

Second point, the use of void* as a pointer to something with non-zero size is obviously not very safe. If your list doesn't cross library boundaries, you can write function-like preprocessor macros with type names as argument to generate the exact function variants you need for every data type which you'll use your list with. It's ugly and no code analysis tool on earth with like it, but this way you can get type checking (and not have to ask for the size of the data when allocating).

Finally, some small scale comments:

• At the very least add some text explaining how to use your code in the documentation block at the top of the header file. Better also put in there the things that the user has to pay attention to in order to not have the whole thing break horribly (i.e. your assumptions about your input).
• If you use malloc then memset then it is always preferable to go straight for calloc. Actually, better always use calloc unless there's a demonstrable performance issue with it.
• Use const whenever you can, except when it's meaningless such as the exterior type of a function parameter in a function declaration. Users will thank you. Yourself will thank you because const prevents you from writing nonsense.
• Don't declare variables until you can give them a meaningful value (and ideally almost always their final value, see the const thing above). All that

GenListNode* node = NULL;

is achieving is to placate the compiler, without actually protecting you against using node before it is set to a good value. In cases such as these it's actually better to leave it uninitialized as then the compiler will figure out cases such as:

int i;
if(somebool) { i = 0; } else { i = 1; }

without complaining.

• In the same spirit, don't re-use allocated variables for different purposes. Allocate your for loop counters inside the for loop initialization statement (actually, minimize the scope of your variables in general).
• Don't omit braces after control flow statements. It's just too easy to make a mistake when refactoring code such as

if (list->count)
    list->count--;

• The standard type to use when a value is semantically the size of an object in bytes is size_t. It is effectively an unsigned int in most cases.

Answer 3

Your test code may cover all the main code, but it has a huge drawback. It won't fail if you make a programming mistake in the main code.

Instead of printing the values from the list, you should rather assert that they are exactly what you expect.

Instead of writing the boring if (status != GEN_LIST_NO_ERR) each time again, you should extract that code into a separate function.

In the type GenListError you are mixing programming errors and runtime errors. I would rather fail fast on any programming mistake and abort() the program. This is the nicest variant of undefined behavior that you can give to the users of your code since it forces them to fix their mistakes early and well.

If you include programming mistakes in the API of your generic list, it will bloat the caller's code since it has to check whether the call succeeded, failed expectedly ("no match") or was aborted by a programming error. If the caller checks only for success or failure, programming errors might silently be interpreted as either of these, which would have unpredictable consequences.

Answer 4

• It reads like list.cmp is required to be initialized, otherwise genListSearchNode is not meaningful. In that case, I would suggest checking cmp's value in function genListNew. If it is null, return a null ptr. Then in function genListSearchNode, we could have checked list->cmp as part of the parameter validations; exit early if list->cmp is null.
• you may consider to include a copy function for node's data. Currently, the code is doing a shallow copy via memcpy.
• In function genListPopHead, it sets list->head = node->pNext before genListCopyNodeData succeeds. If genListCopyNodeData fails then the list is mutated unintendedly. I would suggest swap the order so that make a copy first then change list->head. Also you would want to check if(buf) in this function.

Answer 5

Consistent Naming

Code naming is unnecessarily different

Files are GenericList.*
Functions genList*
Types GenList*
Enums GEN_LIST_*

Consider a common GenList_, GENLIST_

Sizes best as size_t

// unsigned int dataSize;
size_t dataSize;

// GenList *genListNew(unsigned int dataSize, Compare cmp);
GenList *genListNew(size_t dataSize, Compare cmp);
// and various other functions

Save formatting time

Below code hints that automatic formatting is not used. Improve productivity and consistency. Use an auto formatter. Life is too short for manual formatting.

struct GenList_t {


static GenListError genListCopyNodeData(void* data, unsigned int dataSize, void* buf, unsigned int bufSize)
{

DRYer code

// GenList* list = NULL;
// list = malloc(sizeof(*list));
GenList* list = malloc(sizeof *list);

How many enumerations?

Sometimes it is useful to know how many enumerations exist. Consider a last xxx_N one.

typedef enum {
    GEN_LIST_NO_ERR,
    GEN_LIST_WRONG_PAR,
    GEN_LIST_NO_MEMORY,
    GEN_LIST_MATCH,
    GEN_LIST_NO_MATCH,
    GEN_LIST_FULL,
    GEN_LIST_ERROR,
    GEN_LIST_N          // Add this one
} GenListError;

if (error < 0 || error >= GEN_LIST_N) Whoa_Handle_Errant_error_Code();