Rename ptrlist.[ch] to list.[ch]

1 files changed, 305 insertions, 0 deletions

diff --git a/list.c b/list.c
new file mode 100644
index 0000000..6f0996f
--- /dev/null
+++ b/list.c
@@ -0,0 +1,305 @@
+#include "config.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <string.h>
+#include <errno.h>
+
+#include "xmalloc.h"
+#include "list.h"
+
+/* ********************************************************************* */
+/* Tiny list immplementation.                                            */
+/*                                                                       */
+/* Each node contain a void pointer to some opaque data, these functions */
+/* will not try to allocate or free this data pointer.                   */
+/*                                                                       */
+/* Also accessors are not provided, the user has to directly manipulate  */
+/* the structure members (head, tail, len, data, prev, next)             */
+/* ********************************************************************* */
+
+/* ======================== */
+/* Create a new linked list */
+/* ======================== */
+ll_t *
+ll_new(void)
+{
+  ll_t * ret = xmalloc(sizeof(ll_t));
+  ll_init(ret);
+
+  return ret;
+}
+
+/* ======================== */
+/* Initialize a linked list */
+/* ======================== */
+void
+ll_init(ll_t * list)
+{
+  list->head = NULL;
+  list->tail = NULL;
+  list->len  = 0;
+}
+
+/* ==================================================== */
+/* Allocate the space for a new node in the linked list */
+/* ==================================================== */
+ll_node_t *
+ll_new_node(void)
+{
+  ll_node_t * ret = xmalloc(sizeof(ll_node_t));
+
+  if (ret == NULL)
+    errno = ENOMEM;
+
+  return ret;
+}
+
+/* ==================================================================== */
+/* Append a new node filled with its data at the end of the linked list */
+/* The user is responsible for the memory management of the data        */
+/* ==================================================================== */
+int
+ll_append(ll_t * const list, void * const data)
+{
+  int         ret = 1;
+  ll_node_t * node;
+
+  if (list)
+  {
+    node = ll_new_node();
+    if (node)
+    {
+      node->data = data;
+      node->next = NULL;
+
+      node->prev = list->tail;
+      if (list->tail)
+        list->tail->next = node;
+      else
+        list->head = node;
+
+      list->tail = node;
+
+      ++list->len;
+      ret = 0;
+    }
+  }
+
+  return ret;
+}
+
+/* =================================================================== */
+/* Put a new node filled with its data at the beginning of the linked  */
+/* list. The user is responsible for the memory management of the data */
+/* =================================================================== */
+int
+ll_prepend(ll_t * const list, void * const data)
+{
+  int         ret = 1;
+  ll_node_t * node;
+
+  if (list)
+  {
+    node = ll_new_node();
+    if (node)
+    {
+      node->data = data;
+      node->prev = NULL;
+
+      node->next = list->head;
+      if (list->head)
+        list->head->prev = node;
+      else
+        list->tail = node;
+
+      list->head = node;
+
+      ++list->len;
+      ret = 0;
+    }
+  }
+
+  return ret;
+}
+
+/* ======================================================= */
+/* Insert a new node before the specified node in the list */
+/* TODO test it                                           */
+/* ======================================================= */
+void
+ll_insert_before(ll_t * const list, ll_node_t * node, void * const data)
+{
+  ll_node_t * new_node;
+
+  if (list)
+  {
+    if (node->prev == NULL)
+      ll_prepend(list, data);
+    else
+    {
+      new_node = ll_new_node();
+      if (new_node)
+      {
+        new_node->data   = data;
+        new_node->next   = node;
+        new_node->prev   = node->prev;
+        node->prev->next = new_node;
+
+        ++list->len;
+      }
+    }
+  }
+}
+
+/* ====================================================== */
+/* Insert a new node after the specified node in the list */
+/* TODO test it                                           */
+/* ====================================================== */
+void
+ll_insert_after(ll_t * const list, ll_node_t * node, void * const data)
+{
+  ll_node_t * new_node;
+
+  if (list)
+  {
+    if (node->next == NULL)
+      ll_append(list, data);
+    else
+    {
+      new_node = ll_new_node();
+      if (new_node)
+      {
+        new_node->data   = data;
+        new_node->prev   = node;
+        new_node->next   = node->next;
+        node->next->prev = new_node;
+
+        ++list->len;
+      }
+    }
+  }
+}
+
+/* ====================================================== */
+/* Partition code for the quicksort function              */
+/* Based on code found here:                              */
+/* http://www.geeksforgeeks.org/quicksort-for-linked-list */
+/* ====================================================== */
+ll_node_t *
+ll_partition(ll_node_t * l, ll_node_t * h, int (*comp)(void *, void *),
+             void (*swap)(void *, void *))
+{
+  /* Considers last element as pivot, places the pivot element at its       */
+  /* correct position in sorted array, and places all smaller (smaller than */
+  /* pivot) to left of pivot and all greater elements to right of pivot     */
+  /* """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" */
+
+  /* Set pivot as h element */
+  /* """""""""""""""""""""" */
+  void * x = h->data;
+
+  ll_node_t * i = l->prev;
+  ll_node_t * j;
+
+  for (j = l; j != h; j = j->next)
+  {
+    if (comp(j->data, x) < 1)
+    {
+      i = (i == NULL) ? l : i->next;
+
+      swap(i->data, j->data);
+    }
+  }
+
+  i = (i == NULL) ? l : i->next;
+  swap(i->data, h->data);
+
+  return i;
+}
+
+/* ======================================================= */
+/* A recursive implementation of quicksort for linked list */
+/* ======================================================= */
+void
+ll_quicksort(ll_node_t * l, ll_node_t * h, int (*comp)(void *, void *),
+             void (*swap)(void * a, void *))
+{
+  if (h != NULL && l != h && l != h->next)
+  {
+    ll_node_t * p = ll_partition(l, h, comp, swap);
+    ll_quicksort(l, p->prev, comp, swap);
+    ll_quicksort(p->next, h, comp, swap);
+  }
+}
+
+/* =========================== */
+/* A linked list sort function */
+/* =========================== */
+void
+ll_sort(ll_t * list, int (*comp)(void *, void *),
+        void (*swap)(void * a, void *))
+{
+  /* Call the recursive ll_quicksort function */
+  /* """""""""""""""""""""""""""""""""""""""" */
+  ll_quicksort(list->head, list->tail, comp, swap);
+}
+
+/* ================================ */
+/* Remove a node from a linked list */
+/* ================================ */
+int
+ll_delete(ll_t * const list, ll_node_t * node)
+{
+  if (list->head == list->tail)
+  {
+    if (list->head != NULL)
+      list->head = list->tail = NULL;
+    else
+      return 0;
+  }
+  else if (node->prev == NULL)
+  {
+    list->head       = node->next;
+    list->head->prev = NULL;
+  }
+  else if (node->next == NULL)
+  {
+    list->tail       = node->prev;
+    list->tail->next = NULL;
+  }
+  else
+  {
+    node->next->prev = node->prev;
+    node->prev->next = node->next;
+  }
+
+  free(node);
+
+  --list->len;
+
+  return 1;
+}
+
+/* =========================================================================*/
+/* Find a node in the list containing data. Return the node pointer or NULL */
+/* if not found.                                                            */
+/* A comparison function must be provided to compare a and b (strcmp like). */
+/* =========================================================================*/
+ll_node_t *
+ll_find(ll_t * const list, void * const data,
+        int (*cmpfunc)(const void * a, const void * b))
+{
+  ll_node_t * node;
+
+  if (NULL == (node = list->head))
+    return NULL;
+
+  do
+  {
+    if (0 == cmpfunc(node->data, data))
+      return node;
+  } while (NULL != (node = node->next));
+
+  return NULL;
+}