ucx/list.c@e0ec80179a5d
ucx/list.c
Wed, 27 Feb 2013 16:59:02 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Wed, 27 Feb 2013 16:59:02 +0100
- changeset 100
- e0ec80179a5d
- parent 93
- a6a99e721660
- child 103
- 08018864fb91
- permissions
- -rw-r--r--
happy 100th commit + removed deprecated sstrcat + fixed sstrncat
1 #include "list.h"
3 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) {
4 UcxList *ret = NULL;
5 while (l != NULL) {
6 if (fnc != NULL) {
7 ret = ucx_list_append(ret, fnc(l->data, data));
8 } else {
9 ret = ucx_list_append(ret, l->data);
10 }
11 l = l->next;
12 }
13 return ret;
14 }
16 int ucx_list_equals(const UcxList *l1, const UcxList *l2,
17 cmp_func fnc, void* data) {
18 if (l1 == l2) return 1;
20 while (l1 != NULL && l2 != NULL) {
21 if (fnc == NULL) {
22 if (l1->data != l2->data) return 0;
23 } else {
24 if (fnc(l1->data, l2->data, data) != 0) return 0;
25 }
26 l1 = l1->next;
27 l2 = l2->next;
28 }
30 return (l1 == NULL && l2 == NULL);
31 }
33 void ucx_list_free(UcxList *l) {
34 UcxList *e = l, *f;
35 while (e != NULL) {
36 f = e;
37 e = e->next;
38 free(f);
39 }
40 }
42 UcxList *ucx_list_append(UcxList *l, void *data) {
43 UcxList *nl = (UcxList*) malloc(sizeof(UcxList));
44 if (nl == NULL) return NULL;
46 nl->data = data;
47 nl->next = NULL;
48 if (l == NULL) {
49 return nl;
50 } else {
51 UcxList *t = ucx_list_last(l);
52 t->next = nl;
53 return l;
54 }
55 }
57 UcxList *ucx_list_prepend(UcxList *l, void *data) {
58 UcxList *nl = ucx_list_append(NULL, data);
59 if (nl == NULL) return NULL;
61 if (l != NULL) {
62 nl->next = l;
63 }
64 return nl;
65 }
67 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) {
68 if (l1 == NULL) {
69 return l2;
70 } else {
71 UcxList *last = ucx_list_last(l1);
72 last->next = l2;
73 return l1;
74 }
75 }
77 UcxList *ucx_list_last(const UcxList *l) {
78 if (l == NULL) return NULL;
80 const UcxList *e = l;
81 while (e->next != NULL) {
82 e = e->next;
83 }
84 return (UcxList*)e;
85 }
87 UcxList *ucx_list_get(const UcxList *l, int index) {
88 if (l == NULL) return NULL;
90 const UcxList *e = l;
91 while (e->next != NULL && index > 0) {
92 e = e->next;
93 index--;
94 }
96 return (UcxList*)(index == 0 ? e : NULL);
97 }
99 int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
100 UCX_FOREACH(UcxList*, l, e) {
101 if (!fnc(elem, e->data, cmpdata)) {
102 return 1;
103 }
104 }
105 return 0;
106 }
108 size_t ucx_list_size(const UcxList *l) {
109 if (l == NULL) return 0;
111 const UcxList *e = l;
112 size_t s = 1;
113 while (e->next != NULL) {
114 e = e->next;
115 s++;
116 }
118 return s;
119 }
121 UcxList *ucx_list_sort_merge(int length,
122 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,
123 cmp_func fnc, void* data) {
125 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);
126 UcxList *rc, *lc;
128 lc = ls; rc = le;
129 int n = 0;
130 while (lc && lc != le && rc != re) {
131 if (fnc(lc->data, rc->data, data) <= 0) {
132 sorted[n] = lc;
133 lc = lc->next;
134 } else {
135 sorted[n] = rc;
136 rc = rc->next;
137 }
138 n++;
139 }
140 while (lc && lc != le) {
141 sorted[n] = lc;
142 lc = lc->next;
143 n++;
144 }
145 while (rc && rc != re) {
146 sorted[n] = rc;
147 rc = rc->next;
148 n++;
149 }
151 // Update pointer
152 for (int i = 0 ; i < length-1 ; i++) {
153 sorted[i]->next = sorted[i+1];
154 }
155 sorted[length-1]->next = NULL;
157 UcxList *ret = sorted[0];
158 free(sorted);
159 return ret;
160 }
162 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
163 if (l == NULL) {
164 return NULL;
165 }
167 UcxList *lc;
168 int ln = 1;
170 UcxList *restrict ls = l, *restrict le, *restrict re;
171 lc = ls;
172 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
173 lc = lc->next;
174 ln++;
175 }
176 le = lc->next;
178 if (le == NULL) {
179 return l; // this list is already sorted :)
180 } else {
181 UcxList *rc;
182 int rn = 1;
183 rc = le;
184 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
185 rc = rc->next;
186 rn++;
187 }
188 re = rc->next;
190 // Something left? Sort it!
191 UcxList *remainder = re;
192 size_t remainder_length = ucx_list_size(remainder);
193 if (remainder != NULL) {
194 remainder = ucx_list_sort(remainder, fnc, data);
195 }
197 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
198 UcxList *sorted = ucx_list_sort_merge(ln+rn,
199 ls, le, re,
200 fnc, data);
202 // merge sorted list with (also sorted) remainder
203 l = ucx_list_sort_merge(ln+rn+remainder_length,
204 sorted, remainder, NULL, fnc, data);
206 return l;
207 }
208 }
210 /* list specific functions */
211 UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
212 if (e == l) {
213 l = e->next;
214 free(e);
215 } else {
216 UcxList *f = l;
217 while (f->next != NULL && f->next != e) {
218 f = f->next;
219 }
220 /* perform remove if this element is found in this list */
221 if (f->next == e) {
222 f->next = e->next;
223 free(e);
224 }
225 }
226 return l;
227 }
