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