|
1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
|
3 * |
|
4 * Copyright 2013 Olaf Wintermann. All rights reserved. |
|
5 * |
|
6 * Redistribution and use in source and binary forms, with or without |
|
7 * modification, are permitted provided that the following conditions are met: |
|
8 * |
|
9 * 1. Redistributions of source code must retain the above copyright |
|
10 * notice, this list of conditions and the following disclaimer. |
|
11 * |
|
12 * 2. Redistributions in binary form must reproduce the above copyright |
|
13 * notice, this list of conditions and the following disclaimer in the |
|
14 * documentation and/or other materials provided with the distribution. |
|
15 * |
|
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
|
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
|
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
|
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
|
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
|
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
|
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
|
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
|
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
|
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
|
26 * POSSIBILITY OF SUCH DAMAGE. |
|
27 */ |
|
28 |
1 #include "list.h" |
29 #include "list.h" |
2 |
30 |
3 UcxList *restrict ucx_list_clone(UcxList *restrict l, |
31 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { |
|
32 return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data); |
|
33 } |
|
34 |
|
35 UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l, |
4 copy_func fnc, void *data) { |
36 copy_func fnc, void *data) { |
5 UcxList *ret = NULL; |
37 UcxList *ret = NULL; |
6 while (l != NULL) { |
38 while (l) { |
7 if (fnc != NULL) { |
39 if (fnc) { |
8 ret = ucx_list_append(ret, fnc(l->data, data)); |
40 ret = ucx_list_append_a(alloc, ret, fnc(l->data, data)); |
9 } else { |
41 } else { |
10 ret = ucx_list_append(ret, l->data); |
42 ret = ucx_list_append_a(alloc, ret, l->data); |
11 } |
43 } |
12 l = l->next; |
44 l = l->next; |
13 } |
45 } |
14 return ret; |
46 return ret; |
15 } |
47 } |
30 |
62 |
31 return (l1 == NULL && l2 == NULL); |
63 return (l1 == NULL && l2 == NULL); |
32 } |
64 } |
33 |
65 |
34 void ucx_list_free(UcxList *l) { |
66 void ucx_list_free(UcxList *l) { |
|
67 ucx_list_free_a(ucx_default_allocator(), l); |
|
68 } |
|
69 |
|
70 void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) { |
35 UcxList *e = l, *f; |
71 UcxList *e = l, *f; |
36 while (e != NULL) { |
72 while (e != NULL) { |
37 f = e; |
73 f = e; |
38 e = e->next; |
74 e = e->next; |
39 free(f); |
75 alloc->free(alloc->pool, f); |
40 } |
76 } |
41 } |
77 } |
42 |
78 |
43 UcxList *ucx_list_append(UcxList *l, void *data) { |
79 UcxList *ucx_list_append(UcxList *l, void *data) { |
44 UcxList *nl = (UcxList*) malloc(sizeof(UcxList)); |
80 return ucx_list_append_a(ucx_default_allocator(), l, data); |
45 if (nl == NULL) return NULL; |
81 } |
|
82 |
|
83 UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data) { |
|
84 UcxList *nl = (UcxList*) alloc->malloc(alloc->pool, sizeof(UcxList)); |
|
85 if (!nl) { |
|
86 return NULL; |
|
87 } |
46 |
88 |
47 nl->data = data; |
89 nl->data = data; |
48 nl->next = NULL; |
90 nl->next = NULL; |
49 if (l == NULL) { |
91 if (l) { |
50 return nl; |
|
51 } else { |
|
52 UcxList *t = ucx_list_last(l); |
92 UcxList *t = ucx_list_last(l); |
53 t->next = nl; |
93 t->next = nl; |
|
94 nl->prev = t; |
54 return l; |
95 return l; |
|
96 } else { |
|
97 nl->prev = NULL; |
|
98 return nl; |
55 } |
99 } |
56 } |
100 } |
57 |
101 |
58 UcxList *ucx_list_prepend(UcxList *l, void *data) { |
102 UcxList *ucx_list_prepend(UcxList *l, void *data) { |
59 UcxList *nl = ucx_list_append(NULL, data); |
103 return ucx_list_prepend_a(ucx_default_allocator(), l, data); |
60 if (nl == NULL) return NULL; |
104 } |
61 |
105 |
62 if (l != NULL) { |
106 UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) { |
|
107 UcxList *nl = ucx_list_append_a(alloc, NULL, data); |
|
108 if (!nl) { |
|
109 return NULL; |
|
110 } |
|
111 l = ucx_list_first(l); |
|
112 |
|
113 if (l) { |
63 nl->next = l; |
114 nl->next = l; |
|
115 l->prev = nl; |
64 } |
116 } |
65 return nl; |
117 return nl; |
66 } |
118 } |
67 |
119 |
68 UcxList *ucx_list_concat(UcxList *restrict l1, UcxList *restrict l2) { |
120 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { |
69 if (l1 == NULL) { |
121 if (l1) { |
70 return l2; |
|
71 } else { |
|
72 UcxList *last = ucx_list_last(l1); |
122 UcxList *last = ucx_list_last(l1); |
73 last->next = l2; |
123 last->next = l2; |
|
124 l2->prev = last; |
74 return l1; |
125 return l1; |
|
126 } else { |
|
127 return l2; |
75 } |
128 } |
76 } |
129 } |
77 |
130 |
78 UcxList *ucx_list_last(const UcxList *l) { |
131 UcxList *ucx_list_last(const UcxList *l) { |
79 if (l == NULL) return NULL; |
132 if (l == NULL) return NULL; |
83 e = e->next; |
136 e = e->next; |
84 } |
137 } |
85 return (UcxList*)e; |
138 return (UcxList*)e; |
86 } |
139 } |
87 |
140 |
|
141 ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) { |
|
142 ssize_t index = 0; |
|
143 while (list) { |
|
144 if (list == elem) { |
|
145 return index; |
|
146 } |
|
147 list = list->next; |
|
148 index++; |
|
149 } |
|
150 return -1; |
|
151 } |
|
152 |
88 UcxList *ucx_list_get(const UcxList *l, int index) { |
153 UcxList *ucx_list_get(const UcxList *l, int index) { |
89 if (l == NULL) return NULL; |
154 if (l == NULL) return NULL; |
90 |
155 |
91 const UcxList *e = l; |
156 const UcxList *e = l; |
92 while (e->next != NULL && index > 0) { |
157 while (e->next && index > 0) { |
93 e = e->next; |
158 e = e->next; |
94 index--; |
159 index--; |
95 } |
160 } |
96 |
161 |
97 return (UcxList*)(index == 0 ? e : NULL); |
162 return (UcxList*)(index == 0 ? e : NULL); |
|
163 } |
|
164 |
|
165 ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { |
|
166 ssize_t index = 0; |
|
167 UCX_FOREACH(e, l) { |
|
168 if (fnc) { |
|
169 if (fnc(elem, e->data, cmpdata) == 0) { |
|
170 return index; |
|
171 } |
|
172 } else { |
|
173 if (elem == e->data) { |
|
174 return index; |
|
175 } |
|
176 } |
|
177 index++; |
|
178 } |
|
179 return -1; |
|
180 } |
|
181 |
|
182 int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { |
|
183 return ucx_list_find(l, elem, fnc, cmpdata) > -1; |
98 } |
184 } |
99 |
185 |
100 size_t ucx_list_size(const UcxList *l) { |
186 size_t ucx_list_size(const UcxList *l) { |
101 if (l == NULL) return 0; |
187 if (l == NULL) return 0; |
102 |
188 |
197 |
285 |
198 return l; |
286 return l; |
199 } |
287 } |
200 } |
288 } |
201 |
289 |
202 /* list specific functions */ |
290 UcxList *ucx_list_first(const UcxList *l) { |
|
291 if (!l) { |
|
292 return NULL; |
|
293 } |
|
294 |
|
295 const UcxList *e = l; |
|
296 while (e->prev) { |
|
297 e = e->prev; |
|
298 } |
|
299 return (UcxList *)e; |
|
300 } |
|
301 |
203 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { |
302 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { |
204 if (e == l) { |
303 return ucx_list_remove_a(ucx_default_allocator(), l, e); |
205 l = e->next; |
304 } |
206 free(e); |
305 |
|
306 UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) { |
|
307 if (e->prev == NULL) { |
|
308 if(e->next != NULL) { |
|
309 e->next->prev = NULL; |
|
310 l = e->next; |
|
311 } else { |
|
312 l = NULL; |
|
313 } |
|
314 |
207 } else { |
315 } else { |
208 UcxList *f = l; |
316 e->prev->next = e->next; |
209 while (f->next != NULL && f->next != e) { |
317 e->next->prev = e->prev; |
210 f = f->next; |
318 } |
211 } |
319 alloc->free(alloc->pool, e); |
212 /* perform remove if this element is found in this list */ |
|
213 if (f->next == e) { |
|
214 f->next = e->next; |
|
215 free(e); |
|
216 } |
|
217 } |
|
218 return l; |
320 return l; |
219 } |
321 } |