ucx/linked_list.c

Tue, 30 Jan 2024 14:01:04 +0100

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Tue, 30 Jan 2024 14:01:04 +0100
changeset 14
872d570ae843
parent 2
fbdfaacc4182
child 49
2f71f4ee247a
permissions
-rw-r--r--

implement window new button

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

mercurial