C void* Generic Linked List

Question

I once tried to make a generic linked list in pure C (no external libraries, only the C standard library) here using C macros. With the same restrictions as in the previous attempt, this time I'm trying to use void*s.

linkedlist.h:

#include <stdbool.h>
#include <stddef.h>

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

typedef struct LinkedList LinkedList;
typedef struct LinkedListNode LinkedListNode;

struct LinkedListNode {
    LinkedListNode *next;

    void *data;
};

struct LinkedList {
    LinkedList *this;

    LinkedListNode *head;
    size_t size;

    void (*destructor)(LinkedList *this);
    int (*dataComparer)(void *, void *);
    void (*dataDestroyer)(void *);

    int (*add)(LinkedList *this, void *data);
    void *(*find)(LinkedList *this, bool (*comparer)(void *));
    void (*removeByIndex)(LinkedList *this, size_t index);
    void (*removeByObject)(LinkedList *this, void *object);
    void (*clear)(LinkedList *this);
};

LinkedList *newLinkedList(int (*dataComparer)(void *, void *), void (*dataDestroyer)(void *));
void deleteLinkedList(LinkedList *list);

#endif

linkedlist.c:

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>

#include "linkedlist.h"

int ll_default_dataComparer(void *a, void *b) {
    int *castedA = (int *) a;
    int *castedB = (int *) b;

    return *castedA - *castedB;
}

void ll_default_dataDestroyer(void *data) {
    free(data);
}

void ll_default_destructor(LinkedList *this) {
    if (this == NULL) return;

    LinkedListNode *node = this->head;
    while (node != NULL) {
        LinkedListNode *prev = node;
        node = node->next;
        this->dataDestroyer(prev);
    }
}

int ll_default_add(LinkedList *this, void *data) {
    if (this == NULL) return -1;

    LinkedListNode *newNode = malloc(sizeof(LinkedListNode));
    if (newNode == NULL) return -2;

    newNode->next = NULL;
    newNode->data = data;

    LinkedListNode *node = this->head;

    if (node == NULL) {
        this->head = newNode;
    } else {
        while (node->next != NULL) node = node->next;
        node->next = newNode;
    }

    this->size++;

    return 0;
}

void *ll_default_find(LinkedList *this, bool (*comparer)(void *)) {
    if (this == NULL) return NULL;

    LinkedListNode *node = this->head;

    while (node != NULL) {
        if (comparer(node->data)) return node->data;
        node = node->next;
    }

    return NULL;
}

void ll_default_removeByIndex(LinkedList *this, size_t index) {
    if (this == NULL) return;

    if (index >= this->size) return;

    LinkedListNode *prevNode = NULL;
    LinkedListNode *currNode = this->head;

    for (size_t i = 0; i < index; i++) {
        if (currNode == NULL) return;
        prevNode = currNode;
        currNode = currNode->next;
    }

    if (prevNode != NULL) {
        prevNode->next = currNode->next;

        this->dataDestroyer(prevNode->data);
    } else {
        this->head = currNode->next;
    }

    free(prevNode);
    this->size--;
}

void ll_default_removeByObject(LinkedList *this, void *object) {
    if (this == NULL) return;

    LinkedListNode *prevNode = NULL;
    LinkedListNode *currNode = this->head;

    while (currNode != NULL) {
        if (this->dataComparer(currNode->data, object) == 0) {
            if (prevNode != NULL) {
                prevNode->next = currNode->next;

                this->dataDestroyer(currNode->data);
            } else {
                this->head = currNode->next;
            }

            free(currNode);
            this->size--;

            return;
        }

        prevNode = currNode;
        currNode = currNode->next;
    }
}

void ll_default_clear(LinkedList *this) {
    if (this == NULL) return;

    LinkedListNode *prevNode = NULL;
    LinkedListNode *currNode = this->head;

    while (currNode != NULL) {
        prevNode = currNode;
        currNode = currNode->next;

        this->dataDestroyer(prevNode->data);
        free(prevNode);
    }
}

LinkedList *newLinkedList(int (*dataComparer)(void *, void *), void (*dataDestroyer)(void *)) {
    LinkedList *list = malloc(sizeof(LinkedList));
    if (list == NULL) return NULL;

    list->this = list;
    list->destructor = ll_default_destructor;
    list->dataComparer = dataComparer != NULL ? dataComparer : ll_default_dataComparer;
    list->dataDestroyer = dataDestroyer != NULL ? dataDestroyer : ll_default_dataDestroyer;

    list->add = ll_default_add;
    list->find = ll_default_find;
    list->removeByIndex = ll_default_removeByIndex;
    list->removeByObject = ll_default_removeByObject;

    list->head = NULL;
    list->size = 0;

    return list;
}

void deleteLinkedList(LinkedList *list) {
    list->destructor(list->this);
}

main.c (testing code, not as rigorously written as the main linked list code):

#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "linkedlist.h"

typedef struct Cake {
    char name[256];
    size_t size;
} Cake;

