/* ########################################################### */
/* This Software is licensed under the GPL licensed Version 2, */
/* please read http://www.gnu.org/copyleft/gpl.html            */
/* ########################################################### */

/* ********************************************************************* */
/* Tiny linked list implementation.                                      */
/*                                                                       */
/* 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)             */
/* ********************************************************************* */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <errno.h>

#include "xmalloc.h"
#include "list.h"

/* ======================== */
/* 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;
}