Line data Source code
1 : #include <stddef.h>
2 : #include <stdlib.h>
3 : #include <string.h>
4 :
5 : #include <crater/avl_check.h>
6 : #include <crater/avl.h>
7 :
8 : static cr8r_avl_node *cr8r_avl_insert_recursive(cr8r_avl_node *r, void *key, cr8r_avl_ft *ft);
9 : inline static cr8r_avl_node *cr8r_avl_insert_rebalance_r(cr8r_avl_node *p, cr8r_avl_node *n);
10 : inline static cr8r_avl_node *cr8r_avl_insert_rebalance_l(cr8r_avl_node *p, cr8r_avl_node *n);
11 : static cr8r_avl_node *cr8r_avl_insert_retrace(cr8r_avl_node *n);
12 : inline static cr8r_avl_node *cr8r_avl_remove_rebalance_r(cr8r_avl_node *p);
13 : inline static cr8r_avl_node *cr8r_avl_remove_rebalance_l(cr8r_avl_node *p);
14 : static cr8r_avl_node *cr8r_avl_remove_retrace(cr8r_avl_node *n);
15 : inline static cr8r_avl_node *cr8r_avl_remove_trunk(cr8r_avl_node *n, cr8r_avl_ft *ft);
16 : inline static cr8r_avl_node *cr8r_avl_rotate_r(cr8r_avl_node *n);
17 : inline static cr8r_avl_node *cr8r_avl_rotate_l(cr8r_avl_node *n);
18 :
19 : inline static void cr8r_avl_swap_data(cr8r_avl_node *a, cr8r_avl_node *b, uint64_t size);
20 : inline static void cr8r_avl_sift_down_bounded(cr8r_avl_node *r, cr8r_avl_node *u, cr8r_avl_ft *ft);
21 : inline static void cr8r_avl_reorder_recursive(cr8r_avl_node *r, cr8r_avl_ft *ft);
22 : inline static void cr8r_avl_reorder_retrace(cr8r_avl_node *n);
23 : inline static cr8r_avl_node *cr8r_avl_reorder_relink(cr8r_avl_node *n);
24 :
25 :
26 1 : bool cr8r_avl_ft_init(cr8r_avl_ft *ft,
27 : void *data, uint64_t size,
28 : int (*cmp)(const cr8r_base_ft*, const void*, const void*),
29 : int (*add)(cr8r_base_ft*, void*, void*),
30 : void *(*alloc)(cr8r_base_ft*),
31 : void (*free)(cr8r_base_ft*, void*)
32 : ){
33 1 : if(!cmp || !alloc || !free){
34 : return 0;
35 : }
36 1 : ft->base.data = data;
37 1 : ft->base.size = size;
38 1 : ft->cmp = cmp;
39 1 : ft->add = add;
40 1 : ft->alloc = alloc;
41 1 : ft->free = free;
42 1 : return 1;
43 : }
44 :
45 2 : bool cr8r_avl_ft_initsla(cr8r_avl_ft *ft,
46 : cr8r_sla *sla, uint64_t size, uint64_t reserve,
47 : int (*cmp)(const cr8r_base_ft*, const void*, const void*),
48 : int (*add)(cr8r_base_ft*, void*, void*)
49 : ){
50 2 : if(!cmp || !sla || !cr8r_sla_init(sla, offsetof(cr8r_avl_node, data) + size, reserve)){
51 0 : return 0;
52 : }
53 2 : ft->base.data = sla;
54 2 : ft->base.size = size;
55 2 : ft->cmp = cmp;
56 2 : ft->add = add;
57 2 : ft->alloc = cr8r_default_alloc_sla;
58 2 : ft->free = cr8r_default_free_sla;
59 2 : return 1;
60 : }
61 :
62 177828274 : void *cr8r_default_alloc_sla(cr8r_base_ft *ft){
63 177828274 : return cr8r_sla_alloc(ft->data);
64 : }
65 :
66 177821201 : void cr8r_default_free_sla(cr8r_base_ft *ft, void *p){
67 177821201 : cr8r_sla_free(ft->data, p);
68 177821201 : }
69 :
70 :
71 355636926 : cr8r_avl_node *cr8r_avl_next(cr8r_avl_node *n){
72 355636926 : if(n->right){
73 128887576 : return cr8r_avl_first(n->right);
74 : }
75 : cr8r_avl_node *s = n;//inorder successor of n
76 355636752 : while(s->parent && s->parent->left != s){
77 128887402 : s = s->parent;
78 : }
79 226749350 : return s->parent;
80 : }
81 :
82 192 : cr8r_avl_node *cr8r_avl_prev(cr8r_avl_node *n){
83 192 : if(n->left){
84 102 : return cr8r_avl_last(n->left);
85 : }
86 : cr8r_avl_node *p = n;//inorder predecessor of n
87 192 : while(p->parent && p->parent->right != p){
88 102 : p = p->parent;
89 : }
90 90 : return p->parent;
91 : }
92 :
93 177818273 : cr8r_avl_node *cr8r_avl_new(void *key, cr8r_avl_node *left, cr8r_avl_node *right, cr8r_avl_node *parent, char balance, cr8r_avl_ft *ft){
94 177818273 : cr8r_avl_node *ret = ft->alloc(&ft->base);
95 177818273 : if(ret){
96 177818273 : *ret = (cr8r_avl_node){left, right, parent, balance};
97 177818273 : memcpy(ret->data, key, ft->base.size);
98 : }
99 177818273 : return ret;
100 : }
101 :
102 174189738 : cr8r_avl_node *cr8r_avl_root(cr8r_avl_node *n){
103 243442215 : while(n && n->parent){
104 69252477 : n = n->parent;
105 : }
106 174189738 : return n;
107 : }
108 :
109 335561382 : cr8r_avl_node *cr8r_avl_get(cr8r_avl_node *r, void *key, cr8r_avl_ft *ft){
110 335561382 : if(!r){
111 : return NULL;
112 : }
113 335561382 : int ord = ft->cmp(&ft->base, r->data, key);
114 335561382 : if(ord < 0){
115 74941115 : return cr8r_avl_get(r->right, key, ft);
116 260620267 : }else if(ord > 0){
117 82808875 : return cr8r_avl_get(r->left, key, ft);
118 : }//otherwise r->data "==" key
119 : return r;
120 : }
121 :
122 96 : cr8r_avl_node *cr8r_avl_search_dups(cr8r_avl_node *r, void *key, cr8r_avl_ft *ft, int *is_duplicate){
123 96 : if(!r){
124 0 : if(is_duplicate){
125 0 : *is_duplicate = 0;
126 : }
127 0 : return NULL;
128 : }
129 : int found_dup = 0;
130 619 : while(1){
131 619 : int ord = ft->cmp(&ft->base, r->data, key);
132 619 : if(ord < 0){
133 379 : if(!r->right){
134 : break;
135 : }
136 332 : r = r->right;
137 240 : }else if(ord > 0){
138 240 : if(!r->left){
139 : break;
140 : }
141 191 : r = r->left;
142 : }else{
143 0 : found_dup = 1;
144 0 : if(r->balance < 0){
145 0 : if(!r->right){
146 : break;
147 : }
148 0 : r = r->right;
149 0 : }else if(!r->left){
150 : break;
151 : }else{
152 0 : r = r->left;
153 : }
154 : }
155 : }
156 96 : if(is_duplicate){
157 0 : *is_duplicate = found_dup;
158 : }
159 : return r;
160 : }
161 :
162 1218 : cr8r_avl_node *cr8r_avl_search(cr8r_avl_node *r, void *key, cr8r_avl_ft *ft){
163 1218 : if(!r){
164 : return NULL;
165 : }
166 1218 : int ord = ft->cmp(&ft->base, r->data, key);
167 1218 : if(ord < 0){
168 588 : return r->right ? cr8r_avl_search(r->right, key, ft) : r;
169 630 : }else if(ord > 0){
170 534 : return r->left ? cr8r_avl_search(r->left, key, ft) : r;
171 : }
172 : return r;
173 : }
174 :
175 1323 : cr8r_avl_node *cr8r_avl_lower_bound(cr8r_avl_node *r, void *key, cr8r_avl_ft *ft){
176 1323 : cr8r_avl_node *ret = NULL;
177 1323 : if(!r){
178 : return NULL;
179 : }//find largest element l of r such that l <= key
180 1225 : int ord = ft->cmp(&ft->base, r->data, key);
181 1225 : if(ord < 0){
182 588 : ret = cr8r_avl_lower_bound(r->right, key, ft);
183 588 : return ret ? ret : r;
184 637 : }else if(ord > 0){
185 541 : return cr8r_avl_lower_bound(r->left, key, ft);
186 : }//otherwise r->data "==" key
187 : return r;
188 : }
189 :
190 1323 : cr8r_avl_node *cr8r_avl_upper_bound(cr8r_avl_node *r, void *key, cr8r_avl_ft *ft){
191 1323 : cr8r_avl_node *ret = NULL;
192 1323 : if(!r){
193 : return NULL;
194 : }//find smallest element u of r such that r > key
195 1225 : int ord = ft->cmp(&ft->base, r->data, key);
196 1225 : if(ord < 0){
197 588 : return cr8r_avl_upper_bound(r->right, key, ft);
198 637 : }else if(ord > 0){
199 541 : ret = cr8r_avl_upper_bound(r->left, key, ft);
200 541 : return ret ? ret : r;
201 : }//otherwise r->data "==" key
202 96 : return cr8r_avl_next(r);
203 : }
204 :
205 154289183 : cr8r_avl_node *cr8r_avl_first(cr8r_avl_node *r){
206 241252065 : while(r && r->left){
207 86962882 : r = r->left;
208 : }
209 154289183 : return r;
210 : }
211 :
212 157 : cr8r_avl_node *cr8r_avl_last(cr8r_avl_node *r){
213 281 : while(r && r->right){
214 124 : r = r->right;
215 : }
216 157 : return r;
217 : }
218 :
219 177811296 : int cr8r_avl_insert(cr8r_avl_node **r, void *key, cr8r_avl_ft *ft){
220 177811296 : cr8r_avl_node *t = cr8r_avl_insert_recursive(*r, key, ft);
221 177811296 : CR8R_AVL_ASSERT_ALL(*r);
222 177811296 : if(t){
223 177811296 : *r = t;
224 : }
225 177811296 : return !!t;
226 : }
227 :
228 345220348 : cr8r_avl_node *cr8r_avl_insert_recursive(cr8r_avl_node *r, void *key, cr8r_avl_ft *ft){
229 345220348 : if(!r){
230 25401601 : return cr8r_avl_new(key, NULL, NULL, NULL, 0, ft);
231 : }
232 319818747 : int ord = ft->cmp(&ft->base, r->data, key);
233 319818747 : if(ord < 0){
234 159909390 : if(r->right){
235 83704543 : return cr8r_avl_insert_recursive(r->right, key, ft);
236 : }//otherwise insert on the right side
237 76204847 : r->right = cr8r_avl_new(key, NULL, NULL, r, 0, ft);
238 76204847 : if(!r->right){//allocation failed
239 : return NULL;
240 : }
241 76204847 : return cr8r_avl_insert_retrace(r->right);//rebalance
242 159909357 : }else if(ord > 0){
243 159909357 : if(r->left){
244 83704509 : return cr8r_avl_insert_recursive(r->left, key, ft);
245 : }//otherwise insert on the left side
246 76204848 : r->left = cr8r_avl_new(key, NULL, NULL, r, 0, ft);
247 76204848 : if(!r->left){//allocation failed
248 : return NULL;
249 : }
250 76204848 : return cr8r_avl_insert_retrace(r->left);//rebalance
251 : }
252 : return NULL;
253 : }
254 :
255 75328 : int cr8r_avl_insert_update(cr8r_avl_node **r, void *key, cr8r_avl_ft *ft){
256 75328 : if(!*r){
257 1 : *r = cr8r_avl_new(key, NULL, NULL, NULL, 0, ft);
258 1 : return *r ? CR8R_AVL_INSERTED : 0;
259 : }
260 75327 : for(cr8r_avl_node *t = *r;;){
261 740570 : int ord = ft->cmp(&ft->base, t->data, key);
262 740570 : if(ord < 0){
263 326831 : if(t->right){
264 323299 : t = t->right;
265 : }else{
266 3532 : if(!(t->right = cr8r_avl_new(key, NULL, NULL, t, 0, ft))){
267 : return 0;
268 : }
269 3532 : *r = cr8r_avl_insert_retrace(t->right);
270 3532 : CR8R_AVL_ASSERT_ALL(*r);
271 : return CR8R_AVL_INSERTED;
272 : }
273 413739 : }else if(ord > 0){
274 345388 : if(t->left){
275 341944 : t = t->left;
276 : }else{
277 3444 : if(!(t->left = cr8r_avl_new(key, NULL, NULL, t, 0, ft))){
278 : return 0;
279 : }
280 3444 : *r = cr8r_avl_insert_retrace(t->left);
281 3444 : CR8R_AVL_ASSERT_ALL(*r);
282 : return CR8R_AVL_INSERTED;
283 : }
284 : }else{
285 68351 : return ft->add(&ft->base, t->data, key) ? CR8R_AVL_UPDATED : 0;
286 : }
287 : }
288 : }
289 :
290 177811200 : int cr8r_avl_remove(cr8r_avl_node **r, void *key, cr8r_avl_ft *ft){
291 177811200 : cr8r_avl_node *n = cr8r_avl_get(*r, key, ft);
292 177811200 : CR8R_AVL_ASSERT_ALL(*r);
293 177811200 : if(n){
294 177811200 : *r = cr8r_avl_remove_node(n, ft);
295 : }
296 177811200 : return !!n;
297 : }
298 :
299 177811296 : cr8r_avl_node *cr8r_avl_remove_node(cr8r_avl_node *n, cr8r_avl_ft *ft){
300 177811296 : cr8r_avl_node *s = cr8r_avl_next(n);
301 177811296 : if((!n->left) || (!n->right)){//no need to swap with a scapegoat
302 138516530 : return cr8r_avl_remove_trunk(n, ft);
303 : }
304 : //swap all of n and s's parent, left, right, and balance fields
305 : //it would be easier to swap the data fields but that would invalidate iterators to s
306 39294766 : cr8r_avl_node t = *s;//t is an automatic storage variable that holds a copy of *s
307 39294766 : if((s->left = n->left)){
308 39294766 : s->left->parent = s;
309 : }
310 39294766 : if((s->right = n->right)){
311 39294766 : s->right->parent = s;
312 : }
313 39294766 : if((s->parent = n->parent)){
314 11534445 : *(s->parent->left == n ? &s->parent->left : &s->parent->right) = s;//dereference(reference) allows the ternary operator to be an lvalue
315 : }
316 39294766 : s->balance = n->balance;
317 39294766 : n->left = NULL;//s is n's inorder successor and n has a right child so s does not have a left child.
318 39294766 : if((n->right = t.right)){
319 5440608 : n->right->parent = n;
320 : }
321 39294766 : if((n->parent = t.parent)){
322 39294766 : *(n->parent->left == s ? &n->parent->left : &n->parent->right) = n;
323 : }
324 39294766 : n->balance = t.balance;
325 39294766 : if(t.parent == n){//s was n's child. In this case, these pointers loop back and need to be fixed.
326 28803179 : s->right = n;
327 28803179 : n->parent = s;
328 28803179 : n->right = t.right;
329 : }
330 39294766 : return cr8r_avl_remove_trunk(n, ft);
331 : }
332 :
333 177811296 : cr8r_avl_node *cr8r_avl_remove_trunk(cr8r_avl_node *n, cr8r_avl_ft *ft){
334 177811296 : cr8r_avl_node *p = n->parent, *c = n->left ? n->left : n->right, *r;//Parent, Child
335 177811296 : if(!p){
336 38102400 : if(c){
337 12700800 : c->parent = NULL;
338 : }
339 38102400 : ft->free(&ft->base, n);
340 38102400 : return c;//This does not indicate an error if NULL.
341 : }
342 139708896 : if(p->left == n){
343 63785734 : r = cr8r_avl_remove_retrace(n);//r is the root now
344 63785734 : n->parent->left = c;
345 63785734 : if(c){
346 10800026 : c->parent = n->parent;
347 : }
348 63785734 : ft->free(&ft->base, n);
349 63785734 : return r;
350 : }//p->right == n
351 75923162 : r = cr8r_avl_remove_retrace(n);//r is the root
352 75923162 : n->parent->right = c;
353 75923162 : if(c){
354 15298863 : c->parent = n->parent;
355 : }
356 75923162 : ft->free(&ft->base, n);
357 75923162 : return r;
358 : }
359 :
360 348868644 : cr8r_avl_node *cr8r_avl_insert_retrace(cr8r_avl_node *n){
361 348868644 : cr8r_avl_node *p = n->parent;
362 348868644 : if(!p){
363 : return n;
364 : }
365 283550223 : if(n == p->right){//+2 cases
366 141775229 : switch(p->balance){
367 17904003 : case -1://height change absorbed
368 17904003 : p->balance = 0;
369 17904003 : return cr8r_avl_root(p);
370 98225937 : case 0:
371 98225937 : p->balance = 1;
372 98225937 : return cr8r_avl_insert_retrace(p);
373 : }//default: p->balance == 1
374 25645289 : return cr8r_avl_insert_rebalance_r(p, n);//height change will be absorbed
375 : }//otherwise n == p->left
376 141774994 : switch(p->balance){//-2 cases
377 17903877 : case 1://height change absorbed
378 17903877 : p->balance = 0;
379 17903877 : return cr8r_avl_root(p);
380 98225940 : case 0:
381 98225940 : p->balance = -1;
382 98225940 : return cr8r_avl_insert_retrace(p);
383 : }//default: p->balance == -1
384 25645177 : return cr8r_avl_insert_rebalance_l(p, n);//height change will be absorbed
385 : }
386 :
387 25645289 : cr8r_avl_node *cr8r_avl_insert_rebalance_r(cr8r_avl_node *p, cr8r_avl_node *n){
388 25645289 : if(n->balance == 1){//right-right case: only one rotation needed
389 12822689 : cr8r_avl_rotate_r(p);//note n becomes the parent of p
390 12822689 : p->balance = n->balance = 0;
391 12822689 : return cr8r_avl_root(n);
392 : }//otherwise right-left case: two rotations are required and the balance factors have 3 cases
393 12822600 : cr8r_avl_rotate_l(n);
394 12822600 : cr8r_avl_rotate_r(p);//note p, n->left, n change roles from parent, right child, right-left grandchild to left child, parent, right child
395 12822600 : n->balance = +(n->parent->balance == -1);//n, now the right child of n->parent, its old left child, has a balance factor of 1 if the child was -1, else 0
396 12822600 : p->balance = -(n->parent->balance == 1);//p, now the right child of n->parent, has a balance factor of -1 if n->parent was 1, else 0
397 12822600 : n->parent->balance = 0;//if this is still confusing, try drawing out all of the possible trees with root +2 and right child +/-1 with irrelevant subtrees only marked as heights.
398 12822600 : return cr8r_avl_root(n->parent);//there are 4 cases and I will try to put them in a pdf somewhere if I can figure out how to draw it on a computer.
399 : }
400 :
401 25645177 : cr8r_avl_node *cr8r_avl_insert_rebalance_l(cr8r_avl_node *p, cr8r_avl_node *n){//mirror image of cr8r_avl_insert_rebalance_r
402 25645177 : if(n->balance == -1){
403 12822590 : cr8r_avl_rotate_l(p);
404 12822590 : p->balance = n->balance = 0;
405 12822590 : return cr8r_avl_root(n);
406 : }
407 12822587 : cr8r_avl_rotate_r(n);
408 12822587 : cr8r_avl_rotate_l(p);
409 12822587 : n->balance = -(n->parent->balance == 1);
410 12822587 : p->balance = +(n->parent->balance == -1);//unary + for symmetry
411 12822587 : n->parent->balance = 0;
412 12822587 : return cr8r_avl_root(n->parent);
413 : }
414 :
415 227511220 : cr8r_avl_node *cr8r_avl_remove_retrace(cr8r_avl_node *n){
416 227511220 : cr8r_avl_node *p = n->parent;
417 227511220 : if(!p){
418 : return n;
419 : }
420 174893620 : if(n == p->left){//+2 cases
421 78732966 : switch(p->balance){
422 38686487 : case -1:
423 38686487 : p->balance = 0;
424 38686487 : return cr8r_avl_remove_retrace(p);
425 32607414 : case 0://change in height absorbed
426 32607414 : p->balance = 1;
427 32607414 : return cr8r_avl_root(p);
428 : }//default: p->balance == 1
429 7439065 : return cr8r_avl_remove_rebalance_l(p);
430 : }//otherwise n == p->right
431 96160654 : switch(p->balance){//-2 cases
432 30565751 : case 1:
433 30565751 : p->balance = 0;
434 30565751 : return cr8r_avl_remove_retrace(p);
435 51096983 : case 0://change in height absorbed
436 51096983 : p->balance = -1;
437 51096983 : return cr8r_avl_root(p);
438 : }//default: p->balance == -1
439 14497920 : return cr8r_avl_remove_rebalance_r(p);
440 : }
441 :
442 7439065 : cr8r_avl_node *cr8r_avl_remove_rebalance_l(cr8r_avl_node *p){//do not try to understand this until you understand cr8r_avl_insert_rebalance_r
443 7439065 : cr8r_avl_node *n = p->right;//If we've become off balance by a left REMOVAL there must be a right child
444 7439065 : if(n->balance != -1){//not the right-left case
445 3878519 : cr8r_avl_rotate_r(p);//nb. the pointers n and p point to the same nodes but now n is the parent
446 3878519 : p->balance -= n->balance--;//if n is +1, n and p become 0, otherwise n is 0 and they become -1 and +1
447 3878519 : return n->balance ? cr8r_avl_root(n) : cr8r_avl_remove_retrace(n);//if n->balance becomes 0 by removal we still have height decrease to propagate
448 : }//right-left case. This is exactly the same as insertion whereas the previous part included a right-even case not present in insertion
449 3560546 : cr8r_avl_rotate_l(n);
450 3560546 : cr8r_avl_rotate_r(p);
451 3560546 : p->balance = -(n->parent->balance == 1);
452 3560546 : n->balance = +(n->parent->balance == -1);
453 3560546 : n->parent->balance = 0;
454 3560546 : return cr8r_avl_remove_retrace(n->parent);
455 : }
456 :
457 14497920 : cr8r_avl_node *cr8r_avl_remove_rebalance_r(cr8r_avl_node *p){//mirror image of cr8r_avl_remove_rebalance_l
458 14497920 : cr8r_avl_node *n = p->left;
459 14497920 : if(n->balance != 1){
460 9331200 : cr8r_avl_rotate_l(p);
461 9331200 : p->balance -= n->balance++;//if n is -1, n and p become 0, otherwise n is 0 and they become +1 and -1. Note the -= needn't be flipped since -- was
462 9331200 : return n->balance ? cr8r_avl_root(n) : cr8r_avl_remove_retrace(n);
463 : }
464 5166720 : cr8r_avl_rotate_r(n);
465 5166720 : cr8r_avl_rotate_l(p);
466 5166720 : p->balance = +(n->parent->balance == -1);
467 5166720 : n->balance = -(n->parent->balance == 1);
468 5166720 : n->parent->balance = 0;
469 5166720 : return cr8r_avl_remove_retrace(n->parent);
470 : }
471 :
472 56526243 : cr8r_avl_node *cr8r_avl_rotate_l(cr8r_avl_node *n){//does not update balance factors because the caller knows better
473 56526243 : cr8r_avl_node *l = n->left;//assume existence of swapped node
474 56526243 : l->parent = n->parent;
475 56526243 : if(n->parent){
476 30554401 : if(n->parent->left == n){
477 7448551 : n->parent->left = l;
478 : }else{//n->parent->right == n
479 23105850 : n->parent->right = l;
480 : }
481 : }
482 56526243 : n->parent = l;
483 56526243 : n->left = l->right;
484 56526243 : if(n->left){
485 10472505 : n->left->parent = n;
486 : }
487 56526243 : l->right = n;
488 56526243 : return l;
489 : }
490 :
491 51073661 : cr8r_avl_node *cr8r_avl_rotate_r(cr8r_avl_node *n){
492 51073661 : cr8r_avl_node *r = n->right;//assume existence of swapped node
493 51073661 : r->parent = n->parent;
494 51073661 : if(n->parent){
495 31642295 : if(n->parent->left == n){
496 24193647 : n->parent->left = r;
497 : }else{//n->parent->right == n
498 7448648 : n->parent->right = r;
499 : }
500 : }
501 51073661 : n->parent = r;
502 51073661 : n->right = r->left;
503 51073661 : if(n->right){
504 8260731 : n->right->parent = n;
505 : }
506 51073661 : r->left = n;
507 51073661 : return r;
508 : }
509 :
510 193 : void cr8r_avl_delete(cr8r_avl_node *r, cr8r_avl_ft *ft){
511 193 : if(!r)return;
512 96 : cr8r_avl_delete(r->left, ft);
513 96 : cr8r_avl_delete(r->right, ft);
514 96 : ft->free(&ft->base, r);
515 : }
516 :
517 96 : cr8r_avl_node *cr8r_avl_attach(cr8r_avl_node *r, cr8r_avl_node *n, cr8r_avl_ft *ft, int *is_duplicate){
518 96 : if(!r){
519 0 : if(is_duplicate){
520 0 : *is_duplicate = 0;
521 : }
522 0 : return n;
523 : }
524 96 : r = cr8r_avl_search_dups(r, n->data, ft, is_duplicate);
525 96 : int ord = ft->cmp(&ft->base, r->data, n->data);
526 96 : if(ord > 0){
527 49 : r->left = n;
528 47 : }else if(ord < 0 || r->balance < 0){
529 47 : r->right = n;
530 : }else{
531 0 : r->left = n;
532 : }
533 96 : n->parent = r;
534 96 : return cr8r_avl_insert_retrace(n);
535 : }
536 :
537 0 : cr8r_avl_node *cr8r_avl_attach_exclusive(cr8r_avl_node *r, cr8r_avl_node *n, cr8r_avl_ft *ft){
538 0 : if(!r){
539 : return n;
540 : }
541 0 : r = cr8r_avl_search(r, n->data, ft);
542 0 : int ord = ft->cmp(&ft->base, r->data, n->data);
543 0 : if(!ord){
544 : return NULL;
545 : }
546 0 : if(ord > 0){
547 0 : r->left = n;
548 : }else{
549 0 : r->right = n;
550 : }
551 0 : n->parent = r;
552 0 : return cr8r_avl_insert_retrace(n);
553 : }
554 :
555 96 : void cr8r_default_free_pass(cr8r_base_ft *ft, void *p){}
556 :
557 96 : cr8r_avl_node *cr8r_avl_detach(cr8r_avl_node *n, cr8r_avl_ft *ft){
558 96 : cr8r_avl_ft ft_cpy = *ft;
559 96 : ft_cpy.free = cr8r_default_free_pass;
560 96 : cr8r_avl_node *r = cr8r_avl_remove_node(n, &ft_cpy);
561 96 : n->left = n->right = n->parent = NULL;
562 96 : n->balance = 0;
563 96 : return r;
564 : }
565 :
566 96 : cr8r_avl_node *cr8r_avl_decrease(cr8r_avl_node *n, cr8r_avl_ft *ft, int *is_duplicate){
567 96 : cr8r_avl_node *p = cr8r_avl_prev(n);
568 96 : int ord;
569 96 : if(!p || (ord = ft->cmp(&ft->base, p->data, n->data)) < 0){
570 96 : if(is_duplicate){
571 0 : *is_duplicate = 0;
572 : }
573 96 : return cr8r_avl_root(n);
574 0 : }else if(!ord){
575 0 : if(is_duplicate){
576 0 : *is_duplicate = 1;
577 : }
578 0 : return cr8r_avl_root(n);
579 : }
580 0 : p = cr8r_avl_detach(n, ft);
581 0 : return cr8r_avl_attach(p, n, ft, is_duplicate);
582 : }
583 :
584 96 : cr8r_avl_node *cr8r_avl_increase(cr8r_avl_node *n, cr8r_avl_ft *ft, int *is_duplicate){
585 96 : cr8r_avl_node *s = cr8r_avl_next(n);
586 96 : int ord;
587 96 : if(!s || (ord = ft->cmp(&ft->base, s->data, n->data)) > 0){
588 0 : if(is_duplicate){
589 0 : *is_duplicate = 0;
590 : }
591 0 : return cr8r_avl_root(n);
592 96 : }else if(!ord){
593 0 : if(is_duplicate){
594 0 : *is_duplicate = 1;
595 : }
596 0 : return cr8r_avl_root(n);
597 : }
598 96 : s = cr8r_avl_detach(n, ft);
599 96 : return cr8r_avl_attach(s, n, ft, is_duplicate);
600 : }
601 :
602 3037 : cr8r_avl_node *cr8r_avl_first_post(cr8r_avl_node *r){
603 7073 : while(1){
604 7073 : if(r->left){
605 3553 : r = r->left;
606 3520 : }else if(r->right){
607 483 : r = r->right;
608 : }else{
609 3037 : return r;
610 : }
611 : }
612 : }
613 :
614 7073 : cr8r_avl_node *cr8r_avl_next_post(cr8r_avl_node *n){
615 7073 : return n->parent && n == n->parent->left && n->parent->right ? cr8r_avl_first_post(n->parent->right) : n->parent;
616 : }
617 :
618 6320 : void cr8r_avl_swap_data(cr8r_avl_node *a, cr8r_avl_node *b, uint64_t size){
619 6320 : char tmp[size];
620 6320 : memcpy(tmp, a->data, size);
621 6320 : memcpy(a->data, b->data, size);
622 6320 : memcpy(b->data, tmp, size);
623 6320 : }
624 :
625 4136 : void cr8r_avl_sift_down(cr8r_avl_node *r, cr8r_avl_ft *ft){
626 4136 : cr8r_avl_sift_down_bounded(r, NULL, ft);
627 4136 : }
628 :
629 : // sift down for a partially max heap / partially bst avl tree, where u is the first node (in inorder traversal order)
630 : // in the bst portion (and also an upper bound for the max heap under ft->cmp).
631 : // When u is NULL, this decays to sift down for a fully max heap avl tree.
632 : // Partially max heap / partially bst avl trees only arise during execution of avl_reorder,
633 : // and that function does some extra pointer juggling to ensure that only checking right children for u and stopping once
634 : // it is found is correct; see that function for more info
635 4224 : void cr8r_avl_sift_down_bounded(cr8r_avl_node *r, cr8r_avl_node *u, cr8r_avl_ft *ft){
636 10456 : cr8r_avl_node *max_child;
637 16688 : while(1){
638 10456 : if(r->right && r->right != u){
639 7716 : if(r->left){
640 6948 : max_child = ft->cmp(&ft->base, r->left->data, r->right->data) >= 0 ? r->left : r->right;
641 : }else{
642 768 : max_child = r->right;
643 : }
644 2740 : }else if(r->left){
645 900 : max_child = r->left;
646 : }else{
647 : break;
648 : }
649 8616 : if(ft->cmp(&ft->base, max_child->data, r->data) <= 0){
650 : break;
651 : }
652 6232 : cr8r_avl_swap_data(max_child, r, ft->base.size);
653 6232 : r = max_child;
654 : }
655 4224 : }
656 :
657 2 : void cr8r_avl_heapify(cr8r_avl_node *r, cr8r_avl_ft *ft){
658 7075 : for(r = cr8r_avl_first_post(r); r; r = cr8r_avl_next_post(r)){
659 7073 : if(r->left || r->right){
660 4036 : cr8r_avl_sift_down(r, ft);
661 : }
662 : }
663 2 : }
664 :
665 100 : cr8r_avl_node *cr8r_avl_heappop_node(cr8r_avl_node **r, cr8r_avl_ft *ft){
666 100 : if(!*r){
667 : return NULL;
668 : }
669 100 : cr8r_avl_node *s = *r;
670 1500 : while(1){
671 1500 : if(s->balance == -1){
672 726 : s = s->left;
673 774 : }else if(s->right){
674 674 : s = s->right;
675 : }else{
676 : break;
677 : }
678 : }
679 100 : if(s == *r){
680 0 : *r = NULL;
681 0 : return s;
682 : }
683 451 : for(cr8r_avl_node *u = s; u != *r; u = u->parent){
684 451 : signed char db = u->parent->left == u ? 1 : -1;
685 451 : u->parent->balance += db;
686 451 : if(u->parent->balance){
687 : break;
688 : }
689 : }
690 100 : if(s->parent->left == s){
691 48 : s->parent->left = NULL;
692 : }else{
693 52 : s->parent->right = NULL;
694 : }
695 100 : s->parent = NULL;//(*r)->parent must be NULL
696 100 : if((s->left = (*r)->left)){
697 100 : s->left->parent = s;
698 : }
699 100 : if((s->right = (*r)->right)){
700 100 : s->right->parent = s;
701 : }
702 100 : s->balance = (*r)->balance;
703 100 : CR8R_AVL_ASSERT_ALL(s);
704 100 : (*r)->left = (*r)->right = NULL;
705 100 : (*r)->balance = 0;
706 100 : cr8r_avl_node *res = *r;
707 100 : *r = s;
708 100 : cr8r_avl_sift_down(s, ft);
709 100 : return res;
710 : }
711 :
712 1 : void cr8r_avl_reorder(cr8r_avl_node *r, cr8r_avl_ft *ft){
713 1 : cr8r_avl_heapify(r, ft);
714 1 : cr8r_avl_reorder_recursive(r, ft);
715 1 : }
716 :
717 9 : void cr8r_avl_reorder_recursive(cr8r_avl_node *r, cr8r_avl_ft *ft){
718 9 : if(!r){
719 : return;
720 : }
721 : // in this function, r is initially fully a max heap, but as we proceed, we convert
722 : // it to a bst in reverse inorder order. We do this by repeatedly swapping the data
723 : // in the root of the max heap portion with the first unvisited node in reverse inorder order.
724 : // Then we sift down the root of the max heap to preserve the max heap invariant on the
725 : // heap portion of the avl tree. The bst portion trivially has its bst invariant satisfied,
726 : // and we never break the avl invariants because we never actually change the shape of the tree.
727 : // HOWEVER, if leave the links in the tree alone, then the max heap region and the bst region
728 : // are not "nice": in particular if the node we are on in reverse inorder traversal has a left subtree,
729 : // then we have visited it and its right subtree and when we call sift down it would have to
730 : // determine if it ever ran into u or one of u's reverse inorder predecessors and skip any such nodes.
731 : // To avoid this, we use sift_down_bounded and adjust the links in the tree as we go
732 96 : for(cr8r_avl_node *u = cr8r_avl_last(r); u != r;){
733 88 : cr8r_avl_swap_data(u, r, ft->base.size);
734 88 : cr8r_avl_sift_down_bounded(r, u, ft);
735 88 : if(u->left){
736 : // if u has a left subtree, the next node in reverse inorder is cr8r_avl_first(u->left),
737 : // but we want sift_down_bounded to skip u and its reverse inorder predecessors (ie the nodes
738 : // in the bst portion of the avl tree). Therefore, we find the FIRST ancestor of u where u is in its right subtree,
739 : // and we change its right pointer to point to u->left instead. This ancestor is guaranteed to exist because
740 : // u is a right descendent of the root (in a reverse inorder traversal this is true until we hit the root, so once we
741 : // hit the root we force it to continue to be true by recursing on the left subtree, see below).
742 : // Changing the first left ancestor of u (first ancestor where u is a right descendent) so its right child is u->left
743 : // breaks the structure of the tree, but we will fix it later.
744 : // Notice that for ancestors where u is in their left subtree, they are reverse inorder predecessors of u, so
745 : // they have already been visited.
746 46 : cr8r_avl_reorder_retrace(u->left);
747 46 : u = cr8r_avl_last(u->left);
748 : }else{
749 : // find the first left ancestor of u (which must itself be either the root or in the right subtree of the root, since u is in
750 : // the right subtree of the root). Since u has no left subtree, this is u's successor in reverse inorder traversal.
751 : // We also fix this first left ancestor so that its right child pointer points at its descendent again and not u.
752 42 : u = cr8r_avl_reorder_relink(u);
753 : }
754 : }
755 : // if u == r, we have reached the root node. At this point, the top of the heap and the current node in reverse inorder traversal
756 : // are the same, so we don't actually have to call avl_swap_data here.
757 : // We also don't need to temporarily set r->left->parent to NULL, because this recursive call will only look for left ancestors of
758 : // u for u in the right subtree of r->left, so the left ancestor search will always terminate at or before r->left.
759 : // Then the recursive call will recurse to r->left->left if needed and so on.
760 8 : cr8r_avl_reorder_recursive(r->left, ft);
761 : }
762 :
763 : // given n the nonempty left subtree of the just-filled current reverse inorder traversal node u,
764 : // find the first left ancestor of n (the first ancestor where n is a right descendent),
765 : // and change this ancestor's right link to point at n instead. Note that u == n->parent, and the
766 : // original shape of the tree can be recovered later: when we walk up from u, any ancestor that is
767 : // a left child of its parent will still have the correct parent pointer and its parent will still have
768 : // it as a left child. However, the first ancestor that is a right child of its parent will have its parent
769 : // pointer correct but its parent's right child will point to n instead of it.
770 : // this might fail to find a left ancestor, but recursing on the left subtree when u reaches the root ensures
771 : // the root is always a left ancestor. This ensures calling sift_down_bounded on the root with u as the
772 : // bound will see all nodes after u in the reverse inorder traversal of the original tree: when u has a left
773 : // subtree, its entire left subtree is after it in this traversal, and in particular the rightmost element of
774 : // its left subtree is its successor in the traversal. Also, any time we visit a node on the left edge of the
775 : // left subtree, we update the first left ancestor to point at its left subtree as well, if any.
776 46 : void cr8r_avl_reorder_retrace(cr8r_avl_node *n){
777 46 : cr8r_avl_node *a = n;
778 129 : while(a == a->parent->left){
779 83 : a = a->parent;
780 : }
781 46 : a->parent->right = n;
782 46 : }
783 :
784 : // when u does not have a left child, its reverse inorder successor will instead be its first left ancestor.
785 : // of course, this is also the node whose right child pointer we clobbered when first moving from any
786 : // ancestor of u before its first left ancestor, so now is when we fix it up.
787 42 : cr8r_avl_node *cr8r_avl_reorder_relink(cr8r_avl_node *n){
788 88 : while(n == n->parent->left){
789 46 : n = n->parent;
790 : }
791 42 : n->parent->right = n;
792 42 : return n->parent;
793 : }
794 :
|