bool finder(Cake *c) {
    // i forgot c doesn't have lambdas so this is going to be awkward to use
    if (c->size == 69420) return true;
    return false;
}

int compare(Cake *a, Cake *b) {
    return strcmp(a->name, b->name);
}

void destroyCake(Cake *cake) {
    // stub
    //
    // struct Cake has no dynamic allocations, we don't have to do anything
    // to clean it up afterwards
}

void print(LinkedList *list) {
    printf("[\n");

    LinkedListNode *node = list->head;
    while (node != NULL) {
        Cake *cake = node->data;
        printf("\t{ name: \"%s\", size: %zu },\n", cake->name, cake->size);
        node = node->next;
    }

    printf("]\n\n");
}

void cakeprinter(Cake *cake) {
    if (cake == NULL) printf("NULL\n");
    printf("{ name: \"%s\", size: %zu }\n\n", cake->name, cake->size);
}

int main(void) {
    LinkedList *list = newLinkedList(compare, destroyCake);

    if (list == NULL) {
        printf("Something went wrong\n");
        return -1;
    }

    Cake *c1 = malloc(sizeof(Cake));
    strcpy(c1->name, "Cakeus Smallus");
    c1->size = 420;

    Cake *c2 = malloc(sizeof(Cake));
    strcpy(c2->name, "Cakeus Enormous");
    c2->size = 69420;

    Cake *c3 = malloc(sizeof(Cake));
    strcpy(c3->name, "Cakeus Tinyeus");
    c3->size = 69;

    Cake *c4 = malloc(sizeof(Cake));
    strcpy(c4->name, "Cakeus Biggus");
    c4->size = 42069;

    list->add(list->this, c1);
    list->add(list->this, c2);
    list->add(list->this, c3);
    list->add(list->this, c4);

    // did we make cakes?
    printf("const cakes = ");
    print(list);

    // can we find a cake?
    Cake *tc1 = list->find(list->this, finder);
    printf("const cake69420 = ");
    cakeprinter(tc1);

    // lets destroy a cake by index and see if it's gone
    list->removeByIndex(list->this, 0); // should be the first cake
    printf("const cakesnoind = ");
    print(list);

    // lets destroy a cake by object and see if it's gone
    list->removeByObject(list->this, tc1);
    printf("const cakesnoobj = ");
    print(list);

    return 0;
}

Output as tested with ./main > res.txt:

const cakes = [
    { name: "Cakeus Smallus", size: 420 },
    { name: "Cakeus Enormous", size: 69420 },
    { name: "Cakeus Tinyeus", size: 69 },
    { name: "Cakeus Biggus", size: 42069 },
]

const cake69420 = { name: "Cakeus Enormous", size: 69420 }

const cakesnoind = [
    { name: "Cakeus Enormous", size: 69420 },
    { name: "Cakeus Tinyeus", size: 69 },
    { name: "Cakeus Biggus", size: 42069 },
]

const cakesnoobj = [
    { name: "Cakeus Tinyeus", size: 69 },
    { name: "Cakeus Biggus", size: 42069 },
]

The driver code is for quick testing only and is not as rigorously written as the main linked list code is. It compiles with clang -Wall -Wextra -pedantic *.c -o main, albeit with multiple warnings about incompatible function pointer types (the linked list takes in a function taking void pointers, but I shoved in a function taking pointers to the object I'm trying to store).

As with my previous attempt, looking for feedback for potential improvements.

Thank you for your time.

Answer 1

potential improvements.

Merry Christmas

Return a flag

void *ll_default_find(LinkedList *this, bool (*comparer)(void *)) returns NULL when not found. For a linked list of void *, better to not assume NULL is available for ll_...() use. Return a flag on success/failure and pass in a place to store the found value.

Remove functions do not return success indication

I'd expect something indicating success/failure.

Extensions

Consider an apply function. A function that does something to every node in the link-list

I'd expect a size_t LinkedList_Count(const LinkedList *this); to return the list count.

Documentation

Code, especially linkedlist.h lacks documentation. A good model is to assume the user only sees the .h file. Express, especially at the high level there, what code does.

Use const for reference data

When the reference data is not altered, used const. It allows for greater functional use, convey code's intent and helps some compilers.

Example:

// int ll_default_dataComparer(void *a, void *b) {
int ll_default_dataComparer(const void *a, const void *b) {

Avoid overflow

*castedA - *castedB; may overflow. Use a full range compare. Compilers commonly see the below idiom and emit efficient code.

// return *castedA - *castedB;
return (*castedA > *castedB) - (*castedA < *castedB);

-2??

Functions lack documentation about the meaning of return values like -2 from ll_default_add(LinkedList).

Out of order code guard

// #include <stdbool.h>
// #include <stddef.h>

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

// Move here
#include <stdbool.h>
#include <stddef.h>

Allocate to the reference object, not type

Allocate to the referenced object. It is easier to code right, review and maintain.

// c1 = malloc(sizeof(Cake));
c1 = malloc(sizeof c1[0]);

Robust code would check allocation success.