Wed, 05 Jun 2024 19:50:44 +0200
add extra nullptr check in the event loop to handle the case when the finish ptr is set to NULL after it was already scheduled
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1 | /* |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
3 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
4 | * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
5 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
6 | * Redistribution and use in source and binary forms, with or without |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
7 | * modification, are permitted provided that the following conditions are met: |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
8 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
9 | * 1. Redistributions of source code must retain the above copyright |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
10 | * notice, this list of conditions and the following disclaimer. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
11 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
12 | * 2. Redistributions in binary form must reproduce the above copyright |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
13 | * notice, this list of conditions and the following disclaimer in the |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
14 | * documentation and/or other materials provided with the distribution. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
15 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
26 | * POSSIBILITY OF SUCH DAMAGE. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
27 | */ |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
28 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
29 | #include "cx/linked_list.h" |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
30 | #include "cx/utils.h" |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
31 | #include <string.h> |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
32 | #include <assert.h> |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
33 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
34 | // LOW LEVEL LINKED LIST FUNCTIONS |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
35 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
36 | #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
37 | #define ll_prev(node) CX_LL_PTR(node, loc_prev) |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
38 | #define ll_next(node) CX_LL_PTR(node, loc_next) |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
39 | #define ll_advance(node) CX_LL_PTR(node, loc_advance) |
490 | 40 | #define ll_data(node) (((char*)(node))+loc_data) |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
41 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
42 | void *cx_linked_list_at( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
43 | void const *start, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
44 | size_t start_index, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
45 | ptrdiff_t loc_advance, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
46 | size_t index |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
47 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
48 | assert(start != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
49 | assert(loc_advance >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
50 | size_t i = start_index; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
51 | void const *cur = start; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
52 | while (i != index && cur != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
53 | cur = ll_advance(cur); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
54 | i < index ? i++ : i--; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
55 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
56 | return (void *) cur; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
57 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
58 | |
490 | 59 | ssize_t cx_linked_list_find( |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
60 | void const *start, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
61 | ptrdiff_t loc_advance, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
62 | ptrdiff_t loc_data, |
490 | 63 | cx_compare_func cmp_func, |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
64 | void const *elem |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
65 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
66 | assert(start != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
67 | assert(loc_advance >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
68 | assert(loc_data >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
69 | assert(cmp_func); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
70 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
71 | void const *node = start; |
490 | 72 | ssize_t index = 0; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
73 | do { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
74 | void *current = ll_data(node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
75 | if (cmp_func(current, elem) == 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
76 | return index; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
77 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
78 | node = ll_advance(node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
79 | index++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
80 | } while (node != NULL); |
490 | 81 | return -1; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
82 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
83 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
84 | void *cx_linked_list_first( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
85 | void const *node, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
86 | ptrdiff_t loc_prev |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
87 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
88 | return cx_linked_list_last(node, loc_prev); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
89 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
90 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
91 | void *cx_linked_list_last( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
92 | void const *node, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
93 | ptrdiff_t loc_next |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
94 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
95 | assert(node != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
96 | assert(loc_next >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
97 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
98 | void const *cur = node; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
99 | void const *last; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
100 | do { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
101 | last = cur; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
102 | } while ((cur = ll_next(cur)) != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
103 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
104 | return (void *) last; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
105 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
106 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
107 | void *cx_linked_list_prev( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
108 | void const *begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
109 | ptrdiff_t loc_next, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
110 | void const *node |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
111 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
112 | assert(begin != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
113 | assert(node != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
114 | assert(loc_next >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
115 | if (begin == node) return NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
116 | void const *cur = begin; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
117 | void const *next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
118 | while (1) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
119 | next = ll_next(cur); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
120 | if (next == node) return (void *) cur; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
121 | cur = next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
122 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
123 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
124 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
125 | void cx_linked_list_link( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
126 | void *left, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
127 | void *right, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
128 | ptrdiff_t loc_prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
129 | ptrdiff_t loc_next |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
130 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
131 | assert(loc_next >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
132 | ll_next(left) = right; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
133 | if (loc_prev >= 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
134 | ll_prev(right) = left; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
135 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
136 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
137 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
138 | void cx_linked_list_unlink( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
139 | void *left, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
140 | void *right, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
141 | ptrdiff_t loc_prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
142 | ptrdiff_t loc_next |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
143 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
144 | assert (loc_next >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
145 | assert(ll_next(left) == right); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
146 | ll_next(left) = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
147 | if (loc_prev >= 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
148 | assert(ll_prev(right) == left); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
149 | ll_prev(right) = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
150 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
151 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
152 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
153 | void cx_linked_list_add( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
154 | void **begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
155 | void **end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
156 | ptrdiff_t loc_prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
157 | ptrdiff_t loc_next, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
158 | void *new_node |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
159 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
160 | void *last; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
161 | if (end == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
162 | assert(begin != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
163 | last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
164 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
165 | last = *end; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
166 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
167 | cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
168 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
169 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
170 | void cx_linked_list_prepend( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
171 | void **begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
172 | void **end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
173 | ptrdiff_t loc_prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
174 | ptrdiff_t loc_next, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
175 | void *new_node |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
176 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
177 | cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
178 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
179 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
180 | void cx_linked_list_insert( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
181 | void **begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
182 | void **end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
183 | ptrdiff_t loc_prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
184 | ptrdiff_t loc_next, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
185 | void *node, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
186 | void *new_node |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
187 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
188 | cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
189 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
190 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
191 | void cx_linked_list_insert_chain( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
192 | void **begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
193 | void **end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
194 | ptrdiff_t loc_prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
195 | ptrdiff_t loc_next, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
196 | void *node, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
197 | void *insert_begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
198 | void *insert_end |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
199 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
200 | // find the end of the chain, if not specified |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
201 | if (insert_end == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
202 | insert_end = cx_linked_list_last(insert_begin, loc_next); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
203 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
204 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
205 | // determine the successor |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
206 | void *successor; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
207 | if (node == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
208 | assert(begin != NULL || (end != NULL && loc_prev >= 0)); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
209 | if (begin != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
210 | successor = *begin; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
211 | *begin = insert_begin; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
212 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
213 | successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
214 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
215 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
216 | successor = ll_next(node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
217 | cx_linked_list_link(node, insert_begin, loc_prev, loc_next); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
218 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
219 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
220 | if (successor == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
221 | // the list ends with the new chain |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
222 | if (end != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
223 | *end = insert_end; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
224 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
225 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
226 | cx_linked_list_link(insert_end, successor, loc_prev, loc_next); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
227 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
228 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
229 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
230 | void cx_linked_list_remove( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
231 | void **begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
232 | void **end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
233 | ptrdiff_t loc_prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
234 | ptrdiff_t loc_next, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
235 | void *node |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
236 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
237 | assert(node != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
238 | assert(loc_next >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
239 | assert(loc_prev >= 0 || begin != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
240 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
241 | // find adjacent nodes |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
242 | void *next = ll_next(node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
243 | void *prev; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
244 | if (loc_prev >= 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
245 | prev = ll_prev(node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
246 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
247 | prev = cx_linked_list_prev(*begin, loc_next, node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
248 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
249 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
250 | // update next pointer of prev node, or set begin |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
251 | if (prev == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
252 | if (begin != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
253 | *begin = next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
254 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
255 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
256 | ll_next(prev) = next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
257 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
258 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
259 | // update prev pointer of next node, or set end |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
260 | if (next == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
261 | if (end != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
262 | *end = prev; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
263 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
264 | } else if (loc_prev >= 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
265 | ll_prev(next) = prev; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
266 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
267 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
268 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
269 | size_t cx_linked_list_size( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
270 | void const *node, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
271 | ptrdiff_t loc_next |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
272 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
273 | assert(loc_next >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
274 | size_t size = 0; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
275 | while (node != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
276 | node = ll_next(node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
277 | size++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
278 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
279 | return size; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
280 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
281 | |
490 | 282 | #ifndef CX_LINKED_LIST_SORT_SBO_SIZE |
283 | #define CX_LINKED_LIST_SORT_SBO_SIZE 1024 | |
284 | #endif | |
285 | ||
504 | 286 | static void cx_linked_list_sort_merge( |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
287 | ptrdiff_t loc_prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
288 | ptrdiff_t loc_next, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
289 | ptrdiff_t loc_data, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
290 | size_t length, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
291 | void *ls, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
292 | void *le, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
293 | void *re, |
504 | 294 | cx_compare_func cmp_func, |
295 | void **begin, | |
296 | void **end | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
297 | ) { |
490 | 298 | void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; |
299 | void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? | |
300 | malloc(sizeof(void *) * length) : sbo; | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
301 | if (sorted == NULL) abort(); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
302 | void *rc, *lc; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
303 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
304 | lc = ls; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
305 | rc = le; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
306 | size_t n = 0; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
307 | while (lc && lc != le && rc != re) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
308 | if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
309 | sorted[n] = lc; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
310 | lc = ll_next(lc); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
311 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
312 | sorted[n] = rc; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
313 | rc = ll_next(rc); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
314 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
315 | n++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
316 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
317 | while (lc && lc != le) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
318 | sorted[n] = lc; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
319 | lc = ll_next(lc); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
320 | n++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
321 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
322 | while (rc && rc != re) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
323 | sorted[n] = rc; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
324 | rc = ll_next(rc); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
325 | n++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
326 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
327 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
328 | // Update pointer |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
329 | if (loc_prev >= 0) ll_prev(sorted[0]) = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
330 | cx_for_n (i, length - 1) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
331 | cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
332 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
333 | ll_next(sorted[length - 1]) = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
334 | |
504 | 335 | *begin = sorted[0]; |
336 | *end = sorted[length-1]; | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
337 | if (sorted != sbo) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
338 | free(sorted); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
339 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
340 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
341 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
342 | void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
343 | void **begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
344 | void **end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
345 | ptrdiff_t loc_prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
346 | ptrdiff_t loc_next, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
347 | ptrdiff_t loc_data, |
490 | 348 | cx_compare_func cmp_func |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
349 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
350 | assert(begin != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
351 | assert(loc_next >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
352 | assert(loc_data >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
353 | assert(cmp_func); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
354 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
355 | void *lc, *ls, *le, *re; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
356 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
357 | // set start node |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
358 | ls = *begin; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
359 | |
491 | 360 | // early exit when this list is empty |
361 | if (ls == NULL) return; | |
362 | ||
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
363 | // check how many elements are already sorted |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
364 | lc = ls; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
365 | size_t ln = 1; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
366 | while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
367 | lc = ll_next(lc); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
368 | ln++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
369 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
370 | le = ll_next(lc); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
371 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
372 | // if first unsorted node is NULL, the list is already completely sorted |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
373 | if (le != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
374 | void *rc; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
375 | size_t rn = 1; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
376 | rc = le; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
377 | // skip already sorted elements |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
378 | while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
379 | rc = ll_next(rc); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
380 | rn++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
381 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
382 | re = ll_next(rc); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
383 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
384 | // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them |
504 | 385 | void *sorted_begin, *sorted_end; |
386 | cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, | |
387 | ln + rn, ls, le, re, cmp_func, | |
388 | &sorted_begin, &sorted_end); | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
389 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
390 | // Something left? Sort it! |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
391 | size_t remainder_length = cx_linked_list_size(re, loc_next); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
392 | if (remainder_length > 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
393 | void *remainder = re; |
490 | 394 | cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
395 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
396 | // merge sorted list with (also sorted) remainder |
504 | 397 | cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, |
398 | ln + rn + remainder_length, | |
399 | sorted_begin, remainder, NULL, cmp_func, | |
400 | &sorted_begin, &sorted_end); | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
401 | } |
504 | 402 | *begin = sorted_begin; |
403 | if (end) *end = sorted_end; | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
404 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
405 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
406 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
407 | int cx_linked_list_compare( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
408 | void const *begin_left, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
409 | void const *begin_right, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
410 | ptrdiff_t loc_advance, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
411 | ptrdiff_t loc_data, |
490 | 412 | cx_compare_func cmp_func |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
413 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
414 | void const *left = begin_left, *right = begin_right; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
415 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
416 | while (left != NULL && right != NULL) { |
490 | 417 | void const *left_data = ll_data(left); |
418 | void const *right_data = ll_data(right); | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
419 | int result = cmp_func(left_data, right_data); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
420 | if (result != 0) return result; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
421 | left = ll_advance(left); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
422 | right = ll_advance(right); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
423 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
424 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
425 | if (left != NULL) { return 1; } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
426 | else if (right != NULL) { return -1; } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
427 | else { return 0; } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
428 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
429 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
430 | void cx_linked_list_reverse( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
431 | void **begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
432 | void **end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
433 | ptrdiff_t loc_prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
434 | ptrdiff_t loc_next |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
435 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
436 | assert(begin != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
437 | assert(loc_next >= 0); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
438 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
439 | // swap all links |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
440 | void *prev = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
441 | void *cur = *begin; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
442 | while (cur != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
443 | void *next = ll_next(cur); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
444 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
445 | ll_next(cur) = prev; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
446 | if (loc_prev >= 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
447 | ll_prev(cur) = next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
448 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
449 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
450 | prev = cur; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
451 | cur = next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
452 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
453 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
454 | // update begin and end |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
455 | if (end != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
456 | *end = *begin; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
457 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
458 | *begin = prev; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
459 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
460 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
461 | // HIGH LEVEL LINKED LIST IMPLEMENTATION |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
462 | |
490 | 463 | bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false; |
464 | ||
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
465 | typedef struct cx_linked_list_node cx_linked_list_node; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
466 | struct cx_linked_list_node { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
467 | cx_linked_list_node *prev; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
468 | cx_linked_list_node *next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
469 | char payload[]; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
470 | }; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
471 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
472 | #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev) |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
473 | #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next) |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
474 | #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload) |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
475 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
476 | typedef struct { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
477 | struct cx_list_s base; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
478 | cx_linked_list_node *begin; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
479 | cx_linked_list_node *end; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
480 | } cx_linked_list; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
481 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
482 | static cx_linked_list_node *cx_ll_node_at( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
483 | cx_linked_list const *list, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
484 | size_t index |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
485 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
486 | if (index >= list->base.size) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
487 | return NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
488 | } else if (index > list->base.size / 2) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
489 | return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
490 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
491 | return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
492 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
493 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
494 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
495 | static int cx_ll_insert_at( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
496 | struct cx_list_s *list, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
497 | cx_linked_list_node *node, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
498 | void const *elem |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
499 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
500 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
501 | // create the new new_node |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
502 | cx_linked_list_node *new_node = cxMalloc(list->allocator, |
490 | 503 | sizeof(cx_linked_list_node) + list->item_size); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
504 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
505 | // sortir if failed |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
506 | if (new_node == NULL) return 1; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
507 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
508 | // initialize new new_node |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
509 | new_node->prev = new_node->next = NULL; |
490 | 510 | memcpy(new_node->payload, elem, list->item_size); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
511 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
512 | // insert |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
513 | cx_linked_list *ll = (cx_linked_list *) list; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
514 | cx_linked_list_insert_chain( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
515 | (void **) &ll->begin, (void **) &ll->end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
516 | CX_LL_LOC_PREV, CX_LL_LOC_NEXT, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
517 | node, new_node, new_node |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
518 | ); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
519 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
520 | // increase the size and return |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
521 | list->size++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
522 | return 0; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
523 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
524 | |
490 | 525 | static size_t cx_ll_insert_array( |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
526 | struct cx_list_s *list, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
527 | size_t index, |
490 | 528 | void const *array, |
529 | size_t n | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
530 | ) { |
490 | 531 | // out-of bounds and corner case check |
532 | if (index > list->size || n == 0) return 0; | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
533 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
534 | // find position efficiently |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
535 | cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
536 | |
490 | 537 | // perform first insert |
538 | if (0 != cx_ll_insert_at(list, node, array)) { | |
539 | return 1; | |
540 | } | |
541 | ||
542 | // is there more? | |
543 | if (n == 1) return 1; | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
544 | |
490 | 545 | // we now know exactly where we are |
546 | node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
547 | |
490 | 548 | // we can add the remaining nodes and immedately advance to the inserted node |
549 | char const *source = array; | |
550 | for (size_t i = 1; i < n; i++) { | |
551 | source += list->item_size; | |
552 | if (0 != cx_ll_insert_at(list, node, source)) { | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
553 | return i; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
554 | } |
490 | 555 | node = node->next; |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
556 | } |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
557 | return n; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
558 | } |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
559 | |
490 | 560 | static int cx_ll_insert_element( |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
561 | struct cx_list_s *list, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
562 | size_t index, |
490 | 563 | void const *element |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
564 | ) { |
490 | 565 | return 1 != cx_ll_insert_array(list, index, element, 1); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
566 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
567 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
568 | static int cx_ll_remove( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
569 | struct cx_list_s *list, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
570 | size_t index |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
571 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
572 | cx_linked_list *ll = (cx_linked_list *) list; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
573 | cx_linked_list_node *node = cx_ll_node_at(ll, index); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
574 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
575 | // out-of-bounds check |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
576 | if (node == NULL) return 1; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
577 | |
490 | 578 | // element destruction |
579 | cx_invoke_destructor(list, node->payload); | |
580 | ||
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
581 | // remove |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
582 | cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
583 | CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
584 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
585 | // adjust size |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
586 | list->size--; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
587 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
588 | // free and return |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
589 | cxFree(list->allocator, node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
590 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
591 | return 0; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
592 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
593 | |
490 | 594 | static void cx_ll_clear(struct cx_list_s *list) { |
595 | if (list->size == 0) return; | |
596 | ||
597 | cx_linked_list *ll = (cx_linked_list *) list; | |
598 | cx_linked_list_node *node = ll->begin; | |
599 | while (node != NULL) { | |
600 | cx_invoke_destructor(list, node->payload); | |
601 | cx_linked_list_node *next = node->next; | |
602 | cxFree(list->allocator, node); | |
603 | node = next; | |
604 | } | |
605 | ll->begin = ll->end = NULL; | |
606 | list->size = 0; | |
607 | } | |
608 | ||
609 | #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE | |
504 | 610 | #define CX_LINKED_LIST_SWAP_SBO_SIZE 128 |
490 | 611 | #endif |
612 | ||
613 | static int cx_ll_swap( | |
614 | struct cx_list_s *list, | |
615 | size_t i, | |
616 | size_t j | |
617 | ) { | |
618 | if (i >= list->size || j >= list->size) return 1; | |
619 | if (i == j) return 0; | |
620 | ||
621 | // perform an optimized search that finds both elements in one run | |
622 | cx_linked_list *ll = (cx_linked_list *) list; | |
623 | size_t mid = list->size / 2; | |
624 | size_t left, right; | |
625 | if (i < j) { | |
626 | left = i; | |
627 | right = j; | |
628 | } else { | |
629 | left = j; | |
630 | right = i; | |
631 | } | |
632 | cx_linked_list_node *nleft, *nright; | |
633 | if (left < mid && right < mid) { | |
634 | // case 1: both items left from mid | |
635 | nleft = cx_ll_node_at(ll, left); | |
636 | nright = nleft; | |
637 | for (size_t c = left; c < right; c++) { | |
638 | nright = nright->next; | |
639 | } | |
640 | } else if (left >= mid && right >= mid) { | |
641 | // case 2: both items right from mid | |
642 | nright = cx_ll_node_at(ll, right); | |
643 | nleft = nright; | |
644 | for (size_t c = right; c > left; c--) { | |
645 | nleft = nleft->prev; | |
646 | } | |
647 | } else { | |
648 | // case 3: one item left, one item right | |
649 | ||
650 | // chose the closest to begin / end | |
651 | size_t closest; | |
652 | size_t other; | |
653 | size_t diff2boundary = list->size - right - 1; | |
654 | if (left <= diff2boundary) { | |
655 | closest = left; | |
656 | other = right; | |
657 | nleft = cx_ll_node_at(ll, left); | |
658 | } else { | |
659 | closest = right; | |
660 | other = left; | |
661 | diff2boundary = left; | |
662 | nright = cx_ll_node_at(ll, right); | |
663 | } | |
664 | ||
665 | // is other element closer to us or closer to boundary? | |
666 | if (right - left <= diff2boundary) { | |
667 | // search other element starting from already found element | |
668 | if (closest == left) { | |
669 | nright = nleft; | |
670 | for (size_t c = left; c < right; c++) { | |
671 | nright = nright->next; | |
672 | } | |
673 | } else { | |
674 | nleft = nright; | |
675 | for (size_t c = right; c > left; c--) { | |
676 | nleft = nleft->prev; | |
677 | } | |
678 | } | |
679 | } else { | |
680 | // search other element starting at the boundary | |
681 | if (closest == left) { | |
682 | nright = cx_ll_node_at(ll, other); | |
683 | } else { | |
684 | nleft = cx_ll_node_at(ll, other); | |
685 | } | |
686 | } | |
687 | } | |
688 | ||
689 | if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { | |
690 | cx_linked_list_node *prev = nleft->prev; | |
691 | cx_linked_list_node *next = nright->next; | |
692 | cx_linked_list_node *midstart = nleft->next; | |
693 | cx_linked_list_node *midend = nright->prev; | |
694 | ||
695 | if (prev == NULL) { | |
696 | ll->begin = nright; | |
697 | } else { | |
698 | prev->next = nright; | |
699 | } | |
700 | nright->prev = prev; | |
701 | if (midstart == nright) { | |
702 | // special case: both nodes are adjacent | |
703 | nright->next = nleft; | |
704 | nleft->prev = nright; | |
705 | } else { | |
706 | // likely case: a chain is between the two nodes | |
707 | nright->next = midstart; | |
708 | midstart->prev = nright; | |
709 | midend->next = nleft; | |
710 | nleft->prev = midend; | |
711 | } | |
712 | nleft->next = next; | |
713 | if (next == NULL) { | |
714 | ll->end = nleft; | |
715 | } else { | |
716 | next->prev = nleft; | |
717 | } | |
718 | } else { | |
719 | // swap payloads to avoid relinking | |
720 | char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; | |
721 | memcpy(buf, nleft->payload, list->item_size); | |
722 | memcpy(nleft->payload, nright->payload, list->item_size); | |
723 | memcpy(nright->payload, buf, list->item_size); | |
724 | } | |
725 | ||
726 | return 0; | |
727 | } | |
728 | ||
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
729 | static void *cx_ll_at( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
730 | struct cx_list_s const *list, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
731 | size_t index |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
732 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
733 | cx_linked_list *ll = (cx_linked_list *) list; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
734 | cx_linked_list_node *node = cx_ll_node_at(ll, index); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
735 | return node == NULL ? NULL : node->payload; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
736 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
737 | |
490 | 738 | static ssize_t cx_ll_find( |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
739 | struct cx_list_s const *list, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
740 | void const *elem |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
741 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
742 | return cx_linked_list_find(((cx_linked_list *) list)->begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
743 | CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
490 | 744 | list->cmpfunc, elem); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
745 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
746 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
747 | static void cx_ll_sort(struct cx_list_s *list) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
748 | cx_linked_list *ll = (cx_linked_list *) list; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
749 | cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
750 | CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
490 | 751 | list->cmpfunc); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
752 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
753 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
754 | static void cx_ll_reverse(struct cx_list_s *list) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
755 | cx_linked_list *ll = (cx_linked_list *) list; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
756 | cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
757 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
758 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
759 | static int cx_ll_compare( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
760 | struct cx_list_s const *list, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
761 | struct cx_list_s const *other |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
762 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
763 | cx_linked_list *left = (cx_linked_list *) list; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
764 | cx_linked_list *right = (cx_linked_list *) other; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
765 | return cx_linked_list_compare(left->begin, right->begin, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
766 | CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
490 | 767 | list->cmpfunc); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
768 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
769 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
770 | static bool cx_ll_iter_valid(void const *it) { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
771 | struct cx_iterator_s const *iter = it; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
772 | return iter->elem_handle != NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
773 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
774 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
775 | static void cx_ll_iter_next(void *it) { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
776 | struct cx_iterator_base_s *itbase = it; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
777 | if (itbase->remove) { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
778 | itbase->remove = false; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
779 | struct cx_mut_iterator_s *iter = it; |
490 | 780 | struct cx_list_s *list = iter->src_handle; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
781 | cx_linked_list *ll = iter->src_handle; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
782 | cx_linked_list_node *node = iter->elem_handle; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
783 | iter->elem_handle = node->next; |
490 | 784 | cx_invoke_destructor(list, node->payload); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
785 | cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
786 | CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); |
490 | 787 | list->size--; |
788 | cxFree(list->allocator, node); | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
789 | } else { |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
790 | struct cx_iterator_s *iter = it; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
791 | iter->index++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
792 | cx_linked_list_node *node = iter->elem_handle; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
793 | iter->elem_handle = node->next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
794 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
795 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
796 | |
490 | 797 | static void cx_ll_iter_prev(void *it) { |
798 | struct cx_iterator_base_s *itbase = it; | |
799 | if (itbase->remove) { | |
800 | itbase->remove = false; | |
801 | struct cx_mut_iterator_s *iter = it; | |
802 | struct cx_list_s *list = iter->src_handle; | |
803 | cx_linked_list *ll = iter->src_handle; | |
804 | cx_linked_list_node *node = iter->elem_handle; | |
805 | iter->elem_handle = node->prev; | |
806 | iter->index--; | |
807 | cx_invoke_destructor(list, node->payload); | |
808 | cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, | |
809 | CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); | |
810 | list->size--; | |
811 | cxFree(list->allocator, node); | |
812 | } else { | |
813 | struct cx_iterator_s *iter = it; | |
814 | iter->index--; | |
815 | cx_linked_list_node *node = iter->elem_handle; | |
816 | iter->elem_handle = node->prev; | |
817 | } | |
818 | } | |
819 | ||
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
820 | static void *cx_ll_iter_current(void const *it) { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
821 | struct cx_iterator_s const *iter = it; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
822 | cx_linked_list_node *node = iter->elem_handle; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
823 | return node->payload; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
824 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
825 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
826 | static bool cx_ll_iter_flag_rm(void *it) { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
827 | struct cx_iterator_base_s *iter = it; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
828 | if (iter->mutating) { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
829 | iter->remove = true; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
830 | return true; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
831 | } else { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
832 | return false; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
833 | } |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
834 | } |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
835 | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
836 | static CxIterator cx_ll_iterator( |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
837 | struct cx_list_s const *list, |
490 | 838 | size_t index, |
839 | bool backwards | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
840 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
841 | CxIterator iter; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
842 | iter.index = index; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
843 | iter.src_handle = list; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
844 | iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
845 | iter.base.valid = cx_ll_iter_valid; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
846 | iter.base.current = cx_ll_iter_current; |
490 | 847 | iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
848 | iter.base.flag_removal = cx_ll_iter_flag_rm; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
849 | iter.base.mutating = false; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
850 | iter.base.remove = false; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
851 | return iter; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
852 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
853 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
854 | static int cx_ll_insert_iter( |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
855 | CxMutIterator *iter, |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
856 | void const *elem, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
857 | int prepend |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
858 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
859 | struct cx_list_s *list = iter->src_handle; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
860 | cx_linked_list_node *node = iter->elem_handle; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
861 | if (node != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
862 | assert(prepend >= 0 && prepend <= 1); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
863 | cx_linked_list_node *choice[2] = {node, node->prev}; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
864 | int result = cx_ll_insert_at(list, choice[prepend], elem); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
865 | iter->index += prepend * (0 == result); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
866 | return result; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
867 | } else { |
490 | 868 | int result = cx_ll_insert_element(list, list->size, elem); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
869 | iter->index = list->size; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
870 | return result; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
871 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
872 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
873 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
874 | static void cx_ll_destructor(CxList *list) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
875 | cx_linked_list *ll = (cx_linked_list *) list; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
876 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
877 | cx_linked_list_node *node = ll->begin; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
878 | while (node) { |
504 | 879 | cx_invoke_destructor(list, node->payload); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
880 | void *next = node->next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
881 | cxFree(list->allocator, node); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
882 | node = next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
883 | } |
504 | 884 | |
885 | cxFree(list->allocator, list); | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
886 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
887 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
888 | static cx_list_class cx_linked_list_class = { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
889 | cx_ll_destructor, |
490 | 890 | cx_ll_insert_element, |
891 | cx_ll_insert_array, | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
892 | cx_ll_insert_iter, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
893 | cx_ll_remove, |
490 | 894 | cx_ll_clear, |
895 | cx_ll_swap, | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
896 | cx_ll_at, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
897 | cx_ll_find, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
898 | cx_ll_sort, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
899 | cx_ll_compare, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
900 | cx_ll_reverse, |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
901 | cx_ll_iterator, |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
902 | }; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
903 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
904 | CxList *cxLinkedListCreate( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
905 | CxAllocator const *allocator, |
490 | 906 | cx_compare_func comparator, |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
907 | size_t item_size |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
908 | ) { |
490 | 909 | if (allocator == NULL) { |
910 | allocator = cxDefaultAllocator; | |
911 | } | |
912 | ||
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
913 | cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
914 | if (list == NULL) return NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
915 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
916 | list->base.cl = &cx_linked_list_class; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
917 | list->base.allocator = allocator; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
918 | list->base.cmpfunc = comparator; |
490 | 919 | |
920 | if (item_size > 0) { | |
921 | list->base.item_size = item_size; | |
922 | } else { | |
923 | cxListStorePointers((CxList *) list); | |
924 | } | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
925 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
926 | return (CxList *) list; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
927 | } |