Mon, 06 Jan 2025 21:18:36 +0100
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 | 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 | 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 | 59 | ssize_t cx_linked_list_find( |
852 | 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 | 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 | 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 | 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 | 88 | const void *node = start; |
748 | 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 | 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 | 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 | 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 | 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 | 117 | const void *cur = node; |
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 | 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 | 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 | 135 | const void *cur = begin; |
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 | 249 | void cx_linked_list_insert_sorted( |
250 | void **begin, | |
251 | void **end, | |
252 | ptrdiff_t loc_prev, | |
253 | ptrdiff_t loc_next, | |
254 | void *new_node, | |
255 | cx_compare_func cmp_func | |
256 | ) { | |
257 | assert(ll_next(new_node) == NULL); | |
258 | cx_linked_list_insert_sorted_chain( | |
259 | begin, end, loc_prev, loc_next, new_node, cmp_func); | |
260 | } | |
261 | ||
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 | 267 | void *insert_begin, |
268 | cx_compare_func cmp_func | |
269 | ) { | |
270 | assert(begin != NULL); | |
271 | assert(loc_next >= 0); | |
272 | assert(insert_begin != NULL); | |
273 | ||
274 | // track currently observed nodes | |
275 | void *dest_prev = NULL; | |
276 | void *dest = *begin; | |
277 | void *src = insert_begin; | |
278 | ||
279 | // special case: list is empty | |
280 | if (dest == NULL) { | |
281 | *begin = src; | |
282 | if (end != NULL) { | |
283 | *end = cx_linked_list_last(src, loc_next); | |
284 | } | |
285 | return; | |
286 | } | |
287 | ||
288 | // search the list for insertion points | |
289 | while (dest != NULL && src != NULL) { | |
290 | // compare current list node with source node | |
291 | // if less or equal, skip | |
292 | if (cmp_func(dest, src) <= 0) { | |
293 | dest_prev = dest; | |
294 | dest = ll_next(dest); | |
295 | continue; | |
296 | } | |
297 | ||
298 | // determine chain of elements that can be inserted | |
299 | void *end_of_chain = src; | |
300 | void *next_in_chain = ll_next(src); | |
301 | while (next_in_chain != NULL) { | |
302 | // once we become larger than the list elem, break | |
303 | if (cmp_func(dest, next_in_chain) <= 0) { | |
304 | break; | |
305 | } | |
306 | // otherwise, we can insert one more | |
307 | end_of_chain = next_in_chain; | |
308 | next_in_chain = ll_next(next_in_chain); | |
309 | } | |
310 | ||
311 | // insert the elements | |
312 | if (dest_prev == NULL) { | |
313 | // new begin | |
314 | *begin = src; | |
315 | } else { | |
316 | cx_linked_list_link(dest_prev, src, loc_prev, loc_next); | |
317 | } | |
318 | cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next); | |
319 | ||
320 | // continue with next | |
321 | src = next_in_chain; | |
322 | dest_prev = dest; | |
323 | dest = ll_next(dest); | |
324 | } | |
325 | ||
326 | // insert remaining items | |
327 | if (src != NULL) { | |
328 | cx_linked_list_link(dest_prev, src, loc_prev, loc_next); | |
329 | } | |
330 | ||
331 | // determine new end of list, if requested | |
332 | if (end != NULL) { | |
333 | *end = cx_linked_list_last( | |
334 | dest != NULL ? dest : dest_prev, loc_next); | |
335 | } | |
336 | } | |
337 | ||
338 | size_t cx_linked_list_remove_chain( | |
339 | void **begin, | |
340 | void **end, | |
341 | ptrdiff_t loc_prev, | |
342 | ptrdiff_t loc_next, | |
343 | void *node, | |
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 | 350 | // easy exit |
351 | if (num == 0) return 0; | |
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 | 361 | void *next = ll_next(node); |
362 | size_t removed = 1; | |
363 | for (; removed < num && next != NULL ; removed++) { | |
364 | next = ll_next(next); | |
365 | } | |
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 | 384 | |
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 | 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 | 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 | 413 | cx_compare_func cmp_func, |
414 | void **begin, | |
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 | 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 | 454 | *begin = sorted[0]; |
852 | 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 | 479 | // early exit when this list is empty |
480 | if (ls == NULL) return; | |
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 | 504 | void *sorted_begin, *sorted_end; |
505 | cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, | |
506 | ln + rn, ls, le, re, cmp_func, | |
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 | 516 | cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, |
517 | ln + rn + remainder_length, | |
518 | sorted_begin, remainder, NULL, cmp_func, | |
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 | 521 | *begin = sorted_begin; |
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 | 527 | const void *begin_left, |
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 | 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 | 536 | const void *left_data = ll_data(left); |
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 | 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 | 612 | static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) { |
613 | return cxMalloc(list->collection.allocator, | |
614 | sizeof(cx_linked_list_node) + list->collection.elem_size); | |
615 | } | |
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 | 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 | 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 | 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 | 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 | 667 | // we can add the remaining nodes and immediately advance to the inserted node |
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 | 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 | 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 | 685 | static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; |
686 | ||
687 | static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { | |
688 | const cx_linked_list_node *left = l; | |
689 | const cx_linked_list_node *right = r; | |
690 | return cx_ll_insert_sorted_cmp_func(left->payload, right->payload); | |
691 | } | |
692 | ||
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 | 695 | const void *array, |
696 | size_t n | |
697 | ) { | |
698 | // special case | |
699 | if (n == 0) return 0; | |
700 | ||
701 | // create a new chain of nodes | |
702 | cx_linked_list_node *chain = cx_ll_malloc_node(list); | |
703 | if (chain == NULL) return 0; | |
704 | ||
705 | memcpy(chain->payload, array, list->collection.elem_size); | |
706 | chain->prev = NULL; | |
707 | chain->next = NULL; | |
708 | ||
709 | // add all elements from the array to that chain | |
710 | cx_linked_list_node *prev = chain; | |
711 | const char *src = array; | |
712 | size_t inserted = 1; | |
713 | for (; inserted < n; inserted++) { | |
714 | cx_linked_list_node *next = cx_ll_malloc_node(list); | |
715 | if (next == NULL) break; | |
716 | src += list->collection.elem_size; | |
717 | memcpy(next->payload, src, list->collection.elem_size); | |
718 | prev->next = next; | |
719 | next->prev = prev; | |
720 | prev = next; | |
721 | } | |
722 | prev->next = NULL; | |
723 | ||
724 | // invoke the low level function | |
725 | cx_linked_list *ll = (cx_linked_list *) list; | |
726 | cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; | |
727 | cx_linked_list_insert_sorted_chain( | |
728 | (void **) &ll->begin, | |
729 | (void **) &ll->end, | |
730 | CX_LL_LOC_PREV, | |
731 | CX_LL_LOC_NEXT, | |
732 | chain, | |
733 | cx_ll_insert_sorted_cmp_helper | |
734 | ); | |
735 | ||
736 | // adjust the list metadata | |
737 | list->collection.size += inserted; | |
738 | ||
739 | return inserted; | |
740 | } | |
741 | ||
742 | static size_t cx_ll_remove( | |
743 | struct cx_list_s *list, | |
744 | size_t index, | |
745 | size_t num, | |
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 | 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 | 755 | size_t removed = cx_linked_list_remove_chain( |
756 | (void **) &ll->begin, | |
757 | (void **) &ll->end, | |
758 | CX_LL_LOC_PREV, | |
759 | CX_LL_LOC_NEXT, | |
760 | node, | |
761 | num | |
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 | 765 | list->collection.size -= removed; |
766 | ||
767 | // copy or destroy the removed chain | |
768 | if (targetbuf == NULL) { | |
769 | cx_linked_list_node *n = node; | |
770 | for (size_t i = 0; i < removed; i++) { | |
771 | // element destruction | |
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 | 774 | // free the node and advance |
775 | void *next = n->next; | |
776 | cxFree(list->collection.allocator, n); | |
777 | n = next; | |
778 | } | |
779 | } else { | |
780 | char *dest = targetbuf; | |
781 | cx_linked_list_node *n = node; | |
782 | for (size_t i = 0; i < removed; i++) { | |
783 | // copy payload | |
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 | 786 | // advance target buffer |
787 | dest += list->collection.elem_size; | |
788 | ||
789 | // free the node and advance | |
790 | void *next = n->next; | |
791 | cxFree(list->collection.allocator, n); | |
792 | n = next; | |
793 | } | |
794 | } | |
795 | ||
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 | 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 | 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 | 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 | 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 | 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 | 990 | const struct cx_list_s *list, |
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 | 1000 | static bool cx_ll_iter_valid(const void *it) { |
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 | 1046 | static void *cx_ll_iter_current(const void *it) { |
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 | 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 | 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 | 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 | 1082 | if (result == 0) { |
1083 | iter->elem_count++; | |
1084 | if (prepend) { | |
1085 | iter->index++; | |
1086 | } | |
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 | 1091 | if (result == 0) { |
1092 | iter->elem_count++; | |
1093 | iter->index = list->collection.size; | |
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 | 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 | 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 | 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 | 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 | } |