8
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

7
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Re: Return a flag: I am curious, in what circumstance is a NULL value for a void* not available? \$\endgroup\$ Dec 25, 2022 at 10:12
  • 1
    \$\begingroup\$ @404NameNotFound ll_default_find() returns NULL when the item is not found. It also returns node->data which might be NULL. The caller does not know for which reason function returned. \$\endgroup\$ Dec 25, 2022 at 14:04
  • 1
    \$\begingroup\$ I see, thanks for the explanation \$\endgroup\$ Dec 25, 2022 at 14:09
  • 1
    \$\begingroup\$ When ll_default_removeByObject() does not find the object (or in the index case, out of range), there is no flag to indicate this. In cases where the Object/index is not certainly in the list, the caller would need to verify objects existence and then potentially delete. By index, this is not so much an issue. With ...ByObject(), it implies 2 passes when one would do if the delete function flagged it success. \$\endgroup\$ Dec 25, 2022 at 14:10
  • 1
    \$\begingroup\$ Not absolutely necessary, yet useful. Consider if one had multiple ptr in the list and wanted to remove all of them, how many time to call ll_default_find()? IOWs, when ll_default_find() is called the caller does not certainly know it exist in the list and would find it useful to know if a true deletion occurred. It certainly does not cost much to return that info. \$\endgroup\$ Dec 25, 2022 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.