# HG changeset patch
# User Matti Hamalainen <ccr@tnsp.org>
# Date 1288726271 -7200
# Node ID 4ec36204d34e962f5008e63941bd4f05cdc1ff9d
# Parent  26fe4dab7e783e970b22da6d7f44c21316b70910
Add doubly linked list handling functions.

diff -r 26fe4dab7e78 -r 4ec36204d34e th_util.c
--- a/th_util.c	Sat Oct 30 21:08:21 2010 +0300
+++ b/th_util.c	Tue Nov 02 21:31:11 2010 +0200
@@ -1,7 +1,7 @@
 /*
  * Generic utility-functions, macros and defaults
  * Programmed and designed by Matti 'ccr' Hamalainen
- * (C) Copyright 2002-2008 Tecnic Software productions (TNSP)
+ * (C) Copyright 2002-2010 Tecnic Software productions (TNSP)
  *
  * Please read file 'COPYING' for information on license and distribution.
  */
@@ -151,3 +151,246 @@
     return p;
 }
 #endif
+
+
+/* Doubly linked list handling
+ *
+ * In this implementation first node's prev points to last node of the list,
+ * and last node's next is NULL. This way we can semi-efficiently traverse to
+ * beginning and end of the list, assuming user does not do weird things.
+ */
+qlist_t * th_llist_new(void *data)
+{
+    qlist_t *res = th_calloc(sizeof(qlist_t), 1);
+    res->data = data;
+    return res;
+}
+
+void th_llist_free_func(qlist_t *list, void (*freefunc)(void *data))
+{
+    qlist_t *curr = list;
+
+    while (curr != NULL) {
+        qlist_t *next = curr->next;
+        if (freefunc != NULL && curr->data != NULL)
+            freefunc(curr->data);
+        th_free(curr);
+        curr = next;
+    }
+}
+
+
+void th_llist_free(qlist_t *list)
+{
+    th_llist_free_func(list, NULL);
+}
+
+void th_llist_append_node(qlist_t **list, qlist_t *node)
+{
+    if (*list != NULL) {
+        node->prev = (*list)->prev;
+        (*list)->prev->next = node;
+        (*list)->prev = node;
+        (*list)->num++;
+    } else {
+        *list = node;
+        node->prev = *list;
+        (*list)->num = 1;
+    }
+
+    node->next = NULL;
+}
+
+
+qlist_t *th_llist_append(qlist_t **list, void *data)
+{
+    qlist_t *node = th_llist_new(data);
+
+    th_llist_append_node(list, node);
+
+    return node;
+}
+
+
+void th_llist_prepend_node(qlist_t **list, qlist_t *node)
+{
+    if (*list != NULL) {
+        node->prev = (*list)->prev;
+        node->next = *list;
+        (*list)->prev = node;
+        node->num = (*list)->num + 1;
+        *list = node;
+    } else {
+        *list = node->prev = node;
+        node->next = NULL;
+        (*list)->num = 1;
+    }
+
+}
+
+
+qlist_t *th_llist_prepend(qlist_t **list, void *data)
+{
+    qlist_t *node = th_llist_new(data);
+
+    th_llist_prepend_node(list, node);
+
+    return node;
+}
+
+/*
+1) Remove a middle node
+
+    node0->prev->next = node->next (node1)
+    node0->next->prev = node->prev (list)
+
+    node2 <- list <=> node0 <=> node1 <=> node2 -> NULL
+    node2 <- list <=> node1 <=> node2 -> NULL
+
+2) Remove first node when many items
+
+
+    node2 <- list <=> node0 <=> node1 <=> node2 -> NULL
+    node2 <- node0 <=> node1 <=> node2 -> NULL
+
+    *list = node0
+
+3) Remove last node in list
+
+    if (node->next == NULL) {
+        list->prev = node->prev;
+        node->prev->next = NULL;
+    }
+
+    node2 <- list <=> node0 <=> node1 <=> node2 -> NULL
+    node1 <- list <=> node0 <=> node1 -> NULL
+
+4) Remove last
+
+    list <- list -> NULL
+    
+    
+*/
+static void th_llist_delete_node_fast(qlist_t **list, qlist_t *node)
+{
+    if (node == *list) {
+        /* First node in list */
+        qlist_t *tmp = (*list)->next;
+        if (tmp != NULL) {
+            tmp->num = (*list)->num - 1;
+            tmp->prev = (*list)->prev;
+        }
+        *list = tmp;
+    } else {
+        /* Somewhere in middle or end */
+        if (node->prev != NULL)
+            node->prev->next = node->next;
+
+        if (node->next != NULL)
+            node->next->prev = node->prev;
+        else
+            (*list)->prev = node; /* Last node */
+
+        (*list)->num--;
+    }
+    
+    node->next = node->prev = NULL;
+}
+
+
+void th_llist_delete_node(qlist_t **list, qlist_t *node)
+{
+    qlist_t *curr = *list;
+
+    while (curr != NULL) {
+        qlist_t *next = curr->next;
+        if (curr == node) {
+            th_llist_delete_node_fast(list, curr);
+            th_free(node);
+            break;
+        }
+        curr = next;
+    }
+}
+
+
+void th_llist_delete(qlist_t **list, const void *data)
+{
+    qlist_t *curr = *list;
+
+    while (curr != NULL) {
+        qlist_t *next = curr->next;
+        if (curr->data == data) {
+            th_llist_delete_node_fast(list, curr);
+            th_free(curr);
+            break;
+        }
+        curr = next;
+    }
+}
+
+
+qlist_t * th_llist_get_nth(qlist_t *list, const size_t n)
+{
+    qlist_t *curr = list;
+    size_t i;
+
+    for (i = 0; curr != NULL && i < n; curr = curr->next, i++);
+
+    return curr;
+}
+
+
+size_t th_llist_length(const qlist_t *list)
+{
+    if (list == NULL)
+        return 0;
+    else
+        return list->num;
+}
+
+
+ssize_t th_llist_position(const qlist_t *list, const qlist_t *node)
+{
+    const qlist_t *curr = list;
+    ssize_t i = 0;
+
+    while (curr != NULL) {
+        if (curr == node)
+            return i;
+        else
+            i++;
+
+        curr = curr->next;
+    }
+    
+    return -1;
+}
+
+
+qlist_t * th_llist_find(qlist_t *list, const void *data)
+{
+    qlist_t *curr = list;
+
+    while (curr != NULL) {
+        if (curr->data == data)
+            return curr;
+        curr = curr->next;
+    }
+
+    return NULL;
+}
+
+
+qlist_t * th_llist_find_func(qlist_t *list, const void *userdata, int (compare)(const void *, const void *))
+{
+    qlist_t *curr = list;
+
+    while (curr != NULL) {
+        if (compare(curr->data, userdata) == 0)
+            return curr;
+        curr = curr->next;
+    }
+
+    return NULL;
+}
diff -r 26fe4dab7e78 -r 4ec36204d34e th_util.h
--- a/th_util.h	Sat Oct 30 21:08:21 2010 +0300
+++ b/th_util.h	Tue Nov 02 21:31:11 2010 +0200
@@ -1,7 +1,7 @@
 /*
  * Generic utility-functions, macros and defaults
  * Programmed and designed by Matti 'ccr' Hamalainen
- * (C) Copyright 2002-2009 Tecnic Software productions (TNSP)
+ * (C) Copyright 2002-2010 Tecnic Software productions (TNSP)
  *
  * Please read file 'COPYING' for information on license and distribution.
  */
@@ -83,6 +83,33 @@
 void    *th_memset(void *, int, size_t);
 #endif
 
+
+/* Doubly linked list handling
+ */
+typedef struct _qlist_t {
+    void *data;
+    size_t num;
+    struct _qlist_t *prev, *next;
+} qlist_t;
+
+
+qlist_t * th_llist_new(void *data);
+void      th_llist_free(qlist_t *list);
+void      th_llist_free_func(qlist_t *list, void (*freefunc)(void *data));
+
+qlist_t * th_llist_append(qlist_t **list, void *data);
+qlist_t * th_llist_prepend(qlist_t **list, void *data);
+void      th_llist_delete(qlist_t **list, const void *data);
+void      th_llist_delete_node(qlist_t **list, qlist_t *node);
+
+qlist_t * th_llist_get_nth(qlist_t *list, const size_t n);
+size_t    th_llist_length(const qlist_t *list);
+ssize_t   th_llist_position(const qlist_t *list, const qlist_t *node);
+
+qlist_t * th_llist_find(qlist_t *list, const void *data);
+qlist_t * th_llist_find_func(qlist_t *list, const void *userdata, int (compare)(const void *, const void *));
+
+
 #ifdef __cplusplus
 }
 #endif