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 3183 : void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp)
36 : {
37 3183 : tree->root = 0;
38 3183 : tree->count = 0;
39 3183 : tree->cmp = cmp;
40 3183 : }
41 :
42 112376770 : static int tommy_tree_delta(tommy_tree_node* root)
43 : {
44 112376770 : int left_height = root->prev ? root->prev->key : 0;
45 112376770 : int right_height = root->next ? root->next->key : 0;
46 :
47 112376770 : return left_height - right_height;
48 : }
49 :
50 : /* AVL tree operations */
51 : static tommy_tree_node* tommy_tree_balance(tommy_tree_node*);
52 :
53 7495470 : static tommy_tree_node* tommy_tree_rotate_left(tommy_tree_node* root)
54 : {
55 7495470 : tommy_tree_node* next = root->next;
56 :
57 7495470 : root->next = next->prev;
58 :
59 7495470 : next->prev = tommy_tree_balance(root);
60 :
61 7495470 : return tommy_tree_balance(next);
62 : }
63 :
64 191505 : static tommy_tree_node* tommy_tree_rotate_right(tommy_tree_node* root)
65 : {
66 191505 : tommy_tree_node* prev = root->prev;
67 :
68 191505 : root->prev = prev->next;
69 :
70 191505 : prev->next = tommy_tree_balance(root);
71 :
72 191505 : return tommy_tree_balance(prev);
73 : }
74 :
75 185127 : static tommy_tree_node* tommy_tree_move_right(tommy_tree_node* root, tommy_tree_node* node)
76 : {
77 185127 : if (!root)
78 79526 : return node;
79 :
80 105601 : root->next = tommy_tree_move_right(root->next, node);
81 :
82 105601 : return tommy_tree_balance(root);
83 : }
84 :
85 104867285 : static tommy_tree_node* tommy_tree_balance(tommy_tree_node* root)
86 : {
87 104867285 : int delta = tommy_tree_delta(root);
88 :
89 104867285 : if (delta < -1) {
90 7362263 : if (tommy_tree_delta(root->next) > 0)
91 44283 : root->next = tommy_tree_rotate_right(root->next);
92 7362263 : return tommy_tree_rotate_left(root);
93 : }
94 :
95 97505022 : if (delta > 1) {
96 147222 : if (tommy_tree_delta(root->prev) < 0)
97 133207 : root->prev = tommy_tree_rotate_left(root->prev);
98 147222 : return tommy_tree_rotate_right(root);
99 : }
100 :
101 : /* recompute key */
102 97357800 : root->key = 0;
103 :
104 97357800 : if (root->prev && root->prev->key > root->key)
105 78762656 : root->key = root->prev->key;
106 :
107 97357800 : if (root->next && root->next->key > root->key)
108 44762334 : root->key = root->next->key;
109 :
110 : /* count itself */
111 97357800 : root->key += 1;
112 :
113 97357800 : return root;
114 : }
115 :
116 96145167 : 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 96145167 : if (!root)
121 7470770 : return *let;
122 :
123 88674397 : c = cmp((*let)->data, root->data);
124 :
125 88674397 : if (c < 0) {
126 1709200 : root->prev = tommy_tree_insert_node(cmp, root->prev, let);
127 1709200 : return tommy_tree_balance(root);
128 : }
129 :
130 86965197 : if (c > 0) {
131 86965196 : root->next = tommy_tree_insert_node(cmp, root->next, let);
132 86965196 : 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 7470771 : void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data)
142 : {
143 7470771 : tommy_tree_node* insert = node;
144 :
145 7470771 : insert->data = data;
146 7470771 : insert->prev = 0;
147 7470771 : insert->next = 0;
148 7470771 : insert->key = 0;
149 :
150 7470771 : tree->root = tommy_tree_insert_node(tree->cmp, tree->root, &insert);
151 :
152 7470771 : if (insert == node)
153 7470770 : ++tree->count;
154 :
155 7470771 : return insert->data;
156 : }
157 :
158 792992 : 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 792992 : if (!root)
163 128 : return 0;
164 :
165 792864 : c = cmp(data, root->data);
166 :
167 792864 : if (c < 0) {
168 303833 : root->prev = tommy_tree_remove_node(cmp, root->prev, data, let);
169 303833 : return tommy_tree_balance(root);
170 : }
171 :
172 489031 : if (c > 0) {
173 409505 : root->next = tommy_tree_remove_node(cmp, root->next, data, let);
174 409505 : return tommy_tree_balance(root);
175 : }
176 :
177 : /* found */
178 79526 : *let = root;
179 :
180 79526 : return tommy_tree_move_right(root->prev, root->next);
181 : }
182 :
183 79654 : void* tommy_tree_remove(tommy_tree* tree, void* data)
184 : {
185 79654 : tommy_tree_node* node = 0;
186 :
187 79654 : tree->root = tommy_tree_remove_node(tree->cmp, tree->root, data, &node);
188 :
189 79654 : if (!node)
190 128 : return 0;
191 :
192 79526 : --tree->count;
193 :
194 79526 : return node->data;
195 : }
196 :
197 136508576 : static tommy_tree_node* tommy_tree_search_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data)
198 : {
199 : int c;
200 :
201 136508576 : if (!root)
202 1588681 : return 0;
203 :
204 134919895 : c = cmp(data, root->data);
205 :
206 134956499 : if (c < 0)
207 49026647 : return tommy_tree_search_node(cmp, root->prev, data);
208 :
209 85929852 : if (c > 0)
210 75230793 : return tommy_tree_search_node(cmp, root->next, data);
211 :
212 10699059 : 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 12287679 : void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg)
226 : {
227 12287679 : tommy_tree_node* node = tommy_tree_search_node(cmp, tree->root, cmp_arg);
228 :
229 12287492 : if (!node)
230 1588679 : return 0;
231 :
232 10698813 : 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 7052368 : static void tommy_tree_foreach_node(tommy_tree_node* root, tommy_foreach_func* func)
245 : {
246 : tommy_tree_node* next;
247 :
248 7052368 : if (!root)
249 3526914 : return;
250 :
251 3525454 : tommy_tree_foreach_node(root->prev, func);
252 :
253 : /* make a copy in case func is free() */
254 3525454 : next = root->next;
255 :
256 3525454 : func(root->data);
257 :
258 3525454 : tommy_tree_foreach_node(next, func);
259 : }
260 :
261 1460 : void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func)
262 : {
263 1460 : tommy_tree_foreach_node(tree->root, func);
264 1460 : }
265 :
266 26344301 : 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 26344301 : if (!root)
271 13175139 : return;
272 :
273 13169162 : tommy_tree_foreach_arg_node(root->prev, func, arg);
274 :
275 : /* make a copy in case func is free() */
276 13169162 : next = root->next;
277 :
278 13169162 : func(arg, root->data);
279 :
280 13169162 : tommy_tree_foreach_arg_node(next, func, arg);
281 : }
282 :
283 5977 : void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg)
284 : {
285 5977 : tommy_tree_foreach_arg_node(tree->root, func, arg);
286 5977 : }
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 :
|
