Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 481
eef025d82a34
parent 480
e3be53a3354f
child 486
d7ca126eab7f
equal deleted inserted replaced
480:e3be53a3354f 481:eef025d82a34
37 #define ll_prev(node) CX_LL_PTR(node, loc_prev) 37 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
38 #define ll_next(node) CX_LL_PTR(node, loc_next) 38 #define ll_next(node) CX_LL_PTR(node, loc_next)
39 #define ll_advance(node) CX_LL_PTR(node, loc_advance) 39 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
40 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data)) 40 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
41 41
42 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { 42 void *cx_linked_list_at(
43 void *start,
44 size_t start_index,
45 ptrdiff_t loc_advance,
46 size_t index
47 ) {
43 assert(start != NULL); 48 assert(start != NULL);
44 assert(loc_advance >= 0); 49 assert(loc_advance >= 0);
45 size_t i = start_index; 50 size_t i = start_index;
46 void *cur = start; 51 void *cur = start;
47 while (i != index && cur != NULL) { 52 while (i != index && cur != NULL) {
49 i < index ? i++ : i--; 54 i < index ? i++ : i--;
50 } 55 }
51 return cur; 56 return cur;
52 } 57 }
53 58
54 size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr, 59 size_t cx_linked_list_find(
55 CxListComparator cmp_func, void *elem) { 60 void *start,
61 ptrdiff_t loc_advance,
62 ptrdiff_t loc_data,
63 int follow_ptr,
64 CxListComparator cmp_func,
65 void *elem
66 ) {
56 assert(start != NULL); 67 assert(start != NULL);
57 assert(loc_advance >= 0); 68 assert(loc_advance >= 0);
58 assert(loc_data >= 0); 69 assert(loc_data >= 0);
59 assert(cmp_func); 70 assert(cmp_func);
60 71
69 index++; 80 index++;
70 } while (node != NULL); 81 } while (node != NULL);
71 return index; 82 return index;
72 } 83 }
73 84
74 void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) { 85 void *cx_linked_list_first(
86 void *node,
87 ptrdiff_t loc_prev
88 ) {
75 return cx_linked_list_last(node, loc_prev); 89 return cx_linked_list_last(node, loc_prev);
76 } 90 }
77 91
78 void *cx_linked_list_last(void *node, ptrdiff_t loc_next) { 92 void *cx_linked_list_last(
93 void *node,
94 ptrdiff_t loc_next
95 ) {
79 assert(node != NULL); 96 assert(node != NULL);
80 assert(loc_next >= 0); 97 assert(loc_next >= 0);
81 98
82 void *cur = node; 99 void *cur = node;
83 void *last; 100 void *last;
86 } while ((cur = ll_next(cur)) != NULL); 103 } while ((cur = ll_next(cur)) != NULL);
87 104
88 return last; 105 return last;
89 } 106 }
90 107
91 void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) { 108 void *cx_linked_list_prev(
109 void *begin,
110 ptrdiff_t loc_next,
111 void *node
112 ) {
92 assert(begin != NULL); 113 assert(begin != NULL);
93 assert(node != NULL); 114 assert(node != NULL);
94 assert(loc_next >= 0); 115 assert(loc_next >= 0);
95 if (begin == node) return NULL; 116 if (begin == node) return NULL;
96 void *cur = begin; 117 void *cur = begin;
100 if (next == node) return cur; 121 if (next == node) return cur;
101 cur = next; 122 cur = next;
102 } 123 }
103 } 124 }
104 125
105 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { 126 void cx_linked_list_link(
106 assert(new_node != NULL); 127 void *left,
128 void *right,
129 ptrdiff_t loc_prev,
130 ptrdiff_t loc_next
131 ) {
107 assert(loc_next >= 0); 132 assert(loc_next >= 0);
108 assert(ll_next(new_node) == NULL); 133 ll_next(left) = right;
134 if (loc_prev >= 0) {
135 ll_prev(right) = left;
136 }
137 }
138
139 void cx_linked_list_unlink(
140 void *left,
141 void *right,
142 ptrdiff_t loc_prev,
143 ptrdiff_t loc_next
144 ) {
145 assert (loc_next >= 0);
146 assert(ll_next(left) == right);
147 ll_next(left) = NULL;
148 if (loc_prev >= 0) {
149 assert(ll_prev(right) == left);
150 ll_prev(right) = NULL;
151 }
152 }
153
154 void cx_linked_list_add(
155 void **begin,
156 void **end,
157 ptrdiff_t loc_prev,
158 ptrdiff_t loc_next,
159 void *new_node
160 ) {
109 void *last; 161 void *last;
110 if (end == NULL) { 162 if (end == NULL) {
111 assert(begin != NULL); 163 assert(begin != NULL);
112 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next); 164 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
113 } else { 165 } else {
114 last = *end; 166 last = *end;
115 } 167 }
116 if (last == NULL) { 168 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
169 }
170
171 void cx_linked_list_prepend(
172 void **begin,
173 void **end,
174 ptrdiff_t loc_prev,
175 ptrdiff_t loc_next,
176 void *new_node
177 ) {
178 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
179 }
180
181 void cx_linked_list_insert(
182 void **begin,
183 void **end,
184 ptrdiff_t loc_prev,
185 ptrdiff_t loc_next,
186 void *node,
187 void *new_node
188 ) {
189 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
190 }
191
192 void cx_linked_list_insert_chain(
193 void **begin,
194 void **end,
195 ptrdiff_t loc_prev,
196 ptrdiff_t loc_next,
197 void *node,
198 void *insert_begin,
199 void *insert_end
200 ) {
201 // find the end of the chain, if not specified
202 if (insert_end == NULL) {
203 insert_end = cx_linked_list_last(insert_begin, loc_next);
204 }
205
206 // determine the successor
207 void *successor;
208 if (node == NULL) {
209 assert(begin != NULL || (end != NULL && loc_prev >= 0));
117 if (begin != NULL) { 210 if (begin != NULL) {
118 *begin = new_node; 211 successor = *begin;
212 *begin = insert_begin;
213 } else {
214 successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
119 } 215 }
120 } else { 216 } else {
121 // if there is a last node, update its next pointer 217 successor = ll_next(node);
122 ll_next(last) = new_node; 218 cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
123 } 219 }
124 220
125 // if there is an end pointer, update it 221 if (successor == NULL) {
126 if (end != NULL) { 222 // the list ends with the new chain
127 *end = new_node; 223 if (end != NULL) {
128 } 224 *end = insert_end;
129 225 }
130 // if the nodes use a prev pointer, update it
131 if (loc_prev >= 0) {
132 assert(ll_prev(new_node) == NULL);
133 ll_prev(new_node) = last;
134 }
135 }
136
137 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
138 assert(new_node != NULL);
139 assert(loc_next >= 0);
140 assert(ll_next(new_node) == NULL);
141 void *first;
142 if (begin == NULL) {
143 assert(end != NULL);
144 assert(loc_prev >= 0);
145 first = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
146 } else { 226 } else {
147 first = *begin; 227 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
148 } 228 }
149 if (first == NULL) { 229 }
150 if (end != NULL) { 230
151 *end = new_node; 231 void cx_linked_list_remove(
152 } 232 void **begin,
153 } else { 233 void **end,
154 ll_next(new_node) = first; 234 ptrdiff_t loc_prev,
155 if (loc_prev >= 0) { 235 ptrdiff_t loc_next,
156 ll_prev(first) = new_node; 236 void *node
157 } 237 ) {
158 }
159
160 if (begin != NULL) {
161 assert(loc_prev < 0 || ll_prev(new_node) == NULL);
162 *begin = new_node;
163 }
164 }
165
166 void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
167 assert(node != NULL); 238 assert(node != NULL);
168 assert(loc_next >= 0); 239 assert(loc_next >= 0);
169 assert(loc_prev >= 0 || begin != NULL); 240 assert(loc_prev >= 0 || begin != NULL);
170 241
171 // find adjacent nodes 242 // find adjacent nodes
194 } else if (loc_prev >= 0) { 265 } else if (loc_prev >= 0) {
195 ll_prev(next) = prev; 266 ll_prev(next) = prev;
196 } 267 }
197 } 268 }
198 269
199 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { 270 size_t cx_linked_list_size(
271 void *node,
272 ptrdiff_t loc_next
273 ) {
200 assert(loc_next >= 0); 274 assert(loc_next >= 0);
201 size_t size = 0; 275 size_t size = 0;
202 while (node != NULL) { 276 while (node != NULL) {
203 node = ll_next(node); 277 node = ll_next(node);
204 size++; 278 size++;
205 } 279 }
206 return size; 280 return size;
207 } 281 }
208 282
209 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next, 283 static void *cx_linked_list_sort_merge(
210 ptrdiff_t loc_data, int follow_ptr, 284 ptrdiff_t loc_prev,
211 size_t length, void *ls, void *le, void *re, 285 ptrdiff_t loc_next,
212 CxListComparator cmp_func) { 286 ptrdiff_t loc_data,
287 int follow_ptr,
288 size_t length,
289 void *ls,
290 void *le,
291 void *re,
292 CxListComparator cmp_func
293 ) {
213 const size_t sbo_len = 1024; 294 const size_t sbo_len = 1024;
214 void *sbo[sbo_len]; 295 void *sbo[sbo_len];
215 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo; 296 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
216 void *rc, *lc; 297 void *rc, *lc;
217 298
240 } 321 }
241 322
242 // Update pointer 323 // Update pointer
243 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL; 324 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
244 for (size_t i = 0; i < length - 1; i++) { 325 for (size_t i = 0; i < length - 1; i++) {
245 ll_next(sorted[i]) = sorted[i + 1]; 326 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
246 if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
247 } 327 }
248 ll_next(sorted[length - 1]) = NULL; 328 ll_next(sorted[length - 1]) = NULL;
249 329
250 void *ret = sorted[0]; 330 void *ret = sorted[0];
251 if (sorted != sbo) { 331 if (sorted != sbo) {
253 } 333 }
254 return ret; 334 return ret;
255 } 335 }
256 336
257 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */ 337 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
258 void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, 338 void **begin,
259 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) { 339 void **end,
340 ptrdiff_t loc_prev,
341 ptrdiff_t loc_next,
342 ptrdiff_t loc_data,
343 int follow_ptr,
344 CxListComparator cmp_func
345 ) {
260 assert(begin != NULL); 346 assert(begin != NULL);
261 assert(loc_next >= 0); 347 assert(loc_next >= 0);
262 assert(loc_data >= 0); 348 assert(loc_data >= 0);
263 assert(cmp_func); 349 assert(cmp_func);
264 350
308 } 394 }
309 if (end) *end = cx_linked_list_last(sorted, loc_next); 395 if (end) *end = cx_linked_list_last(sorted, loc_next);
310 } 396 }
311 } 397 }
312 398
313 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) { 399 void cx_linked_list_reverse(
400 void **begin,
401 void **end,
402 ptrdiff_t loc_prev,
403 ptrdiff_t loc_next
404 ) {
314 assert(begin != NULL); 405 assert(begin != NULL);
315 assert(loc_next >= 0); 406 assert(loc_next >= 0);
316 407
317 // swap all links 408 // swap all links
318 void *prev = NULL; 409 void *prev = NULL;
353 cx_list_s base; 444 cx_list_s base;
354 cx_linked_list_node *begin; 445 cx_linked_list_node *begin;
355 cx_linked_list_node *end; 446 cx_linked_list_node *end;
356 } cx_linked_list; 447 } cx_linked_list;
357 448
358 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) { 449 static cx_linked_list_node *cx_ll_node_at(
450 cx_linked_list *list,
451 size_t index
452 ) {
359 if (index >= list->base.size) { 453 if (index >= list->base.size) {
360 return NULL; 454 return NULL;
361 } else if (index > list->base.size / 2) { 455 } else if (index > list->base.size / 2) {
362 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); 456 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
363 } else { 457 } else {
364 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 458 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
365 } 459 }
366 } 460 }
367 461
368 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { 462 static int cx_ll_insert(
463 cx_list_s *list,
464 size_t index,
465 void *elem
466 ) {
369 // out-of bounds check 467 // out-of bounds check
370 if (index > list->size) return 1; 468 if (index > list->size) return 1;
371 469
372 // cast a linked list pointer 470 // cast a linked list pointer
373 cx_linked_list *ll = (cx_linked_list *) list; 471 cx_linked_list *ll = (cx_linked_list *) list;
374 472
375 // create the new node 473 // create the new new_node
376 cx_linked_list_node *node = cxMalloc(list->allocator, 474 cx_linked_list_node *new_node = cxMalloc(list->allocator,
377 sizeof(cx_linked_list_node) + list->itemsize); 475 sizeof(cx_linked_list_node) + list->itemsize);
378 476
379 // sortir if failed 477 // sortir if failed
380 if (node == NULL) return 1; 478 if (new_node == NULL) return 1;
381 479
382 // copy payload to the new node 480 // initialize new new_node
383 memcpy(node->payload, elem, list->itemsize); 481 new_node->prev = new_node->next = NULL;
384 482 memcpy(new_node->payload, elem, list->itemsize);
385 // check if this is the first node 483
386 if (ll->begin == NULL) { 484 // find position efficiently
387 node->prev = node->next = NULL; 485 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at(ll, index - 1);
388 ll->begin = ll->end = node; 486
389 } else { 487 // insert
390 // check if this shall be the new end node 488 cx_linked_list_insert_chain(
391 if (index == list->size) { 489 (void **) &ll->begin, (void **) &ll->end,
392 ll->end->next = node; 490 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
393 node->prev = ll->end; 491 node, new_node, new_node
394 node->next = NULL; 492 );
395 ll->end = node;
396 }
397 // check if this shall be the new start node
398 else if (index == 0) {
399 ll->begin->prev = node;
400 node->next = ll->begin;
401 node->prev = NULL;
402 ll->begin = node;
403 } else {
404 // find the node at the current index
405 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
406
407 // insert before that node
408 // (we know all ptr are non-null because we handled all other cases before)
409 node->next = cur;
410 node->prev = cur->prev;
411 cur->prev = node;
412 node->prev->next = node;
413 }
414 }
415 493
416 // increase the size and return 494 // increase the size and return
417 list->size++; 495 list->size++;
418 return 0; 496 return 0;
419 } 497 }
420 498
421 static int cx_ll_add(cx_list_s *list, void *elem) { 499 static int cx_ll_add(
500 cx_list_s *list,
501 void *elem
502 ) {
422 return cx_ll_insert(list, list->size, elem); 503 return cx_ll_insert(list, list->size, elem);
423 } 504 }
424 505
425 static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) { 506 static int cx_pll_insert(
507 cx_list_s *list,
508 size_t index,
509 void *elem
510 ) {
426 return cx_ll_insert(list, index, &elem); 511 return cx_ll_insert(list, index, &elem);
427 } 512 }
428 513
429 static int cx_pll_add(cx_list_s *list, void *elem) { 514 static int cx_pll_add(
515 cx_list_s *list,
516 void *elem
517 ) {
430 return cx_ll_insert(list, list->size, &elem); 518 return cx_ll_insert(list, list->size, &elem);
431 } 519 }
432 520
433 static int cx_ll_remove(cx_list_s *list, size_t index) { 521 static int cx_ll_remove(
522 cx_list_s *list,
523 size_t index
524 ) {
434 cx_linked_list *ll = (cx_linked_list *) list; 525 cx_linked_list *ll = (cx_linked_list *) list;
435 cx_linked_list_node *node = cx_ll_node_at(ll, index); 526 cx_linked_list_node *node = cx_ll_node_at(ll, index);
436 527
437 // out-of-bounds check 528 // out-of-bounds check
438 if (node == NULL) return 1; 529 if (node == NULL) return 1;
448 cxFree(list->allocator, node); 539 cxFree(list->allocator, node);
449 540
450 return 0; 541 return 0;
451 } 542 }
452 543
453 static void *cx_ll_at(cx_list_s *list, size_t index) { 544 static void *cx_ll_at(
545 cx_list_s *list,
546 size_t index
547 ) {
454 cx_linked_list *ll = (cx_linked_list *) list; 548 cx_linked_list *ll = (cx_linked_list *) list;
455 cx_linked_list_node *node = cx_ll_node_at(ll, index); 549 cx_linked_list_node *node = cx_ll_node_at(ll, index);
456 return node == NULL ? NULL : node->payload; 550 return node == NULL ? NULL : node->payload;
457 } 551 }
458 552
459 static void *cx_pll_at(cx_list_s *list, size_t index) { 553 static void *cx_pll_at(
554 cx_list_s *list,
555 size_t index
556 ) {
460 cx_linked_list *ll = (cx_linked_list *) list; 557 cx_linked_list *ll = (cx_linked_list *) list;
461 cx_linked_list_node *node = cx_ll_node_at(ll, index); 558 cx_linked_list_node *node = cx_ll_node_at(ll, index);
462 return node == NULL ? NULL : *(void **) node->payload; 559 return node == NULL ? NULL : *(void **) node->payload;
463 } 560 }
464 561
465 static size_t cx_ll_find(cx_list_s *list, void *elem) { 562 static size_t cx_ll_find(
563 cx_list_s *list,
564 void *elem
565 ) {
466 return cx_linked_list_find(((cx_linked_list *) list)->begin, 566 return cx_linked_list_find(((cx_linked_list *) list)->begin,
467 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 567 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
468 0, list->cmpfunc, elem); 568 0, list->cmpfunc, elem);
469 } 569 }
470 570
471 static size_t cx_pll_find(cx_list_s *list, void *elem) { 571 static size_t cx_pll_find(
572 cx_list_s *list,
573 void *elem
574 ) {
472 return cx_linked_list_find(((cx_linked_list *) list)->begin, 575 return cx_linked_list_find(((cx_linked_list *) list)->begin,
473 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 576 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
474 1, list->cmpfunc, elem); 577 1, list->cmpfunc, elem);
475 } 578 }
476 579
504 cx_pll_at, 607 cx_pll_at,
505 cx_pll_find, 608 cx_pll_find,
506 cx_pll_sort 609 cx_pll_sort
507 }; 610 };
508 611
509 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) { 612 CxList cxLinkedListCreate(
613 CxAllocator allocator,
614 CxListComparator comparator,
615 size_t item_size
616 ) {
510 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list)); 617 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
511 if (list == NULL) 618 if (list == NULL)
512 return NULL; 619 return NULL;
513 620
514 list->base.cl = &cx_linked_list_class; 621 list->base.cl = &cx_linked_list_class;
522 list->end = NULL; 629 list->end = NULL;
523 630
524 return (CxList) list; 631 return (CxList) list;
525 } 632 }
526 633
527 CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) { 634 CxList cxPointerLinkedListCreate(
635 CxAllocator allocator,
636 CxListComparator comparator
637 ) {
528 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list)); 638 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
529 if (list == NULL) 639 if (list == NULL)
530 return NULL; 640 return NULL;
531 641
532 list->base.cl = &cx_pointer_linked_list_class; 642 list->base.cl = &cx_pointer_linked_list_class;

Mercurial Repository: ucx

mercurial