ucx/linked_list.c

Mon, 06 Jan 2025 21:18:36 +0100

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Mon, 06 Jan 2025 21:18:36 +0100
changeset 852
83fdf679df99
parent 816
839fefbdedc7
permissions
-rw-r--r--

update ucx

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

mercurial