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 3207 : void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp)
36 : {
37 3207 : tree->root = 0;
38 3207 : tree->count = 0;
39 3207 : tree->cmp = cmp;
40 3207 : }
41 :
42 112284588 : static tommy_ssize_t tommy_tree_delta(tommy_tree_node* root)
43 : {
44 112284588 : tommy_ssize_t left_height = root->prev ? root->prev->index : 0;
45 112284588 : tommy_ssize_t right_height = root->next ? root->next->index : 0;
46 :
47 112284588 : return left_height - right_height;
48 : }
49 :
50 : /* AVL tree operations */
51 : static tommy_tree_node* tommy_tree_balance(tommy_tree_node*);
52 :
53 7486713 : static tommy_tree_node* tommy_tree_rotate_left(tommy_tree_node* root)
54 : {
55 7486713 : tommy_tree_node* next = root->next;
56 :
57 7486713 : root->next = next->prev;
58 :
59 7486713 : next->prev = tommy_tree_balance(root);
60 :
61 7486713 : return tommy_tree_balance(next);
62 : }
63 :
64 182144 : static tommy_tree_node* tommy_tree_rotate_right(tommy_tree_node* root)
65 : {
66 182144 : tommy_tree_node* prev = root->prev;
67 :
68 182144 : root->prev = prev->next;
69 :
70 182144 : prev->next = tommy_tree_balance(root);
71 :
72 182144 : return tommy_tree_balance(prev);
73 : }
74 :
75 175482 : static tommy_tree_node* tommy_tree_move_right(tommy_tree_node* root, tommy_tree_node* node)
76 : {
77 175482 : if (!root)
78 75984 : return node;
79 :
80 99498 : root->next = tommy_tree_move_right(root->next, node);
81 :
82 99498 : return tommy_tree_balance(root);
83 : }
84 :
85 104782540 : static tommy_tree_node* tommy_tree_balance(tommy_tree_node* root)
86 : {
87 104782540 : tommy_ssize_t delta = tommy_tree_delta(root);
88 :
89 104782540 : if (delta < -1) {
90 7363666 : if (tommy_tree_delta(root->next) > 0)
91 43762 : root->next = tommy_tree_rotate_right(root->next);
92 7363666 : return tommy_tree_rotate_left(root);
93 : }
94 :
95 97418874 : if (delta > 1) {
96 138382 : if (tommy_tree_delta(root->prev) < 0)
97 123047 : root->prev = tommy_tree_rotate_left(root->prev);
98 138382 : return tommy_tree_rotate_right(root);
99 : }
100 :
101 : /* recompute key */
102 97280492 : root->index = 0;
103 :
104 97280492 : if (root->prev && root->prev->index > root->index)
105 78672822 : root->index = root->prev->index;
106 :
107 97280492 : if (root->next && root->next->index > root->index)
108 44743628 : root->index = root->next->index;
109 :
110 : /* count itself */
111 97280492 : root->index += 1;
112 :
113 97280492 : return root;
114 : }
115 :
116 96147634 : 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 96147634 : if (!root)
121 7479052 : return *let;
122 :
123 88668582 : c = cmp((*let)->data, root->data);
124 :
125 88668582 : if (c < 0) {
126 1658515 : root->prev = tommy_tree_insert_node(cmp, root->prev, let);
127 1658515 : return tommy_tree_balance(root);
128 : }
129 :
130 87010067 : if (c > 0) {
131 87010066 : root->next = tommy_tree_insert_node(cmp, root->next, let);
132 87010066 : 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 7479053 : void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data)
142 : {
143 7479053 : tommy_tree_node* insert = node;
144 :
145 7479053 : insert->data = data;
146 7479053 : insert->prev = 0;
147 7479053 : insert->next = 0;
148 7479053 : insert->index = 0;
149 :
150 7479053 : tree->root = tommy_tree_insert_node(tree->cmp, tree->root, &insert);
151 :
152 7479053 : if (insert == node)
153 7479052 : ++tree->count;
154 :
155 7479053 : return insert->data;
156 : }
157 :
158 752859 : 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 752859 : if (!root)
163 128 : return 0;
164 :
165 752731 : c = cmp(data, root->data);
166 :
167 752731 : if (c < 0) {
168 310947 : root->prev = tommy_tree_remove_node(cmp, root->prev, data, let);
169 310947 : return tommy_tree_balance(root);
170 : }
171 :
172 441784 : if (c > 0) {
173 365800 : root->next = tommy_tree_remove_node(cmp, root->next, data, let);
174 365800 : return tommy_tree_balance(root);
175 : }
176 :
177 : /* found */
178 75984 : *let = root;
179 :
180 75984 : return tommy_tree_move_right(root->prev, root->next);
181 : }
182 :
183 76112 : void* tommy_tree_remove(tommy_tree* tree, void* data)
184 : {
185 76112 : tommy_tree_node* node = 0;
186 :
187 76112 : tree->root = tommy_tree_remove_node(tree->cmp, tree->root, data, &node);
188 :
189 76112 : if (!node)
190 128 : return 0;
191 :
192 75984 : --tree->count;
193 :
194 75984 : return node->data;
195 : }
196 :
197 124647940 : static tommy_tree_node* tommy_tree_search_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data)
198 : {
199 : int c;
200 :
201 124647940 : if (!root)
202 1481018 : return 0;
203 :
204 123166922 : c = cmp(data, root->data);
205 :
206 123166922 : if (c < 0)
207 44542253 : return tommy_tree_search_node(cmp, root->prev, data);
208 :
209 78624669 : if (c > 0)
210 68915282 : return tommy_tree_search_node(cmp, root->next, data);
211 :
212 9709387 : return root;
213 : }
214 :
215 2 : 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 11190403 : void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg)
226 : {
227 11190403 : tommy_tree_node* node = tommy_tree_search_node(cmp, tree->root, cmp_arg);
228 :
229 11190403 : if (!node)
230 1481017 : return 0;
231 :
232 9709386 : return node->data;
233 : }
234 :
235 128 : 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 7313558 : static void tommy_tree_foreach_node(tommy_tree_node* root, tommy_foreach_func* func)
245 : {
246 : tommy_tree_node* next;
247 :
248 7313558 : if (!root)
249 3657551 : return;
250 :
251 3656007 : tommy_tree_foreach_node(root->prev, func);
252 :
253 : /* make a copy in case func is free() */
254 3656007 : next = root->next;
255 :
256 3656007 : func(root->data);
257 :
258 3656007 : tommy_tree_foreach_node(next, func);
259 : }
260 :
261 1544 : void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func)
262 : {
263 1544 : tommy_tree_foreach_node(tree->root, func);
264 1544 : }
265 :
266 26162749 : 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 26162749 : if (!root)
271 13084339 : return;
272 :
273 13078410 : tommy_tree_foreach_arg_node(root->prev, func, arg);
274 :
275 : /* make a copy in case func is free() */
276 13078410 : next = root->next;
277 :
278 13078410 : func(arg, root->data);
279 :
280 13078410 : tommy_tree_foreach_arg_node(next, func, arg);
281 : }
282 :
283 5929 : void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg)
284 : {
285 5929 : tommy_tree_foreach_arg_node(tree->root, func, arg);
286 5929 : }
287 :
288 1 : tommy_size_t tommy_tree_memory_usage(tommy_tree* tree)
289 : {
290 1 : return tommy_tree_count(tree) * sizeof(tommy_tree_node);
291 : }
292 :
|
