--- /dev/null
+#include "list.h"
+#include <assert.h>
+#include <stdlib.h>
+
+struct d_list {
+ d_list_it_t *top;
+ d_list_it_t *bottom;
+ int len;
+ int ref;
+};
+
+#define check_list(list) \
+ assert((list->len == 0 && !list->top && !list->bottom) || \
+ (list->len > 0 && list->top && list->bottom))
+
+
+d_list_t*
+list_new(void)
+{
+ d_list_t *list = malloc(sizeof(d_list_t));
+ list->top = NULL;
+ list->bottom = NULL;
+ list->ref = 1;
+ list->len = 0;
+ return list;
+}
+
+void
+list_ref(d_list_t *list)
+{
+ ++list->ref;
+}
+
+void
+list_unref(d_list_t *list)
+{
+ if (list && --list->ref == 0) {
+ while (list->len)
+ list_delete_link(list, list->top);
+ free(list);
+ }
+}
+
+d_list_it_t*
+list_prepend(d_list_t *list, void *data)
+{
+ d_list_it_t *n = malloc(sizeof(d_list_it_t));
+ n->data = data;
+
+ n->prev = NULL;
+ n->next = list->top;
+ if (n->next) n->next->prev = n;
+
+ list->top = n;
+ if (!list->bottom) list->bottom = n;
+ ++list->len;
+ return n;
+}
+
+void
+list_delete_link(d_list_t *list, d_list_it_t *pos)
+{
+ d_list_it_t *prev = pos->prev;
+ d_list_it_t *next = pos->next;
+
+ if (next)
+ next->prev = prev;
+ if (prev)
+ prev->next = next;
+ if (!next) {
+ assert(list->bottom == pos);
+ list->bottom = prev;
+ }
+ if (!prev) {
+ assert(list->top == pos);
+ list->top = next;
+ }
+
+ --list->len;
+ check_list(list);
+ free(pos);
+}
+
+void
+list_move_before(d_list_t *list, d_list_it_t *move, d_list_it_t *before)
+{
+ d_list_it_t *prev, *next;
+
+ /* these won't move it anywhere */
+ if (move == before || move->next == before) return;
+
+ prev = move->prev;
+ next = move->next;
+
+ /* remove it from the list */
+ if (next) next->prev = prev;
+ else list->bottom = prev;
+ if (prev) prev->next = next;
+ else list->top = next;
+
+ /* reinsert it */
+ if (before) {
+ move->next = before;
+ move->prev = before->prev;
+ move->next->prev = move;
+ if (move->prev) move->prev->next = move;
+ }
+ else {
+ /* after the bottom */
+ move->prev = list->bottom;
+ move->next = NULL;
+ if (move->prev) move->prev->next = move;
+ list->bottom = move;
+ }
+
+ if (!move->prev) list->top = move;
+}
+
+int
+list_length(d_list_t *list)
+{
+ return list->len;
+}
+
+d_list_it_t*
+list_top(d_list_t *list)
+{
+ return list->top;
+}
+
+d_list_it_t*
+list_bottom(d_list_t *list)
+{
+ return list->bottom;
+}
+
+d_list_it_t*
+list_nth(d_list_t *list, int n)
+{
+ int i;
+ d_list_it_t *it;
+
+ assert(n >= 0);
+ assert(n < list->len);
+
+ it = list->top;
+ for (i = 0; i < n; ++i)
+ it = it->next;
+ return it;
+}
--- /dev/null
+#ifndef dc__list_h
+#define dc__list_h
+
+/* To make a new list, create 2 pointers: one for the head, one for the
+ tail. Initialize them both to NULL. Then pass them to loco_list_prepend.
+*/
+
+typedef struct d_list d_list_t;
+
+typedef struct d_list_it {
+ struct d_list_it *next;
+ struct d_list_it *prev;
+ void *data;
+} d_list_it_t;
+
+d_list_t* list_new(void);
+
+void list_ref(d_list_t *list);
+void list_unref(d_list_t *list);
+
+d_list_it_t* list_prepend(d_list_t *list, void *data);
+void list_delete_link(d_list_t *list, d_list_it_t *pos);
+void list_move_before(d_list_t *list, d_list_it_t *move, d_list_it_t *before);
+
+int list_length(d_list_t *list);
+d_list_it_t* list_top(d_list_t *list);
+d_list_it_t* list_bottom(d_list_t *list);
+d_list_it_t* list_nth(d_list_t *list, int n);
+
+#endif