1 /*
2 * Copyright (c) 2010 The WebM project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #ifndef VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_
12 #define VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_
13
14 /* Abstract AVL Tree Generic C Package.
15 ** Implementation generation header file.
16 **
17 ** This code is in the public domain. See cavl_tree.html for interface
18 ** documentation.
19 **
20 ** Version: 1.5 Author: Walt Karas
21 */
22
23 #undef L_
24 #undef L_EST_LONG_BIT
25 #undef L_SIZE
26 #undef l_tree
27 #undef L_MASK_HIGH_BIT
28 #undef L_LONG_BIT
29 #undef L_BIT_ARR_DEFN
30 #undef L_BIT_ARR_VAL
31 #undef L_BIT_ARR_0
32 #undef L_BIT_ARR_1
33 #undef L_BIT_ARR_ALL
34 #undef L_BIT_ARR_LONGS
35 #undef L_IMPL_MASK
36 #undef L_CHECK_READ_ERROR
37 #undef L_CHECK_READ_ERROR_INV_DEPTH
38 #undef L_SC
39 #undef L_BALANCE_PARAM_PREFIX
40
41 #ifdef AVL_UNIQUE
42
43 #define L_ AVL_UNIQUE
44
45 #else
46
47 #define L_(X) X
48
49 #endif
50
51 /* Determine correct storage class for functions */
52 #ifdef AVL_PRIVATE
53
54 #define L_SC static
55
56 #else
57
58 #define L_SC
59
60 #endif
61
62 #ifdef AVL_SIZE
63
64 #define L_SIZE AVL_SIZE
65
66 #else
67
68 #define L_SIZE unsigned long
69
70 #endif
71
72 #define L_MASK_HIGH_BIT ((int) ~ ((~ (unsigned) 0) >> 1))
73
74 /* ANSI C/ISO C++ require that a long have at least 32 bits. Set
75 ** L_EST_LONG_BIT to be the greatest multiple of 8 in the range
76 ** 32 - 64 (inclusive) that is less than or equal to the number of
77 ** bits in a long.
78 */
79
80 #if (((LONG_MAX >> 31) >> 7) == 0)
81
82 #define L_EST_LONG_BIT 32
83
84 #elif (((LONG_MAX >> 31) >> 15) == 0)
85
86 #define L_EST_LONG_BIT 40
87
88 #elif (((LONG_MAX >> 31) >> 23) == 0)
89
90 #define L_EST_LONG_BIT 48
91
92 #elif (((LONG_MAX >> 31) >> 31) == 0)
93
94 #define L_EST_LONG_BIT 56
95
96 #else
97
98 #define L_EST_LONG_BIT 64
99
100 #endif
101
102 #define L_LONG_BIT (sizeof(long) * CHAR_BIT)
103
104 #if ((AVL_MAX_DEPTH) > L_EST_LONG_BIT)
105
106 /* The maximum depth may be greater than the number of bits in a long,
107 ** so multiple longs are needed to hold a bit array indexed by node
108 ** depth. */
109
110 #define L_BIT_ARR_LONGS (((AVL_MAX_DEPTH) + L_LONG_BIT - 1) / L_LONG_BIT)
111
112 #define L_BIT_ARR_DEFN(NAME) unsigned long NAME[L_BIT_ARR_LONGS];
113
114 #define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) \
115 ((BIT_ARR)[(BIT_NUM) / L_LONG_BIT] & (1L << ((BIT_NUM) % L_LONG_BIT)))
116
117 #define L_BIT_ARR_0(BIT_ARR, BIT_NUM) \
118 (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] &= ~(1L << ((BIT_NUM) % L_LONG_BIT));
119
120 #define L_BIT_ARR_1(BIT_ARR, BIT_NUM) \
121 (BIT_ARR)[(BIT_NUM) / L_LONG_BIT] |= 1L << ((BIT_NUM) % L_LONG_BIT);
122
123 #define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) \
124 { int i = L_BIT_ARR_LONGS; do (BIT_ARR)[--i] = 0L - (BIT_VAL); while(i); }
125
126 #else /* The bit array can definitely fit in one long */
127
128 #define L_BIT_ARR_DEFN(NAME) unsigned long NAME;
129
130 #define L_BIT_ARR_VAL(BIT_ARR, BIT_NUM) ((BIT_ARR) & (1L << (BIT_NUM)))
131
132 #define L_BIT_ARR_0(BIT_ARR, BIT_NUM) (BIT_ARR) &= ~(1L << (BIT_NUM));
133
134 #define L_BIT_ARR_1(BIT_ARR, BIT_NUM) (BIT_ARR) |= 1L << (BIT_NUM);
135
136 #define L_BIT_ARR_ALL(BIT_ARR, BIT_VAL) (BIT_ARR) = 0L - (BIT_VAL);
137
138 #endif
139
140 #ifdef AVL_READ_ERRORS_HAPPEN
141
142 #define L_CHECK_READ_ERROR(ERROR_RETURN) \
143 { if (AVL_READ_ERROR) return(ERROR_RETURN); }
144
145 #else
146
147 #define L_CHECK_READ_ERROR(ERROR_RETURN)
148
149 #endif
150
151 /* The presumed reason that an instantiation places additional fields
152 ** inside the AVL tree structure is that the SET_ and GET_ macros
153 ** need these fields. The "balance" function does not explicitly use
154 ** any fields in the AVL tree structure, so only pass an AVL tree
155 ** structure pointer to "balance" if it has instantiation-specific
156 ** fields that are (presumably) needed by the SET_/GET_ calls within
157 ** "balance".
158 */
159 #ifdef AVL_INSIDE_STRUCT
160
161 #define L_BALANCE_PARAM_CALL_PREFIX l_tree,
162 #define L_BALANCE_PARAM_DECL_PREFIX L_(avl) *l_tree,
163
164 #else
165
166 #define L_BALANCE_PARAM_CALL_PREFIX
167 #define L_BALANCE_PARAM_DECL_PREFIX
168
169 #endif
170
171 #ifdef AVL_IMPL_MASK
172
173 #define L_IMPL_MASK (AVL_IMPL_MASK)
174
175 #else
176
177 /* Define all functions. */
178 #define L_IMPL_MASK AVL_IMPL_ALL
179
180 #endif
181
182 #if (L_IMPL_MASK & AVL_IMPL_INIT)
183
L_(init)184 L_SC void L_(init)(L_(avl) *l_tree) {
185 l_tree->root = AVL_NULL;
186 }
187
188 #endif
189
190 #if (L_IMPL_MASK & AVL_IMPL_IS_EMPTY)
191
L_(is_empty)192 L_SC int L_(is_empty)(L_(avl) *l_tree) {
193 return(l_tree->root == AVL_NULL);
194 }
195
196 #endif
197
198 /* Put the private balance function in the same compilation module as
199 ** the insert function. */
200 #if (L_IMPL_MASK & AVL_IMPL_INSERT)
201
202 /* Balances subtree, returns handle of root node of subtree after balancing.
203 */
L_(balance)204 L_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h) {
205 AVL_HANDLE deep_h;
206
207 /* Either the "greater than" or the "less than" subtree of
208 ** this node has to be 2 levels deeper (or else it wouldn't
209 ** need balancing).
210 */
211 if (AVL_GET_BALANCE_FACTOR(bal_h) > 0) {
212 /* "Greater than" subtree is deeper. */
213
214 deep_h = AVL_GET_GREATER(bal_h, 1);
215
216 L_CHECK_READ_ERROR(AVL_NULL)
217
218 if (AVL_GET_BALANCE_FACTOR(deep_h) < 0) {
219 int bf;
220
221 AVL_HANDLE old_h = bal_h;
222 bal_h = AVL_GET_LESS(deep_h, 1);
223 L_CHECK_READ_ERROR(AVL_NULL)
224 AVL_SET_GREATER(old_h, AVL_GET_LESS(bal_h, 1))
225 AVL_SET_LESS(deep_h, AVL_GET_GREATER(bal_h, 1))
226 AVL_SET_LESS(bal_h, old_h)
227 AVL_SET_GREATER(bal_h, deep_h)
228
229 bf = AVL_GET_BALANCE_FACTOR(bal_h);
230
231 if (bf != 0) {
232 if (bf > 0) {
233 AVL_SET_BALANCE_FACTOR(old_h, -1)
234 AVL_SET_BALANCE_FACTOR(deep_h, 0)
235 } else {
236 AVL_SET_BALANCE_FACTOR(deep_h, 1)
237 AVL_SET_BALANCE_FACTOR(old_h, 0)
238 }
239
240 AVL_SET_BALANCE_FACTOR(bal_h, 0)
241 } else {
242 AVL_SET_BALANCE_FACTOR(old_h, 0)
243 AVL_SET_BALANCE_FACTOR(deep_h, 0)
244 }
245 } else {
246 AVL_SET_GREATER(bal_h, AVL_GET_LESS(deep_h, 0))
247 AVL_SET_LESS(deep_h, bal_h)
248
249 if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) {
250 AVL_SET_BALANCE_FACTOR(deep_h, -1)
251 AVL_SET_BALANCE_FACTOR(bal_h, 1)
252 } else {
253 AVL_SET_BALANCE_FACTOR(deep_h, 0)
254 AVL_SET_BALANCE_FACTOR(bal_h, 0)
255 }
256
257 bal_h = deep_h;
258 }
259 } else {
260 /* "Less than" subtree is deeper. */
261
262 deep_h = AVL_GET_LESS(bal_h, 1);
263 L_CHECK_READ_ERROR(AVL_NULL)
264
265 if (AVL_GET_BALANCE_FACTOR(deep_h) > 0) {
266 int bf;
267 AVL_HANDLE old_h = bal_h;
268 bal_h = AVL_GET_GREATER(deep_h, 1);
269 L_CHECK_READ_ERROR(AVL_NULL)
270 AVL_SET_LESS(old_h, AVL_GET_GREATER(bal_h, 0))
271 AVL_SET_GREATER(deep_h, AVL_GET_LESS(bal_h, 0))
272 AVL_SET_GREATER(bal_h, old_h)
273 AVL_SET_LESS(bal_h, deep_h)
274
275 bf = AVL_GET_BALANCE_FACTOR(bal_h);
276
277 if (bf != 0) {
278 if (bf < 0) {
279 AVL_SET_BALANCE_FACTOR(old_h, 1)
280 AVL_SET_BALANCE_FACTOR(deep_h, 0)
281 } else {
282 AVL_SET_BALANCE_FACTOR(deep_h, -1)
283 AVL_SET_BALANCE_FACTOR(old_h, 0)
284 }
285
286 AVL_SET_BALANCE_FACTOR(bal_h, 0)
287 } else {
288 AVL_SET_BALANCE_FACTOR(old_h, 0)
289 AVL_SET_BALANCE_FACTOR(deep_h, 0)
290 }
291 } else {
292 AVL_SET_LESS(bal_h, AVL_GET_GREATER(deep_h, 0))
293 AVL_SET_GREATER(deep_h, bal_h)
294
295 if (AVL_GET_BALANCE_FACTOR(deep_h) == 0) {
296 AVL_SET_BALANCE_FACTOR(deep_h, 1)
297 AVL_SET_BALANCE_FACTOR(bal_h, -1)
298 } else {
299 AVL_SET_BALANCE_FACTOR(deep_h, 0)
300 AVL_SET_BALANCE_FACTOR(bal_h, 0)
301 }
302
303 bal_h = deep_h;
304 }
305 }
306
307 return(bal_h);
308 }
309
L_(insert)310 L_SC AVL_HANDLE L_(insert)(L_(avl) *l_tree, AVL_HANDLE h) {
311 AVL_SET_LESS(h, AVL_NULL)
312 AVL_SET_GREATER(h, AVL_NULL)
313 AVL_SET_BALANCE_FACTOR(h, 0)
314
315 if (l_tree->root == AVL_NULL)
316 l_tree->root = h;
317 else {
318 /* Last unbalanced node encountered in search for insertion point. */
319 AVL_HANDLE unbal = AVL_NULL;
320 /* Parent of last unbalanced node. */
321 AVL_HANDLE parent_unbal = AVL_NULL;
322 /* Balance factor of last unbalanced node. */
323 int unbal_bf;
324
325 /* Zero-based depth in tree. */
326 unsigned depth = 0, unbal_depth = 0;
327
328 /* Records a path into the tree. If bit n is true, indicates
329 ** take greater branch from the nth node in the path, otherwise
330 ** take the less branch. bit 0 gives branch from root, and
331 ** so on. */
332 L_BIT_ARR_DEFN(branch)
333
334 AVL_HANDLE hh = l_tree->root;
335 AVL_HANDLE parent = AVL_NULL;
336 int cmp;
337
338 do {
339 if (AVL_GET_BALANCE_FACTOR(hh) != 0) {
340 unbal = hh;
341 parent_unbal = parent;
342 unbal_depth = depth;
343 }
344
345 cmp = AVL_COMPARE_NODE_NODE(h, hh);
346
347 if (cmp == 0)
348 /* Duplicate key. */
349 return(hh);
350
351 parent = hh;
352
353 if (cmp > 0) {
354 hh = AVL_GET_GREATER(hh, 1);
355 L_BIT_ARR_1(branch, depth)
356 } else {
357 hh = AVL_GET_LESS(hh, 1);
358 L_BIT_ARR_0(branch, depth)
359 }
360
361 L_CHECK_READ_ERROR(AVL_NULL)
362 depth++;
363 } while (hh != AVL_NULL);
364
365 /* Add node to insert as leaf of tree. */
366 if (cmp < 0)
367 AVL_SET_LESS(parent, h)
368 else
369 AVL_SET_GREATER(parent, h)
370
371 depth = unbal_depth;
372
373 if (unbal == AVL_NULL)
374 hh = l_tree->root;
375 else {
376 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1;
377 depth++;
378 unbal_bf = AVL_GET_BALANCE_FACTOR(unbal);
379
380 if (cmp < 0)
381 unbal_bf--;
382 else /* cmp > 0 */
383 unbal_bf++;
384
385 hh = cmp < 0 ? AVL_GET_LESS(unbal, 1) : AVL_GET_GREATER(unbal, 1);
386 L_CHECK_READ_ERROR(AVL_NULL)
387
388 if ((unbal_bf != -2) && (unbal_bf != 2)) {
389 /* No rebalancing of tree is necessary. */
390 AVL_SET_BALANCE_FACTOR(unbal, unbal_bf)
391 unbal = AVL_NULL;
392 }
393 }
394
395 if (hh != AVL_NULL)
396 while (h != hh) {
397 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1;
398 depth++;
399
400 if (cmp < 0) {
401 AVL_SET_BALANCE_FACTOR(hh, -1)
402 hh = AVL_GET_LESS(hh, 1);
403 } else { /* cmp > 0 */
404 AVL_SET_BALANCE_FACTOR(hh, 1)
405 hh = AVL_GET_GREATER(hh, 1);
406 }
407
408 L_CHECK_READ_ERROR(AVL_NULL)
409 }
410
411 if (unbal != AVL_NULL) {
412 unbal = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX unbal);
413 L_CHECK_READ_ERROR(AVL_NULL)
414
415 if (parent_unbal == AVL_NULL)
416 l_tree->root = unbal;
417 else {
418 depth = unbal_depth - 1;
419 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1;
420
421 if (cmp < 0)
422 AVL_SET_LESS(parent_unbal, unbal)
423 else /* cmp > 0 */
424 AVL_SET_GREATER(parent_unbal, unbal)
425 }
426 }
427
428 }
429
430 return(h);
431 }
432
433 #endif
434
435 #if (L_IMPL_MASK & AVL_IMPL_SEARCH)
436
L_(search)437 L_SC AVL_HANDLE L_(search)(L_(avl) *l_tree, AVL_KEY k, avl_search_type st) {
438 int cmp, target_cmp;
439 AVL_HANDLE match_h = AVL_NULL;
440 AVL_HANDLE h = l_tree->root;
441
442 if (st & AVL_LESS)
443 target_cmp = 1;
444 else if (st & AVL_GREATER)
445 target_cmp = -1;
446 else
447 target_cmp = 0;
448
449 while (h != AVL_NULL) {
450 cmp = AVL_COMPARE_KEY_NODE(k, h);
451
452 if (cmp == 0) {
453 if (st & AVL_EQUAL) {
454 match_h = h;
455 break;
456 }
457
458 cmp = -target_cmp;
459 } else if (target_cmp != 0)
460 if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT))
461 /* cmp and target_cmp are both positive or both negative. */
462 match_h = h;
463
464 h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1);
465 L_CHECK_READ_ERROR(AVL_NULL)
466 }
467
468 return(match_h);
469 }
470
471 #endif
472
473 #if (L_IMPL_MASK & AVL_IMPL_SEARCH_LEAST)
474
L_(search_least)475 L_SC AVL_HANDLE L_(search_least)(L_(avl) *l_tree) {
476 AVL_HANDLE h = l_tree->root;
477 AVL_HANDLE parent = AVL_NULL;
478
479 while (h != AVL_NULL) {
480 parent = h;
481 h = AVL_GET_LESS(h, 1);
482 L_CHECK_READ_ERROR(AVL_NULL)
483 }
484
485 return(parent);
486 }
487
488 #endif
489
490 #if (L_IMPL_MASK & AVL_IMPL_SEARCH_GREATEST)
491
L_(search_greatest)492 L_SC AVL_HANDLE L_(search_greatest)(L_(avl) *l_tree) {
493 AVL_HANDLE h = l_tree->root;
494 AVL_HANDLE parent = AVL_NULL;
495
496 while (h != AVL_NULL) {
497 parent = h;
498 h = AVL_GET_GREATER(h, 1);
499 L_CHECK_READ_ERROR(AVL_NULL)
500 }
501
502 return(parent);
503 }
504
505 #endif
506
507 #if (L_IMPL_MASK & AVL_IMPL_REMOVE)
508
509 /* Prototype of balance function (called by remove) in case not in
510 ** same compilation unit.
511 */
512 L_SC AVL_HANDLE L_(balance)(L_BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h);
513
L_(remove)514 L_SC AVL_HANDLE L_(remove)(L_(avl) *l_tree, AVL_KEY k) {
515 /* Zero-based depth in tree. */
516 unsigned depth = 0, rm_depth;
517
518 /* Records a path into the tree. If bit n is true, indicates
519 ** take greater branch from the nth node in the path, otherwise
520 ** take the less branch. bit 0 gives branch from root, and
521 ** so on. */
522 L_BIT_ARR_DEFN(branch)
523
524 AVL_HANDLE h = l_tree->root;
525 AVL_HANDLE parent = AVL_NULL;
526 AVL_HANDLE child;
527 AVL_HANDLE path;
528 int cmp, cmp_shortened_sub_with_path;
529 int reduced_depth;
530 int bf;
531 AVL_HANDLE rm;
532 AVL_HANDLE parent_rm;
533
534 for (;;) {
535 if (h == AVL_NULL)
536 /* No node in tree with given key. */
537 return(AVL_NULL);
538
539 cmp = AVL_COMPARE_KEY_NODE(k, h);
540
541 if (cmp == 0)
542 /* Found node to remove. */
543 break;
544
545 parent = h;
546
547 if (cmp > 0) {
548 h = AVL_GET_GREATER(h, 1);
549 L_BIT_ARR_1(branch, depth)
550 } else {
551 h = AVL_GET_LESS(h, 1);
552 L_BIT_ARR_0(branch, depth)
553 }
554
555 L_CHECK_READ_ERROR(AVL_NULL)
556 depth++;
557 cmp_shortened_sub_with_path = cmp;
558 }
559
560 rm = h;
561 parent_rm = parent;
562 rm_depth = depth;
563
564 /* If the node to remove is not a leaf node, we need to get a
565 ** leaf node, or a node with a single leaf as its child, to put
566 ** in the place of the node to remove. We will get the greatest
567 ** node in the less subtree (of the node to remove), or the least
568 ** node in the greater subtree. We take the leaf node from the
569 ** deeper subtree, if there is one. */
570
571 if (AVL_GET_BALANCE_FACTOR(h) < 0) {
572 child = AVL_GET_LESS(h, 1);
573 L_BIT_ARR_0(branch, depth)
574 cmp = -1;
575 } else {
576 child = AVL_GET_GREATER(h, 1);
577 L_BIT_ARR_1(branch, depth)
578 cmp = 1;
579 }
580
581 L_CHECK_READ_ERROR(AVL_NULL)
582 depth++;
583
584 if (child != AVL_NULL) {
585 cmp = -cmp;
586
587 do {
588 parent = h;
589 h = child;
590
591 if (cmp < 0) {
592 child = AVL_GET_LESS(h, 1);
593 L_BIT_ARR_0(branch, depth)
594 } else {
595 child = AVL_GET_GREATER(h, 1);
596 L_BIT_ARR_1(branch, depth)
597 }
598
599 L_CHECK_READ_ERROR(AVL_NULL)
600 depth++;
601 } while (child != AVL_NULL);
602
603 if (parent == rm)
604 /* Only went through do loop once. Deleted node will be replaced
605 ** in the tree structure by one of its immediate children. */
606 cmp_shortened_sub_with_path = -cmp;
607 else
608 cmp_shortened_sub_with_path = cmp;
609
610 /* Get the handle of the opposite child, which may not be null. */
611 child = cmp > 0 ? AVL_GET_LESS(h, 0) : AVL_GET_GREATER(h, 0);
612 }
613
614 if (parent == AVL_NULL)
615 /* There were only 1 or 2 nodes in this tree. */
616 l_tree->root = child;
617 else if (cmp_shortened_sub_with_path < 0)
618 AVL_SET_LESS(parent, child)
619 else
620 AVL_SET_GREATER(parent, child)
621
622 /* "path" is the parent of the subtree being eliminated or reduced
623 ** from a depth of 2 to 1. If "path" is the node to be removed, we
624 ** set path to the node we're about to poke into the position of the
625 ** node to be removed. */
626 path = parent == rm ? h : parent;
627
628 if (h != rm) {
629 /* Poke in the replacement for the node to be removed. */
630 AVL_SET_LESS(h, AVL_GET_LESS(rm, 0))
631 AVL_SET_GREATER(h, AVL_GET_GREATER(rm, 0))
632 AVL_SET_BALANCE_FACTOR(h, AVL_GET_BALANCE_FACTOR(rm))
633
634 if (parent_rm == AVL_NULL)
635 l_tree->root = h;
636 else {
637 depth = rm_depth - 1;
638
639 if (L_BIT_ARR_VAL(branch, depth))
640 AVL_SET_GREATER(parent_rm, h)
641 else
642 AVL_SET_LESS(parent_rm, h)
643 }
644 }
645
646 if (path != AVL_NULL) {
647 /* Create a temporary linked list from the parent of the path node
648 ** to the root node. */
649 h = l_tree->root;
650 parent = AVL_NULL;
651 depth = 0;
652
653 while (h != path) {
654 if (L_BIT_ARR_VAL(branch, depth)) {
655 child = AVL_GET_GREATER(h, 1);
656 AVL_SET_GREATER(h, parent)
657 } else {
658 child = AVL_GET_LESS(h, 1);
659 AVL_SET_LESS(h, parent)
660 }
661
662 L_CHECK_READ_ERROR(AVL_NULL)
663 depth++;
664 parent = h;
665 h = child;
666 }
667
668 /* Climb from the path node to the root node using the linked
669 ** list, restoring the tree structure and rebalancing as necessary.
670 */
671 reduced_depth = 1;
672 cmp = cmp_shortened_sub_with_path;
673
674 for (;;) {
675 if (reduced_depth) {
676 bf = AVL_GET_BALANCE_FACTOR(h);
677
678 if (cmp < 0)
679 bf++;
680 else /* cmp > 0 */
681 bf--;
682
683 if ((bf == -2) || (bf == 2)) {
684 h = L_(balance)(L_BALANCE_PARAM_CALL_PREFIX h);
685 L_CHECK_READ_ERROR(AVL_NULL)
686 bf = AVL_GET_BALANCE_FACTOR(h);
687 } else
688 AVL_SET_BALANCE_FACTOR(h, bf)
689 reduced_depth = (bf == 0);
690 }
691
692 if (parent == AVL_NULL)
693 break;
694
695 child = h;
696 h = parent;
697 depth--;
698 cmp = L_BIT_ARR_VAL(branch, depth) ? 1 : -1;
699
700 if (cmp < 0) {
701 parent = AVL_GET_LESS(h, 1);
702 AVL_SET_LESS(h, child)
703 } else {
704 parent = AVL_GET_GREATER(h, 1);
705 AVL_SET_GREATER(h, child)
706 }
707
708 L_CHECK_READ_ERROR(AVL_NULL)
709 }
710
711 l_tree->root = h;
712 }
713
714 return(rm);
715 }
716
717 #endif
718
719 #if (L_IMPL_MASK & AVL_IMPL_SUBST)
720
L_(subst)721 L_SC AVL_HANDLE L_(subst)(L_(avl) *l_tree, AVL_HANDLE new_node) {
722 AVL_HANDLE h = l_tree->root;
723 AVL_HANDLE parent = AVL_NULL;
724 int cmp, last_cmp;
725
726 /* Search for node already in tree with same key. */
727 for (;;) {
728 if (h == AVL_NULL)
729 /* No node in tree with same key as new node. */
730 return(AVL_NULL);
731
732 cmp = AVL_COMPARE_NODE_NODE(new_node, h);
733
734 if (cmp == 0)
735 /* Found the node to substitute new one for. */
736 break;
737
738 last_cmp = cmp;
739 parent = h;
740 h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1);
741 L_CHECK_READ_ERROR(AVL_NULL)
742 }
743
744 /* Copy tree housekeeping fields from node in tree to new node. */
745 AVL_SET_LESS(new_node, AVL_GET_LESS(h, 0))
746 AVL_SET_GREATER(new_node, AVL_GET_GREATER(h, 0))
747 AVL_SET_BALANCE_FACTOR(new_node, AVL_GET_BALANCE_FACTOR(h))
748
749 if (parent == AVL_NULL)
750 /* New node is also new root. */
751 l_tree->root = new_node;
752 else {
753 /* Make parent point to new node. */
754 if (last_cmp < 0)
755 AVL_SET_LESS(parent, new_node)
756 else
757 AVL_SET_GREATER(parent, new_node)
758 }
759
760 return(h);
761 }
762
763 #endif
764
765 #ifdef AVL_BUILD_ITER_TYPE
766
767 #if (L_IMPL_MASK & AVL_IMPL_BUILD)
768
L_(build)769 L_SC int L_(build)(
770 L_(avl) *l_tree, AVL_BUILD_ITER_TYPE p, L_SIZE num_nodes) {
771 /* Gives path to subtree being built. If bit n is false, branch
772 ** less from the node at depth n, if true branch greater. */
773 L_BIT_ARR_DEFN(branch)
774
775 /* If bit n is true, then for the current subtree at depth n, its
776 ** greater subtree has one more node than its less subtree. */
777 L_BIT_ARR_DEFN(rem)
778
779 /* Depth of root node of current subtree. */
780 unsigned depth = 0;
781
782 /* Number of nodes in current subtree. */
783 L_SIZE num_sub = num_nodes;
784
785 /* The algorithm relies on a stack of nodes whose less subtree has
786 ** been built, but whose greater subtree has not yet been built.
787 ** The stack is implemented as linked list. The nodes are linked
788 ** together by having the "greater" handle of a node set to the
789 ** next node in the list. "less_parent" is the handle of the first
790 ** node in the list. */
791 AVL_HANDLE less_parent = AVL_NULL;
792
793 /* h is root of current subtree, child is one of its children. */
794 AVL_HANDLE h;
795 AVL_HANDLE child;
796
797 if (num_nodes == 0) {
798 l_tree->root = AVL_NULL;
799 return(1);
800 }
801
802 for (;;) {
803 while (num_sub > 2) {
804 /* Subtract one for root of subtree. */
805 num_sub--;
806
807 if (num_sub & 1)
808 L_BIT_ARR_1(rem, depth)
809 else
810 L_BIT_ARR_0(rem, depth)
811 L_BIT_ARR_0(branch, depth)
812 depth++;
813
814 num_sub >>= 1;
815 }
816
817 if (num_sub == 2) {
818 /* Build a subtree with two nodes, slanting to greater.
819 ** I arbitrarily chose to always have the extra node in the
820 ** greater subtree when there is an odd number of nodes to
821 ** split between the two subtrees. */
822
823 h = AVL_BUILD_ITER_VAL(p);
824 L_CHECK_READ_ERROR(0)
825 AVL_BUILD_ITER_INCR(p)
826 child = AVL_BUILD_ITER_VAL(p);
827 L_CHECK_READ_ERROR(0)
828 AVL_BUILD_ITER_INCR(p)
829 AVL_SET_LESS(child, AVL_NULL)
830 AVL_SET_GREATER(child, AVL_NULL)
831 AVL_SET_BALANCE_FACTOR(child, 0)
832 AVL_SET_GREATER(h, child)
833 AVL_SET_LESS(h, AVL_NULL)
834 AVL_SET_BALANCE_FACTOR(h, 1)
835 } else { /* num_sub == 1 */
836 /* Build a subtree with one node. */
837
838 h = AVL_BUILD_ITER_VAL(p);
839 L_CHECK_READ_ERROR(0)
840 AVL_BUILD_ITER_INCR(p)
841 AVL_SET_LESS(h, AVL_NULL)
842 AVL_SET_GREATER(h, AVL_NULL)
843 AVL_SET_BALANCE_FACTOR(h, 0)
844 }
845
846 while (depth) {
847 depth--;
848
849 if (!L_BIT_ARR_VAL(branch, depth))
850 /* We've completed a less subtree. */
851 break;
852
853 /* We've completed a greater subtree, so attach it to
854 ** its parent (that is less than it). We pop the parent
855 ** off the stack of less parents. */
856 child = h;
857 h = less_parent;
858 less_parent = AVL_GET_GREATER(h, 1);
859 L_CHECK_READ_ERROR(0)
860 AVL_SET_GREATER(h, child)
861 /* num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 */
862 num_sub <<= 1;
863 num_sub += L_BIT_ARR_VAL(rem, depth) ? 0 : 1;
864
865 if (num_sub & (num_sub - 1))
866 /* num_sub is not a power of 2. */
867 AVL_SET_BALANCE_FACTOR(h, 0)
868 else
869 /* num_sub is a power of 2. */
870 AVL_SET_BALANCE_FACTOR(h, 1)
871 }
872
873 if (num_sub == num_nodes)
874 /* We've completed the full tree. */
875 break;
876
877 /* The subtree we've completed is the less subtree of the
878 ** next node in the sequence. */
879
880 child = h;
881 h = AVL_BUILD_ITER_VAL(p);
882 L_CHECK_READ_ERROR(0)
883 AVL_BUILD_ITER_INCR(p)
884 AVL_SET_LESS(h, child)
885
886 /* Put h into stack of less parents. */
887 AVL_SET_GREATER(h, less_parent)
888 less_parent = h;
889
890 /* Proceed to creating greater than subtree of h. */
891 L_BIT_ARR_1(branch, depth)
892 num_sub += L_BIT_ARR_VAL(rem, depth) ? 1 : 0;
893 depth++;
894
895 } /* end for (;; ) */
896
897 l_tree->root = h;
898
899 return(1);
900 }
901
902 #endif
903
904 #endif
905
906 #if (L_IMPL_MASK & AVL_IMPL_INIT_ITER)
907
908 /* Initialize depth to invalid value, to indicate iterator is
909 ** invalid. (Depth is zero-base.) It's not necessary to initialize
910 ** iterators prior to passing them to the "start" function.
911 */
L_(init_iter)912 L_SC void L_(init_iter)(L_(iter) *iter) {
913 iter->depth = ~0;
914 }
915
916 #endif
917
918 #ifdef AVL_READ_ERRORS_HAPPEN
919
920 #define L_CHECK_READ_ERROR_INV_DEPTH \
921 { if (AVL_READ_ERROR) { iter->depth = ~0; return; } }
922
923 #else
924
925 #define L_CHECK_READ_ERROR_INV_DEPTH
926
927 #endif
928
929 #if (L_IMPL_MASK & AVL_IMPL_START_ITER)
930
L_(start_iter)931 L_SC void L_(start_iter)(
932 L_(avl) *l_tree, L_(iter) *iter, AVL_KEY k, avl_search_type st) {
933 AVL_HANDLE h = l_tree->root;
934 unsigned d = 0;
935 int cmp, target_cmp;
936
937 /* Save the tree that we're going to iterate through in a
938 ** member variable. */
939 iter->tree_ = l_tree;
940
941 iter->depth = ~0;
942
943 if (h == AVL_NULL)
944 /* Tree is empty. */
945 return;
946
947 if (st & AVL_LESS)
948 /* Key can be greater than key of starting node. */
949 target_cmp = 1;
950 else if (st & AVL_GREATER)
951 /* Key can be less than key of starting node. */
952 target_cmp = -1;
953 else
954 /* Key must be same as key of starting node. */
955 target_cmp = 0;
956
957 for (;;) {
958 cmp = AVL_COMPARE_KEY_NODE(k, h);
959
960 if (cmp == 0) {
961 if (st & AVL_EQUAL) {
962 /* Equal node was sought and found as starting node. */
963 iter->depth = d;
964 break;
965 }
966
967 cmp = -target_cmp;
968 } else if (target_cmp != 0)
969 if (!((cmp ^ target_cmp) & L_MASK_HIGH_BIT))
970 /* cmp and target_cmp are both negative or both positive. */
971 iter->depth = d;
972
973 h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1);
974 L_CHECK_READ_ERROR_INV_DEPTH
975
976 if (h == AVL_NULL)
977 break;
978
979 if (cmp > 0)
980 L_BIT_ARR_1(iter->branch, d)
981 else
982 L_BIT_ARR_0(iter->branch, d)
983 iter->path_h[d++] = h;
984 }
985 }
986
987 #endif
988
989 #if (L_IMPL_MASK & AVL_IMPL_START_ITER_LEAST)
990
L_(start_iter_least)991 L_SC void L_(start_iter_least)(L_(avl) *l_tree, L_(iter) *iter) {
992 AVL_HANDLE h = l_tree->root;
993
994 iter->tree_ = l_tree;
995
996 iter->depth = ~0;
997
998 L_BIT_ARR_ALL(iter->branch, 0)
999
1000 while (h != AVL_NULL) {
1001 if (iter->depth != ~0)
1002 iter->path_h[iter->depth] = h;
1003
1004 iter->depth++;
1005 h = AVL_GET_LESS(h, 1);
1006 L_CHECK_READ_ERROR_INV_DEPTH
1007 }
1008 }
1009
1010 #endif
1011
1012 #if (L_IMPL_MASK & AVL_IMPL_START_ITER_GREATEST)
1013
L_(start_iter_greatest)1014 L_SC void L_(start_iter_greatest)(L_(avl) *l_tree, L_(iter) *iter) {
1015 AVL_HANDLE h = l_tree->root;
1016
1017 iter->tree_ = l_tree;
1018
1019 iter->depth = ~0;
1020
1021 L_BIT_ARR_ALL(iter->branch, 1)
1022
1023 while (h != AVL_NULL) {
1024 if (iter->depth != ~0)
1025 iter->path_h[iter->depth] = h;
1026
1027 iter->depth++;
1028 h = AVL_GET_GREATER(h, 1);
1029 L_CHECK_READ_ERROR_INV_DEPTH
1030 }
1031 }
1032
1033 #endif
1034
1035 #if (L_IMPL_MASK & AVL_IMPL_GET_ITER)
1036
L_(get_iter)1037 L_SC AVL_HANDLE L_(get_iter)(L_(iter) *iter) {
1038 if (iter->depth == ~0)
1039 return(AVL_NULL);
1040
1041 return(iter->depth == 0 ?
1042 iter->tree_->root : iter->path_h[iter->depth - 1]);
1043 }
1044
1045 #endif
1046
1047 #if (L_IMPL_MASK & AVL_IMPL_INCR_ITER)
1048
L_(incr_iter)1049 L_SC void L_(incr_iter)(L_(iter) *iter) {
1050 #define l_tree (iter->tree_)
1051
1052 if (iter->depth != ~0) {
1053 AVL_HANDLE h =
1054 AVL_GET_GREATER((iter->depth == 0 ?
1055 iter->tree_->root : iter->path_h[iter->depth - 1]), 1);
1056 L_CHECK_READ_ERROR_INV_DEPTH
1057
1058 if (h == AVL_NULL)
1059 do {
1060 if (iter->depth == 0) {
1061 iter->depth = ~0;
1062 break;
1063 }
1064
1065 iter->depth--;
1066 } while (L_BIT_ARR_VAL(iter->branch, iter->depth));
1067 else {
1068 L_BIT_ARR_1(iter->branch, iter->depth)
1069 iter->path_h[iter->depth++] = h;
1070
1071 for (;;) {
1072 h = AVL_GET_LESS(h, 1);
1073 L_CHECK_READ_ERROR_INV_DEPTH
1074
1075 if (h == AVL_NULL)
1076 break;
1077
1078 L_BIT_ARR_0(iter->branch, iter->depth)
1079 iter->path_h[iter->depth++] = h;
1080 }
1081 }
1082 }
1083
1084 #undef l_tree
1085 }
1086
1087 #endif
1088
1089 #if (L_IMPL_MASK & AVL_IMPL_DECR_ITER)
1090
L_(decr_iter)1091 L_SC void L_(decr_iter)(L_(iter) *iter) {
1092 #define l_tree (iter->tree_)
1093
1094 if (iter->depth != ~0) {
1095 AVL_HANDLE h =
1096 AVL_GET_LESS((iter->depth == 0 ?
1097 iter->tree_->root : iter->path_h[iter->depth - 1]), 1);
1098 L_CHECK_READ_ERROR_INV_DEPTH
1099
1100 if (h == AVL_NULL)
1101 do {
1102 if (iter->depth == 0) {
1103 iter->depth = ~0;
1104 break;
1105 }
1106
1107 iter->depth--;
1108 } while (!L_BIT_ARR_VAL(iter->branch, iter->depth));
1109 else {
1110 L_BIT_ARR_0(iter->branch, iter->depth)
1111 iter->path_h[iter->depth++] = h;
1112
1113 for (;;) {
1114 h = AVL_GET_GREATER(h, 1);
1115 L_CHECK_READ_ERROR_INV_DEPTH
1116
1117 if (h == AVL_NULL)
1118 break;
1119
1120 L_BIT_ARR_1(iter->branch, iter->depth)
1121 iter->path_h[iter->depth++] = h;
1122 }
1123 }
1124 }
1125
1126 #undef l_tree
1127 }
1128
1129 #endif
1130
1131 /* Tidy up the preprocessor symbol name space. */
1132 #undef L_
1133 #undef L_EST_LONG_BIT
1134 #undef L_SIZE
1135 #undef L_MASK_HIGH_BIT
1136 #undef L_LONG_BIT
1137 #undef L_BIT_ARR_DEFN
1138 #undef L_BIT_ARR_VAL
1139 #undef L_BIT_ARR_0
1140 #undef L_BIT_ARR_1
1141 #undef L_BIT_ARR_ALL
1142 #undef L_CHECK_READ_ERROR
1143 #undef L_CHECK_READ_ERROR_INV_DEPTH
1144 #undef L_BIT_ARR_LONGS
1145 #undef L_IMPL_MASK
1146 #undef L_CHECK_READ_ERROR
1147 #undef L_CHECK_READ_ERROR_INV_DEPTH
1148 #undef L_SC
1149 #undef L_BALANCE_PARAM_CALL_PREFIX
1150 #undef L_BALANCE_PARAM_DECL_PREFIX
1151
1152 #endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_CAVL_IMPL_H_
1153