list.c

   1 /* ################################################################### */
   2 /* Copyright 2015, Pierre Gentile (p.gen.progs@gmail.com)              */
   3 /*                                                                     */
   4 /* This Source Code Form is subject to the terms of the Mozilla Public */
   5 /* License, v. 2.0. If a copy of the MPL was not distributed with this */
   6 /* file, You can obtain one at https://mozilla.org/MPL/2.0/.           */
   7 /* ################################################################### */
   8
   9 /* ********************************************************************* */
  10 /* Tiny linked list implementation.                                      */
  11 /*                                                                       */
  12 /* Each node contain a void pointer to some opaque data, these functions */
  13 /* will not try to allocate or free this data pointer.                   */
  14 /*                                                                       */
  15 /* Also accessors are not provided, the user has to directly manipulate  */
  16 /* the structure members (head, tail, len, data, prev, next).            */
  17 /* ********************************************************************* */
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <limits.h>
  22 #include <string.h>
  23 #include <errno.h>
  24
  25 #include "xmalloc.h"
  26 #include "list.h"
  27
  28 static ll_node_t *
  29 ll_partition(ll_node_t *l,
  30              ll_node_t *h,
  31              int (*comp)(void const *, void const *),
  32              void (*swap)(void **, void **));
  33
  34 static void
  35 ll_quicksort(ll_node_t *l,
  36              ll_node_t *h,
  37              int (*comp)(void const *, void const *),
  38              void (*swap)(void **, void **));
  39
  40 /* ========================== */
  41 /* Creates a new linked list. */
  42 /* ========================== */
  43 ll_t *
  44 ll_new(void)
  45 {
  46   ll_t *ret = xmalloc(sizeof(ll_t));
  47   ll_init(ret);
  48
  49   return ret;
  50 }
  51
  52 /* ========================== */
  53 /* Initializes a linked list. */
  54 /* ========================== */
  55 void
  56 ll_init(ll_t *list)
  57 {
  58   list->head = NULL;
  59   list->tail = NULL;
  60   list->len  = 0;
  61 }
  62
  63 /* ====================================================== */
  64 /* Allocates the space for a new node in the linked list. */
  65 /* ====================================================== */
  66 ll_node_t *
  67 ll_new_node(void)
  68 {
  69   return xmalloc(sizeof(ll_node_t));
  70 }
  71
  72 /* ====================================================================== */
  73 /* Appends a new node filled with its data at the end of the linked list. */
  74 /* The user is responsible for the memory management of the data.         */
  75 /*                                                                        */
  76 /* Note: list is assumed to be initialized by ll_new().                   */
  77 /* ====================================================================== */
  78 void
  79 ll_append(ll_t * const list, void * const data)
  80 {
  81   ll_node_t *node;
  82
  83   node = ll_new_node(); /* ll_new_node cannot return NULL because it   *
  84                          | uses xmalloc which does not return if there *
  85                          | is an allocation error.                     */
  86
  87   node->data = data;
  88   node->next = NULL;       /* This node will be the last. */
  89   node->prev = list->tail; /* NULL if it is a new list.   */
  90
  91   if (list->tail != NULL)
  92     list->tail->next = node;
  93   else
  94     list->head = node;
  95
  96   list->tail = node;
  97
  98   ++list->len; /* One more node in the list. */
  99 }
 100
 101 /* ================================== */
 102 /* Removes a node from a linked list. */
 103 /* ================================== */
 104 int
 105 ll_delete(ll_t * const list, ll_node_t *node)
 106 {
 107   if (list->head == list->tail)
 108   {
 109     /* We delete the last remaining element from the list. */
 110     /* """"""""""""""""""""""""""""""""""""""""""""""""""" */
 111     if (list->head == NULL)
 112       return 0;
 113
 114     list->head = list->tail = NULL;
 115   }
 116   else if (node->prev == NULL)
 117   {
 118     /* We delete the first element from the list. */
 119     /* """""""""""""""""""""""""""""""""""""""""" */
 120     list->head       = node->next;
 121     list->head->prev = NULL;
 122   }
 123   else if (node->next == NULL)
 124   {
 125     /* We delete the last element from the list. */
 126     /* """"""""""""""""""""""""""""""""""""""""" */
 127     list->tail       = node->prev;
 128     list->tail->next = NULL;
 129   }
 130   else
 131   {
 132     /* We delete an element from the list. */
 133     /* """"""""""""""""""""""""""""""""""" */
 134     node->next->prev = node->prev;
 135     node->prev->next = node->next;
 136   }
 137
 138   free(node);
 139
 140   --list->len; /* One less node in the list. */
 141
 142   return 1;
 143 }
 144
 145 /* ====================================================== */
 146 /* Partition code for the quicksort function.             */
 147 /* Based on code found here:                              */
 148 /* http://www.geeksforgeeks.org/quicksort-for-linked-list */
 149 /* ====================================================== */
 150 static ll_node_t *
 151 ll_partition(ll_node_t *l,
 152              ll_node_t *h,
 153              int (*comp)(void const *, void const *),
 154              void (*swap)(void **, void **))
 155 {
 156   /* Considers last element as pivot, places the pivot element at its       */
 157   /* correct position in sorted array, and places all smaller (smaller than */
 158   /* pivot) to left of pivot and all greater elements to right of pivot.    */
 159   /* """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" */
 160
 161   /* Set pivot as h element. */
 162   /* """"""""""""""""""""""" */
 163   void *x = h->data;
 164
 165   ll_node_t *i = l->prev;
 166   ll_node_t *j;
 167
 168   for (j = l; j != h; j = j->next)
 169   {
 170     if (comp(j->data, x) < 1)
 171     {
 172       i = (i == NULL) ? l : i->next;
 173
 174       swap(&(i->data), &(j->data));
 175     }
 176   }
 177
 178   i = (i == NULL) ? l : i->next;
 179   swap(&(i->data), &(h->data));
 180
 181   return i;
 182 }
 183
 184 /* ======================================================== */
 185 /* A recursive implementation of quicksort for linked list. */
 186 /* Based on code found here:                                */
 187 /* http://www.geeksforgeeks.org/quicksort-for-linked-list   */
 188 /* ======================================================== */
 189 static void
 190 ll_quicksort(ll_node_t *l,
 191              ll_node_t *h,
 192              int (*comp)(void const *, void const *),
 193              void (*swap)(void **, void **))
 194 {
 195   if (h != NULL && l != h && l != h->next)
 196   {
 197     ll_node_t *p = ll_partition(l, h, comp, swap);
 198     ll_quicksort(l, p->prev, comp, swap);
 199     ll_quicksort(p->next, h, comp, swap);
 200   }
 201 }
 202
 203 /* ============================ */
 204 /* A linked list sort function. */
 205 /* ============================ */
 206 void
 207 ll_sort(ll_t *list,
 208         int (*comp)(void const *, void const *),
 209         void (*swap)(void **, void **))
 210 {
 211   /* Call the recursive ll_quicksort function. */
 212   /* """"""""""""""""""""""""""""""""""""""""" */
 213   ll_quicksort(list->head, list->tail, comp, swap);
 214 }
 215
 216 /* ==========================================================================*/
 217 /* Finds a node in the list containing data. Return the node pointer or NULL */
 218 /* if not found.                                                             */
 219 /* A comparison function must be provided to compare a and b (strcmp like).  */
 220 /* ==========================================================================*/
 221 ll_node_t *
 222 ll_find(ll_t * const list,
 223         void * const data,
 224         int (*cmpfunc)(const void *, const void *))
 225 {
 226   ll_node_t *node;
 227
 228   if (NULL == (node = list->head))
 229     return NULL;
 230
 231   do
 232   {
 233     if (0 == cmpfunc(node->data, data))
 234       return node;
 235   } while (NULL != (node = node->next));
 236
 237   return NULL;
 238 }
 239
 240 /* =============================================== */
 241 /* Free all the elements of a list (make it empty) */
 242 /* NULL or a custom function may be used to free   */
 243 /* the sub components of the elements.             */
 244 /* =============================================== */
 245 void
 246 ll_free(ll_t * const list, void (*clean)(void *))
 247 {
 248   if (list != NULL)
 249   {
 250     ll_node_t *node = list->head;
 251
 252     while (node)
 253     {
 254       /* Apply a custom cleaner if not NULL. */
 255       /* """"""""""""""""""""""""""""""""""" */
 256       if (clean)
 257         clean(node->data);
 258
 259       ll_delete(list, node);
 260
 261       node = list->head;
 262     }
 263   }
 264 }
 265
 266 /* ==================================== */
 267 /* Destroy a list and all its elements. */
 268 /* ==================================== */
 269 void
 270 ll_destroy(ll_t *list, void (*clean)(void *))
 271 {
 272   if (list != NULL)
 273   {
 274     ll_free(list, clean);
 275     free(list);
 276   }
 277 }