Generic linked lists

automatic_test.c

// To compile: cc -c -std=c99 linked_list.c
//             cc -std=c99 automatic_test.c linked_list.o -o automatic_test

#include <stdio.h>
#include <string.h>

#include "linked_list.h"
    
struct apple_linked_list {
    struct automatic_linked_list_node linked_list;
    char *colour;
};

int apple_search(void *node, void *item) {
    struct apple_linked_list *n = node;
    return strcmp(n->colour, item);
}

int main(void) {
    struct apple_linked_list *root = NULL,
                              red = { .colour = "red" },
                              blue = { .colour = "blue" },
                              green = { .colour = "green" };

    root = automatic_linked_list_add(root, &red);
    root = automatic_linked_list_add(root, &blue);
    root = automatic_linked_list_add(root, &green);

    for (struct apple_linked_list *a = root; a != NULL; a = linked_list_next(a)) {
        printf("We have %s apples!\n", a->colour);
    }

    puts("Taking away the blue apples...");
    automatic_linked_list_remove(root, apple_search, "blue");

    for (struct apple_linked_list *a = root; a != NULL; a = linked_list_next(a)) {
        printf("We have %s apples!\n", a->colour);
    }
}

dynamic_test.c

// To compile: cc -c -std=c99 linked_list.c
//             cc -std=c99 dynamic_test.c linked_list.o -o dynamic_test

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

#include "linked_list.h"
    
struct apple_linked_list {
    struct automatic_linked_list_node linked_list;
    char *colour;
};

int apple_search(void *node, void *item) {
    struct apple_linked_list *n = node;
    return strcmp(n->colour, item);
}

int main(void) {
    struct dynamic_linked_list *root = linked_list_create(sizeof (struct apple_linked_list));
    if (root == NULL) { goto end; } // Failure mode!

    void *temp = dynamic_linked_list_add(root, &(struct apple_linked_list){ .colour = "red" });
    if (temp == NULL) { goto end; } // Failure mode!
    root = temp;

    temp = dynamic_linked_list_add(root, &(struct apple_linked_list){ .colour = "blue" });
    if (temp == NULL) { goto end; } // Failure mode!
    root = temp;

    temp = dynamic_linked_list_add(root, &(struct apple_linked_list){ .colour = "green" });
    if (temp == NULL) { goto end; } // Failure mode!
    root = temp;

    for (struct apple_linked_list *a = root->head; a != NULL; a = linked_list_next(a)) {
        printf("We have %s apples!\n", a->colour);
    }

    puts("Taking away the blue apples...");
    dynamic_linked_list_remove(root, apple_search, "blue");

    for (struct apple_linked_list *a = root->head; a != NULL; a = linked_list_next(a)) {
        printf("We have %s apples!\n", a->colour);
    }

end:free(root);
}

linked_list.c

#include "linked_list.h"
#include <stdlib.h>
#include <string.h>

void *automatic_linked_list_add(void *root, void *node) {
    ((struct automatic_linked_list_node *)node)->next = root;
    return node;
}

void *linked_list_next(void *node) {
    return ((struct automatic_linked_list_node *) node)->next;
}

void *automatic_linked_list_remove(void *root, search_func *fun, void *item) {
    void **n = &root;
    while (*n && fun(*n, item)) {
        n = &((struct automatic_linked_list_node *)*n)->next;
    }
    if (*n) {
        *n = ((struct automatic_linked_list_node *)*n)->next;
    }
    return root;
}

struct dynamic_linked_list *linked_list_create(size_t node_size) {
    struct dynamic_linked_list *root = malloc(sizeof *root);
    if (root == NULL) { return NULL; }
    *root = (struct dynamic_linked_list) { .node_size = node_size };
    return root;
}

struct dynamic_linked_list *dynamic_linked_list_add(struct dynamic_linked_list *root, void *node) {
    void *n = root->free;
    if (!n) {
        if ((root->node_count & (root->node_count + 1)) == 0) {
            root = realloc(root, sizeof *root + root->node_size * (root->node_count * 2 + 1));
            if (root == NULL) {
                return NULL;
            }
        }
        n = (char *) root->node + (root->node_size * root->node_count++);
    }

    memcpy(n, node, root->node_size);
    root->head = automatic_linked_list_add(root->head, n);
    return root;
}

void dynamic_linked_list_remove(void *root, search_func *fun, void *item) {
    struct dynamic_linked_list *r = root;
    void **n = &r->head;
    while (*n && fun(*n, item)) {
        n = &((struct automatic_linked_list_node *)*n)->next;
    }
    if (*n) {
        struct automatic_linked_list_node *node = *n;
        *n = node->next;
        *node = (struct automatic_linked_list_node){ .next = r->free };
        r->free = node;
    }
}

linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <stddef.h>

struct automatic_linked_list_node {
    void *next;
};

void *automatic_linked_list_add(void *root, void *node);
void *linked_list_next(void *node);
typedef int search_func(void *node, void *item);
void *automatic_linked_list_remove(void *root, search_func *fun, void *item);

struct dynamic_linked_list {
    void *head;
    struct automatic_linked_list_node *free;
    size_t node_size, node_count;
    struct automatic_linked_list_node node[];
};

struct dynamic_linked_list *linked_list_create(size_t node_size);
struct dynamic_linked_list *dynamic_linked_list_add(struct dynamic_linked_list *root, void *node);
void dynamic_linked_list_remove(void *root, search_func *fun, void *item);
#endif