src/ucx/linked_list.c

Fri, 10 Mar 2023 22:45:58 +0100

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Fri, 10 Mar 2023 22:45:58 +0100
changeset 459
f21b4ff81c01
parent 438
22eca559aded
child 490
d218607f5a7e
permissions
-rw-r--r--

log error in get_next_token()

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 <stdint.h>
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
32 #include <string.h>
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
33 #include <assert.h>
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
34
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
35 // LOW LEVEL LINKED LIST FUNCTIONS
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
36
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
37 #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
38 #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
39 #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
40 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
41 #define ll_data_f(node, follow_ptr) ((follow_ptr)?CX_LL_PTR(node, loc_data):(((char*)(node))+loc_data))
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
42 #define ll_data(node) ll_data_f(node,follow_ptr)
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
43
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
44 void *cx_linked_list_at(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
45 void const *start,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
46 size_t start_index,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
47 ptrdiff_t loc_advance,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
48 size_t index
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
49 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
50 assert(start != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
51 assert(loc_advance >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
52 size_t i = start_index;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
53 void const *cur = start;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
54 while (i != index && cur != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
55 cur = ll_advance(cur);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
56 i < index ? i++ : i--;
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 return (void *) cur;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
59 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
60
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
61 size_t cx_linked_list_find(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
62 void const *start,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 ptrdiff_t loc_advance,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
64 ptrdiff_t loc_data,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
65 bool follow_ptr,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
66 CxListComparator cmp_func,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
67 void const *elem
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
68 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
69 assert(start != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
70 assert(loc_advance >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
71 assert(loc_data >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
72 assert(cmp_func);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
73
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
74 void const *node = start;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
75 size_t index = 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
76 do {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
77 void *current = ll_data(node);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
78 if (cmp_func(current, elem) == 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
79 return index;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
80 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
81 node = ll_advance(node);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
82 index++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
83 } while (node != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
84 return index;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
85 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
86
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
87 void *cx_linked_list_first(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
88 void const *node,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
89 ptrdiff_t loc_prev
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 return cx_linked_list_last(node, loc_prev);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
92 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
93
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
94 void *cx_linked_list_last(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
95 void const *node,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
96 ptrdiff_t loc_next
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 assert(node != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
99 assert(loc_next >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
100
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
101 void const *cur = node;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
102 void const *last;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
103 do {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
104 last = cur;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
105 } while ((cur = ll_next(cur)) != NULL);
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 return (void *) last;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
108 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
109
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
110 void *cx_linked_list_prev(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
111 void const *begin,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
112 ptrdiff_t loc_next,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
113 void const *node
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
114 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
115 assert(begin != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
116 assert(node != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
117 assert(loc_next >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
118 if (begin == node) return NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
119 void const *cur = begin;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
120 void const *next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
121 while (1) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
122 next = ll_next(cur);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
123 if (next == node) return (void *) cur;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
124 cur = next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
125 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
126 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
127
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
128 void cx_linked_list_link(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
129 void *left,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
130 void *right,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
131 ptrdiff_t loc_prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
132 ptrdiff_t loc_next
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
133 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
134 assert(loc_next >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
135 ll_next(left) = right;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
136 if (loc_prev >= 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
137 ll_prev(right) = left;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
138 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
139 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
140
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
141 void cx_linked_list_unlink(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
142 void *left,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
143 void *right,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
144 ptrdiff_t loc_prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
145 ptrdiff_t loc_next
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
146 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
147 assert (loc_next >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
148 assert(ll_next(left) == right);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
149 ll_next(left) = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
150 if (loc_prev >= 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
151 assert(ll_prev(right) == left);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
152 ll_prev(right) = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
153 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
154 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
155
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
156 void cx_linked_list_add(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
157 void **begin,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
158 void **end,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
159 ptrdiff_t loc_prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
160 ptrdiff_t loc_next,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
161 void *new_node
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
162 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
163 void *last;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
164 if (end == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
165 assert(begin != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
166 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
167 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
168 last = *end;
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 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
171 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
172
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
173 void cx_linked_list_prepend(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
174 void **begin,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
175 void **end,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
176 ptrdiff_t loc_prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
177 ptrdiff_t loc_next,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
178 void *new_node
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 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
181 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
182
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
183 void cx_linked_list_insert(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
184 void **begin,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
185 void **end,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
186 ptrdiff_t loc_prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
187 ptrdiff_t loc_next,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
188 void *node,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
189 void *new_node
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 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
192 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
193
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
194 void cx_linked_list_insert_chain(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
195 void **begin,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
196 void **end,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
197 ptrdiff_t loc_prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
198 ptrdiff_t loc_next,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
199 void *node,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
200 void *insert_begin,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
201 void *insert_end
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
202 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
203 // 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
204 if (insert_end == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
205 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
206 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
207
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
208 // determine the successor
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
209 void *successor;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
210 if (node == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
211 assert(begin != NULL || (end != NULL && loc_prev >= 0));
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
212 if (begin != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
213 successor = *begin;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
214 *begin = insert_begin;
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 = *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
217 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
218 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
219 successor = ll_next(node);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
220 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
221 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
222
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
223 if (successor == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
224 // the list ends with the new chain
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
225 if (end != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
226 *end = insert_end;
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 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
229 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
230 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
231 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
232
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
233 void cx_linked_list_remove(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
234 void **begin,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
235 void **end,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
236 ptrdiff_t loc_prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
237 ptrdiff_t loc_next,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
238 void *node
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
239 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
240 assert(node != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
241 assert(loc_next >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
242 assert(loc_prev >= 0 || begin != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
243
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
244 // find adjacent nodes
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
245 void *next = ll_next(node);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
246 void *prev;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
247 if (loc_prev >= 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
248 prev = ll_prev(node);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
249 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
250 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
251 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
252
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
253 // 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
254 if (prev == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
255 if (begin != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
256 *begin = 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 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
259 ll_next(prev) = next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
260 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
261
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
262 // 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
263 if (next == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
264 if (end != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
265 *end = 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 } else if (loc_prev >= 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
268 ll_prev(next) = prev;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
269 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
270 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
271
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
272 size_t cx_linked_list_size(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
273 void const *node,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
274 ptrdiff_t loc_next
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
275 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
276 assert(loc_next >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
277 size_t size = 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
278 while (node != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
279 node = ll_next(node);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
280 size++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
281 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
282 return size;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
283 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
284
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
285 static void *cx_linked_list_sort_merge(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
286 ptrdiff_t loc_prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
287 ptrdiff_t loc_next,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
288 ptrdiff_t loc_data,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
289 bool follow_ptr,
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,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
294 CxListComparator cmp_func
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
295 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
296 const size_t sbo_len = 1024;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
297 void *sbo[sbo_len];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
298 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
299 if (sorted == NULL) abort();
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
300 void *rc, *lc;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
301
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
302 lc = ls;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
303 rc = le;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
304 size_t n = 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
305 while (lc && lc != le && rc != re) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
306 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
307 sorted[n] = lc;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
308 lc = ll_next(lc);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
309 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
310 sorted[n] = rc;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
311 rc = ll_next(rc);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
312 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
313 n++;
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 while (lc && lc != le) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
316 sorted[n] = lc;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
317 lc = ll_next(lc);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
318 n++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
319 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
320 while (rc && rc != re) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
321 sorted[n] = rc;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
322 rc = ll_next(rc);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
323 n++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
324 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
325
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
326 // Update pointer
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
327 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
328 cx_for_n (i, length - 1) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
329 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
330 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
331 ll_next(sorted[length - 1]) = NULL;
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 void *ret = sorted[0];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
334 if (sorted != sbo) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
335 free(sorted);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
336 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
337 return ret;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
338 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
339
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
340 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
341 void **begin,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
342 void **end,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
343 ptrdiff_t loc_prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
344 ptrdiff_t loc_next,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
345 ptrdiff_t loc_data,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
346 bool follow_ptr,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
347 CxListComparator cmp_func
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
348 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
349 assert(begin != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
350 assert(loc_next >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
351 assert(loc_data >= 0);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
352 assert(cmp_func);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
353
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
354 void *lc, *ls, *le, *re;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
355
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
356 // set start node
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
357 ls = *begin;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
358
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
359 // check how many elements are already sorted
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
360 lc = ls;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
361 size_t ln = 1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
362 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
363 lc = ll_next(lc);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
364 ln++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
365 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
366 le = ll_next(lc);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
367
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
368 // 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
369 if (le != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
370 void *rc;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
371 size_t rn = 1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
372 rc = le;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
373 // skip already sorted elements
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
374 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
375 rc = ll_next(rc);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
376 rn++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
377 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
378 re = ll_next(rc);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
379
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
380 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
381 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
382 ln + rn, ls, le, re, cmp_func);
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 // Something left? Sort it!
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
385 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
386 if (remainder_length > 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
387 void *remainder = re;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
388 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
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 // merge sorted list with (also sorted) remainder
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
391 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
392 ln + rn + remainder_length,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
393 sorted, remainder, NULL, cmp_func);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
394 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
395 // no remainder - we've got our sorted list
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
396 *begin = sorted;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
397 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
398 if (end) *end = cx_linked_list_last(sorted, loc_next);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
399 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
400 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
401
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
402 int cx_linked_list_compare(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
403 void const *begin_left,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
404 void const *begin_right,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
405 ptrdiff_t loc_advance,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
406 ptrdiff_t loc_data,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
407 bool follow_ptr_left,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
408 bool follow_ptr_right,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
409 CxListComparator cmp_func
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
410 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
411 void const *left = begin_left, *right = begin_right;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
412
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
413 while (left != NULL && right != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
414 void const *left_data = ll_data_f(left, follow_ptr_left);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
415 void const *right_data = ll_data_f(right, follow_ptr_right);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
416 int result = cmp_func(left_data, right_data);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
417 if (result != 0) return result;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
418 left = ll_advance(left);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
419 right = ll_advance(right);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
420 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
421
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
422 if (left != NULL) { return 1; }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
423 else if (right != NULL) { return -1; }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
424 else { return 0; }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
425 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
426
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
427 void cx_linked_list_reverse(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
428 void **begin,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
429 void **end,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
430 ptrdiff_t loc_prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
431 ptrdiff_t loc_next
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
432 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
433 assert(begin != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
434 assert(loc_next >= 0);
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 // swap all links
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
437 void *prev = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
438 void *cur = *begin;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
439 while (cur != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
440 void *next = ll_next(cur);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
441
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
442 ll_next(cur) = prev;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
443 if (loc_prev >= 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
444 ll_prev(cur) = next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
445 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
446
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
447 prev = cur;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
448 cur = next;
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
451 // update begin and end
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
452 if (end != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
453 *end = *begin;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
454 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
455 *begin = prev;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
456 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
457
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
458 // HIGH LEVEL LINKED LIST IMPLEMENTATION
415
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 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
461 struct cx_linked_list_node {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
462 cx_linked_list_node *prev;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
463 cx_linked_list_node *next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
464 char payload[];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
465 };
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
466
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
467 #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
468 #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
469 #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
470
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
471 typedef struct {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
472 struct cx_list_s base;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
473 cx_linked_list_node *begin;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
474 cx_linked_list_node *end;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
475 bool follow_ptr;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
476 } cx_linked_list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
477
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
478 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
479 cx_linked_list const *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
480 size_t index
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 if (index >= list->base.size) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
483 return NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
484 } else if (index > list->base.size / 2) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
485 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
486 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
487 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
488 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
489 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
490
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
491 static int cx_ll_insert_at(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
492 struct cx_list_s *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
493 cx_linked_list_node *node,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
494 void const *elem
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
495 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
496
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
497 // create the new new_node
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
498 cx_linked_list_node *new_node = cxMalloc(list->allocator,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
499 sizeof(cx_linked_list_node) + list->itemsize);
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 // sortir if failed
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
502 if (new_node == NULL) return 1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
503
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
504 // initialize new new_node
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
505 new_node->prev = new_node->next = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
506 memcpy(new_node->payload, elem, list->itemsize);
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 // insert
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
509 cx_linked_list *ll = (cx_linked_list *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
510 cx_linked_list_insert_chain(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
511 (void **) &ll->begin, (void **) &ll->end,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
512 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
513 node, new_node, new_node
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
514 );
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
515
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
516 // increase the size and return
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
517 list->size++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
518 return 0;
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
521 static int cx_ll_insert(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
522 struct cx_list_s *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
523 size_t index,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
524 void const *elem
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
525 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
526 // out-of bounds check
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
527 if (index > list->size) return 1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
528
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
529 // find position efficiently
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
530 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
531
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
532 // perform insert
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
533 return cx_ll_insert_at(list, node, elem);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
534 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
535
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
536 static int cx_ll_add(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
537 struct cx_list_s *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
538 void const *elem
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
539 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
540 return cx_ll_insert(list, list->size, elem);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
541 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
542
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
543 static size_t cx_ll_add_array(
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
544 struct cx_list_s *list,
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
545 void const *array,
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
546 size_t n
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
547 ) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
548 // TODO: redirect to cx_ll_insert_array
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
549 cx_for_n (i, n) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
550 if (cx_ll_add(list, ((char const *) array) + i * list->itemsize)) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
551 return i;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
552 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
553 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
554 return n;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
555 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
556
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
557 static int cx_pll_insert(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
558 struct cx_list_s *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
559 size_t index,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
560 void const *elem
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
561 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
562 return cx_ll_insert(list, index, &elem);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
563 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
564
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
565 static int cx_pll_add(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
566 struct cx_list_s *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
567 void const *elem
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
568 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
569 return cx_ll_insert(list, list->size, &elem);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
570 }
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 static int cx_ll_remove(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
573 struct cx_list_s *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
574 size_t index
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
575 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
576 cx_linked_list *ll = (cx_linked_list *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
577 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
578
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
579 // out-of-bounds check
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
580 if (node == NULL) return 1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
581
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
582 // remove
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
583 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
584 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
585
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
586 // adjust size
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
587 list->size--;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
588
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
589 // free and return
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
590 cxFree(list->allocator, node);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
591
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
592 return 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
593 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
594
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
595 static void *cx_ll_at(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
596 struct cx_list_s const *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
597 size_t index
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
598 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
599 cx_linked_list *ll = (cx_linked_list *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
600 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
601 return node == NULL ? NULL : node->payload;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
602 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
603
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
604 static void *cx_pll_at(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
605 struct cx_list_s const *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
606 size_t index
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
607 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
608 cx_linked_list *ll = (cx_linked_list *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
609 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
610 return node == NULL ? NULL : *(void **) node->payload;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
611 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
612
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
613 static size_t cx_ll_find(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
614 struct cx_list_s const *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
615 void const *elem
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
616 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
617 cx_linked_list *ll = (cx_linked_list *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
618 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
619 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
620 ll->follow_ptr, list->cmpfunc, elem);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
621 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
622
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
623 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
624 cx_linked_list *ll = (cx_linked_list *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
625 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
626 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
627 ll->follow_ptr, list->cmpfunc);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
628 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
629
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
630 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
631 cx_linked_list *ll = (cx_linked_list *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
632 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
633 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
634
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
635 static int cx_ll_compare(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
636 struct cx_list_s const *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
637 struct cx_list_s const *other
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
638 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
639 cx_linked_list *left = (cx_linked_list *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
640 cx_linked_list *right = (cx_linked_list *) other;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
641 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
642 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
643 left->follow_ptr, right->follow_ptr, list->cmpfunc);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
644 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
645
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
646 static bool cx_ll_iter_valid(void const *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
647 struct cx_iterator_s const *iter = it;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
648 return iter->elem_handle != NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
649 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
650
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
651 static void cx_ll_iter_next(void *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
652 struct cx_iterator_base_s *itbase = it;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
653 if (itbase->remove) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
654 itbase->remove = false;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
655 struct cx_mut_iterator_s *iter = it;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
656 cx_linked_list *ll = iter->src_handle;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
657 cx_linked_list_node *node = iter->elem_handle;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
658 iter->elem_handle = node->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
659 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
660 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
661 ll->base.size--;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
662 cxFree(ll->base.allocator, node);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
663 } else {
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
664 struct cx_iterator_s *iter = it;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
665 iter->index++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
666 cx_linked_list_node *node = iter->elem_handle;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
667 iter->elem_handle = node->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
668 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
669 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
670
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
671 static void *cx_ll_iter_current(void const *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
672 struct cx_iterator_s const *iter = it;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
673 cx_linked_list_node *node = iter->elem_handle;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
674 return node->payload;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
675 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
676
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
677 static void *cx_pll_iter_current(void const *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
678 struct cx_iterator_s const *iter = it;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
679 cx_linked_list_node *node = iter->elem_handle;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
680 return *(void **) node->payload;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
681 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
682
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
683 static bool cx_ll_iter_flag_rm(void *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
684 struct cx_iterator_base_s *iter = it;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
685 if (iter->mutating) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
686 iter->remove = true;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
687 return true;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
688 } else {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
689 return false;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
690 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
691 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
692
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
693 static CxIterator cx_ll_iterator(
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
694 struct cx_list_s const *list,
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
695 size_t index
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
696 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
697 CxIterator iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
698 iter.index = index;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
699 iter.src_handle = list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
700 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
701 iter.base.valid = cx_ll_iter_valid;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
702 iter.base.current = cx_ll_iter_current;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
703 iter.base.next = cx_ll_iter_next;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
704 iter.base.flag_removal = cx_ll_iter_flag_rm;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
705 iter.base.mutating = false;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
706 iter.base.remove = false;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
707 return iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
708 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
709
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
710 static CxIterator cx_pll_iterator(
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
711 struct cx_list_s const *list,
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
712 size_t index
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
713 ) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
714 CxIterator iter = cx_ll_iterator(list, index);
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
715 iter.base.current = cx_pll_iter_current;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
716 return iter;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
717 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
718
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
719 static CxMutIterator cx_ll_mut_iterator(
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
720 struct cx_list_s *list,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
721 size_t index
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
722 ) {
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
723 CxIterator it = cx_ll_iterator(list, index);
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
724 it.base.mutating = true;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
725
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
726 // we know the iterators share the same memory layout
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
727 CxMutIterator iter;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
728 memcpy(&iter, &it, sizeof(CxMutIterator));
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
729 return iter;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
730 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
731
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
732 static CxMutIterator cx_pll_mut_iterator(
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
733 struct cx_list_s *list,
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
734 size_t index
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
735 ) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
736 CxMutIterator iter = cx_ll_mut_iterator(list, index);
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
737 iter.base.current = cx_pll_iter_current;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
738 return iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
739 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
740
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
741 static int cx_ll_insert_iter(
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
742 CxMutIterator *iter,
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
743 void const *elem,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
744 int prepend
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 struct cx_list_s *list = iter->src_handle;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
747 cx_linked_list_node *node = iter->elem_handle;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
748 if (node != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
749 assert(prepend >= 0 && prepend <= 1);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
750 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
751 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
752 iter->index += prepend * (0 == result);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
753 return result;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
754 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
755 int result = cx_ll_insert(list, list->size, elem);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
756 iter->index = list->size;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
757 return result;
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 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
760
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
761 static int cx_pll_insert_iter(
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
762 CxMutIterator *iter,
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
763 void const *elem,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
764 int prepend
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
765 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
766 return cx_ll_insert_iter(iter, &elem, prepend);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
767 }
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 static void cx_ll_destructor(CxList *list) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
770 cx_linked_list *ll = (cx_linked_list *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
771
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
772 cx_linked_list_node *node = ll->begin;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
773 while (node) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
774 void *next = node->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
775 cxFree(list->allocator, node);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
776 node = next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
777 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
778 // do not free the list pointer, this is just a destructor!
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
779 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
780
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
781 static cx_list_class cx_linked_list_class = {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
782 cx_ll_destructor,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
783 cx_ll_add,
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
784 cx_ll_add_array,
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
785 cx_ll_insert,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
786 cx_ll_insert_iter,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
787 cx_ll_remove,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
788 cx_ll_at,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
789 cx_ll_find,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
790 cx_ll_sort,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
791 cx_ll_compare,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
792 cx_ll_reverse,
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
793 cx_ll_iterator,
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
794 cx_ll_mut_iterator,
415
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
797 static cx_list_class cx_pointer_linked_list_class = {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
798 cx_ll_destructor,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
799 cx_pll_add,
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
800 cx_ll_add_array,
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
801 cx_pll_insert,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
802 cx_pll_insert_iter,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
803 cx_ll_remove,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
804 cx_pll_at,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
805 cx_ll_find,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
806 cx_ll_sort,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
807 cx_ll_compare,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
808 cx_ll_reverse,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
809 cx_pll_iterator,
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
810 cx_pll_mut_iterator,
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
811 };
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
812
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
813 CxList *cxLinkedListCreate(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
814 CxAllocator const *allocator,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
815 CxListComparator comparator,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
816 size_t item_size
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
817 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
818 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
819 if (list == NULL) return NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
820
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
821 list->follow_ptr = false;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
822 list->base.cl = &cx_linked_list_class;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
823 list->base.allocator = allocator;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
824 list->base.cmpfunc = comparator;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
825 list->base.itemsize = item_size;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
826 list->base.capacity = SIZE_MAX;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
827
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
828 return (CxList *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
829 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
830
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
831 CxList *cxPointerLinkedListCreate(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
832 CxAllocator const *allocator,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
833 CxListComparator comparator
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
834 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
835 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
836 if (list == NULL) return NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
837
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
838 list->follow_ptr = true;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
839 list->base.cl = &cx_pointer_linked_list_class;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
840 list->base.allocator = allocator;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
841 list->base.cmpfunc = comparator;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
842 list->base.itemsize = sizeof(void *);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
843 list->base.capacity = SIZE_MAX;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
844
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
845 return (CxList *) list;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
846 }

mercurial