1 /*
2 * linklist.c -- generic linked list
3 *
4 * Yet Another FTP Client
5 * Copyright (C) 1998-2001, Martin Hedenfalk <mhe@stacken.kth.se>
6 * Copyright (C) 2015, Sebastian RAmacher <sebastian+dev@ramacher.at>
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version. See COPYING for more details.
12 */
13
14 #include "syshdr.h"
15
16 #include "linklist.h"
17 #include "xmalloc.h"
18
new_item(void)19 static listitem *new_item(void)
20 {
21 return xmalloc(sizeof(listitem));
22 }
23
list_new(listfunc freefunc)24 list *list_new(listfunc freefunc)
25 {
26 list* lp = xmalloc(sizeof(list));
27 lp->freefunc = freefunc;
28 lp->first = NULL;
29 lp->last = NULL;
30 return lp;
31 }
32
list_free(list * lp)33 void list_free(list *lp)
34 {
35 list_clear(lp);
36 free(lp);
37 }
38
list_clear(list * lp)39 void list_clear(list *lp)
40 {
41 if (!lp)
42 return;
43
44 while (lp->first)
45 list_delitem(lp, lp->first);
46 }
47
list_search(list * lp,listsearchfunc cmpfunc,const void * arg)48 listitem *list_search(list *lp, listsearchfunc cmpfunc, const void *arg)
49 {
50 if(!lp)
51 return NULL;
52
53 listitem* lip = lp->first;
54 while (lip)
55 {
56 if (cmpfunc(lip->data, arg) == 0)
57 return lip;
58 lip = lip->next;
59 }
60 return NULL;
61 }
62
list_delitem(list * lp,listitem * lip)63 void list_delitem(list *lp, listitem *lip)
64 {
65 if (!lp || !lp->first)
66 return;
67
68 if (lp->freefunc)
69 lp->freefunc(lip->data);
70
71 list_removeitem(lp, lip);
72 free(lip);
73 }
74
list_additem(list * lp,void * data)75 void list_additem(list *lp, void *data)
76 {
77 if (!lp)
78 return;
79
80 listitem* lip = new_item();
81 lip->data = data;
82 lip->next = NULL;
83 lip->prev = NULL;
84
85 if (!lp->first)
86 lp->last = lp->first = lip;
87 else
88 {
89 listitem* current_last = lp->last;
90 lip->prev = current_last;
91 current_last->next = lip;
92 lp->last = lip;
93 }
94 lp->numitem++;
95 }
96
list_numitem(list * lp)97 size_t list_numitem(list *lp)
98 {
99 if (!lp)
100 return 0;
101
102 return lp->numitem;
103 }
104
list_swap(list * lp,listitem * a,listitem * b)105 static void list_swap(list *lp, listitem *a, listitem *b)
106 {
107 if (!a || !b || a->data == b->data)
108 return;
109
110 void* tmp = a->data;
111 a->data = b->data;
112 b->data = tmp;
113 }
114
115 /* simple bubble-sort */
list_sort(list * lp,listsortfunc cmp,bool reverse)116 void list_sort(list *lp, listsortfunc cmp, bool reverse)
117 {
118 listitem *last = NULL;
119 bool swapped = true;
120
121 while (swapped)
122 {
123 swapped = false;
124 for (listitem* li = lp->first; li && li->next; li = li->next)
125 {
126 if (li->next == last)
127 {
128 last = li;
129 break;
130 }
131 const int c = cmp(li->data, li->next->data);
132 if (reverse ? c < 0 : c > 0)
133 {
134 list_swap(lp, li, li->next);
135 swapped = true;
136 }
137 }
138 }
139 }
140
list_removeitem(list * lp,listitem * lip)141 void list_removeitem(list *lp, listitem *lip)
142 {
143 if (!lp || !lp->first)
144 return;
145
146 if (lip->prev)
147 lip->prev->next = lip->next;
148 else
149 lp->first = lip->next;
150 if (lip->next)
151 lip->next->prev = lip->prev;
152 else
153 lp->last = lip->prev;
154 lp->numitem--;
155 }
156
list_clone(list * lp,listclonefunc clonefunc)157 list *list_clone(list *lp, listclonefunc clonefunc)
158 {
159 if (!lp || !clonefunc)
160 return NULL;
161
162 list* cloned = list_new(lp->freefunc);
163 for (listitem* li = lp->first; li; li = li->next)
164 list_additem(cloned, clonefunc(li->data));
165
166 return cloned;
167 }
168
list_equal(list * a,list * b,listsortfunc cmpfunc)169 int list_equal(list *a, list *b, listsortfunc cmpfunc)
170 {
171 if (a == b)
172 return 1;
173
174 if (list_numitem(a) != list_numitem(b) || a == 0 || b == 0)
175 return 0;
176
177 for (listitem* ai = a->first, *bi = b->first; ai && bi; ai = ai->next, bi = bi->next)
178 {
179 if (cmpfunc(ai->data, bi->data) != 0)
180 return 0;
181 }
182 return 1;
183 }
184