]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - repair/avl.c
2 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
28 register avltree_desc_t
*tree
,
29 register avlnode_t
*np
)
31 register avlnode_t
*back
= np
->avl_back
;
32 register avlnode_t
*forw
= np
->avl_forw
;
33 register avlnode_t
*nextino
= np
->avl_nextino
;
34 register int bal
= np
->avl_balance
;
36 ASSERT(bal
!= AVL_BALANCE
|| (!back
&& !forw
) || (back
&& forw
));
37 ASSERT(bal
!= AVL_FORW
|| forw
);
38 ASSERT(bal
!= AVL_BACK
|| back
);
41 ASSERT(AVL_START(tree
, np
) < AVL_START(tree
, forw
));
42 ASSERT(np
->avl_forw
->avl_parent
== np
);
43 ASSERT(back
|| bal
== AVL_FORW
);
45 ASSERT(bal
!= AVL_FORW
);
46 ASSERT(bal
== AVL_BALANCE
|| back
);
47 ASSERT(bal
== AVL_BACK
|| !back
);
51 ASSERT(AVL_START(tree
, np
) > AVL_START(tree
, back
));
52 ASSERT(np
->avl_back
->avl_parent
== np
);
53 ASSERT(forw
|| bal
== AVL_BACK
);
55 ASSERT(bal
!= AVL_BACK
);
56 ASSERT(bal
== AVL_BALANCE
|| forw
);
57 ASSERT(bal
== AVL_FORW
|| !forw
);
63 ASSERT(AVL_END(tree
, np
) <= AVL_START(tree
, nextino
));
68 register avltree_desc_t
*tree
,
69 register avlnode_t
*root
)
71 register avlnode_t
*nlast
, *nnext
, *np
;
72 __psunsigned_t offset
= 0;
77 ASSERT(!nnext
|| nnext
->avl_parent
== NULL
);
81 avl_checknode(tree
, nnext
);
82 end
= AVL_END(tree
, nnext
);
85 if ((np
= nnext
->avl_forw
) && np
!= nlast
) {
90 nnext
= nnext
->avl_parent
;
96 if (np
= nnext
->avl_back
) {
97 if (AVL_END(tree
, np
) > offset
) {
104 nnext
= nnext
->avl_forw
;
106 nnext
= np
->avl_parent
;
111 #else /* ! AVL_DEBUG */
112 #define avl_checktree(t,x)
113 #endif /* AVL_DEBUG */
117 * Reset balance for np up through tree.
118 * ``direction'' is the way that np's balance
119 * is headed after the deletion of one of its children --
120 * e.g., deleting a avl_forw child sends avl_balance toward AVL_BACK.
121 * Called only when deleting a node from the tree.
125 avltree_desc_t
*tree
,
126 register avlnode_t
*np
,
127 register int direction
)
129 register avlnode_t
**rootp
= &tree
->avl_root
;
130 register avlnode_t
*parent
;
131 register avlnode_t
*child
;
132 register avlnode_t
*tmp
;
136 ASSERT(direction
== AVL_BACK
|| direction
== AVL_FORW
);
138 if (np
->avl_balance
== AVL_BALANCE
) {
139 np
->avl_balance
= direction
;
143 parent
= np
->avl_parent
;
146 * If balance is being restored, no local node
147 * reorganization is necessary, but may be at
148 * a higher node. Reset direction and continue.
150 if (direction
!= np
->avl_balance
) {
151 np
->avl_balance
= AVL_BALANCE
;
153 if (parent
->avl_forw
== np
)
154 direction
= AVL_BACK
;
156 direction
= AVL_FORW
;
165 * Imbalance. If a avl_forw node was removed, direction
166 * (and, by reduction, np->avl_balance) is/was AVL_BACK.
168 if (np
->avl_balance
== AVL_BACK
) {
170 ASSERT(direction
== AVL_BACK
);
171 child
= np
->avl_back
;
172 bal
= child
->avl_balance
;
174 if (bal
!= AVL_FORW
) /* single LL */ {
176 * np gets pushed down to lesser child's
181 * child-> B deleted A -D
186 if (!(tree
->avl_flags
& AVLF_DUPLICITY
))
187 cmn_err(CE_CONT
, "!LL delete b 0x%x c 0x%x\n",
190 np
->avl_back
= child
->avl_forw
;
192 child
->avl_forw
->avl_parent
= np
;
193 child
->avl_forw
= np
;
196 if (parent
->avl_forw
== np
) {
197 parent
->avl_forw
= child
;
198 direction
= AVL_BACK
;
200 ASSERT(parent
->avl_back
== np
);
201 parent
->avl_back
= child
;
202 direction
= AVL_FORW
;
205 ASSERT(*rootp
== np
);
208 np
->avl_parent
= child
;
209 child
->avl_parent
= parent
;
211 if (bal
== AVL_BALANCE
) {
212 np
->avl_balance
= AVL_BACK
;
213 child
->avl_balance
= AVL_FORW
;
216 np
->avl_balance
= AVL_BALANCE
;
217 child
->avl_balance
= AVL_BALANCE
;
219 avl_checktree(tree
, *rootp
);
224 /* child->avl_balance == AVL_FORW double LR rotation
226 * child's avl_forw node gets promoted up, along with
227 * its avl_forw subtree
238 if (!(tree
->avl_flags
& AVLF_DUPLICITY
))
239 cmn_err(CE_CONT
, "!LR delete b 0x%x c 0x%x t 0x%x\n",
240 np
, child
, child
->avl_forw
);
242 tmp
= child
->avl_forw
;
243 bal
= tmp
->avl_balance
;
245 child
->avl_forw
= tmp
->avl_back
;
247 tmp
->avl_back
->avl_parent
= child
;
249 tmp
->avl_back
= child
;
250 child
->avl_parent
= tmp
;
252 np
->avl_back
= tmp
->avl_forw
;
254 tmp
->avl_forw
->avl_parent
= np
;
258 child
->avl_balance
= AVL_BACK
;
260 child
->avl_balance
= AVL_BALANCE
;
263 np
->avl_balance
= AVL_FORW
;
265 np
->avl_balance
= AVL_BALANCE
;
270 ASSERT(np
->avl_balance
== AVL_FORW
&& direction
== AVL_FORW
);
272 child
= np
->avl_forw
;
273 bal
= child
->avl_balance
;
275 if (bal
!= AVL_BACK
) /* single RR */ {
277 * np gets pushed down to greater child's
282 * deleted D <-child +B E
287 if (!(tree
->avl_flags
& AVLF_DUPLICITY
))
288 cmn_err(CE_CONT
, "!RR delete b 0x%x c 0x%x\n",
291 np
->avl_forw
= child
->avl_back
;
293 child
->avl_back
->avl_parent
= np
;
294 child
->avl_back
= np
;
297 if (parent
->avl_forw
== np
) {
298 parent
->avl_forw
= child
;
299 direction
= AVL_BACK
;
301 ASSERT(parent
->avl_back
== np
);
302 parent
->avl_back
= child
;
303 direction
= AVL_FORW
;
306 ASSERT(*rootp
== np
);
309 np
->avl_parent
= child
;
310 child
->avl_parent
= parent
;
312 if (bal
== AVL_BALANCE
) {
313 np
->avl_balance
= AVL_FORW
;
314 child
->avl_balance
= AVL_BACK
;
317 np
->avl_balance
= AVL_BALANCE
;
318 child
->avl_balance
= AVL_BALANCE
;
320 avl_checktree(tree
, *rootp
);
325 /* child->avl_balance == AVL_BACK double RL rotation */
327 if (!(tree
->avl_flags
& AVLF_DUPLICITY
))
328 cmn_err(CE_CONT
, "!RL delete b 0x%x c 0x%x t 0x%x\n",
329 np
, child
, child
->avl_back
);
331 tmp
= child
->avl_back
;
332 bal
= tmp
->avl_balance
;
334 child
->avl_back
= tmp
->avl_forw
;
336 tmp
->avl_forw
->avl_parent
= child
;
338 tmp
->avl_forw
= child
;
339 child
->avl_parent
= tmp
;
341 np
->avl_forw
= tmp
->avl_back
;
343 tmp
->avl_back
->avl_parent
= np
;
347 child
->avl_balance
= AVL_FORW
;
349 child
->avl_balance
= AVL_BALANCE
;
352 np
->avl_balance
= AVL_BACK
;
354 np
->avl_balance
= AVL_BALANCE
;
356 np
->avl_parent
= tmp
;
357 tmp
->avl_balance
= AVL_BALANCE
;
358 tmp
->avl_parent
= parent
;
361 if (parent
->avl_forw
== np
) {
362 parent
->avl_forw
= tmp
;
363 direction
= AVL_BACK
;
365 ASSERT(parent
->avl_back
== np
);
366 parent
->avl_back
= tmp
;
367 direction
= AVL_FORW
;
370 ASSERT(*rootp
== np
);
376 avl_checktree(tree
, *rootp
);
381 * Remove node from tree.
382 * avl_delete does the local tree manipulations,
383 * calls retreat() to rebalance tree up to its root.
387 register avltree_desc_t
*tree
,
388 register avlnode_t
*np
)
390 register avlnode_t
*forw
= np
->avl_forw
;
391 register avlnode_t
*back
= np
->avl_back
;
392 register avlnode_t
*parent
= np
->avl_parent
;
393 register avlnode_t
*nnext
;
398 * a left child exits, then greatest left descendent's nextino
399 * is pointing to np; make it point to np->nextino.
401 nnext
= np
->avl_back
;
403 if (!nnext
->avl_forw
)
404 break; /* can't find anything bigger */
405 nnext
= nnext
->avl_forw
;
408 if (np
->avl_parent
) {
410 * find nearest ancestor with lesser value. That ancestor's
411 * nextino is pointing to np; make it point to np->nextino
413 nnext
= np
->avl_parent
;
415 if (AVL_END(tree
, nnext
) <= AVL_END(tree
, np
))
417 nnext
= nnext
->avl_parent
;
423 ASSERT(nnext
->avl_nextino
== np
);
424 nnext
->avl_nextino
= np
->avl_nextino
;
426 * Something preceeds np; np cannot be firstino.
428 ASSERT(tree
->avl_firstino
!= np
);
432 * Nothing preceeding np; after deletion, np's nextino
433 * is firstino of tree.
435 ASSERT(tree
->avl_firstino
== np
);
436 tree
->avl_firstino
= np
->avl_nextino
;
441 * Degenerate cases...
451 forw
->avl_parent
= parent
;
453 if (parent
->avl_forw
== np
) {
454 parent
->avl_forw
= forw
;
455 retreat(tree
, parent
, AVL_BACK
);
457 ASSERT(parent
->avl_back
== np
);
458 parent
->avl_back
= forw
;
459 retreat(tree
, parent
, AVL_FORW
);
462 ASSERT(tree
->avl_root
== np
);
463 tree
->avl_root
= forw
;
465 avl_checktree(tree
, tree
->avl_root
);
470 * Harder case: children on both sides.
471 * If back's avl_forw pointer is null, just have back
472 * inherit np's avl_forw tree, remove np from the tree
473 * and adjust balance counters starting at back.
475 * np-> xI xH (befor retreat())
483 if ((forw
= back
->avl_forw
) == NULL
) {
485 * AVL_FORW retreat below will set back's
486 * balance to AVL_BACK.
488 back
->avl_balance
= np
->avl_balance
;
489 back
->avl_forw
= forw
= np
->avl_forw
;
490 forw
->avl_parent
= back
;
491 back
->avl_parent
= parent
;
494 if (parent
->avl_forw
== np
)
495 parent
->avl_forw
= back
;
497 ASSERT(parent
->avl_back
== np
);
498 parent
->avl_back
= back
;
501 ASSERT(tree
->avl_root
== np
);
502 tree
->avl_root
= back
;
506 * back is taking np's place in the tree, and
507 * has therefore lost a avl_back node (itself).
509 retreat(tree
, back
, AVL_FORW
);
510 avl_checktree(tree
, tree
->avl_root
);
515 * Hardest case: children on both sides, and back's
516 * avl_forw pointer isn't null. Find the immediately
517 * inferior buffer by following back's avl_forw line
518 * to the end, then have it inherit np's avl_forw tree.
522 * G J back-> G J (before retreat())
530 while ((back
= forw
->avl_forw
))
534 * Will be adjusted by retreat() below.
536 forw
->avl_balance
= np
->avl_balance
;
539 * forw inherits np's avl_forw...
541 forw
->avl_forw
= np
->avl_forw
;
542 np
->avl_forw
->avl_parent
= forw
;
545 * ... forw's parent gets forw's avl_back...
547 back
= forw
->avl_parent
;
548 back
->avl_forw
= forw
->avl_back
;
550 forw
->avl_back
->avl_parent
= back
;
553 * ... forw gets np's avl_back...
555 forw
->avl_back
= np
->avl_back
;
556 np
->avl_back
->avl_parent
= forw
;
559 * ... and forw gets np's parent.
561 forw
->avl_parent
= parent
;
564 if (parent
->avl_forw
== np
)
565 parent
->avl_forw
= forw
;
567 parent
->avl_back
= forw
;
569 ASSERT(tree
->avl_root
== np
);
570 tree
->avl_root
= forw
;
574 * What used to be forw's parent is the starting
575 * point for rebalancing. It has lost a avl_forw node.
577 retreat(tree
, back
, AVL_BACK
);
578 avl_checktree(tree
, tree
->avl_root
);
585 * Given range r [start, end), find any range which is contained in r.
586 * if checklen is non-zero, then only ranges of non-zero length are
587 * considered in finding a match.
591 register avltree_desc_t
*tree
,
592 register __psunsigned_t start
,
593 register __psunsigned_t end
,
596 register avlnode_t
*np
= tree
->avl_root
;
598 /* np = avl_findadjacent(tree, start, AVL_SUCCEED); */
600 if (start
< AVL_START(tree
, np
)) {
605 /* if we were to add node with start, would
606 * have a growth of AVL_BACK
608 /* if succeeding node is needed, this is it.
612 if (start
>= AVL_END(tree
, np
)) {
617 /* if we were to add node with start, would
618 * have a growth of AVL_FORW;
620 /* we are looking for a succeeding node;
623 np
= np
->avl_nextino
;
626 /* AVL_START(tree, np) <= start < AVL_END(tree, np) */
630 if (checklen
== AVL_INCLUDE_ZEROLEN
) {
631 if (end
<= AVL_START(tree
, np
)) {
632 /* something follows start, but is
633 * is entierly after the range (end)
637 /* np may stradle [start, end) */
641 * find non-zero length region
643 while (np
&& (AVL_END(tree
, np
) - AVL_START(tree
, np
) == 0)
644 && (AVL_START(tree
, np
) < end
))
645 np
= np
->avl_nextino
;
647 if ((np
== NULL
) || (AVL_START(tree
, np
) >= end
))
652 * nothing succeeds start, all existing ranges are before start.
658 * Returns a pointer to node which contains exact value.
662 register avltree_desc_t
*tree
,
663 register __psunsigned_t value
)
665 register avlnode_t
*np
= tree
->avl_root
;
666 register __psunsigned_t nvalue
;
669 nvalue
= AVL_START(tree
, np
);
670 if (value
< nvalue
) {
674 if (value
== nvalue
) {
684 * Balance buffer AVL tree after attaching a new node to root.
685 * Called only by avl_insert.
689 register avlnode_t
**rootp
,
690 register avlnode_t
*np
,
694 * At this point, np points to the node to which
695 * a new node has been attached. All that remains is to
696 * propagate avl_balance up the tree.
699 register avlnode_t
*parent
= np
->avl_parent
;
700 register avlnode_t
*child
;
702 CERT(growth
== AVL_BACK
|| growth
== AVL_FORW
);
705 * If the buffer was already balanced, set avl_balance
706 * to the new direction. Continue if there is a
707 * parent after setting growth to reflect np's
708 * relation to its parent.
710 if (np
->avl_balance
== AVL_BALANCE
) {
711 np
->avl_balance
= growth
;
713 if (parent
->avl_forw
== np
)
716 ASSERT(parent
->avl_back
== np
);
726 if (growth
!= np
->avl_balance
) {
728 * Subtree is now balanced -- no net effect
729 * in the size of the subtree, so leave.
731 np
->avl_balance
= AVL_BALANCE
;
735 if (growth
== AVL_BACK
) {
737 child
= np
->avl_back
;
738 CERT(np
->avl_balance
== AVL_BACK
&& child
);
740 if (child
->avl_balance
== AVL_BACK
) { /* single LL */
742 * ``A'' just got inserted;
743 * np points to ``E'', child to ``C'',
744 * and it is already AVL_BACK --
745 * child will get promoted to top of subtree.
755 Note that child->avl_parent and
756 avl_balance get set in common code.
758 np
->avl_parent
= child
;
759 np
->avl_balance
= AVL_BALANCE
;
760 np
->avl_back
= child
->avl_forw
;
762 child
->avl_forw
->avl_parent
= np
;
763 child
->avl_forw
= np
;
768 * child's avl_forw node gets promoted to
769 * the top of the subtree.
780 register avlnode_t
*tmp
= child
->avl_forw
;
782 CERT(child
->avl_balance
== AVL_FORW
&& tmp
);
784 child
->avl_forw
= tmp
->avl_back
;
786 tmp
->avl_back
->avl_parent
= child
;
788 tmp
->avl_back
= child
;
789 child
->avl_parent
= tmp
;
791 np
->avl_back
= tmp
->avl_forw
;
793 tmp
->avl_forw
->avl_parent
= np
;
796 np
->avl_parent
= tmp
;
798 if (tmp
->avl_balance
== AVL_BACK
)
799 np
->avl_balance
= AVL_FORW
;
801 np
->avl_balance
= AVL_BALANCE
;
803 if (tmp
->avl_balance
== AVL_FORW
)
804 child
->avl_balance
= AVL_BACK
;
806 child
->avl_balance
= AVL_BALANCE
;
809 * Set child to point to tmp since it is
810 * now the top of the subtree, and will
811 * get attached to the subtree parent in
812 * the common code below.
817 } else /* growth == AVL_BACK */ {
820 * This code is the mirror image of AVL_FORW above.
823 child
= np
->avl_forw
;
824 CERT(np
->avl_balance
== AVL_FORW
&& child
);
826 if (child
->avl_balance
== AVL_FORW
) { /* single RR */
827 np
->avl_parent
= child
;
828 np
->avl_balance
= AVL_BALANCE
;
829 np
->avl_forw
= child
->avl_back
;
831 child
->avl_back
->avl_parent
= np
;
832 child
->avl_back
= np
;
837 register avlnode_t
*tmp
= child
->avl_back
;
839 ASSERT(child
->avl_balance
== AVL_BACK
&& tmp
);
841 child
->avl_back
= tmp
->avl_forw
;
843 tmp
->avl_forw
->avl_parent
= child
;
845 tmp
->avl_forw
= child
;
846 child
->avl_parent
= tmp
;
848 np
->avl_forw
= tmp
->avl_back
;
850 tmp
->avl_back
->avl_parent
= np
;
853 np
->avl_parent
= tmp
;
855 if (tmp
->avl_balance
== AVL_FORW
)
856 np
->avl_balance
= AVL_BACK
;
858 np
->avl_balance
= AVL_BALANCE
;
860 if (tmp
->avl_balance
== AVL_BACK
)
861 child
->avl_balance
= AVL_FORW
;
863 child
->avl_balance
= AVL_BALANCE
;
869 child
->avl_parent
= parent
;
870 child
->avl_balance
= AVL_BALANCE
;
873 if (parent
->avl_back
== np
)
874 parent
->avl_back
= child
;
876 parent
->avl_forw
= child
;
878 ASSERT(*rootp
== np
);
888 avl_insert_find_growth(
889 register avltree_desc_t
*tree
,
890 register __psunsigned_t start
, /* range start at start, */
891 register __psunsigned_t end
, /* exclusive */
892 register int *growthp
) /* OUT */
894 avlnode_t
*root
= tree
->avl_root
;
895 register avlnode_t
*np
;
898 ASSERT(np
); /* caller ensures that there is atleast one node in tree */
901 CERT(np
->avl_parent
|| root
== np
);
902 CERT(!np
->avl_parent
|| root
!= np
);
903 CERT(!(np
->avl_back
) || np
->avl_back
->avl_parent
== np
);
904 CERT(!(np
->avl_forw
) || np
->avl_forw
->avl_parent
== np
);
905 CERT(np
->avl_balance
!= AVL_FORW
|| np
->avl_forw
);
906 CERT(np
->avl_balance
!= AVL_BACK
|| np
->avl_back
);
907 CERT(np
->avl_balance
!= AVL_BALANCE
||
908 np
->avl_back
== NULL
|| np
->avl_forw
);
909 CERT(np
->avl_balance
!= AVL_BALANCE
||
910 np
->avl_forw
== NULL
|| np
->avl_back
);
912 if (AVL_START(tree
, np
) >= end
) {
921 if (AVL_END(tree
, np
) <= start
) {
929 /* found exact match -- let caller decide if it is an error */
938 register avltree_desc_t
*tree
,
939 register avlnode_t
*parent
,
940 register avlnode_t
*newnode
,
943 register avlnode_t
*nnext
;
944 register __psunsigned_t start
= AVL_START(tree
, newnode
);
946 if (growth
== AVL_BACK
) {
948 parent
->avl_back
= newnode
;
950 * we are growing to the left; previous in-order to newnode is
951 * closest ancestor with lesser value. Before this
952 * insertion, this ancestor will be pointing to
953 * newnode's parent. After insertion, next in-order to newnode
956 newnode
->avl_nextino
= parent
;
959 if (AVL_END(tree
, nnext
) <= start
)
961 nnext
= nnext
->avl_parent
;
965 * nnext will be null if newnode is
966 * the least element, and hence very first in the list.
968 ASSERT(nnext
->avl_nextino
== parent
);
969 nnext
->avl_nextino
= newnode
;
973 parent
->avl_forw
= newnode
;
974 newnode
->avl_nextino
= parent
->avl_nextino
;
975 parent
->avl_nextino
= newnode
;
982 register avltree_desc_t
*tree
,
983 register avlnode_t
*newnode
)
985 register avlnode_t
*np
;
986 register __psunsigned_t start
= AVL_START(tree
, newnode
);
987 register __psunsigned_t end
= AVL_END(tree
, newnode
);
991 ASSERT(start
<= end
);
994 * Clean all pointers for sanity; some will be reset as necessary.
996 newnode
->avl_nextino
= NULL
;
997 newnode
->avl_parent
= NULL
;
998 newnode
->avl_forw
= NULL
;
999 newnode
->avl_back
= NULL
;
1000 newnode
->avl_balance
= AVL_BALANCE
;
1002 if ((np
= tree
->avl_root
) == NULL
) { /* degenerate case... */
1003 tree
->avl_root
= newnode
;
1004 tree
->avl_firstino
= newnode
;
1008 if ((np
= avl_insert_find_growth(tree
, start
, end
, &growth
)) == NULL
) {
1009 if (start
!= end
) { /* non-zero length range */
1011 _("avl_insert: Warning! duplicate range [%llu,%llu]\n"),
1012 (unsigned long long)start
,
1013 (unsigned long long)end
);
1018 avl_insert_grow(tree
, np
, newnode
, growth
);
1019 if (growth
== AVL_BACK
) {
1021 * Growing to left. if np was firstino, newnode will be firstino
1023 if (tree
->avl_firstino
== np
)
1024 tree
->avl_firstino
= newnode
;
1028 if (growth
== AVL_FORW
)
1030 * Cannot possibly be firstino; there is somebody to our left.
1035 newnode
->avl_parent
= np
;
1036 CERT(np
->avl_forw
== newnode
|| np
->avl_back
== newnode
);
1038 avl_balance(&tree
->avl_root
, np
, growth
);
1040 avl_checktree(tree
, tree
->avl_root
);
1047 * avl_insert_immediate(tree, afterp, newnode):
1048 * insert newnode immediately into tree immediately after afterp.
1049 * after insertion, newnode is right child of afterp.
1052 avl_insert_immediate(
1053 avltree_desc_t
*tree
,
1058 * Clean all pointers for sanity; some will be reset as necessary.
1060 newnode
->avl_nextino
= NULL
;
1061 newnode
->avl_parent
= NULL
;
1062 newnode
->avl_forw
= NULL
;
1063 newnode
->avl_back
= NULL
;
1064 newnode
->avl_balance
= AVL_BALANCE
;
1066 if (afterp
== NULL
) {
1067 tree
->avl_root
= newnode
;
1068 tree
->avl_firstino
= newnode
;
1072 ASSERT(afterp
->avl_forw
== NULL
);
1073 avl_insert_grow(tree
, afterp
, newnode
, AVL_FORW
); /* grow to right */
1074 CERT(afterp
->avl_forw
== newnode
);
1075 avl_balance(&tree
->avl_root
, afterp
, AVL_FORW
);
1076 avl_checktree(tree
, tree
->avl_root
);
1081 * Returns first in order node
1084 avl_firstino(register avlnode_t
*root
)
1086 register avlnode_t
*np
;
1088 if ((np
= root
) == NULL
)
1091 while (np
->avl_back
)
1097 * Returns last in order node
1100 avl_lastino(register avlnode_t
*root
)
1102 register avlnode_t
*np
;
1104 if ((np
= root
) == NULL
)
1107 while (np
->avl_forw
)
1113 avl_init_tree(avltree_desc_t
*tree
, avlops_t
*ops
)
1115 tree
->avl_root
= NULL
;
1116 tree
->avl_firstino
= NULL
;
1117 tree
->avl_ops
= ops
;
1122 avl_printnode(avltree_desc_t
*tree
, avlnode_t
*np
, int nl
)
1124 printf("[%d-%d]%c", AVL_START(tree
, np
),
1125 (AVL_END(tree
, np
) - 1), nl
? '\n' : ' ');
1128 #ifdef STAND_ALONE_DEBUG
1130 struct avl_debug_node
{
1132 xfs_off_t avl_start
;
1133 unsigned int avl_size
;
1136 avlops_t avl_debug_ops
= {
1141 static __psunsigned_t
1142 avl_debug_start(avlnode_t
*node
)
1144 return (__psunsigned_t
)(struct avl_debug_node
*)node
->avl_start
;
1147 static __psunsigned_t
1148 avl_debug_end(avlnode_t
*node
)
1150 return (__psunsigned_t
)
1151 ((struct avl_debug_node
*)node
->avl_start
+
1152 (struct avl_debug_node
*)node
->avl_size
);
1155 avl_debug_node freenodes
[100];
1156 avl_debug_node
*freehead
= &freenodes
[0];
1159 alloc_avl_debug_node()
1161 freehead
->avl_balance
= AVL_BALANCE
;
1162 freehead
->avl_parent
= freehead
->avl_forw
= freehead
->avl_back
= NULL
;
1167 avl_print(avltree_desc_t
*tree
, avlnode_t
*root
, int depth
)
1174 avl_print(tree
, root
->avl_forw
, depth
+5);
1175 for (i
= 0; i
< depth
; i
++)
1177 avl_printnode(tree
, root
,1);
1179 avl_print(tree
, root
->avl_back
, depth
+5);
1186 avltree_desc_t tree
;
1187 char linebuf
[256], cmd
[256];
1189 avl_init_tree(&tree
, &avl_debug_ops
);
1191 for (i
= 100; i
> 0; i
= i
- 10)
1193 np
= alloc__debug_avlnode();
1197 avl_insert(&tree
, np
);
1199 avl_print(&tree
, tree
.avl_root
, 0);
1201 for (np
= tree
.avl_firstino
; np
!= NULL
; np
= np
->avl_nextino
)
1202 avl_printnode(&tree
, np
, 0);
1206 printf(_("Command [fpdir] : "));
1207 fgets(linebuf
, 256, stdin
);
1208 if (feof(stdin
)) break;
1210 if (sscanf(linebuf
, "%[fpdir]%d", cmd
, &i
) != 2)
1215 printf(_("end of range ? "));
1216 fgets(linebuf
, 256, stdin
);
1219 if (i
== j
) j
= i
+1;
1220 np
= avl_findinrange(&tree
,i
,j
);
1222 avl_printnode(&tree
, np
, 1);
1224 avl_delete(&tree
, np
);
1226 printf(_("Cannot find %d\n"), i
);
1229 avl_print(&tree
, tree
.avl_root
, 0);
1230 for (np
= tree
.avl_firstino
;
1231 np
!= NULL
; np
= np
->avl_nextino
)
1232 avl_printnode(&tree
, np
, 0);
1236 np
= alloc_avlnode();
1239 printf(_("size of range ? "));
1240 fgets(linebuf
, 256, stdin
);
1244 avl_insert(&tree
, np
);
1247 avlnode_t
*b
, *e
, *t
;
1250 printf(_("End of range ? "));
1251 fgets(linebuf
, 256, stdin
);
1254 printf(_("checklen 0/1 ? "));
1255 fgets(linebuf
, 256, stdin
);
1256 checklen
= atoi(linebuf
);
1259 b
= avl_findanyrange(&tree
, i
, j
, checklen
);
1261 printf(_("Found something\n"));
1265 AVL_START(&tree
, t
) >= j
)
1267 avl_printnode(&tree
, t
, 0);
1279 * Given a tree, find value; will find return range enclosing value,
1280 * or range immediately succeeding value,
1281 * or range immediately preceeding value.
1285 register avltree_desc_t
*tree
,
1286 register __psunsigned_t value
,
1289 register avlnode_t
*np
= tree
->avl_root
;
1292 if (value
< AVL_START(tree
, np
)) {
1297 /* if we were to add node with value, would
1298 * have a growth of AVL_BACK
1300 if (dir
== AVL_SUCCEED
) {
1301 /* if succeeding node is needed, this is it.
1305 if (dir
== AVL_PRECEED
) {
1307 * find nearest ancestor with lesser value.
1309 np
= np
->avl_parent
;
1311 if (AVL_END(tree
, np
) <= value
)
1313 np
= np
->avl_parent
;
1317 ASSERT(dir
== AVL_SUCCEED
|| dir
== AVL_PRECEED
);
1320 if (value
>= AVL_END(tree
, np
)) {
1325 /* if we were to add node with value, would
1326 * have a growth of AVL_FORW;
1328 if (dir
== AVL_SUCCEED
) {
1329 /* we are looking for a succeeding node;
1332 return(np
->avl_nextino
);
1334 if (dir
== AVL_PRECEED
) {
1335 /* looking for a preceeding node; this is it. */
1338 ASSERT(dir
== AVL_SUCCEED
|| dir
== AVL_PRECEED
);
1340 /* AVL_START(tree, np) <= value < AVL_END(tree, np) */
1350 * Given range r [start, end), find all ranges in tree which are contained
1351 * in r. At return, startp and endp point to first and last of
1352 * a chain of elements which describe the contained ranges. Elements
1353 * in startp ... endp are in sort order, and can be accessed by
1354 * using avl_nextino.
1359 register avltree_desc_t
*tree
,
1360 register __psunsigned_t start
,
1361 register __psunsigned_t end
,
1365 register avlnode_t
*np
;
1367 np
= avl_findadjacent(tree
, start
, AVL_SUCCEED
);
1368 if (np
== NULL
/* nothing succeding start */
1369 || (np
&& (end
<= AVL_START(tree
, np
))))
1370 /* something follows start,
1371 but... is entirely after end */
1380 /* see if end is in this region itself */
1381 if (end
<= AVL_END(tree
, np
) ||
1382 np
->avl_nextino
== NULL
||
1384 (end
<= AVL_START(tree
, np
->avl_nextino
)))) {
1388 /* have to munge for end */
1390 * note: have to look for (end - 1), since
1391 * findadjacent will look for exact value, and does not
1392 * care about the fact that end is actually one more
1393 * than the value actually being looked for; thus feed it one less.
1395 *endp
= avl_findadjacent(tree
, (end
-1), AVL_PRECEED
);