Line data Source code
1 : /*
2 : * Copyright (c) 2015, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : #include "tommytree.h"
29 :
30 : #include <assert.h> /* for assert */
31 :
32 : /******************************************************************************/
33 : /* tree */
34 :
35 3503 : TOMMY_API void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp)
36 : {
37 3503 : tree->root = 0;
38 3503 : tree->count = 0;
39 3503 : tree->cmp = cmp;
40 3503 : }
41 :
42 118998899 : static tommy_ssize_t tommy_tree_delta(tommy_tree_node* root)
43 : {
44 118998899 : tommy_ssize_t left_height = root->prev ? root->prev->index : 0;
45 118998899 : tommy_ssize_t right_height = root->next ? root->next->index : 0;
46 :
47 118998899 : return left_height - right_height;
48 : }
49 :
50 : /* AVL tree operations */
51 : static tommy_tree_node* tommy_tree_balance(tommy_tree_node*);
52 :
53 7949278 : static tommy_tree_node* tommy_tree_rotate_left(tommy_tree_node* root)
54 : {
55 7949278 : tommy_tree_node* next = root->next;
56 :
57 7949278 : root->next = next->prev;
58 :
59 7949278 : next->prev = tommy_tree_balance(root);
60 :
61 7949278 : return tommy_tree_balance(next);
62 : }
63 :
64 186401 : static tommy_tree_node* tommy_tree_rotate_right(tommy_tree_node* root)
65 : {
66 186401 : tommy_tree_node* prev = root->prev;
67 :
68 186401 : root->prev = prev->next;
69 :
70 186401 : prev->next = tommy_tree_balance(root);
71 :
72 186401 : return tommy_tree_balance(prev);
73 : }
74 :
75 180036 : static tommy_tree_node* tommy_tree_move_right(tommy_tree_node* root, tommy_tree_node* node)
76 : {
77 180036 : if (!root)
78 76802 : return node;
79 :
80 103234 : root->next = tommy_tree_move_right(root->next, node);
81 :
82 103234 : return tommy_tree_balance(root);
83 : }
84 :
85 111032190 : static tommy_tree_node* tommy_tree_balance(tommy_tree_node* root)
86 : {
87 111032190 : tommy_ssize_t delta = tommy_tree_delta(root);
88 :
89 111032190 : if (delta < -1) {
90 7826651 : if (tommy_tree_delta(root->next) > 0)
91 46343 : root->next = tommy_tree_rotate_right(root->next);
92 7826651 : return tommy_tree_rotate_left(root);
93 : }
94 :
95 103205539 : if (delta > 1) {
96 140058 : if (tommy_tree_delta(root->prev) < 0)
97 122627 : root->prev = tommy_tree_rotate_left(root->prev);
98 140058 : return tommy_tree_rotate_right(root);
99 : }
100 :
101 : /* recompute key */
102 103065481 : root->index = 0;
103 :
104 103065481 : if (root->prev && root->prev->index > root->index)
105 83311053 : root->index = root->prev->index;
106 :
107 103065481 : if (root->next && root->next->index > root->index)
108 47468605 : root->index = root->next->index;
109 :
110 : /* count itself */
111 103065481 : root->index += 1;
112 :
113 103065481 : return root;
114 : }
115 :
116 101908803 : static tommy_tree_node* tommy_tree_insert_node(tommy_compare_func* cmp, tommy_tree_node* root, tommy_tree_node** let)
117 : {
118 : int c;
119 :
120 101908803 : if (!root)
121 7939062 : return *let;
122 :
123 93969741 : c = cmp((*let)->data, root->data);
124 :
125 93969741 : if (c < 0) {
126 1723159 : root->prev = tommy_tree_insert_node(cmp, root->prev, let);
127 1723159 : return tommy_tree_balance(root);
128 : }
129 :
130 92246582 : if (c > 0) {
131 92246581 : root->next = tommy_tree_insert_node(cmp, root->next, let);
132 92246581 : return tommy_tree_balance(root);
133 : }
134 :
135 : /* already present, set the return pointer */
136 1 : *let = root;
137 :
138 1 : return root;
139 : }
140 :
141 7939063 : TOMMY_API void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data)
142 : {
143 7939063 : tommy_tree_node* insert = node;
144 :
145 7939063 : insert->data = data;
146 7939063 : insert->prev = 0;
147 7939063 : insert->next = 0;
148 7939063 : insert->index = 0;
149 :
150 7939063 : tree->root = tommy_tree_insert_node(tree->cmp, tree->root, &insert);
151 :
152 7939063 : if (insert == node)
153 7939062 : ++tree->count;
154 :
155 7939063 : return insert->data;
156 : }
157 :
158 764788 : static tommy_tree_node* tommy_tree_remove_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data, tommy_tree_node** let)
159 : {
160 : int c;
161 :
162 764788 : if (!root)
163 128 : return 0;
164 :
165 764660 : c = cmp(data, root->data);
166 :
167 764660 : if (c < 0) {
168 309500 : root->prev = tommy_tree_remove_node(cmp, root->prev, data, let);
169 309500 : return tommy_tree_balance(root);
170 : }
171 :
172 455160 : if (c > 0) {
173 378358 : root->next = tommy_tree_remove_node(cmp, root->next, data, let);
174 378358 : return tommy_tree_balance(root);
175 : }
176 :
177 : /* found */
178 76802 : *let = root;
179 :
180 76802 : return tommy_tree_move_right(root->prev, root->next);
181 : }
182 :
183 76930 : TOMMY_API void* tommy_tree_remove(tommy_tree* tree, void* data)
184 : {
185 76930 : tommy_tree_node* node = 0;
186 :
187 76930 : tree->root = tommy_tree_remove_node(tree->cmp, tree->root, data, &node);
188 :
189 76930 : if (!node)
190 128 : return 0;
191 :
192 76802 : --tree->count;
193 :
194 76802 : return node->data;
195 : }
196 :
197 192185055 : static tommy_tree_node* tommy_tree_search_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data)
198 : {
199 : int c;
200 :
201 192185055 : if (!root)
202 2136337 : return 0;
203 :
204 190048718 : c = cmp(data, root->data);
205 :
206 190048718 : if (c < 0)
207 70037663 : return tommy_tree_search_node(cmp, root->prev, data);
208 :
209 120011055 : if (c > 0)
210 104756738 : return tommy_tree_search_node(cmp, root->next, data);
211 :
212 15254317 : return root;
213 : }
214 :
215 2 : TOMMY_API void* tommy_tree_search(tommy_tree* tree, void* data)
216 : {
217 2 : tommy_tree_node* node = tommy_tree_search_node(tree->cmp, tree->root, data);
218 :
219 2 : if (!node)
220 1 : return 0;
221 :
222 1 : return node->data;
223 : }
224 :
225 17390652 : TOMMY_API void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg)
226 : {
227 17390652 : tommy_tree_node* node = tommy_tree_search_node(cmp, tree->root, cmp_arg);
228 :
229 17390652 : if (!node)
230 2136336 : return 0;
231 :
232 15254316 : return node->data;
233 : }
234 :
235 128 : TOMMY_API void* tommy_tree_remove_existing(tommy_tree* tree, tommy_tree_node* node)
236 : {
237 128 : void* data = tommy_tree_remove(tree, node->data);
238 :
239 128 : assert(data != 0);
240 :
241 128 : return data;
242 : }
243 :
244 7773286 : static void tommy_tree_foreach_node(tommy_tree_node* root, tommy_foreach_func* func)
245 : {
246 : tommy_tree_node* next;
247 :
248 7773286 : if (!root)
249 3887489 : return;
250 :
251 3885797 : tommy_tree_foreach_node(root->prev, func);
252 :
253 : /* make a copy in case func is free() */
254 3885797 : next = root->next;
255 :
256 3885797 : func(root->data);
257 :
258 3885797 : tommy_tree_foreach_node(next, func);
259 : }
260 :
261 1692 : TOMMY_API void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func)
262 : {
263 1692 : tommy_tree_foreach_node(tree->root, func);
264 1692 : }
265 :
266 28327581 : static void tommy_tree_foreach_arg_node(tommy_tree_node* root, tommy_foreach_arg_func* func, void* arg)
267 : {
268 : tommy_tree_node* next;
269 :
270 28327581 : if (!root)
271 14167013 : return;
272 :
273 14160568 : tommy_tree_foreach_arg_node(root->prev, func, arg);
274 :
275 : /* make a copy in case func is free() */
276 14160568 : next = root->next;
277 :
278 14160568 : func(arg, root->data);
279 :
280 14160568 : tommy_tree_foreach_arg_node(next, func, arg);
281 : }
282 :
283 6445 : TOMMY_API void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg)
284 : {
285 6445 : tommy_tree_foreach_arg_node(tree->root, func, arg);
286 6445 : }
287 :
288 1 : TOMMY_API tommy_size_t tommy_tree_memory_usage(tommy_tree* tree)
289 : {
290 1 : return tommy_tree_count(tree) * sizeof(tommy_tree_node);
291 : }
292 :
|
