Line data Source code
1 : // SPDX-License-Identifier: BSD-2-Clause
2 : // Copyright (C) 2015 Andrea Mazzoleni
3 :
4 : #include "tommytree.h"
5 :
6 : #include <assert.h> /* for assert */
7 :
8 : /******************************************************************************/
9 : /* tree */
10 :
11 3701 : TOMMY_API void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp)
12 : {
13 3701 : tree->root = 0;
14 3701 : tree->count = 0;
15 3701 : tree->cmp = cmp;
16 3701 : }
17 :
18 120764469 : static tommy_ssize_t tommy_tree_delta(tommy_tree_node* root)
19 : {
20 120764469 : tommy_ssize_t left_height = root->prev ? root->prev->index : 0;
21 120764469 : tommy_ssize_t right_height = root->next ? root->next->index : 0;
22 :
23 120764469 : return left_height - right_height;
24 : }
25 :
26 : /* AVL tree operations */
27 : static tommy_tree_node* tommy_tree_balance(tommy_tree_node*);
28 :
29 8089193 : static tommy_tree_node* tommy_tree_rotate_left(tommy_tree_node* root)
30 : {
31 8089193 : tommy_tree_node* next = root->next;
32 :
33 8089193 : root->next = next->prev;
34 :
35 8089193 : next->prev = tommy_tree_balance(root);
36 :
37 8089193 : return tommy_tree_balance(next);
38 : }
39 :
40 195595 : static tommy_tree_node* tommy_tree_rotate_right(tommy_tree_node* root)
41 : {
42 195595 : tommy_tree_node* prev = root->prev;
43 :
44 195595 : root->prev = prev->next;
45 :
46 195595 : prev->next = tommy_tree_balance(root);
47 :
48 195595 : return tommy_tree_balance(prev);
49 : }
50 :
51 199670 : static tommy_tree_node* tommy_tree_move_right(tommy_tree_node* root, tommy_tree_node* node)
52 : {
53 199670 : if (!root)
54 84622 : return node;
55 :
56 115048 : root->next = tommy_tree_move_right(root->next, node);
57 :
58 115048 : return tommy_tree_balance(root);
59 : }
60 :
61 112656697 : static tommy_tree_node* tommy_tree_balance(tommy_tree_node* root)
62 : {
63 112656697 : tommy_ssize_t delta = tommy_tree_delta(root);
64 :
65 112656697 : if (delta < -1) {
66 7962401 : if (tommy_tree_delta(root->next) > 0)
67 50224 : root->next = tommy_tree_rotate_right(root->next);
68 7962401 : return tommy_tree_rotate_left(root);
69 : }
70 :
71 104694296 : if (delta > 1) {
72 145371 : if (tommy_tree_delta(root->prev) < 0)
73 126792 : root->prev = tommy_tree_rotate_left(root->prev);
74 145371 : return tommy_tree_rotate_right(root);
75 : }
76 :
77 : /* recompute key */
78 104548925 : root->index = 0;
79 :
80 104548925 : if (root->prev && root->prev->index > root->index)
81 84475885 : root->index = root->prev->index;
82 :
83 104548925 : if (root->next && root->next->index > root->index)
84 48112306 : root->index = root->next->index;
85 :
86 : /* count itself */
87 104548925 : root->index += 1;
88 :
89 104548925 : return root;
90 : }
91 :
92 103293953 : static tommy_tree_node* tommy_tree_insert_node(tommy_compare_func* cmp, tommy_tree_node* root, tommy_tree_node** let)
93 : {
94 : int c;
95 :
96 103293953 : if (!root)
97 8065146 : return *let;
98 :
99 95228807 : c = cmp((*let)->data, root->data);
100 :
101 95228807 : if (c < 0) {
102 1773421 : root->prev = tommy_tree_insert_node(cmp, root->prev, let);
103 1773421 : return tommy_tree_balance(root);
104 : }
105 :
106 93455386 : if (c > 0) {
107 93455385 : root->next = tommy_tree_insert_node(cmp, root->next, let);
108 93455385 : return tommy_tree_balance(root);
109 : }
110 :
111 : /* already present, set the return pointer */
112 1 : *let = root;
113 :
114 1 : return root;
115 : }
116 :
117 8065147 : TOMMY_API void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data)
118 : {
119 8065147 : tommy_tree_node* insert = node;
120 :
121 8065147 : insert->data = data;
122 8065147 : insert->prev = 0;
123 8065147 : insert->next = 0;
124 8065147 : insert->index = 0;
125 :
126 8065147 : tree->root = tommy_tree_insert_node(tree->cmp, tree->root, &insert);
127 :
128 8065147 : if (insert == node)
129 8065146 : ++tree->count;
130 :
131 8065147 : return insert->data;
132 : }
133 :
134 828017 : static tommy_tree_node* tommy_tree_remove_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data, tommy_tree_node** let)
135 : {
136 : int c;
137 :
138 828017 : if (!root)
139 128 : return 0;
140 :
141 827889 : c = cmp(data, root->data);
142 :
143 827889 : if (c < 0) {
144 336145 : root->prev = tommy_tree_remove_node(cmp, root->prev, data, let);
145 336145 : return tommy_tree_balance(root);
146 : }
147 :
148 491744 : if (c > 0) {
149 407122 : root->next = tommy_tree_remove_node(cmp, root->next, data, let);
150 407122 : return tommy_tree_balance(root);
151 : }
152 :
153 : /* found */
154 84622 : *let = root;
155 :
156 84622 : return tommy_tree_move_right(root->prev, root->next);
157 : }
158 :
159 84750 : TOMMY_API void* tommy_tree_remove(tommy_tree* tree, void* data)
160 : {
161 84750 : tommy_tree_node* node = 0;
162 :
163 84750 : tree->root = tommy_tree_remove_node(tree->cmp, tree->root, data, &node);
164 :
165 84750 : if (!node)
166 128 : return 0;
167 :
168 84622 : --tree->count;
169 :
170 84622 : return node->data;
171 : }
172 :
173 195194354 : static tommy_tree_node* tommy_tree_search_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data)
174 : {
175 : int c;
176 :
177 195194354 : if (!root)
178 2167732 : return 0;
179 :
180 193026622 : c = cmp(data, root->data);
181 :
182 193026622 : if (c < 0)
183 71213608 : return tommy_tree_search_node(cmp, root->prev, data);
184 :
185 121813014 : if (c > 0)
186 106258181 : return tommy_tree_search_node(cmp, root->next, data);
187 :
188 15554833 : return root;
189 : }
190 :
191 2 : TOMMY_API void* tommy_tree_search(tommy_tree* tree, void* data)
192 : {
193 2 : tommy_tree_node* node = tommy_tree_search_node(tree->cmp, tree->root, data);
194 :
195 2 : if (!node)
196 1 : return 0;
197 :
198 1 : return node->data;
199 : }
200 :
201 17722563 : TOMMY_API void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg)
202 : {
203 17722563 : tommy_tree_node* node = tommy_tree_search_node(cmp, tree->root, cmp_arg);
204 :
205 17722563 : if (!node)
206 2167731 : return 0;
207 :
208 15554832 : return node->data;
209 : }
210 :
211 128 : TOMMY_API void* tommy_tree_remove_existing(tommy_tree* tree, tommy_tree_node* node)
212 : {
213 128 : void* data = tommy_tree_remove(tree, node->data);
214 :
215 128 : assert(data != 0);
216 :
217 128 : return data;
218 : }
219 :
220 7486367 : static void tommy_tree_foreach_node(tommy_tree_node* root, tommy_foreach_func* func)
221 : {
222 : tommy_tree_node* next;
223 :
224 7486367 : if (!root)
225 3744043 : return;
226 :
227 3742324 : tommy_tree_foreach_node(root->prev, func);
228 :
229 : /* make a copy in case func is free() */
230 3742324 : next = root->next;
231 :
232 3742324 : func(root->data);
233 :
234 3742324 : tommy_tree_foreach_node(next, func);
235 : }
236 :
237 1719 : TOMMY_API void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func)
238 : {
239 1719 : tommy_tree_foreach_node(tree->root, func);
240 1719 : }
241 :
242 28830723 : static void tommy_tree_foreach_arg_node(tommy_tree_node* root, tommy_foreach_arg_func* func, void* arg)
243 : {
244 : tommy_tree_node* next;
245 :
246 28830723 : if (!root)
247 14418731 : return;
248 :
249 14411992 : tommy_tree_foreach_arg_node(root->prev, func, arg);
250 :
251 : /* make a copy in case func is free() */
252 14411992 : next = root->next;
253 :
254 14411992 : func(arg, root->data);
255 :
256 14411992 : tommy_tree_foreach_arg_node(next, func, arg);
257 : }
258 :
259 6739 : TOMMY_API void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg)
260 : {
261 6739 : tommy_tree_foreach_arg_node(tree->root, func, arg);
262 6739 : }
263 :
264 1 : TOMMY_API tommy_size_t tommy_tree_memory_usage(tommy_tree* tree)
265 : {
266 1 : return tommy_tree_count(tree) * sizeof(tommy_tree_node);
267 : }
268 :
|
