ucx/list.c@cf3757c60c8f
ucx/list.c
Wed, 06 Feb 2013 14:31:44 +0100
- author
- Olaf Wintermann <olaf.wintermann@gmail.com>
- date
- Wed, 06 Feb 2013 14:31:44 +0100
- changeset 79
- cf3757c60c8f
- parent 73
- f15c7d6aebb9
- child 87
- bd444539cced
- permissions
- -rw-r--r--
fixed macros and ucx_map_store_enc
1 #include "list.h"
3 UcxList *restrict ucx_list_clone(UcxList *restrict l,
4 copy_func fnc, void *data) {
5 UcxList *ret = NULL;
6 while (l != NULL) {
7 if (fnc != NULL) {
8 ret = ucx_list_append(ret, fnc(l->data, data));
9 } else {
10 ret = ucx_list_append(ret, l->data);
11 }
12 l = l->next;
13 }
14 return ret;
15 }
17 int ucx_list_equals(const UcxList *l1, const UcxList *l2,
18 cmp_func fnc, void* data) {
19 if (l1 == l2) return 1;
21 while (l1 != NULL && l2 != NULL) {
22 if (fnc == NULL) {
23 if (l1->data != l2->data) return 0;
24 } else {
25 if (fnc(l1->data, l2->data, data) != 0) return 0;
26 }
27 l1 = l1->next;
28 l2 = l2->next;
29 }
31 return (l1 == NULL && l2 == NULL);
32 }
34 void ucx_list_free(UcxList *l) {
35 UcxList *e = l, *f;
36 while (e != NULL) {
37 f = e;
38 e = e->next;
39 free(f);
40 }
41 }
43 UcxList *ucx_list_append(UcxList *l, void *data) {
44 UcxList *nl = (UcxList*) malloc(sizeof(UcxList));
45 if (nl == NULL) return NULL;
47 nl->data = data;
48 nl->next = NULL;
49 if (l == NULL) {
50 return nl;
51 } else {
52 UcxList *t = ucx_list_last(l);
53 t->next = nl;
54 return l;
55 }
56 }
58 UcxList *ucx_list_prepend(UcxList *l, void *data) {
59 UcxList *nl = ucx_list_append(NULL, data);
60 if (nl == NULL) return NULL;
62 if (l != NULL) {
63 nl->next = l;
64 }
65 return nl;
66 }
68 UcxList *ucx_list_concat(UcxList *restrict l1, UcxList *restrict l2) {
69 if (l1 == NULL) {
70 return l2;
71 } else {
72 UcxList *last = ucx_list_last(l1);
73 last->next = l2;
74 return l1;
75 }
76 }
78 UcxList *ucx_list_last(const UcxList *l) {
79 if (l == NULL) return NULL;
81 const UcxList *e = l;
82 while (e->next != NULL) {
83 e = e->next;
84 }
85 return (UcxList*)e;
86 }
88 UcxList *ucx_list_get(const UcxList *l, int index) {
89 if (l == NULL) return NULL;
91 const UcxList *e = l;
92 while (e->next != NULL && index > 0) {
93 e = e->next;
94 index--;
95 }
97 return (UcxList*)(index == 0 ? e : NULL);
98 }
100 size_t ucx_list_size(const UcxList *l) {
101 if (l == NULL) return 0;
103 const UcxList *e = l;
104 size_t s = 1;
105 while (e->next != NULL) {
106 e = e->next;
107 s++;
108 }
110 return s;
111 }
113 UcxList *ucx_list_sort_merge(int length,
114 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,
115 cmp_func fnc, void* data) {
117 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);
118 UcxList *rc, *lc;
120 lc = ls; rc = le;
121 int n = 0;
122 while (lc && lc != le && rc != re) {
123 if (fnc(lc->data, rc->data, data) <= 0) {
124 sorted[n] = lc;
125 lc = lc->next;
126 } else {
127 sorted[n] = rc;
128 rc = rc->next;
129 }
130 n++;
131 }
132 while (lc && lc != le) {
133 sorted[n] = lc;
134 lc = lc->next;
135 n++;
136 }
137 while (rc && rc != re) {
138 sorted[n] = rc;
139 rc = rc->next;
140 n++;
141 }
143 // Update pointer
144 for (int i = 0 ; i < length-1 ; i++) {
145 sorted[i]->next = sorted[i+1];
146 }
147 sorted[length-1]->next = NULL;
149 UcxList *ret = sorted[0];
150 free(sorted);
151 return ret;
152 }
154 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
155 if (l == NULL) {
156 return NULL;
157 }
159 UcxList *lc;
160 int ln = 1;
162 UcxList *restrict ls = l, *restrict le, *restrict re;
163 lc = ls;
164 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
165 lc = lc->next;
166 ln++;
167 }
168 le = lc->next;
170 if (le == NULL) {
171 return l; // this list is already sorted :)
172 } else {
173 UcxList *rc;
174 int rn = 1;
175 rc = le;
176 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
177 rc = rc->next;
178 rn++;
179 }
180 re = rc->next;
182 // Something left? Sort it!
183 UcxList *remainder = re;
184 size_t remainder_length = ucx_list_size(remainder);
185 if (remainder != NULL) {
186 remainder = ucx_list_sort(remainder, fnc, data);
187 }
189 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
190 UcxList *sorted = ucx_list_sort_merge(ln+rn,
191 ls, le, re,
192 fnc, data);
194 // merge sorted list with (also sorted) remainder
195 l = ucx_list_sort_merge(ln+rn+remainder_length,
196 sorted, remainder, NULL, fnc, data);
198 return l;
199 }
200 }
202 /* list specific functions */
203 UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
204 if (e == l) {
205 l = e->next;
206 free(e);
207 } else {
208 UcxList *f = l;
209 while (f->next != NULL && f->next != e) {
210 f = f->next;
211 }
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;
219 }
