From 492bff46bdaca15d66ccb37badcda0876ea2a468 Mon Sep 17 00:00:00 2001
From: Dana Jansens <danakj@orodu.net>
Date: Tue, 4 Mar 2008 17:26:24 -0500
Subject: [PATCH] add a list data structure that's much more efficient that
 glists

---
 list.c | 150 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 list.h |  30 ++++++++++++
 2 files changed, 180 insertions(+)
 create mode 100644 list.c
 create mode 100644 list.h

diff --git a/list.c b/list.c
new file mode 100644
index 0000000..83ae21e
--- /dev/null
+++ b/list.c
@@ -0,0 +1,150 @@
+#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;
+}
diff --git a/list.h b/list.h
new file mode 100644
index 0000000..f35ae8b
--- /dev/null
+++ b/list.h
@@ -0,0 +1,30 @@
+#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
-- 
2.34.1