Functional-style linked list written in C

Question

For my Operating Systems class, I needed a linked list data structure and didn't have one already written. During the course of thinking about how to implement a linked list again (it had been a while..), I decided that a lot of the most common functions used on linked lists can be implemented based on applying or composing a few core functions.

First, I wrote a function that iterates over the list starting from list->head while applying a function to each element. After each iteration, if the function returned false, then stop iterating and return a pointer to the node which terminated the loop. Otherwise, iterate until list->tail had the function applied to it.

Basically all of the rest of my functions fall from this one function. I was able to quickly implement map by calling the iteration function and always returning true (and therefore the iteration will never end prematurely). I was also able to implement a general iterative "test" function, which requires a function parameter that accepts two node arguments and produces a boolean. The point of the iterative test function is to implement things like sorting or testing for equality in a composable way.

I think my attempt isn't half bad, given that I was writing in C without any anonymous functions or closures (of which my knowledge is limited). That being said, I'm glad to hear what criticisms the community has on the implementation on a whole or nit-picking.

llist.h

#ifndef LLIST_H
#define LLIST_H
/* Fields */
typedef struct _node {
 struct _node *next, *prev;
 void *data;
} node;
typedef struct {
 node *head, *tail;
 size_t size;
} llist;
typedef enum {FALSE, TRUE} bool;
typedef void (*nodefunc)(node *);
typedef bool (*nodeiter)(node *);
typedef bool (*nodetest)(void *, void *);
/* Methods */
void llist_init(llist *l);
void llist_node_init(node *n);
void map(llist *l, nodefunc f);
void *llist_iter(llist *l, nodeiter f);
void *llist_test(llist *l, void *q, nodetest t);
void llist_append(llist *l, node *n);
void llist_remove(llist *l, node *n);
void llist_destroy(llist *l, nodefunc node_free);
#endif

llist.c

#include <stdlib.h>
#include "llist.h"
void llist_init(llist *l) {
 l->head = NULL;
 l->tail = NULL;
 l->size = 0;
}
void llist_node_init(node *n) {
 n->data = NULL;
 n->next = NULL;
 n->prev = NULL;
}
void *llist_iter(llist *l, nodeiter f) {
 node *n = l->head, *next = NULL;
 void *result = 0;
 while (n != NULL && result == 0) {
 next = n->next;
 if (!f(n))
 result = (void*)n;
 n = next;
 }
 return result;
}
void *llist_test(llist *l, void *q, nodetest t) {
 bool iter_test(node *n) {
 return !( t((void*)n->data, q) );
 }
 return llist_iter(l, iter_test);
}
// not a true map since f can have side effects
void map(llist *l, nodefunc f) {
 bool iter_true(node *n) {
 f(n);
 return TRUE;
 }
 llist_iter(l, iter_true);
}
void llist_append(llist *l, node *n) {
 if (l->size == 0) {
 l->head = n;
 l->tail = n;
 } else {
 n->prev = l->tail;
 l->tail->next = n;
 l->tail = n;
 }
 l->size++;
}
void llist_remove(llist *l, node *n) {
 if (n) {
 if (n->prev)
 n->prev->next = n->next;
 else
 l->head = n->next;
 if (n->next)
 n->next->prev = n->prev;
 else
 l->tail = n->prev;
 l->size--;
 }
}
void llist_destroy(llist *l, nodefunc node_free) {
 void iter_remove(node *n) {
 llist_remove(l, n);
 node_free(n);
 }
 map(l, iter_remove);
}

From this, I'm able to implement in a program, for example, a print function based on the type of data that is stored in the linked list:

llist_test.c

#include <stdio.h>
#include <stdlib.h>
#include "llist.h"
void llist_print(llist *l) {
 void iter_print(node *n) {
 printf("value: %d\n", *(int*)n->data);
 }
 map(l, iter_print);
}
void node_free(node *n) { free(n); }
node *alloc_node(int *data) {
 node *n = malloc(sizeof(node));
 llist_node_init(n);
 n->data = data;
 return n;
}
int main() {
 llist *l = malloc(sizeof(llist));
 llist_init(l);
 int x = 4, y = 8;
 llist_append(l, alloc_node(&x));
 // ...
 llist_destroy(l, node_free);
 free(l);
 return 0;
}

Answer 1

C Standard doesn't allow nested functions. A strictly conforming compiler must fail to compile llist_test and friends. If you are OK with deviating from Standard, take a look at blocks, which are considered much more secure and have a chance (unlike nested functions) to eventually get into Standard.

• itsjareds: Oof. Thanks for the information. This is actually really important for me because my instructor might be compiling with clang, not gcc. That didn't even occur to me until now.

Answer 2

• Linked lists come in all sorts of flavors--singly linked, doubly linked, circularly linked, .... Instead of using 'll' as the prefix (presumably for linked list), I would suggest using 'dll' for doubly linked list.
• Watch your namespace pollution. 'node' and '_node' are fairly generic names and it is not unreasonable to expect that a module that includes this header file could define structures of that type. Minimize the expected namespace collision by naming this structure type as '_dllnode' or 'dllnode'.
• If you want a 'bool' type, I would suggest including 'stdbool.h' instead of defining your own. stdbool.h defines 'true' and 'false'. If memory serves, this is something that is for C99 and later.
• If you are going to typedef the function pointers, it may be beneficial to change the names to make it easier to identify that these are function pointer typedefs.
• The name 'map()' appears out of place. All the other routines that operate on a list have a 'llist_' prefix. Consistency is important.
• As a user of this, I would have expected to see a routine named 'llist_insert' for inserting a node into an arbitrary point in the linked list.
• This may be a matter of preference, but for a general linked list implementation, I don't think the linked list node should have any references to the data (pointer or otherwise). If you want a node with data ...

struct my_node {
 dll_node node;
 <data>
};

• Following the previous, llist_destroy() should be implemented at a higher level. There are going to be lots of times when the user of this module may want the benefits of a linked list, but do not want to dynamically allocate the elements.
• llist_node_init() should initialize the structure fields in the same order as they were declared. This makes it easier to ensure that items were not missed.
• As a personal preference, I like to see one variable defined per line. (This is highly subjective).
• In llist_iter(), 'result' is a pointer and should be initialized to NULL, not 0. Similarly, it should be compared against NULL in the loop.
• Better yet, rewrite llist_iter() to eliminate the need for 'result' and some unnecessary assignments of 'n' when leaving the loop.

while (n != NULL) {
 if (!f(n)) {
 return (void *)n;
 }
 n = n->next;
}
return NULL;

• Someone else has already mentioned nested functions, so I won't go into more on that.
• What is meant by a 'true map'? What is meant by 'map'?
• In llist_remove(), I would suggest that you avoid one level of indentation by returning early if 'n' is NULL.

Hope this helps.