]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libfrog/avl64.c
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
8 #include "platform_defs.h"
17 avl64tree_desc_t
*tree
,
20 avl64node_t
*back
= np
->avl_back
;
21 avl64node_t
*forw
= np
->avl_forw
;
22 avl64node_t
*nextino
= np
->avl_nextino
;
23 int bal
= np
->avl_balance
;
25 ASSERT(bal
!= AVL_BALANCE
|| (!back
&& !forw
) || (back
&& forw
));
26 ASSERT(bal
!= AVL_FORW
|| forw
);
27 ASSERT(bal
!= AVL_BACK
|| back
);
30 ASSERT(AVL_START(tree
, np
) < AVL_START(tree
, forw
));
31 ASSERT(np
->avl_forw
->avl_parent
== np
);
32 ASSERT(back
|| bal
== AVL_FORW
);
34 ASSERT(bal
!= AVL_FORW
);
35 ASSERT(bal
== AVL_BALANCE
|| back
);
36 ASSERT(bal
== AVL_BACK
|| !back
);
40 ASSERT(AVL_START(tree
, np
) > AVL_START(tree
, back
));
41 ASSERT(np
->avl_back
->avl_parent
== np
);
42 ASSERT(forw
|| bal
== AVL_BACK
);
44 ASSERT(bal
!= AVL_BACK
);
45 ASSERT(bal
== AVL_BALANCE
|| forw
);
46 ASSERT(bal
== AVL_FORW
|| !forw
);
52 ASSERT(AVL_END(tree
, np
) <= AVL_START(tree
, nextino
));
57 avl64tree_desc_t
*tree
,
60 avl64node_t
*nlast
, *nnext
, *np
;
66 ASSERT(!nnext
|| nnext
->avl_parent
== NULL
);
70 avl64_checknode(tree
, nnext
);
71 end
= AVL_END(tree
, nnext
);
74 if ((np
= nnext
->avl_forw
) && np
!= nlast
) {
79 nnext
= nnext
->avl_parent
;
85 if (np
= nnext
->avl_back
) {
86 if (AVL_END(tree
, np
) > offset
) {
93 nnext
= nnext
->avl_forw
;
95 nnext
= np
->avl_parent
;
100 #else /* ! AVL_DEBUG */
101 #define avl64_checktree(t,x)
102 #endif /* AVL_DEBUG */
106 * Reset balance for np up through tree.
107 * ``direction'' is the way that np's balance
108 * is headed after the deletion of one of its children --
109 * e.g., deleting a avl_forw child sends avl_balance toward AVL_BACK.
110 * Called only when deleting a node from the tree.
114 avl64tree_desc_t
*tree
,
118 avl64node_t
**rootp
= &tree
->avl_root
;
125 ASSERT(direction
== AVL_BACK
|| direction
== AVL_FORW
);
127 if (np
->avl_balance
== AVL_BALANCE
) {
128 np
->avl_balance
= direction
;
132 parent
= np
->avl_parent
;
135 * If balance is being restored, no local node
136 * reorganization is necessary, but may be at
137 * a higher node. Reset direction and continue.
139 if (direction
!= np
->avl_balance
) {
140 np
->avl_balance
= AVL_BALANCE
;
142 if (parent
->avl_forw
== np
)
143 direction
= AVL_BACK
;
145 direction
= AVL_FORW
;
154 * Imbalance. If a avl_forw node was removed, direction
155 * (and, by reduction, np->avl_balance) is/was AVL_BACK.
157 if (np
->avl_balance
== AVL_BACK
) {
159 ASSERT(direction
== AVL_BACK
);
160 child
= np
->avl_back
;
161 bal
= child
->avl_balance
;
163 if (bal
!= AVL_FORW
) /* single LL */ {
165 * np gets pushed down to lesser child's
170 * child-> B deleted A -D
173 cmn_err(CE_CONT, "!LL delete b 0x%x c 0x%x\n",
177 np
->avl_back
= child
->avl_forw
;
179 child
->avl_forw
->avl_parent
= np
;
180 child
->avl_forw
= np
;
183 if (parent
->avl_forw
== np
) {
184 parent
->avl_forw
= child
;
185 direction
= AVL_BACK
;
187 ASSERT(parent
->avl_back
== np
);
188 parent
->avl_back
= child
;
189 direction
= AVL_FORW
;
192 ASSERT(*rootp
== np
);
195 np
->avl_parent
= child
;
196 child
->avl_parent
= parent
;
198 if (bal
== AVL_BALANCE
) {
199 np
->avl_balance
= AVL_BACK
;
200 child
->avl_balance
= AVL_FORW
;
203 np
->avl_balance
= AVL_BALANCE
;
204 child
->avl_balance
= AVL_BALANCE
;
206 avl64_checktree(tree
, *rootp
);
211 /* child->avl_balance == AVL_FORW double LR rotation
213 * child's avl_forw node gets promoted up, along with
214 * its avl_forw subtree
223 cmn_err(CE_CONT, "!LR delete b 0x%x c 0x%x t 0x%x\n",
224 np, child, child->avl_forw);
227 tmp
= child
->avl_forw
;
228 bal
= tmp
->avl_balance
;
230 child
->avl_forw
= tmp
->avl_back
;
232 tmp
->avl_back
->avl_parent
= child
;
234 tmp
->avl_back
= child
;
235 child
->avl_parent
= tmp
;
237 np
->avl_back
= tmp
->avl_forw
;
239 tmp
->avl_forw
->avl_parent
= np
;
243 child
->avl_balance
= AVL_BACK
;
245 child
->avl_balance
= AVL_BALANCE
;
248 np
->avl_balance
= AVL_FORW
;
250 np
->avl_balance
= AVL_BALANCE
;
255 ASSERT(np
->avl_balance
== AVL_FORW
&& direction
== AVL_FORW
);
257 child
= np
->avl_forw
;
258 bal
= child
->avl_balance
;
260 if (bal
!= AVL_BACK
) /* single RR */ {
262 * np gets pushed down to greater child's
267 * deleted D <-child +B E
270 cmn_err(CE_CONT, "!RR delete b 0x%x c 0x%x\n",
274 np
->avl_forw
= child
->avl_back
;
276 child
->avl_back
->avl_parent
= np
;
277 child
->avl_back
= np
;
280 if (parent
->avl_forw
== np
) {
281 parent
->avl_forw
= child
;
282 direction
= AVL_BACK
;
284 ASSERT(parent
->avl_back
== np
);
285 parent
->avl_back
= child
;
286 direction
= AVL_FORW
;
289 ASSERT(*rootp
== np
);
292 np
->avl_parent
= child
;
293 child
->avl_parent
= parent
;
295 if (bal
== AVL_BALANCE
) {
296 np
->avl_balance
= AVL_FORW
;
297 child
->avl_balance
= AVL_BACK
;
300 np
->avl_balance
= AVL_BALANCE
;
301 child
->avl_balance
= AVL_BALANCE
;
303 avl64_checktree(tree
, *rootp
);
308 /* child->avl_balance == AVL_BACK double RL rotation
309 cmn_err(CE_CONT, "!RL delete b 0x%x c 0x%x t 0x%x\n",
310 np, child, child->avl_back);
313 tmp
= child
->avl_back
;
314 bal
= tmp
->avl_balance
;
316 child
->avl_back
= tmp
->avl_forw
;
318 tmp
->avl_forw
->avl_parent
= child
;
320 tmp
->avl_forw
= child
;
321 child
->avl_parent
= tmp
;
323 np
->avl_forw
= tmp
->avl_back
;
325 tmp
->avl_back
->avl_parent
= np
;
329 child
->avl_balance
= AVL_FORW
;
331 child
->avl_balance
= AVL_BALANCE
;
334 np
->avl_balance
= AVL_BACK
;
336 np
->avl_balance
= AVL_BALANCE
;
338 np
->avl_parent
= tmp
;
339 tmp
->avl_balance
= AVL_BALANCE
;
340 tmp
->avl_parent
= parent
;
343 if (parent
->avl_forw
== np
) {
344 parent
->avl_forw
= tmp
;
345 direction
= AVL_BACK
;
347 ASSERT(parent
->avl_back
== np
);
348 parent
->avl_back
= tmp
;
349 direction
= AVL_FORW
;
352 ASSERT(*rootp
== np
);
358 avl64_checktree(tree
, *rootp
);
363 * Remove node from tree.
364 * avl_delete does the local tree manipulations,
365 * calls retreat() to rebalance tree up to its root.
369 avl64tree_desc_t
*tree
,
372 avl64node_t
*forw
= np
->avl_forw
;
373 avl64node_t
*back
= np
->avl_back
;
374 avl64node_t
*parent
= np
->avl_parent
;
380 * a left child exits, then greatest left descendent's nextino
381 * is pointing to np; make it point to np->nextino.
383 nnext
= np
->avl_back
;
385 if (!nnext
->avl_forw
)
386 break; /* can't find anything bigger */
387 nnext
= nnext
->avl_forw
;
390 if (np
->avl_parent
) {
392 * find nearest ancestor with lesser value. That ancestor's
393 * nextino is pointing to np; make it point to np->nextino
395 nnext
= np
->avl_parent
;
397 if (AVL_END(tree
, nnext
) <= AVL_END(tree
, np
))
399 nnext
= nnext
->avl_parent
;
405 ASSERT(nnext
->avl_nextino
== np
);
406 nnext
->avl_nextino
= np
->avl_nextino
;
408 * Something preceeds np; np cannot be firstino.
410 ASSERT(tree
->avl_firstino
!= np
);
414 * Nothing preceeding np; after deletion, np's nextino
415 * is firstino of tree.
417 ASSERT(tree
->avl_firstino
== np
);
418 tree
->avl_firstino
= np
->avl_nextino
;
423 * Degenerate cases...
433 forw
->avl_parent
= parent
;
435 if (parent
->avl_forw
== np
) {
436 parent
->avl_forw
= forw
;
437 retreat(tree
, parent
, AVL_BACK
);
439 ASSERT(parent
->avl_back
== np
);
440 parent
->avl_back
= forw
;
441 retreat(tree
, parent
, AVL_FORW
);
444 ASSERT(tree
->avl_root
== np
);
445 tree
->avl_root
= forw
;
447 avl64_checktree(tree
, tree
->avl_root
);
452 * Harder case: children on both sides.
453 * If back's avl_forw pointer is null, just have back
454 * inherit np's avl_forw tree, remove np from the tree
455 * and adjust balance counters starting at back.
457 * np-> xI xH (befor retreat())
465 if ((forw
= back
->avl_forw
) == NULL
) {
467 * AVL_FORW retreat below will set back's
468 * balance to AVL_BACK.
470 back
->avl_balance
= np
->avl_balance
;
471 back
->avl_forw
= forw
= np
->avl_forw
;
472 forw
->avl_parent
= back
;
473 back
->avl_parent
= parent
;
476 if (parent
->avl_forw
== np
)
477 parent
->avl_forw
= back
;
479 ASSERT(parent
->avl_back
== np
);
480 parent
->avl_back
= back
;
483 ASSERT(tree
->avl_root
== np
);
484 tree
->avl_root
= back
;
488 * back is taking np's place in the tree, and
489 * has therefore lost a avl_back node (itself).
491 retreat(tree
, back
, AVL_FORW
);
492 avl64_checktree(tree
, tree
->avl_root
);
497 * Hardest case: children on both sides, and back's
498 * avl_forw pointer isn't null. Find the immediately
499 * inferior buffer by following back's avl_forw line
500 * to the end, then have it inherit np's avl_forw tree.
504 * G J back-> G J (before retreat())
512 while ((back
= forw
->avl_forw
))
516 * Will be adjusted by retreat() below.
518 forw
->avl_balance
= np
->avl_balance
;
521 * forw inherits np's avl_forw...
523 forw
->avl_forw
= np
->avl_forw
;
524 np
->avl_forw
->avl_parent
= forw
;
527 * ... forw's parent gets forw's avl_back...
529 back
= forw
->avl_parent
;
530 back
->avl_forw
= forw
->avl_back
;
532 forw
->avl_back
->avl_parent
= back
;
535 * ... forw gets np's avl_back...
537 forw
->avl_back
= np
->avl_back
;
538 np
->avl_back
->avl_parent
= forw
;
541 * ... and forw gets np's parent.
543 forw
->avl_parent
= parent
;
546 if (parent
->avl_forw
== np
)
547 parent
->avl_forw
= forw
;
549 parent
->avl_back
= forw
;
551 ASSERT(tree
->avl_root
== np
);
552 tree
->avl_root
= forw
;
556 * What used to be forw's parent is the starting
557 * point for rebalancing. It has lost a avl_forw node.
559 retreat(tree
, back
, AVL_BACK
);
560 avl64_checktree(tree
, tree
->avl_root
);
567 * Given range r [start, end), find any range which is contained in r.
568 * if checklen is non-zero, then only ranges of non-zero length are
569 * considered in finding a match.
573 avl64tree_desc_t
*tree
,
578 avl64node_t
*np
= tree
->avl_root
;
580 /* np = avl64_findadjacent(tree, start, AVL_SUCCEED); */
582 if (start
< AVL_START(tree
, np
)) {
587 /* if we were to add node with start, would
588 * have a growth of AVL_BACK
590 /* if succeeding node is needed, this is it.
594 if (start
>= AVL_END(tree
, np
)) {
599 /* if we were to add node with start, would
600 * have a growth of AVL_FORW;
602 /* we are looking for a succeeding node;
605 np
= np
->avl_nextino
;
608 /* AVL_START(tree, np) <= start < AVL_END(tree, np) */
612 if (checklen
== AVL_INCLUDE_ZEROLEN
) {
613 if (end
<= AVL_START(tree
, np
)) {
614 /* something follows start, but is
615 * is entierly after the range (end)
619 /* np may stradle [start, end) */
623 * find non-zero length region
625 while (np
&& (AVL_END(tree
, np
) - AVL_START(tree
, np
) == 0)
626 && (AVL_START(tree
, np
) < end
))
627 np
= np
->avl_nextino
;
629 if ((np
== NULL
) || (AVL_START(tree
, np
) >= end
))
634 * nothing succeeds start, all existing ranges are before start.
641 * Returns a pointer to range which contains value.
645 avl64tree_desc_t
*tree
,
648 avl64node_t
*np
= tree
->avl_root
;
651 if (value
< AVL_START(tree
, np
)) {
655 if (value
>= AVL_END(tree
, np
)) {
659 ASSERT(AVL_START(tree
, np
) <= value
&&
660 value
< AVL_END(tree
, np
));
668 * Returns a pointer to node which contains exact value.
672 avl64tree_desc_t
*tree
,
675 avl64node_t
*np
= tree
->avl_root
;
679 nvalue
= AVL_START(tree
, np
);
680 if (value
< nvalue
) {
684 if (value
== nvalue
) {
694 * Balance buffer AVL tree after attaching a new node to root.
695 * Called only by avl_insert.
704 * At this point, np points to the node to which
705 * a new node has been attached. All that remains is to
706 * propagate avl_balance up the tree.
709 avl64node_t
*parent
= np
->avl_parent
;
712 CERT(growth
== AVL_BACK
|| growth
== AVL_FORW
);
715 * If the buffer was already balanced, set avl_balance
716 * to the new direction. Continue if there is a
717 * parent after setting growth to reflect np's
718 * relation to its parent.
720 if (np
->avl_balance
== AVL_BALANCE
) {
721 np
->avl_balance
= growth
;
723 if (parent
->avl_forw
== np
)
726 ASSERT(parent
->avl_back
== np
);
736 if (growth
!= np
->avl_balance
) {
738 * Subtree is now balanced -- no net effect
739 * in the size of the subtree, so leave.
741 np
->avl_balance
= AVL_BALANCE
;
745 if (growth
== AVL_BACK
) {
747 child
= np
->avl_back
;
748 CERT(np
->avl_balance
== AVL_BACK
&& child
);
750 if (child
->avl_balance
== AVL_BACK
) { /* single LL */
752 * ``A'' just got inserted;
753 * np points to ``E'', child to ``C'',
754 * and it is already AVL_BACK --
755 * child will get promoted to top of subtree.
765 Note that child->avl_parent and
766 avl_balance get set in common code.
768 np
->avl_parent
= child
;
769 np
->avl_balance
= AVL_BALANCE
;
770 np
->avl_back
= child
->avl_forw
;
772 child
->avl_forw
->avl_parent
= np
;
773 child
->avl_forw
= np
;
778 * child's avl_forw node gets promoted to
779 * the top of the subtree.
790 avl64node_t
*tmp
= child
->avl_forw
;
792 CERT(child
->avl_balance
== AVL_FORW
&& tmp
);
794 child
->avl_forw
= tmp
->avl_back
;
796 tmp
->avl_back
->avl_parent
= child
;
798 tmp
->avl_back
= child
;
799 child
->avl_parent
= tmp
;
801 np
->avl_back
= tmp
->avl_forw
;
803 tmp
->avl_forw
->avl_parent
= np
;
806 np
->avl_parent
= tmp
;
808 if (tmp
->avl_balance
== AVL_BACK
)
809 np
->avl_balance
= AVL_FORW
;
811 np
->avl_balance
= AVL_BALANCE
;
813 if (tmp
->avl_balance
== AVL_FORW
)
814 child
->avl_balance
= AVL_BACK
;
816 child
->avl_balance
= AVL_BALANCE
;
819 * Set child to point to tmp since it is
820 * now the top of the subtree, and will
821 * get attached to the subtree parent in
822 * the common code below.
827 } else /* growth == AVL_BACK */ {
830 * This code is the mirror image of AVL_FORW above.
833 child
= np
->avl_forw
;
834 CERT(np
->avl_balance
== AVL_FORW
&& child
);
836 if (child
->avl_balance
== AVL_FORW
) { /* single RR */
837 np
->avl_parent
= child
;
838 np
->avl_balance
= AVL_BALANCE
;
839 np
->avl_forw
= child
->avl_back
;
841 child
->avl_back
->avl_parent
= np
;
842 child
->avl_back
= np
;
847 avl64node_t
*tmp
= child
->avl_back
;
849 ASSERT(child
->avl_balance
== AVL_BACK
&& tmp
);
851 child
->avl_back
= tmp
->avl_forw
;
853 tmp
->avl_forw
->avl_parent
= child
;
855 tmp
->avl_forw
= child
;
856 child
->avl_parent
= tmp
;
858 np
->avl_forw
= tmp
->avl_back
;
860 tmp
->avl_back
->avl_parent
= np
;
863 np
->avl_parent
= tmp
;
865 if (tmp
->avl_balance
== AVL_FORW
)
866 np
->avl_balance
= AVL_BACK
;
868 np
->avl_balance
= AVL_BALANCE
;
870 if (tmp
->avl_balance
== AVL_BACK
)
871 child
->avl_balance
= AVL_FORW
;
873 child
->avl_balance
= AVL_BALANCE
;
879 child
->avl_parent
= parent
;
880 child
->avl_balance
= AVL_BALANCE
;
883 if (parent
->avl_back
== np
)
884 parent
->avl_back
= child
;
886 parent
->avl_forw
= child
;
888 ASSERT(*rootp
== np
);
898 avl64_insert_find_growth(
899 avl64tree_desc_t
*tree
,
900 uint64_t start
, /* range start at start, */
901 uint64_t end
, /* exclusive */
902 int *growthp
) /* OUT */
904 avl64node_t
*root
= tree
->avl_root
;
908 ASSERT(np
); /* caller ensures that there is atleast one node in tree */
911 CERT(np
->avl_parent
|| root
== np
);
912 CERT(!np
->avl_parent
|| root
!= np
);
913 CERT(!(np
->avl_back
) || np
->avl_back
->avl_parent
== np
);
914 CERT(!(np
->avl_forw
) || np
->avl_forw
->avl_parent
== np
);
915 CERT(np
->avl_balance
!= AVL_FORW
|| np
->avl_forw
);
916 CERT(np
->avl_balance
!= AVL_BACK
|| np
->avl_back
);
917 CERT(np
->avl_balance
!= AVL_BALANCE
||
918 np
->avl_back
== NULL
|| np
->avl_forw
);
919 CERT(np
->avl_balance
!= AVL_BALANCE
||
920 np
->avl_forw
== NULL
|| np
->avl_back
);
922 if (AVL_START(tree
, np
) >= end
) {
931 if (AVL_END(tree
, np
) <= start
) {
939 /* found exact match -- let caller decide if it is an error */
948 avl64tree_desc_t
*tree
,
950 avl64node_t
*newnode
,
954 uint64_t start
= AVL_START(tree
, newnode
);
956 if (growth
== AVL_BACK
) {
958 parent
->avl_back
= newnode
;
960 * we are growing to the left; previous in-order to newnode is
961 * closest ancestor with lesser value. Before this
962 * insertion, this ancestor will be pointing to
963 * newnode's parent. After insertion, next in-order to newnode
966 newnode
->avl_nextino
= parent
;
969 if (AVL_END(tree
, nnext
) <= start
)
971 nnext
= nnext
->avl_parent
;
975 * nnext will be null if newnode is
976 * the least element, and hence very first in the list.
978 ASSERT(nnext
->avl_nextino
== parent
);
979 nnext
->avl_nextino
= newnode
;
983 parent
->avl_forw
= newnode
;
984 newnode
->avl_nextino
= parent
->avl_nextino
;
985 parent
->avl_nextino
= newnode
;
992 avl64tree_desc_t
*tree
,
993 avl64node_t
*newnode
)
996 uint64_t start
= AVL_START(tree
, newnode
);
997 uint64_t end
= AVL_END(tree
, newnode
);
1002 * Clean all pointers for sanity; some will be reset as necessary.
1004 newnode
->avl_nextino
= NULL
;
1005 newnode
->avl_parent
= NULL
;
1006 newnode
->avl_forw
= NULL
;
1007 newnode
->avl_back
= NULL
;
1008 newnode
->avl_balance
= AVL_BALANCE
;
1010 if ((np
= tree
->avl_root
) == NULL
) { /* degenerate case... */
1011 tree
->avl_root
= newnode
;
1012 tree
->avl_firstino
= newnode
;
1016 if ((np
= avl64_insert_find_growth(tree
, start
, end
, &growth
))
1018 if (start
!= end
) { /* non-zero length range */
1020 _("avl_insert: Warning! duplicate range [%llu,%llu]\n"),
1021 (unsigned long long)start
,
1022 (unsigned long long)end
);
1027 avl64_insert_grow(tree
, np
, newnode
, growth
);
1028 if (growth
== AVL_BACK
) {
1030 * Growing to left. if np was firstino, newnode will be firstino
1032 if (tree
->avl_firstino
== np
)
1033 tree
->avl_firstino
= newnode
;
1037 if (growth
== AVL_FORW
)
1039 * Cannot possibly be firstino; there is somebody to our left.
1044 newnode
->avl_parent
= np
;
1045 CERT(np
->avl_forw
== newnode
|| np
->avl_back
== newnode
);
1047 avl64_balance(&tree
->avl_root
, np
, growth
);
1049 avl64_checktree(tree
, tree
->avl_root
);
1056 * avl64_insert_immediate(tree, afterp, newnode):
1057 * insert newnode immediately into tree immediately after afterp.
1058 * after insertion, newnode is right child of afterp.
1061 avl64_insert_immediate(
1062 avl64tree_desc_t
*tree
,
1063 avl64node_t
*afterp
,
1064 avl64node_t
*newnode
)
1067 * Clean all pointers for sanity; some will be reset as necessary.
1069 newnode
->avl_nextino
= NULL
;
1070 newnode
->avl_parent
= NULL
;
1071 newnode
->avl_forw
= NULL
;
1072 newnode
->avl_back
= NULL
;
1073 newnode
->avl_balance
= AVL_BALANCE
;
1075 if (afterp
== NULL
) {
1076 tree
->avl_root
= newnode
;
1077 tree
->avl_firstino
= newnode
;
1081 ASSERT(afterp
->avl_forw
== NULL
);
1082 avl64_insert_grow(tree
, afterp
, newnode
, AVL_FORW
); /* grow to right */
1083 CERT(afterp
->avl_forw
== newnode
);
1084 avl64_balance(&tree
->avl_root
, afterp
, AVL_FORW
);
1085 avl64_checktree(tree
, tree
->avl_root
);
1090 * Returns first in order node
1093 avl64_firstino(avl64node_t
*root
)
1097 if ((np
= root
) == NULL
)
1100 while (np
->avl_back
)
1106 * Returns last in order node
1109 avl64_lastino(avl64node_t
*root
)
1113 if ((np
= root
) == NULL
)
1116 while (np
->avl_forw
)
1122 avl64_init_tree(avl64tree_desc_t
*tree
, avl64ops_t
*ops
)
1124 tree
->avl_root
= NULL
;
1125 tree
->avl_firstino
= NULL
;
1126 tree
->avl_ops
= ops
;
1131 avl64_printnode(avl64tree_desc_t
*tree
, avl64node_t
*np
, int nl
)
1133 printf("[%d-%d]%c", AVL_START(tree
, np
),
1134 (AVL_END(tree
, np
) - 1), nl
? '\n' : ' ');
1137 #ifdef STAND_ALONE_DEBUG
1139 struct avl_debug_node
{
1140 avl64node_t avl_node
;
1141 xfs_off_t avl_start
;
1142 unsigned int avl_size
;
1145 avl64ops_t avl_debug_ops
= {
1151 avl64_debug_start(avl64node_t
*node
)
1153 return (uint64_t)(struct avl_debug_node
*)node
->avl_start
;
1157 avl64_debug_end(avl64node_t
*node
)
1160 ((struct avl_debug_node
*)node
->avl_start
+
1161 (struct avl_debug_node
*)node
->avl_size
);
1164 avl_debug_node freenodes
[100];
1165 avl_debug_node
*freehead
= &freenodes
[0];
1167 static avl64node_t
*
1168 alloc_avl64_debug_node()
1170 freehead
->avl_balance
= AVL_BALANCE
;
1171 freehead
->avl_parent
= freehead
->avl_forw
= freehead
->avl_back
= NULL
;
1176 avl64_print(avl64tree_desc_t
*tree
, avl64node_t
*root
, int depth
)
1183 avl64_print(tree
, root
->avl_forw
, depth
+5);
1184 for (i
= 0; i
< depth
; i
++)
1186 avl64_printnode(tree
, root
,1);
1188 avl64_print(tree
, root
->avl_back
, depth
+5);
1195 avl64tree_desc_t tree
;
1196 char linebuf
[256], cmd
[256];
1198 avl64_init_tree(&tree
, &avl_debug_ops
);
1200 for (i
= 100; i
> 0; i
= i
- 10)
1202 np
= alloc__debug_avlnode();
1206 avl64_insert(&tree
, np
);
1208 avl64_print(&tree
, tree
.avl_root
, 0);
1210 for (np
= tree
.avl_firstino
; np
!= NULL
; np
= np
->avl_nextino
)
1211 avl64_printnode(&tree
, np
, 0);
1215 printf(_("Command [fpdir] : "));
1216 fgets(linebuf
, 256, stdin
);
1217 if (feof(stdin
)) break;
1219 if (sscanf(linebuf
, "%[fpdir]%d", cmd
, &i
) != 2)
1224 printf(_("end of range ? "));
1225 fgets(linebuf
, 256, stdin
);
1228 if (i
== j
) j
= i
+1;
1229 np
= avl64_findinrange(&tree
,i
,j
);
1231 avl64_printnode(&tree
, np
, 1);
1233 avl64_delete(&tree
, np
);
1235 printf(_("Cannot find %d\n"), i
);
1238 avl64_print(&tree
, tree
.avl_root
, 0);
1239 for (np
= tree
.avl_firstino
;
1240 np
!= NULL
; np
= np
->avl_nextino
)
1241 avl64_printnode(&tree
, np
, 0);
1245 np
= alloc_avlnode();
1248 printf(_("size of range ? "));
1249 fgets(linebuf
, 256, stdin
);
1253 avl64_insert(&tree
, np
);
1256 avl64node_t
*b
, *e
, *t
;
1259 printf(_("End of range ? "));
1260 fgets(linebuf
, 256, stdin
);
1263 printf(_("checklen 0/1 ? "));
1264 fgets(linebuf
, 256, stdin
);
1265 checklen
= atoi(linebuf
);
1268 b
= avl64_findanyrange(&tree
, i
, j
, checklen
);
1270 printf(_("Found something\n"));
1274 AVL_START(&tree
, t
) >= j
)
1276 avl64_printnode(&tree
, t
, 0);
1288 * Given a tree, find value; will find return range enclosing value,
1289 * or range immediately succeeding value,
1290 * or range immediately preceeding value.
1294 avl64tree_desc_t
*tree
,
1298 avl64node_t
*np
= tree
->avl_root
;
1301 if (value
< AVL_START(tree
, np
)) {
1306 /* if we were to add node with value, would
1307 * have a growth of AVL_BACK
1309 if (dir
== AVL_SUCCEED
) {
1310 /* if succeeding node is needed, this is it.
1314 if (dir
== AVL_PRECEED
) {
1316 * find nearest ancestor with lesser value.
1318 np
= np
->avl_parent
;
1320 if (AVL_END(tree
, np
) <= value
)
1322 np
= np
->avl_parent
;
1326 ASSERT(dir
== AVL_SUCCEED
|| dir
== AVL_PRECEED
);
1329 if (value
>= AVL_END(tree
, np
)) {
1334 /* if we were to add node with value, would
1335 * have a growth of AVL_FORW;
1337 if (dir
== AVL_SUCCEED
) {
1338 /* we are looking for a succeeding node;
1341 return(np
->avl_nextino
);
1343 if (dir
== AVL_PRECEED
) {
1344 /* looking for a preceeding node; this is it. */
1347 ASSERT(dir
== AVL_SUCCEED
|| dir
== AVL_PRECEED
);
1349 /* AVL_START(tree, np) <= value < AVL_END(tree, np) */
1359 * Given range r [start, end), find all ranges in tree which are contained
1360 * in r. At return, startp and endp point to first and last of
1361 * a chain of elements which describe the contained ranges. Elements
1362 * in startp ... endp are in sort order, and can be accessed by
1363 * using avl_nextino.
1368 avl64tree_desc_t
*tree
,
1371 avl64node_t
**startp
,
1376 np
= avl64_findadjacent(tree
, start
, AVL_SUCCEED
);
1377 if (np
== NULL
/* nothing succeding start */
1378 || (np
&& (end
<= AVL_START(tree
, np
))))
1379 /* something follows start,
1380 but... is entirely after end */
1389 /* see if end is in this region itself */
1390 if (end
<= AVL_END(tree
, np
) ||
1391 np
->avl_nextino
== NULL
||
1393 (end
<= AVL_START(tree
, np
->avl_nextino
)))) {
1397 /* have to munge for end */
1399 * note: have to look for (end - 1), since
1400 * findadjacent will look for exact value, and does not
1401 * care about the fact that end is actually one more
1402 * than the value actually being looked for; thus feed it one less.
1404 *endp
= avl64_findadjacent(tree
, (end
-1), AVL_PRECEED
);