]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - repair/avl.c
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
19 avlnode_t
*back
= np
->avl_back
;
20 avlnode_t
*forw
= np
->avl_forw
;
21 avlnode_t
*nextino
= np
->avl_nextino
;
22 int bal
= np
->avl_balance
;
24 ASSERT(bal
!= AVL_BALANCE
|| (!back
&& !forw
) || (back
&& forw
));
25 ASSERT(bal
!= AVL_FORW
|| forw
);
26 ASSERT(bal
!= AVL_BACK
|| back
);
29 ASSERT(AVL_START(tree
, np
) < AVL_START(tree
, forw
));
30 ASSERT(np
->avl_forw
->avl_parent
== np
);
31 ASSERT(back
|| bal
== AVL_FORW
);
33 ASSERT(bal
!= AVL_FORW
);
34 ASSERT(bal
== AVL_BALANCE
|| back
);
35 ASSERT(bal
== AVL_BACK
|| !back
);
39 ASSERT(AVL_START(tree
, np
) > AVL_START(tree
, back
));
40 ASSERT(np
->avl_back
->avl_parent
== np
);
41 ASSERT(forw
|| bal
== AVL_BACK
);
43 ASSERT(bal
!= AVL_BACK
);
44 ASSERT(bal
== AVL_BALANCE
|| forw
);
45 ASSERT(bal
== AVL_FORW
|| !forw
);
51 ASSERT(AVL_END(tree
, np
) <= AVL_START(tree
, nextino
));
59 avlnode_t
*nlast
, *nnext
, *np
;
65 ASSERT(!nnext
|| nnext
->avl_parent
== NULL
);
69 avl_checknode(tree
, nnext
);
70 end
= AVL_END(tree
, nnext
);
73 if ((np
= nnext
->avl_forw
) && np
!= nlast
) {
78 nnext
= nnext
->avl_parent
;
84 if (np
= nnext
->avl_back
) {
85 if (AVL_END(tree
, np
) > offset
) {
92 nnext
= nnext
->avl_forw
;
94 nnext
= np
->avl_parent
;
99 #else /* ! AVL_DEBUG */
100 #define avl_checktree(t,x)
101 #endif /* AVL_DEBUG */
105 * Reset balance for np up through tree.
106 * ``direction'' is the way that np's balance
107 * is headed after the deletion of one of its children --
108 * e.g., deleting a avl_forw child sends avl_balance toward AVL_BACK.
109 * Called only when deleting a node from the tree.
113 avltree_desc_t
*tree
,
117 avlnode_t
**rootp
= &tree
->avl_root
;
124 ASSERT(direction
== AVL_BACK
|| direction
== AVL_FORW
);
126 if (np
->avl_balance
== AVL_BALANCE
) {
127 np
->avl_balance
= direction
;
131 parent
= np
->avl_parent
;
134 * If balance is being restored, no local node
135 * reorganization is necessary, but may be at
136 * a higher node. Reset direction and continue.
138 if (direction
!= np
->avl_balance
) {
139 np
->avl_balance
= AVL_BALANCE
;
141 if (parent
->avl_forw
== np
)
142 direction
= AVL_BACK
;
144 direction
= AVL_FORW
;
153 * Imbalance. If a avl_forw node was removed, direction
154 * (and, by reduction, np->avl_balance) is/was AVL_BACK.
156 if (np
->avl_balance
== AVL_BACK
) {
158 ASSERT(direction
== AVL_BACK
);
159 child
= np
->avl_back
;
160 bal
= child
->avl_balance
;
162 if (bal
!= AVL_FORW
) /* single LL */ {
164 * np gets pushed down to lesser child's
169 * child-> B deleted A -D
174 if (!(tree
->avl_flags
& AVLF_DUPLICITY
))
175 cmn_err(CE_CONT
, "!LL delete b 0x%x c 0x%x\n",
178 np
->avl_back
= child
->avl_forw
;
180 child
->avl_forw
->avl_parent
= np
;
181 child
->avl_forw
= np
;
184 if (parent
->avl_forw
== np
) {
185 parent
->avl_forw
= child
;
186 direction
= AVL_BACK
;
188 ASSERT(parent
->avl_back
== np
);
189 parent
->avl_back
= child
;
190 direction
= AVL_FORW
;
193 ASSERT(*rootp
== np
);
196 np
->avl_parent
= child
;
197 child
->avl_parent
= parent
;
199 if (bal
== AVL_BALANCE
) {
200 np
->avl_balance
= AVL_BACK
;
201 child
->avl_balance
= AVL_FORW
;
204 np
->avl_balance
= AVL_BALANCE
;
205 child
->avl_balance
= AVL_BALANCE
;
207 avl_checktree(tree
, *rootp
);
212 /* child->avl_balance == AVL_FORW double LR rotation
214 * child's avl_forw node gets promoted up, along with
215 * its avl_forw subtree
226 if (!(tree
->avl_flags
& AVLF_DUPLICITY
))
227 cmn_err(CE_CONT
, "!LR delete b 0x%x c 0x%x t 0x%x\n",
228 np
, child
, child
->avl_forw
);
230 tmp
= child
->avl_forw
;
231 bal
= tmp
->avl_balance
;
233 child
->avl_forw
= tmp
->avl_back
;
235 tmp
->avl_back
->avl_parent
= child
;
237 tmp
->avl_back
= child
;
238 child
->avl_parent
= tmp
;
240 np
->avl_back
= tmp
->avl_forw
;
242 tmp
->avl_forw
->avl_parent
= np
;
246 child
->avl_balance
= AVL_BACK
;
248 child
->avl_balance
= AVL_BALANCE
;
251 np
->avl_balance
= AVL_FORW
;
253 np
->avl_balance
= AVL_BALANCE
;
258 ASSERT(np
->avl_balance
== AVL_FORW
&& direction
== AVL_FORW
);
260 child
= np
->avl_forw
;
261 bal
= child
->avl_balance
;
263 if (bal
!= AVL_BACK
) /* single RR */ {
265 * np gets pushed down to greater child's
270 * deleted D <-child +B E
275 if (!(tree
->avl_flags
& AVLF_DUPLICITY
))
276 cmn_err(CE_CONT
, "!RR delete b 0x%x c 0x%x\n",
279 np
->avl_forw
= child
->avl_back
;
281 child
->avl_back
->avl_parent
= np
;
282 child
->avl_back
= np
;
285 if (parent
->avl_forw
== np
) {
286 parent
->avl_forw
= child
;
287 direction
= AVL_BACK
;
289 ASSERT(parent
->avl_back
== np
);
290 parent
->avl_back
= child
;
291 direction
= AVL_FORW
;
294 ASSERT(*rootp
== np
);
297 np
->avl_parent
= child
;
298 child
->avl_parent
= parent
;
300 if (bal
== AVL_BALANCE
) {
301 np
->avl_balance
= AVL_FORW
;
302 child
->avl_balance
= AVL_BACK
;
305 np
->avl_balance
= AVL_BALANCE
;
306 child
->avl_balance
= AVL_BALANCE
;
308 avl_checktree(tree
, *rootp
);
313 /* child->avl_balance == AVL_BACK double RL rotation */
315 if (!(tree
->avl_flags
& AVLF_DUPLICITY
))
316 cmn_err(CE_CONT
, "!RL delete b 0x%x c 0x%x t 0x%x\n",
317 np
, child
, child
->avl_back
);
319 tmp
= child
->avl_back
;
320 bal
= tmp
->avl_balance
;
322 child
->avl_back
= tmp
->avl_forw
;
324 tmp
->avl_forw
->avl_parent
= child
;
326 tmp
->avl_forw
= child
;
327 child
->avl_parent
= tmp
;
329 np
->avl_forw
= tmp
->avl_back
;
331 tmp
->avl_back
->avl_parent
= np
;
335 child
->avl_balance
= AVL_FORW
;
337 child
->avl_balance
= AVL_BALANCE
;
340 np
->avl_balance
= AVL_BACK
;
342 np
->avl_balance
= AVL_BALANCE
;
344 np
->avl_parent
= tmp
;
345 tmp
->avl_balance
= AVL_BALANCE
;
346 tmp
->avl_parent
= parent
;
349 if (parent
->avl_forw
== np
) {
350 parent
->avl_forw
= tmp
;
351 direction
= AVL_BACK
;
353 ASSERT(parent
->avl_back
== np
);
354 parent
->avl_back
= tmp
;
355 direction
= AVL_FORW
;
358 ASSERT(*rootp
== np
);
364 avl_checktree(tree
, *rootp
);
369 * Remove node from tree.
370 * avl_delete does the local tree manipulations,
371 * calls retreat() to rebalance tree up to its root.
375 avltree_desc_t
*tree
,
378 avlnode_t
*forw
= np
->avl_forw
;
379 avlnode_t
*back
= np
->avl_back
;
380 avlnode_t
*parent
= np
->avl_parent
;
386 * a left child exits, then greatest left descendent's nextino
387 * is pointing to np; make it point to np->nextino.
389 nnext
= np
->avl_back
;
391 if (!nnext
->avl_forw
)
392 break; /* can't find anything bigger */
393 nnext
= nnext
->avl_forw
;
396 if (np
->avl_parent
) {
398 * find nearest ancestor with lesser value. That ancestor's
399 * nextino is pointing to np; make it point to np->nextino
401 nnext
= np
->avl_parent
;
403 if (AVL_END(tree
, nnext
) <= AVL_END(tree
, np
))
405 nnext
= nnext
->avl_parent
;
411 ASSERT(nnext
->avl_nextino
== np
);
412 nnext
->avl_nextino
= np
->avl_nextino
;
414 * Something preceeds np; np cannot be firstino.
416 ASSERT(tree
->avl_firstino
!= np
);
420 * Nothing preceeding np; after deletion, np's nextino
421 * is firstino of tree.
423 ASSERT(tree
->avl_firstino
== np
);
424 tree
->avl_firstino
= np
->avl_nextino
;
429 * Degenerate cases...
439 forw
->avl_parent
= parent
;
441 if (parent
->avl_forw
== np
) {
442 parent
->avl_forw
= forw
;
443 retreat(tree
, parent
, AVL_BACK
);
445 ASSERT(parent
->avl_back
== np
);
446 parent
->avl_back
= forw
;
447 retreat(tree
, parent
, AVL_FORW
);
450 ASSERT(tree
->avl_root
== np
);
451 tree
->avl_root
= forw
;
453 avl_checktree(tree
, tree
->avl_root
);
458 * Harder case: children on both sides.
459 * If back's avl_forw pointer is null, just have back
460 * inherit np's avl_forw tree, remove np from the tree
461 * and adjust balance counters starting at back.
463 * np-> xI xH (befor retreat())
471 if ((forw
= back
->avl_forw
) == NULL
) {
473 * AVL_FORW retreat below will set back's
474 * balance to AVL_BACK.
476 back
->avl_balance
= np
->avl_balance
;
477 back
->avl_forw
= forw
= np
->avl_forw
;
478 forw
->avl_parent
= back
;
479 back
->avl_parent
= parent
;
482 if (parent
->avl_forw
== np
)
483 parent
->avl_forw
= back
;
485 ASSERT(parent
->avl_back
== np
);
486 parent
->avl_back
= back
;
489 ASSERT(tree
->avl_root
== np
);
490 tree
->avl_root
= back
;
494 * back is taking np's place in the tree, and
495 * has therefore lost a avl_back node (itself).
497 retreat(tree
, back
, AVL_FORW
);
498 avl_checktree(tree
, tree
->avl_root
);
503 * Hardest case: children on both sides, and back's
504 * avl_forw pointer isn't null. Find the immediately
505 * inferior buffer by following back's avl_forw line
506 * to the end, then have it inherit np's avl_forw tree.
510 * G J back-> G J (before retreat())
518 while ((back
= forw
->avl_forw
))
522 * Will be adjusted by retreat() below.
524 forw
->avl_balance
= np
->avl_balance
;
527 * forw inherits np's avl_forw...
529 forw
->avl_forw
= np
->avl_forw
;
530 np
->avl_forw
->avl_parent
= forw
;
533 * ... forw's parent gets forw's avl_back...
535 back
= forw
->avl_parent
;
536 back
->avl_forw
= forw
->avl_back
;
538 forw
->avl_back
->avl_parent
= back
;
541 * ... forw gets np's avl_back...
543 forw
->avl_back
= np
->avl_back
;
544 np
->avl_back
->avl_parent
= forw
;
547 * ... and forw gets np's parent.
549 forw
->avl_parent
= parent
;
552 if (parent
->avl_forw
== np
)
553 parent
->avl_forw
= forw
;
555 parent
->avl_back
= forw
;
557 ASSERT(tree
->avl_root
== np
);
558 tree
->avl_root
= forw
;
562 * What used to be forw's parent is the starting
563 * point for rebalancing. It has lost a avl_forw node.
565 retreat(tree
, back
, AVL_BACK
);
566 avl_checktree(tree
, tree
->avl_root
);
573 * Given range r [start, end), find any range which is contained in r.
574 * if checklen is non-zero, then only ranges of non-zero length are
575 * considered in finding a match.
579 avltree_desc_t
*tree
,
584 avlnode_t
*np
= tree
->avl_root
;
586 /* np = avl_findadjacent(tree, start, AVL_SUCCEED); */
588 if (start
< AVL_START(tree
, np
)) {
593 /* if we were to add node with start, would
594 * have a growth of AVL_BACK
596 /* if succeeding node is needed, this is it.
600 if (start
>= AVL_END(tree
, np
)) {
605 /* if we were to add node with start, would
606 * have a growth of AVL_FORW;
608 /* we are looking for a succeeding node;
611 np
= np
->avl_nextino
;
614 /* AVL_START(tree, np) <= start < AVL_END(tree, np) */
618 if (checklen
== AVL_INCLUDE_ZEROLEN
) {
619 if (end
<= AVL_START(tree
, np
)) {
620 /* something follows start, but is
621 * is entierly after the range (end)
625 /* np may stradle [start, end) */
629 * find non-zero length region
631 while (np
&& (AVL_END(tree
, np
) - AVL_START(tree
, np
) == 0)
632 && (AVL_START(tree
, np
) < end
))
633 np
= np
->avl_nextino
;
635 if ((np
== NULL
) || (AVL_START(tree
, np
) >= end
))
640 * nothing succeeds start, all existing ranges are before start.
646 * Returns a pointer to node which contains exact value.
650 avltree_desc_t
*tree
,
653 avlnode_t
*np
= tree
->avl_root
;
657 nvalue
= AVL_START(tree
, np
);
658 if (value
< nvalue
) {
662 if (value
== nvalue
) {
672 * Balance buffer AVL tree after attaching a new node to root.
673 * Called only by avl_insert.
682 * At this point, np points to the node to which
683 * a new node has been attached. All that remains is to
684 * propagate avl_balance up the tree.
687 avlnode_t
*parent
= np
->avl_parent
;
690 CERT(growth
== AVL_BACK
|| growth
== AVL_FORW
);
693 * If the buffer was already balanced, set avl_balance
694 * to the new direction. Continue if there is a
695 * parent after setting growth to reflect np's
696 * relation to its parent.
698 if (np
->avl_balance
== AVL_BALANCE
) {
699 np
->avl_balance
= growth
;
701 if (parent
->avl_forw
== np
)
704 ASSERT(parent
->avl_back
== np
);
714 if (growth
!= np
->avl_balance
) {
716 * Subtree is now balanced -- no net effect
717 * in the size of the subtree, so leave.
719 np
->avl_balance
= AVL_BALANCE
;
723 if (growth
== AVL_BACK
) {
725 child
= np
->avl_back
;
726 CERT(np
->avl_balance
== AVL_BACK
&& child
);
728 if (child
->avl_balance
== AVL_BACK
) { /* single LL */
730 * ``A'' just got inserted;
731 * np points to ``E'', child to ``C'',
732 * and it is already AVL_BACK --
733 * child will get promoted to top of subtree.
743 Note that child->avl_parent and
744 avl_balance get set in common code.
746 np
->avl_parent
= child
;
747 np
->avl_balance
= AVL_BALANCE
;
748 np
->avl_back
= child
->avl_forw
;
750 child
->avl_forw
->avl_parent
= np
;
751 child
->avl_forw
= np
;
756 * child's avl_forw node gets promoted to
757 * the top of the subtree.
768 avlnode_t
*tmp
= child
->avl_forw
;
770 CERT(child
->avl_balance
== AVL_FORW
&& tmp
);
772 child
->avl_forw
= tmp
->avl_back
;
774 tmp
->avl_back
->avl_parent
= child
;
776 tmp
->avl_back
= child
;
777 child
->avl_parent
= tmp
;
779 np
->avl_back
= tmp
->avl_forw
;
781 tmp
->avl_forw
->avl_parent
= np
;
784 np
->avl_parent
= tmp
;
786 if (tmp
->avl_balance
== AVL_BACK
)
787 np
->avl_balance
= AVL_FORW
;
789 np
->avl_balance
= AVL_BALANCE
;
791 if (tmp
->avl_balance
== AVL_FORW
)
792 child
->avl_balance
= AVL_BACK
;
794 child
->avl_balance
= AVL_BALANCE
;
797 * Set child to point to tmp since it is
798 * now the top of the subtree, and will
799 * get attached to the subtree parent in
800 * the common code below.
805 } else /* growth == AVL_BACK */ {
808 * This code is the mirror image of AVL_FORW above.
811 child
= np
->avl_forw
;
812 CERT(np
->avl_balance
== AVL_FORW
&& child
);
814 if (child
->avl_balance
== AVL_FORW
) { /* single RR */
815 np
->avl_parent
= child
;
816 np
->avl_balance
= AVL_BALANCE
;
817 np
->avl_forw
= child
->avl_back
;
819 child
->avl_back
->avl_parent
= np
;
820 child
->avl_back
= np
;
825 avlnode_t
*tmp
= child
->avl_back
;
827 ASSERT(child
->avl_balance
== AVL_BACK
&& tmp
);
829 child
->avl_back
= tmp
->avl_forw
;
831 tmp
->avl_forw
->avl_parent
= child
;
833 tmp
->avl_forw
= child
;
834 child
->avl_parent
= tmp
;
836 np
->avl_forw
= tmp
->avl_back
;
838 tmp
->avl_back
->avl_parent
= np
;
841 np
->avl_parent
= tmp
;
843 if (tmp
->avl_balance
== AVL_FORW
)
844 np
->avl_balance
= AVL_BACK
;
846 np
->avl_balance
= AVL_BALANCE
;
848 if (tmp
->avl_balance
== AVL_BACK
)
849 child
->avl_balance
= AVL_FORW
;
851 child
->avl_balance
= AVL_BALANCE
;
857 child
->avl_parent
= parent
;
858 child
->avl_balance
= AVL_BALANCE
;
861 if (parent
->avl_back
== np
)
862 parent
->avl_back
= child
;
864 parent
->avl_forw
= child
;
866 ASSERT(*rootp
== np
);
876 avl_insert_find_growth(
877 avltree_desc_t
*tree
,
878 uintptr_t start
, /* range start at start, */
879 uintptr_t end
, /* exclusive */
880 int *growthp
) /* OUT */
882 avlnode_t
*root
= tree
->avl_root
;
886 ASSERT(np
); /* caller ensures that there is atleast one node in tree */
889 CERT(np
->avl_parent
|| root
== np
);
890 CERT(!np
->avl_parent
|| root
!= np
);
891 CERT(!(np
->avl_back
) || np
->avl_back
->avl_parent
== np
);
892 CERT(!(np
->avl_forw
) || np
->avl_forw
->avl_parent
== np
);
893 CERT(np
->avl_balance
!= AVL_FORW
|| np
->avl_forw
);
894 CERT(np
->avl_balance
!= AVL_BACK
|| np
->avl_back
);
895 CERT(np
->avl_balance
!= AVL_BALANCE
||
896 np
->avl_back
== NULL
|| np
->avl_forw
);
897 CERT(np
->avl_balance
!= AVL_BALANCE
||
898 np
->avl_forw
== NULL
|| np
->avl_back
);
900 if (AVL_START(tree
, np
) >= end
) {
909 if (AVL_END(tree
, np
) <= start
) {
917 /* found exact match -- let caller decide if it is an error */
926 avltree_desc_t
*tree
,
932 uintptr_t start
= AVL_START(tree
, newnode
);
934 if (growth
== AVL_BACK
) {
936 parent
->avl_back
= newnode
;
938 * we are growing to the left; previous in-order to newnode is
939 * closest ancestor with lesser value. Before this
940 * insertion, this ancestor will be pointing to
941 * newnode's parent. After insertion, next in-order to newnode
944 newnode
->avl_nextino
= parent
;
947 if (AVL_END(tree
, nnext
) <= start
)
949 nnext
= nnext
->avl_parent
;
953 * nnext will be null if newnode is
954 * the least element, and hence very first in the list.
956 ASSERT(nnext
->avl_nextino
== parent
);
957 nnext
->avl_nextino
= newnode
;
961 parent
->avl_forw
= newnode
;
962 newnode
->avl_nextino
= parent
->avl_nextino
;
963 parent
->avl_nextino
= newnode
;
970 avltree_desc_t
*tree
,
974 uintptr_t start
= AVL_START(tree
, newnode
);
975 uintptr_t end
= AVL_END(tree
, newnode
);
979 ASSERT(start
<= end
);
982 * Clean all pointers for sanity; some will be reset as necessary.
984 newnode
->avl_nextino
= NULL
;
985 newnode
->avl_parent
= NULL
;
986 newnode
->avl_forw
= NULL
;
987 newnode
->avl_back
= NULL
;
988 newnode
->avl_balance
= AVL_BALANCE
;
990 if ((np
= tree
->avl_root
) == NULL
) { /* degenerate case... */
991 tree
->avl_root
= newnode
;
992 tree
->avl_firstino
= newnode
;
996 if ((np
= avl_insert_find_growth(tree
, start
, end
, &growth
)) == NULL
) {
997 if (start
!= end
) { /* non-zero length range */
999 _("avl_insert: Warning! duplicate range [%llu,%llu]\n"),
1000 (unsigned long long)start
,
1001 (unsigned long long)end
);
1006 avl_insert_grow(tree
, np
, newnode
, growth
);
1007 if (growth
== AVL_BACK
) {
1009 * Growing to left. if np was firstino, newnode will be firstino
1011 if (tree
->avl_firstino
== np
)
1012 tree
->avl_firstino
= newnode
;
1016 if (growth
== AVL_FORW
)
1018 * Cannot possibly be firstino; there is somebody to our left.
1023 newnode
->avl_parent
= np
;
1024 CERT(np
->avl_forw
== newnode
|| np
->avl_back
== newnode
);
1026 avl_balance(&tree
->avl_root
, np
, growth
);
1028 avl_checktree(tree
, tree
->avl_root
);
1035 * avl_insert_immediate(tree, afterp, newnode):
1036 * insert newnode immediately into tree immediately after afterp.
1037 * after insertion, newnode is right child of afterp.
1040 avl_insert_immediate(
1041 avltree_desc_t
*tree
,
1046 * Clean all pointers for sanity; some will be reset as necessary.
1048 newnode
->avl_nextino
= NULL
;
1049 newnode
->avl_parent
= NULL
;
1050 newnode
->avl_forw
= NULL
;
1051 newnode
->avl_back
= NULL
;
1052 newnode
->avl_balance
= AVL_BALANCE
;
1054 if (afterp
== NULL
) {
1055 tree
->avl_root
= newnode
;
1056 tree
->avl_firstino
= newnode
;
1060 ASSERT(afterp
->avl_forw
== NULL
);
1061 avl_insert_grow(tree
, afterp
, newnode
, AVL_FORW
); /* grow to right */
1062 CERT(afterp
->avl_forw
== newnode
);
1063 avl_balance(&tree
->avl_root
, afterp
, AVL_FORW
);
1064 avl_checktree(tree
, tree
->avl_root
);
1069 * Returns first in order node
1072 avl_firstino(avlnode_t
*root
)
1076 if ((np
= root
) == NULL
)
1079 while (np
->avl_back
)
1085 * Returns last in order node
1088 avl_lastino(avlnode_t
*root
)
1092 if ((np
= root
) == NULL
)
1095 while (np
->avl_forw
)
1101 avl_init_tree(avltree_desc_t
*tree
, avlops_t
*ops
)
1103 tree
->avl_root
= NULL
;
1104 tree
->avl_firstino
= NULL
;
1105 tree
->avl_ops
= ops
;
1110 avl_printnode(avltree_desc_t
*tree
, avlnode_t
*np
, int nl
)
1112 printf("[%d-%d]%c", AVL_START(tree
, np
),
1113 (AVL_END(tree
, np
) - 1), nl
? '\n' : ' ');
1116 #ifdef STAND_ALONE_DEBUG
1118 struct avl_debug_node
{
1120 xfs_off_t avl_start
;
1121 unsigned int avl_size
;
1124 avlops_t avl_debug_ops
= {
1130 avl_debug_start(avlnode_t
*node
)
1132 return (uintptr_t)(struct avl_debug_node
*)node
->avl_start
;
1136 avl_debug_end(avlnode_t
*node
)
1139 ((struct avl_debug_node
*)node
->avl_start
+
1140 (struct avl_debug_node
*)node
->avl_size
);
1143 avl_debug_node freenodes
[100];
1144 avl_debug_node
*freehead
= &freenodes
[0];
1147 alloc_avl_debug_node()
1149 freehead
->avl_balance
= AVL_BALANCE
;
1150 freehead
->avl_parent
= freehead
->avl_forw
= freehead
->avl_back
= NULL
;
1155 avl_print(avltree_desc_t
*tree
, avlnode_t
*root
, int depth
)
1162 avl_print(tree
, root
->avl_forw
, depth
+5);
1163 for (i
= 0; i
< depth
; i
++)
1165 avl_printnode(tree
, root
,1);
1167 avl_print(tree
, root
->avl_back
, depth
+5);
1174 avltree_desc_t tree
;
1175 char linebuf
[256], cmd
[256];
1177 avl_init_tree(&tree
, &avl_debug_ops
);
1179 for (i
= 100; i
> 0; i
= i
- 10)
1181 np
= alloc__debug_avlnode();
1185 avl_insert(&tree
, np
);
1187 avl_print(&tree
, tree
.avl_root
, 0);
1189 for (np
= tree
.avl_firstino
; np
!= NULL
; np
= np
->avl_nextino
)
1190 avl_printnode(&tree
, np
, 0);
1194 printf(_("Command [fpdir] : "));
1195 fgets(linebuf
, 256, stdin
);
1196 if (feof(stdin
)) break;
1198 if (sscanf(linebuf
, "%[fpdir]%d", cmd
, &i
) != 2)
1203 printf(_("end of range ? "));
1204 fgets(linebuf
, 256, stdin
);
1207 if (i
== j
) j
= i
+1;
1208 np
= avl_findinrange(&tree
,i
,j
);
1210 avl_printnode(&tree
, np
, 1);
1212 avl_delete(&tree
, np
);
1214 printf(_("Cannot find %d\n"), i
);
1217 avl_print(&tree
, tree
.avl_root
, 0);
1218 for (np
= tree
.avl_firstino
;
1219 np
!= NULL
; np
= np
->avl_nextino
)
1220 avl_printnode(&tree
, np
, 0);
1224 np
= alloc_avlnode();
1227 printf(_("size of range ? "));
1228 fgets(linebuf
, 256, stdin
);
1232 avl_insert(&tree
, np
);
1235 avlnode_t
*b
, *e
, *t
;
1238 printf(_("End of range ? "));
1239 fgets(linebuf
, 256, stdin
);
1242 printf(_("checklen 0/1 ? "));
1243 fgets(linebuf
, 256, stdin
);
1244 checklen
= atoi(linebuf
);
1247 b
= avl_findanyrange(&tree
, i
, j
, checklen
);
1249 printf(_("Found something\n"));
1253 AVL_START(&tree
, t
) >= j
)
1255 avl_printnode(&tree
, t
, 0);
1267 * Given a tree, find value; will find return range enclosing value,
1268 * or range immediately succeeding value,
1269 * or range immediately preceeding value.
1273 avltree_desc_t
*tree
,
1277 avlnode_t
*np
= tree
->avl_root
;
1280 if (value
< AVL_START(tree
, np
)) {
1285 /* if we were to add node with value, would
1286 * have a growth of AVL_BACK
1288 if (dir
== AVL_SUCCEED
) {
1289 /* if succeeding node is needed, this is it.
1293 if (dir
== AVL_PRECEED
) {
1295 * find nearest ancestor with lesser value.
1297 np
= np
->avl_parent
;
1299 if (AVL_END(tree
, np
) <= value
)
1301 np
= np
->avl_parent
;
1305 ASSERT(dir
== AVL_SUCCEED
|| dir
== AVL_PRECEED
);
1308 if (value
>= AVL_END(tree
, np
)) {
1313 /* if we were to add node with value, would
1314 * have a growth of AVL_FORW;
1316 if (dir
== AVL_SUCCEED
) {
1317 /* we are looking for a succeeding node;
1320 return(np
->avl_nextino
);
1322 if (dir
== AVL_PRECEED
) {
1323 /* looking for a preceeding node; this is it. */
1326 ASSERT(dir
== AVL_SUCCEED
|| dir
== AVL_PRECEED
);
1328 /* AVL_START(tree, np) <= value < AVL_END(tree, np) */
1338 * Given range r [start, end), find all ranges in tree which are contained
1339 * in r. At return, startp and endp point to first and last of
1340 * a chain of elements which describe the contained ranges. Elements
1341 * in startp ... endp are in sort order, and can be accessed by
1342 * using avl_nextino.
1347 avltree_desc_t
*tree
,
1355 np
= avl_findadjacent(tree
, start
, AVL_SUCCEED
);
1356 if (np
== NULL
/* nothing succeding start */
1357 || (np
&& (end
<= AVL_START(tree
, np
))))
1358 /* something follows start,
1359 but... is entirely after end */
1368 /* see if end is in this region itself */
1369 if (end
<= AVL_END(tree
, np
) ||
1370 np
->avl_nextino
== NULL
||
1372 (end
<= AVL_START(tree
, np
->avl_nextino
)))) {
1376 /* have to munge for end */
1378 * note: have to look for (end - 1), since
1379 * findadjacent will look for exact value, and does not
1380 * care about the fact that end is actually one more
1381 * than the value actually being looked for; thus feed it one less.
1383 *endp
= avl_findadjacent(tree
, (end
-1), AVL_PRECEED
);