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 1 : void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp)
36 : {
37 1 : tree->root = 0;
38 1 : tree->count = 0;
39 1 : tree->cmp = cmp;
40 1 : }
41 :
42 34670891 : static tommy_ssize_t tommy_tree_delta(tommy_tree_node* root)
43 : {
44 34670891 : tommy_ssize_t left_height = root->prev ? root->prev->index : 0;
45 34670891 : tommy_ssize_t right_height = root->next ? root->next->index : 0;
46 :
47 34670891 : return left_height - right_height;
48 : }
49 :
50 : /* AVL tree operations */
51 : static tommy_tree_node* tommy_tree_balance(tommy_tree_node*);
52 :
53 1323565 : static tommy_tree_node* tommy_tree_rotate_left(tommy_tree_node* root)
54 : {
55 1323565 : tommy_tree_node* next = root->next;
56 :
57 1323565 : root->next = next->prev;
58 :
59 1323565 : next->prev = tommy_tree_balance(root);
60 :
61 1323565 : return tommy_tree_balance(next);
62 : }
63 :
64 663118 : static tommy_tree_node* tommy_tree_rotate_right(tommy_tree_node* root)
65 : {
66 663118 : tommy_tree_node* prev = root->prev;
67 :
68 663118 : root->prev = prev->next;
69 :
70 663118 : prev->next = tommy_tree_balance(root);
71 :
72 663118 : return tommy_tree_balance(prev);
73 : }
74 :
75 1317359 : static tommy_tree_node* tommy_tree_move_right(tommy_tree_node* root, tommy_tree_node* node)
76 : {
77 1317359 : if (!root)
78 750000 : return node;
79 :
80 567359 : root->next = tommy_tree_move_right(root->next, node);
81 :
82 567359 : return tommy_tree_balance(root);
83 : }
84 :
85 32941689 : static tommy_tree_node* tommy_tree_balance(tommy_tree_node* root)
86 : {
87 32941689 : tommy_ssize_t delta = tommy_tree_delta(root);
88 :
89 32941689 : if (delta < -1) {
90 1262823 : if (tommy_tree_delta(root->next) > 0)
91 196739 : root->next = tommy_tree_rotate_right(root->next);
92 1262823 : return tommy_tree_rotate_left(root);
93 : }
94 :
95 31678866 : if (delta > 1) {
96 466379 : if (tommy_tree_delta(root->prev) < 0)
97 60742 : root->prev = tommy_tree_rotate_left(root->prev);
98 466379 : return tommy_tree_rotate_right(root);
99 : }
100 :
101 : /* recompute key */
102 31212487 : root->index = 0;
103 :
104 31212487 : if (root->prev && root->prev->index > root->index)
105 29060015 : root->index = root->prev->index;
106 :
107 31212487 : if (root->next && root->next->index > root->index)
108 7300994 : root->index = root->next->index;
109 :
110 : /* count itself */
111 31212487 : root->index += 1;
112 :
113 31212487 : return root;
114 : }
115 :
116 18185468 : 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 18185468 : if (!root)
121 750000 : return *let;
122 :
123 17435468 : c = cmp((*let)->data, root->data);
124 :
125 17435468 : if (c < 0) {
126 8635115 : root->prev = tommy_tree_insert_node(cmp, root->prev, let);
127 8635115 : return tommy_tree_balance(root);
128 : }
129 :
130 8800353 : if (c > 0) {
131 8550353 : root->next = tommy_tree_insert_node(cmp, root->next, let);
132 8550353 : return tommy_tree_balance(root);
133 : }
134 :
135 : /* already present, set the return pointer */
136 250000 : *let = root;
137 :
138 250000 : return root;
139 : }
140 :
141 1000000 : void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data)
142 : {
143 1000000 : tommy_tree_node* insert = node;
144 :
145 1000000 : insert->data = data;
146 1000000 : insert->prev = 0;
147 1000000 : insert->next = 0;
148 1000000 : insert->index = 0;
149 :
150 1000000 : tree->root = tommy_tree_insert_node(tree->cmp, tree->root, &insert);
151 :
152 1000000 : if (insert == node)
153 750000 : ++tree->count;
154 :
155 1000000 : return insert->data;
156 : }
157 :
158 12090496 : 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 12090496 : if (!root)
163 125000 : return 0;
164 :
165 11965496 : c = cmp(data, root->data);
166 :
167 11965496 : if (c < 0) {
168 6435032 : root->prev = tommy_tree_remove_node(cmp, root->prev, data, let);
169 6435032 : return tommy_tree_balance(root);
170 : }
171 :
172 5530464 : if (c > 0) {
173 4780464 : root->next = tommy_tree_remove_node(cmp, root->next, data, let);
174 4780464 : return tommy_tree_balance(root);
175 : }
176 :
177 : /* found */
178 750000 : *let = root;
179 :
180 750000 : return tommy_tree_move_right(root->prev, root->next);
181 : }
182 :
183 875000 : void* tommy_tree_remove(tommy_tree* tree, void* data)
184 : {
185 875000 : tommy_tree_node* node = 0;
186 :
187 875000 : tree->root = tommy_tree_remove_node(tree->cmp, tree->root, data, &node);
188 :
189 875000 : if (!node)
190 125000 : return 0;
191 :
192 750000 : --tree->count;
193 :
194 750000 : return node->data;
195 : }
196 :
197 8000014 : static tommy_tree_node* tommy_tree_search_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data)
198 : {
199 : int c;
200 :
201 8000014 : if (!root)
202 250000 : return 0;
203 :
204 7750014 : c = cmp(data, root->data);
205 :
206 7750014 : if (c < 0)
207 5653752 : return tommy_tree_search_node(cmp, root->prev, data);
208 :
209 2096262 : if (c > 0)
210 1846262 : return tommy_tree_search_node(cmp, root->next, data);
211 :
212 250000 : return root;
213 : }
214 :
215 250000 : void* tommy_tree_search(tommy_tree* tree, void* data)
216 : {
217 250000 : tommy_tree_node* node = tommy_tree_search_node(tree->cmp, tree->root, data);
218 :
219 250000 : if (!node)
220 125000 : return 0;
221 :
222 125000 : return node->data;
223 : }
224 :
225 250000 : void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg)
226 : {
227 250000 : tommy_tree_node* node = tommy_tree_search_node(cmp, tree->root, cmp_arg);
228 :
229 250000 : if (!node)
230 125000 : return 0;
231 :
232 125000 : return node->data;
233 : }
234 :
235 625000 : void* tommy_tree_remove_existing(tommy_tree* tree, tommy_tree_node* node)
236 : {
237 625000 : void* data = tommy_tree_remove(tree, node->data);
238 :
239 625000 : assert(data != 0);
240 :
241 625000 : return data;
242 : }
243 :
244 500001 : static void tommy_tree_foreach_node(tommy_tree_node* root, tommy_foreach_func* func)
245 : {
246 : tommy_tree_node* next;
247 :
248 500001 : if (!root)
249 250001 : return;
250 :
251 250000 : tommy_tree_foreach_node(root->prev, func);
252 :
253 : /* make a copy in case func is free() */
254 250000 : next = root->next;
255 :
256 250000 : func(root->data);
257 :
258 250000 : tommy_tree_foreach_node(next, func);
259 : }
260 :
261 1 : void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func)
262 : {
263 1 : tommy_tree_foreach_node(tree->root, func);
264 1 : }
265 :
266 500001 : 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 500001 : if (!root)
271 250001 : return;
272 :
273 250000 : tommy_tree_foreach_arg_node(root->prev, func, arg);
274 :
275 : /* make a copy in case func is free() */
276 250000 : next = root->next;
277 :
278 250000 : func(arg, root->data);
279 :
280 250000 : tommy_tree_foreach_arg_node(next, func, arg);
281 : }
282 :
283 1 : void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg)
284 : {
285 1 : tommy_tree_foreach_arg_node(tree->root, func, arg);
286 1 : }
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 :
|
