Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 469
75ae1dccd101
parent 467
95e42a963520
child 470
0458bff0b1cd
equal deleted inserted replaced
467:95e42a963520 469:75ae1dccd101
31 #include <string.h> 31 #include <string.h>
32 #include <assert.h> 32 #include <assert.h>
33 33
34 /* LOW LEVEL LINKED LIST FUNCTIONS */ 34 /* LOW LEVEL LINKED LIST FUNCTIONS */
35 35
36 #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off)) 36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
37 37
38 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { 38 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
39 size_t i = start_index; 39 size_t i = start_index;
40 void *cur = start; 40 void *cur = start;
41 while (i != index && cur != NULL) { 41 while (i != index && cur != NULL) {
42 cur = *CX_LL_PTR(cur, loc_advance); 42 cur = CX_LL_PTR(cur, loc_advance);
43 i < index ? i++ : i--; 43 i < index ? i++ : i--;
44 } 44 }
45 return cur; 45 return cur;
46 } 46 }
47 47
51 51
52 void *cur = begin; 52 void *cur = begin;
53 void *last; 53 void *last;
54 do { 54 do {
55 last = cur; 55 last = cur;
56 } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL); 56 } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
57 57
58 return last; 58 return last;
59 } 59 }
60 60
61 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { 61 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
69 if (last == NULL) { 69 if (last == NULL) {
70 assert(begin != NULL); 70 assert(begin != NULL);
71 *begin = new_node; 71 *begin = new_node;
72 } else { 72 } else {
73 // if there is a last node, update its next pointer 73 // if there is a last node, update its next pointer
74 void **next = CX_LL_PTR(last, loc_next); 74 CX_LL_PTR(last, loc_next) = new_node;
75 *next = new_node;
76 } 75 }
77 76
78 // if there is an end pointer, update it 77 // if there is an end pointer, update it
79 if (end != NULL) { 78 if (end != NULL) {
80 *end = cx_linked_list_last(new_node, loc_next); 79 *end = cx_linked_list_last(new_node, loc_next);
81 } 80 }
82 81
83 // if the nodes use a prev pointer, update it 82 // if the nodes use a prev pointer, update it
84 if (loc_prev >= 0) { 83 if (loc_prev >= 0) {
85 void **prev = CX_LL_PTR(new_node, loc_prev); 84 CX_LL_PTR(new_node, loc_prev) = last;
86 *prev = last; 85 }
87 } 86 }
88 } 87
88 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
89 size_t size = 0;
90 while (node != NULL) {
91 node = CX_LL_PTR(node, loc_next);
92 size++;
93 }
94 return size;
95 }
96
97 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
98 #define ll_next(node) CX_LL_PTR(node, loc_next)
99 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
100
101 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
102 ptrdiff_t loc_data, int follow_ptr,
103 size_t length, void *ls, void *le, void *re,
104 CxListComparator cmp_func) {
105 const size_t sbo_len = 1024;
106 void *sbo[sbo_len];
107 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
108 void *rc, *lc;
109
110 lc = ls;
111 rc = le;
112 size_t n = 0;
113 while (lc && lc != le && rc != re) {
114 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
115 sorted[n] = lc;
116 lc = ll_next(lc);
117 } else {
118 sorted[n] = rc;
119 rc = ll_next(rc);
120 }
121 n++;
122 }
123 while (lc && lc != le) {
124 sorted[n] = lc;
125 lc = ll_next(lc);
126 n++;
127 }
128 while (rc && rc != re) {
129 sorted[n] = rc;
130 rc = ll_next(rc);
131 n++;
132 }
133
134 // Update pointer
135 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
136 for (size_t i = 0; i < length - 1; i++) {
137 ll_next(sorted[i]) = sorted[i + 1];
138 if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
139 }
140 ll_next(sorted[length - 1]) = NULL;
141
142 void *ret = sorted[0];
143 if (sorted != sbo) {
144 free(sorted);
145 }
146 return ret;
147 }
148
149 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
150 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
151 assert(begin != NULL);
152
153 void *lc, *ls, *le, *re;
154
155 // set start node
156 ls = *begin;
157
158 // check how many elements are already sorted
159 lc = ls;
160 size_t ln = 1;
161 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
162 lc = ll_next(lc);
163 ln++;
164 }
165 le = ll_next(lc);
166
167 // if first unsorted node is NULL, the list is already completely sorted
168 if (le != NULL) {
169 void *rc;
170 size_t rn = 1;
171 rc = le;
172 // skip already sorted elements
173 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
174 rc = ll_next(rc);
175 rn++;
176 }
177 re = ll_next(rc);
178
179 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
180 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
181 ln + rn, ls, le, re, cmp_func);
182
183 // Something left? Sort it!
184 size_t remainder_length = cx_linked_list_size(re, loc_next);
185 if (remainder_length > 0) {
186 void *remainder = re;
187 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
188
189 // merge sorted list with (also sorted) remainder
190 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
191 ln + rn + remainder_length,
192 sorted, remainder, NULL, cmp_func);
193 } else {
194 // no remainder - we've got our sorted list
195 *begin = sorted;
196 }
197 if (end) *end = cx_linked_list_last(sorted, loc_next);
198 }
199 }
200
201 #undef ll_next
202 #undef ll_data
89 203
90 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ 204 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
91 205
92 typedef struct cx_linked_list_node cx_linked_list_node; 206 typedef struct cx_linked_list_node cx_linked_list_node;
93 struct cx_linked_list_node { 207 struct cx_linked_list_node {
107 221
108 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) { 222 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
109 if (index >= list->base.size) { 223 if (index >= list->base.size) {
110 return NULL; 224 return NULL;
111 } else if (index > list->base.size / 2) { 225 } else if (index > list->base.size / 2) {
112 return cx_linked_list_at(list->end, list->base.size-1, CX_LL_LOC_PREV, index); 226 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
113 } else { 227 } else {
114 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 228 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
115 } 229 }
116 } 230 }
117 231
142 ll->end->next = node; 256 ll->end->next = node;
143 node->prev = ll->end; 257 node->prev = ll->end;
144 node->next = NULL; 258 node->next = NULL;
145 ll->end = node; 259 ll->end = node;
146 } 260 }
147 // check if this shall be the new start node 261 // check if this shall be the new start node
148 else if (index == 0) { 262 else if (index == 0) {
149 ll->begin->prev = node; 263 ll->begin->prev = node;
150 node->next = ll->begin; 264 node->next = ll->begin;
151 node->prev = NULL; 265 node->prev = NULL;
152 ll->begin = node; 266 ll->begin = node;
217 } 331 }
218 332
219 static void *cx_pll_at(cx_list_s *list, size_t index) { 333 static void *cx_pll_at(cx_list_s *list, size_t index) {
220 cx_linked_list *ll = (cx_linked_list *) list; 334 cx_linked_list *ll = (cx_linked_list *) list;
221 cx_linked_list_node *node = cx_ll_node_at(ll, index); 335 cx_linked_list_node *node = cx_ll_node_at(ll, index);
222 return node == NULL ? NULL : *(void**)node->payload; 336 return node == NULL ? NULL : *(void **) node->payload;
223 } 337 }
224 338
225 static size_t cx_ll_find(cx_list_s *list, void *elem) { 339 static size_t cx_ll_find(cx_list_s *list, void *elem) {
226 CxListComparator cmp = list->cmpfunc; 340 CxListComparator cmp = list->cmpfunc;
227 cx_linked_list *ll = (cx_linked_list *) list; 341 cx_linked_list *ll = (cx_linked_list *) list;
243 cx_linked_list *ll = (cx_linked_list *) list; 357 cx_linked_list *ll = (cx_linked_list *) list;
244 358
245 size_t index; 359 size_t index;
246 cx_linked_list_node *node = ll->begin; 360 cx_linked_list_node *node = ll->begin;
247 for (index = 0; index < list->size; index++) { 361 for (index = 0; index < list->size; index++) {
248 void *current = *(void**)node->payload; 362 void *current = *(void **) node->payload;
249 if (cmp(current, elem) == 0) { 363 if (cmp(current, elem) == 0) {
250 return index; 364 return index;
251 } 365 }
252 node = node->next; 366 node = node->next;
253 } 367 }
261 } 375 }
262 376
263 static void *cx_pll_last(cx_list_s *list) { 377 static void *cx_pll_last(cx_list_s *list) {
264 cx_linked_list *ll = (cx_linked_list *) list; 378 cx_linked_list *ll = (cx_linked_list *) list;
265 cx_linked_list_node *last = ll->end; 379 cx_linked_list_node *last = ll->end;
266 return last == NULL ? NULL : *(void**)last->payload; 380 return last == NULL ? NULL : *(void **) last->payload;
267 } 381 }
268 382
269 static cx_list_class cx_linked_list_class = { 383 static cx_list_class cx_linked_list_class = {
270 cx_ll_add, 384 cx_ll_add,
271 cx_ll_insert, 385 cx_ll_insert,
308 return NULL; 422 return NULL;
309 423
310 list->base.cl = &cx_pointer_linked_list_class; 424 list->base.cl = &cx_pointer_linked_list_class;
311 list->base.allocator = allocator; 425 list->base.allocator = allocator;
312 list->base.cmpfunc = comparator; 426 list->base.cmpfunc = comparator;
313 list->base.itemsize = sizeof(void*); 427 list->base.itemsize = sizeof(void *);
314 list->base.capacity = SIZE_MAX; 428 list->base.capacity = SIZE_MAX;
315 list->base.size = 0; 429 list->base.size = 0;
316 430
317 list->begin = NULL; 431 list->begin = NULL;
318 list->end = NULL; 432 list->end = NULL;

Mercurial Repository: ucx

mercurial