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;
}
