]> git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - repair/avl.c
projects / thirdparty / xfsprogs-dev.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Merge whitespace changes over
[thirdparty/xfsprogs-dev.git] / repair / avl.c
1 /**************************************************************************
2 * *
3 * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of version 2 of the GNU General Public License as
7 * published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it would be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 *
13 * Further, this software is distributed without any warranty that it is
14 * free of the rightful claim of any third person regarding infringement
15 * or the like. Any license provided herein, whether implied or
16 * otherwise, applies only to this software file. Patent licenses, if
17 * any, provided herein do not apply to combinations of this program with
18 * other software, or any other product whatsoever.
19 *
20 * You should have received a copy of the GNU General Public License along
21 * with this program; if not, write the Free Software Foundation, Inc., 59
22 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 *
24 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
25 * Mountain View, CA 94043, or:
26 *
27 * http://www.sgi.com
28 *
29 * For further information regarding this notice, see:
30 *
31 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
32 * *
33 **************************************************************************/
34
35 #include <libxfs.h>
36
37 #include "avl.h"
38
39 #define CERT ASSERT
40
41 #ifdef AVL_DEBUG
42
43 static void
44 avl_checknode(
45 register avltree_desc_t *tree,
46 register avlnode_t *np)
47 {
48 register avlnode_t *back = np->avl_back;
49 register avlnode_t *forw = np->avl_forw;
50 register avlnode_t *nextino = np->avl_nextino;
51 register int bal = np->avl_balance;
52
53 ASSERT(bal != AVL_BALANCE || (!back && !forw) || (back && forw));
54 ASSERT(bal != AVL_FORW || forw);
55 ASSERT(bal != AVL_BACK || back);
56
57 if (forw) {
58 ASSERT(AVL_START(tree, np) < AVL_START(tree, forw));
59 ASSERT(np->avl_forw->avl_parent == np);
60 ASSERT(back || bal == AVL_FORW);
61 } else {
62 ASSERT(bal != AVL_FORW);
63 ASSERT(bal == AVL_BALANCE || back);
64 ASSERT(bal == AVL_BACK || !back);
65 }
66
67 if (back) {
68 ASSERT(AVL_START(tree, np) > AVL_START(tree, back));
69 ASSERT(np->avl_back->avl_parent == np);
70 ASSERT(forw || bal == AVL_BACK);
71 } else {
72 ASSERT(bal != AVL_BACK);
73 ASSERT(bal == AVL_BALANCE || forw);
74 ASSERT(bal == AVL_FORW || !forw);
75 }
76
77 if (nextino == NULL)
78 ASSERT(forw == NULL);
79 else
80 ASSERT(AVL_END(tree, np) <= AVL_START(tree, nextino));
81 }
82
83 static void
84 avl_checktree(
85 register avltree_desc_t *tree,
86 register avlnode_t *root)
87 {
88 register avlnode_t *nlast, *nnext, *np;
89 __psunsigned_t offset = 0;
90 __psunsigned_t end;
91
92 nlast = nnext = root;
93
94 ASSERT(!nnext || nnext->avl_parent == NULL);
95
96 while (nnext) {
97
98 avl_checknode(tree, nnext);
99 end = AVL_END(tree, nnext);
100
101 if (end <= offset) {
102 if ((np = nnext->avl_forw) && np != nlast) {
103 nlast = nnext;
104 nnext = np;
105 } else {
106 nlast = nnext;
107 nnext = nnext->avl_parent;
108 }
109 continue;
110 }
111
112 nlast = nnext;
113 if (np = nnext->avl_back) {
114 if (AVL_END(tree, np) > offset) {
115 nnext = np;
116 continue;
117 }
118 }
119
120 np = nnext;
121 nnext = nnext->avl_forw;
122 if (!nnext)
123 nnext = np->avl_parent;
124
125 offset = end;
126 }
127 }
128 #else /* ! AVL_DEBUG */
129 #define avl_checktree(t,x)
130 #endif /* AVL_DEBUG */
131
132
133 /*
134 * Reset balance for np up through tree.
135 * ``direction'' is the way that np's balance
136 * is headed after the deletion of one of its children --
137 * e.g., deleting a avl_forw child sends avl_balance toward AVL_BACK.
138 * Called only when deleting a node from the tree.
139 */
140 static void
141 retreat(
142 avltree_desc_t *tree,
143 register avlnode_t *np,
144 register int direction)
145 {
146 register avlnode_t **rootp = &tree->avl_root;
147 register avlnode_t *parent;
148 register avlnode_t *child;
149 register avlnode_t *tmp;
150 register int bal;
151
152 do {
153 ASSERT(direction == AVL_BACK || direction == AVL_FORW);
154
155 if (np->avl_balance == AVL_BALANCE) {
156 np->avl_balance = direction;
157 return;
158 }
159
160 parent = np->avl_parent;
161
162 /*
163 * If balance is being restored, no local node
164 * reorganization is necessary, but may be at
165 * a higher node. Reset direction and continue.
166 */
167 if (direction != np->avl_balance) {
168 np->avl_balance = AVL_BALANCE;
169 if (parent) {
170 if (parent->avl_forw == np)
171 direction = AVL_BACK;
172 else
173 direction = AVL_FORW;
174
175 np = parent;
176 continue;
177 }
178 return;
179 }
180
181 /*
182 * Imbalance. If a avl_forw node was removed, direction
183 * (and, by reduction, np->avl_balance) is/was AVL_BACK.
184 */
185 if (np->avl_balance == AVL_BACK) {
186
187 ASSERT(direction == AVL_BACK);
188 child = np->avl_back;
189 bal = child->avl_balance;
190
191 if (bal != AVL_FORW) /* single LL */ {
192 /*
193 * np gets pushed down to lesser child's
194 * avl_forw branch.
195 *
196 * np-> -D +B
197 * / \ / \
198 * child-> B deleted A -D
199 * / \ /
200 * A C C
201 */
202 #ifdef AVL_PRINT
203 if (!(tree->avl_flags & AVLF_DUPLICITY))
204 cmn_err(CE_CONT, "!LL delete b 0x%x c 0x%x\n",
205 np, child);
206 #endif
207 np->avl_back = child->avl_forw;
208 if (child->avl_forw)
209 child->avl_forw->avl_parent = np;
210 child->avl_forw = np;
211
212 if (parent) {
213 if (parent->avl_forw == np) {
214 parent->avl_forw = child;
215 direction = AVL_BACK;
216 } else {
217 ASSERT(parent->avl_back == np);
218 parent->avl_back = child;
219 direction = AVL_FORW;
220 }
221 } else {
222 ASSERT(*rootp == np);
223 *rootp = child;
224 }
225 np->avl_parent = child;
226 child->avl_parent = parent;
227
228 if (bal == AVL_BALANCE) {
229 np->avl_balance = AVL_BACK;
230 child->avl_balance = AVL_FORW;
231 return;
232 } else {
233 np->avl_balance = AVL_BALANCE;
234 child->avl_balance = AVL_BALANCE;
235 np = parent;
236 avl_checktree(tree, *rootp);
237 continue;
238 }
239 }
240
241 /* child->avl_balance == AVL_FORW double LR rotation
242 *
243 * child's avl_forw node gets promoted up, along with
244 * its avl_forw subtree
245 *
246 * np-> -G C
247 * / \ / \
248 * child-> +B H -B G
249 * / \ \ / / \
250 * A +C deleted A D H
251 * \
252 * D
253 */
254 #ifdef AVL_PRINT
255 if (!(tree->avl_flags & AVLF_DUPLICITY))
256 cmn_err(CE_CONT, "!LR delete b 0x%x c 0x%x t 0x%x\n",
257 np, child, child->avl_forw);
258 #endif
259 tmp = child->avl_forw;
260 bal = tmp->avl_balance;
261
262 child->avl_forw = tmp->avl_back;
263 if (tmp->avl_back)
264 tmp->avl_back->avl_parent = child;
265
266 tmp->avl_back = child;
267 child->avl_parent = tmp;
268
269 np->avl_back = tmp->avl_forw;
270 if (tmp->avl_forw)
271 tmp->avl_forw->avl_parent = np;
272 tmp->avl_forw = np;
273
274 if (bal == AVL_FORW)
275 child->avl_balance = AVL_BACK;
276 else
277 child->avl_balance = AVL_BALANCE;
278
279 if (bal == AVL_BACK)
280 np->avl_balance = AVL_FORW;
281 else
282 np->avl_balance = AVL_BALANCE;
283
284 goto next;
285 }
286
287 ASSERT(np->avl_balance == AVL_FORW && direction == AVL_FORW);
288
289 child = np->avl_forw;
290 bal = child->avl_balance;
291
292 if (bal != AVL_BACK) /* single RR */ {
293 /*
294 * np gets pushed down to greater child's
295 * avl_back branch.
296 *
297 * np-> +B -D
298 * / \ / \
299 * deleted D <-child +B E
300 * / \ \
301 * C E C
302 */
303 #ifdef AVL_PRINT
304 if (!(tree->avl_flags & AVLF_DUPLICITY))
305 cmn_err(CE_CONT, "!RR delete b 0x%x c 0x%x\n",
306 np, child);
307 #endif
308 np->avl_forw = child->avl_back;
309 if (child->avl_back)
310 child->avl_back->avl_parent = np;
311 child->avl_back = np;
312
313 if (parent) {
314 if (parent->avl_forw == np) {
315 parent->avl_forw = child;
316 direction = AVL_BACK;
317 } else {
318 ASSERT(parent->avl_back == np);
319 parent->avl_back = child;
320 direction = AVL_FORW;
321 }
322 } else {
323 ASSERT(*rootp == np);
324 *rootp = child;
325 }
326 np->avl_parent = child;
327 child->avl_parent = parent;
328
329 if (bal == AVL_BALANCE) {
330 np->avl_balance = AVL_FORW;
331 child->avl_balance = AVL_BACK;
332 return;
333 } else {
334 np->avl_balance = AVL_BALANCE;
335 child->avl_balance = AVL_BALANCE;
336 np = parent;
337 avl_checktree(tree, *rootp);
338 continue;
339 }
340 }
341
342 /* child->avl_balance == AVL_BACK double RL rotation */
343 #ifdef AVL_PRINT
344 if (!(tree->avl_flags & AVLF_DUPLICITY))
345 cmn_err(CE_CONT, "!RL delete b 0x%x c 0x%x t 0x%x\n",
346 np, child, child->avl_back);
347 #endif
348 tmp = child->avl_back;
349 bal = tmp->avl_balance;
350
351 child->avl_back = tmp->avl_forw;
352 if (tmp->avl_forw)
353 tmp->avl_forw->avl_parent = child;
354
355 tmp->avl_forw = child;
356 child->avl_parent = tmp;
357
358 np->avl_forw = tmp->avl_back;
359 if (tmp->avl_back)
360 tmp->avl_back->avl_parent = np;
361 tmp->avl_back = np;
362
363 if (bal == AVL_BACK)
364 child->avl_balance = AVL_FORW;
365 else
366 child->avl_balance = AVL_BALANCE;
367
368 if (bal == AVL_FORW)
369 np->avl_balance = AVL_BACK;
370 else
371 np->avl_balance = AVL_BALANCE;
372 next:
373 np->avl_parent = tmp;
374 tmp->avl_balance = AVL_BALANCE;
375 tmp->avl_parent = parent;
376
377 if (parent) {
378 if (parent->avl_forw == np) {
379 parent->avl_forw = tmp;
380 direction = AVL_BACK;
381 } else {
382 ASSERT(parent->avl_back == np);
383 parent->avl_back = tmp;
384 direction = AVL_FORW;
385 }
386 } else {
387 ASSERT(*rootp == np);
388 *rootp = tmp;
389 return;
390 }
391
392 np = parent;
393 avl_checktree(tree, *rootp);
394 } while (np);
395 }
396
397 /*
398 * Remove node from tree.
399 * avl_delete does the local tree manipulations,
400 * calls retreat() to rebalance tree up to its root.
401 */
402 void
403 avl_delete(
404 register avltree_desc_t *tree,
405 register avlnode_t *np)
406 {
407 register avlnode_t *forw = np->avl_forw;
408 register avlnode_t *back = np->avl_back;
409 register avlnode_t *parent = np->avl_parent;
410 register avlnode_t *nnext;
411
412
413 if (np->avl_back) {
414 /*
415 * a left child exits, then greatest left descendent's nextino
416 * is pointing to np; make it point to np->nextino.
417 */
418 nnext = np->avl_back;
419 while (nnext) {
420 if (!nnext->avl_forw)
421 break; /* can't find anything bigger */
422 nnext = nnext->avl_forw;
423 }
424 } else
425 if (np->avl_parent) {
426 /*
427 * find nearest ancestor with lesser value. That ancestor's
428 * nextino is pointing to np; make it point to np->nextino
429 */
430 nnext = np->avl_parent;
431 while (nnext) {
432 if (AVL_END(tree, nnext) <= AVL_END(tree, np))
433 break;
434 nnext = nnext->avl_parent;
435 }
436 } else
437 nnext = NULL;
438
439 if (nnext) {
440 ASSERT(nnext->avl_nextino == np);
441 nnext->avl_nextino = np->avl_nextino;
442 /*
443 * Something preceeds np; np cannot be firstino.
444 */
445 ASSERT(tree->avl_firstino != np);
446 }
447 else {
448 /*
449 * Nothing preceeding np; after deletion, np's nextino
450 * is firstino of tree.
451 */
452 ASSERT(tree->avl_firstino == np);
453 tree->avl_firstino = np->avl_nextino;
454 }
455
456
457 /*
458 * Degenerate cases...
459 */
460 if (forw == NULL) {
461 forw = back;
462 goto attach;
463 }
464
465 if (back == NULL) {
466 attach:
467 if (forw)
468 forw->avl_parent = parent;
469 if (parent) {
470 if (parent->avl_forw == np) {
471 parent->avl_forw = forw;
472 retreat(tree, parent, AVL_BACK);
473 } else {
474 ASSERT(parent->avl_back == np);
475 parent->avl_back = forw;
476 retreat(tree, parent, AVL_FORW);
477 }
478 } else {
479 ASSERT(tree->avl_root == np);
480 tree->avl_root = forw;
481 }
482 avl_checktree(tree, tree->avl_root);
483 return;
484 }
485
486 /*
487 * Harder case: children on both sides.
488 * If back's avl_forw pointer is null, just have back
489 * inherit np's avl_forw tree, remove np from the tree
490 * and adjust balance counters starting at back.
491 *
492 * np-> xI xH (befor retreat())
493 * / \ / \
494 * back-> H J G J
495 * / / \ / \
496 * G ? ? ? ?
497 * / \
498 * ? ?
499 */
500 if ((forw = back->avl_forw) == NULL) {
501 /*
502 * AVL_FORW retreat below will set back's
503 * balance to AVL_BACK.
504 */
505 back->avl_balance = np->avl_balance;
506 back->avl_forw = forw = np->avl_forw;
507 forw->avl_parent = back;
508 back->avl_parent = parent;
509
510 if (parent) {
511 if (parent->avl_forw == np)
512 parent->avl_forw = back;
513 else {
514 ASSERT(parent->avl_back == np);
515 parent->avl_back = back;
516 }
517 } else {
518 ASSERT(tree->avl_root == np);
519 tree->avl_root = back;
520 }
521
522 /*
523 * back is taking np's place in the tree, and
524 * has therefore lost a avl_back node (itself).
525 */
526 retreat(tree, back, AVL_FORW);
527 avl_checktree(tree, tree->avl_root);
528 return;
529 }
530
531 /*
532 * Hardest case: children on both sides, and back's
533 * avl_forw pointer isn't null. Find the immediately
534 * inferior buffer by following back's avl_forw line
535 * to the end, then have it inherit np's avl_forw tree.
536 *
537 * np-> xI xH
538 * / \ / \
539 * G J back-> G J (before retreat())
540 * / \ / \
541 * F ?... F ?1
542 * / \
543 * ? H <-forw
544 * /
545 * ?1
546 */
547 while ((back = forw->avl_forw))
548 forw = back;
549
550 /*
551 * Will be adjusted by retreat() below.
552 */
553 forw->avl_balance = np->avl_balance;
554
555 /*
556 * forw inherits np's avl_forw...
557 */
558 forw->avl_forw = np->avl_forw;
559 np->avl_forw->avl_parent = forw;
560
561 /*
562 * ... forw's parent gets forw's avl_back...
563 */
564 back = forw->avl_parent;
565 back->avl_forw = forw->avl_back;
566 if (forw->avl_back)
567 forw->avl_back->avl_parent = back;
568
569 /*
570 * ... forw gets np's avl_back...
571 */
572 forw->avl_back = np->avl_back;
573 np->avl_back->avl_parent = forw;
574
575 /*
576 * ... and forw gets np's parent.
577 */
578 forw->avl_parent = parent;
579
580 if (parent) {
581 if (parent->avl_forw == np)
582 parent->avl_forw = forw;
583 else
584 parent->avl_back = forw;
585 } else {
586 ASSERT(tree->avl_root == np);
587 tree->avl_root = forw;
588 }
589
590 /*
591 * What used to be forw's parent is the starting
592 * point for rebalancing. It has lost a avl_forw node.
593 */
594 retreat(tree, back, AVL_BACK);
595 avl_checktree(tree, tree->avl_root);
596 }
597
598
599 /*
600 * avl_findanyrange:
601 *
602 * Given range r [start, end), find any range which is contained in r.
603 * if checklen is non-zero, then only ranges of non-zero length are
604 * considered in finding a match.
605 */
606 avlnode_t *
607 avl_findanyrange(
608 register avltree_desc_t *tree,
609 register __psunsigned_t start,
610 register __psunsigned_t end,
611 int checklen)
612 {
613 register avlnode_t *np = tree->avl_root;
614
615 /* np = avl_findadjacent(tree, start, AVL_SUCCEED); */
616 while (np) {
617 if (start < AVL_START(tree, np)) {
618 if (np->avl_back) {
619 np = np->avl_back;
620 continue;
621 }
622 /* if we were to add node with start, would
623 * have a growth of AVL_BACK
624 */
625 /* if succeeding node is needed, this is it.
626 */
627 break;
628 }
629 if (start >= AVL_END(tree, np)) {
630 if (np->avl_forw) {
631 np = np->avl_forw;
632 continue;
633 }
634 /* if we were to add node with start, would
635 * have a growth of AVL_FORW;
636 */
637 /* we are looking for a succeeding node;
638 * this is nextino.
639 */
640 np = np->avl_nextino;
641 break;
642 }
643 /* AVL_START(tree, np) <= start < AVL_END(tree, np) */
644 break;
645 }
646 if (np) {
647 if (checklen == AVL_INCLUDE_ZEROLEN) {
648 if (end <= AVL_START(tree, np)) {
649 /* something follows start, but is
650 * is entierly after the range (end)
651 */
652 return(NULL);
653 }
654 /* np may stradle [start, end) */
655 return(np);
656 }
657 /*
658 * find non-zero length region
659 */
660 while (np && (AVL_END(tree, np) - AVL_START(tree, np) == 0)
661 && (AVL_START(tree, np) < end))
662 np = np->avl_nextino;
663
664 if ((np == NULL) || (AVL_START(tree, np) >= end))
665 return NULL;
666 return(np);
667 }
668 /*
669 * nothing succeeds start, all existing ranges are before start.
670 */
671 return NULL;
672 }
673
674
675 /*
676 * Returns a pointer to range which contains value.
677 */
678 avlnode_t *
679 avl_findrange(
680 register avltree_desc_t *tree,
681 register __psunsigned_t value)
682 {
683 register avlnode_t *np = tree->avl_root;
684
685 while (np) {
686 if (value < AVL_START(tree, np)) {
687 np = np->avl_back;
688 continue;
689 }
690 if (value >= AVL_END(tree, np)) {
691 np = np->avl_forw;
692 continue;
693 }
694 ASSERT(AVL_START(tree, np) <= value &&
695 value < AVL_END(tree, np));
696 return np;
697 }
698 return NULL;
699 }
700
701
702 /*
703 * Returns a pointer to node which contains exact value.
704 */
705 avlnode_t *
706 avl_find(
707 register avltree_desc_t *tree,
708 register __psunsigned_t value)
709 {
710 register avlnode_t *np = tree->avl_root;
711 register __psunsigned_t nvalue;
712
713 while (np) {
714 nvalue = AVL_START(tree, np);
715 if (value < nvalue) {
716 np = np->avl_back;
717 continue;
718 }
719 if (value == nvalue) {
720 return np;
721 }
722 np = np->avl_forw;
723 }
724 return NULL;
725 }
726
727
728 /*
729 * Balance buffer AVL tree after attaching a new node to root.
730 * Called only by avl_insert.
731 */
732 static void
733 avl_balance(
734 register avlnode_t **rootp,
735 register avlnode_t *np,
736 register int growth)
737 {
738 /*
739 * At this point, np points to the node to which
740 * a new node has been attached. All that remains is to
741 * propagate avl_balance up the tree.
742 */
743 for ( ; ; ) {
744 register avlnode_t *parent = np->avl_parent;
745 register avlnode_t *child;
746
747 CERT(growth == AVL_BACK || growth == AVL_FORW);
748
749 /*
750 * If the buffer was already balanced, set avl_balance
751 * to the new direction. Continue if there is a
752 * parent after setting growth to reflect np's
753 * relation to its parent.
754 */
755 if (np->avl_balance == AVL_BALANCE) {
756 np->avl_balance = growth;
757 if (parent) {
758 if (parent->avl_forw == np)
759 growth = AVL_FORW;
760 else {
761 ASSERT(parent->avl_back == np);
762 growth = AVL_BACK;
763 }
764
765 np = parent;
766 continue;
767 }
768 break;
769 }
770
771 if (growth != np->avl_balance) {
772 /*
773 * Subtree is now balanced -- no net effect
774 * in the size of the subtree, so leave.
775 */
776 np->avl_balance = AVL_BALANCE;
777 break;
778 }
779
780 if (growth == AVL_BACK) {
781
782 child = np->avl_back;
783 CERT(np->avl_balance == AVL_BACK && child);
784
785 if (child->avl_balance == AVL_BACK) { /* single LL */
786 /*
787 * ``A'' just got inserted;
788 * np points to ``E'', child to ``C'',
789 * and it is already AVL_BACK --
790 * child will get promoted to top of subtree.
791
792 np-> -E C
793 / \ / \
794 child-> -C F -B E
795 / \ / / \
796 -B D A D F
797 /
798 A
799
800 Note that child->avl_parent and
801 avl_balance get set in common code.
802 */
803 np->avl_parent = child;
804 np->avl_balance = AVL_BALANCE;
805 np->avl_back = child->avl_forw;
806 if (child->avl_forw)
807 child->avl_forw->avl_parent = np;
808 child->avl_forw = np;
809 } else {
810 /*
811 * double LR
812 *
813 * child's avl_forw node gets promoted to
814 * the top of the subtree.
815
816 np-> -E C
817 / \ / \
818 child-> +B F -B E
819 / \ / / \
820 A +C A D F
821 \
822 D
823
824 */
825 register avlnode_t *tmp = child->avl_forw;
826
827 CERT(child->avl_balance == AVL_FORW && tmp);
828
829 child->avl_forw = tmp->avl_back;
830 if (tmp->avl_back)
831 tmp->avl_back->avl_parent = child;
832
833 tmp->avl_back = child;
834 child->avl_parent = tmp;
835
836 np->avl_back = tmp->avl_forw;
837 if (tmp->avl_forw)
838 tmp->avl_forw->avl_parent = np;
839
840 tmp->avl_forw = np;
841 np->avl_parent = tmp;
842
843 if (tmp->avl_balance == AVL_BACK)
844 np->avl_balance = AVL_FORW;
845 else
846 np->avl_balance = AVL_BALANCE;
847
848 if (tmp->avl_balance == AVL_FORW)
849 child->avl_balance = AVL_BACK;
850 else
851 child->avl_balance = AVL_BALANCE;
852
853 /*
854 * Set child to point to tmp since it is
855 * now the top of the subtree, and will
856 * get attached to the subtree parent in
857 * the common code below.
858 */
859 child = tmp;
860 }
861
862 } else /* growth == AVL_BACK */ {
863
864 /*
865 * This code is the mirror image of AVL_FORW above.
866 */
867
868 child = np->avl_forw;
869 CERT(np->avl_balance == AVL_FORW && child);
870
871 if (child->avl_balance == AVL_FORW) { /* single RR */
872 np->avl_parent = child;
873 np->avl_balance = AVL_BALANCE;
874 np->avl_forw = child->avl_back;
875 if (child->avl_back)
876 child->avl_back->avl_parent = np;
877 child->avl_back = np;
878 } else {
879 /*
880 * double RL
881 */
882 register avlnode_t *tmp = child->avl_back;
883
884 ASSERT(child->avl_balance == AVL_BACK && tmp);
885
886 child->avl_back = tmp->avl_forw;
887 if (tmp->avl_forw)
888 tmp->avl_forw->avl_parent = child;
889
890 tmp->avl_forw = child;
891 child->avl_parent = tmp;
892
893 np->avl_forw = tmp->avl_back;
894 if (tmp->avl_back)
895 tmp->avl_back->avl_parent = np;
896
897 tmp->avl_back = np;
898 np->avl_parent = tmp;
899
900 if (tmp->avl_balance == AVL_FORW)
901 np->avl_balance = AVL_BACK;
902 else
903 np->avl_balance = AVL_BALANCE;
904
905 if (tmp->avl_balance == AVL_BACK)
906 child->avl_balance = AVL_FORW;
907 else
908 child->avl_balance = AVL_BALANCE;
909
910 child = tmp;
911 }
912 }
913
914 child->avl_parent = parent;
915 child->avl_balance = AVL_BALANCE;
916
917 if (parent) {
918 if (parent->avl_back == np)
919 parent->avl_back = child;
920 else
921 parent->avl_forw = child;
922 } else {
923 ASSERT(*rootp == np);
924 *rootp = child;
925 }
926
927 break;
928 }
929 }
930
931 static
932 avlnode_t *
933 avl_insert_find_growth(
934 register avltree_desc_t *tree,
935 register __psunsigned_t start, /* range start at start, */
936 register __psunsigned_t end, /* exclusive */
937 register int *growthp) /* OUT */
938 {
939 avlnode_t *root = tree->avl_root;
940 register avlnode_t *np;
941
942 np = root;
943 ASSERT(np); /* caller ensures that there is atleast one node in tree */
944
945 for ( ; ; ) {
946 CERT(np->avl_parent || root == np);
947 CERT(!np->avl_parent || root != np);
948 CERT(!(np->avl_back) || np->avl_back->avl_parent == np);
949 CERT(!(np->avl_forw) || np->avl_forw->avl_parent == np);
950 CERT(np->avl_balance != AVL_FORW || np->avl_forw);
951 CERT(np->avl_balance != AVL_BACK || np->avl_back);
952 CERT(np->avl_balance != AVL_BALANCE ||
953 np->avl_back == NULL || np->avl_forw);
954 CERT(np->avl_balance != AVL_BALANCE ||
955 np->avl_forw == NULL || np->avl_back);
956
957 if (AVL_START(tree, np) >= end) {
958 if (np->avl_back) {
959 np = np->avl_back;
960 continue;
961 }
962 *growthp = AVL_BACK;
963 break;
964 }
965
966 if (AVL_END(tree, np) <= start) {
967 if (np->avl_forw) {
968 np = np->avl_forw;
969 continue;
970 }
971 *growthp = AVL_FORW;
972 break;
973 }
974 /* found exact match -- let caller decide if it is an error */
975 return(NULL);
976 }
977 return(np);
978 }
979
980
981 static void
982 avl_insert_grow(
983 register avltree_desc_t *tree,
984 register avlnode_t *parent,
985 register avlnode_t *newnode,
986 register int growth)
987 {
988 register avlnode_t *nnext;
989 register __psunsigned_t start = AVL_START(tree, newnode);
990
991 if (growth == AVL_BACK) {
992
993 parent->avl_back = newnode;
994 /*
995 * we are growing to the left; previous in-order to newnode is
996 * closest ancestor with lesser value. Before this
997 * insertion, this ancestor will be pointing to
998 * newnode's parent. After insertion, next in-order to newnode
999 * is the parent.
1000 */
1001 newnode->avl_nextino = parent;
1002 nnext = parent;
1003 while (nnext) {
1004 if (AVL_END(tree, nnext) <= start)
1005 break;
1006 nnext = nnext->avl_parent;
1007 }
1008 if (nnext) {
1009 /*
1010 * nnext will be null if newnode is
1011 * the least element, and hence very first in the list.
1012 */
1013 ASSERT(nnext->avl_nextino == parent);
1014 nnext->avl_nextino = newnode;
1015 }
1016 }
1017 else {
1018 parent->avl_forw = newnode;
1019 newnode->avl_nextino = parent->avl_nextino;
1020 parent->avl_nextino = newnode;
1021 }
1022 }
1023
1024
1025 avlnode_t *
1026 avl_insert(
1027 register avltree_desc_t *tree,
1028 register avlnode_t *newnode)
1029 {
1030 register avlnode_t *np;
1031 register __psunsigned_t start = AVL_START(tree, newnode);
1032 register __psunsigned_t end = AVL_END(tree, newnode);
1033 int growth;
1034
1035 ASSERT(newnode);
1036 ASSERT(start <= end);
1037
1038 /*
1039 * Clean all pointers for sanity; some will be reset as necessary.
1040 */
1041 newnode->avl_nextino = NULL;
1042 newnode->avl_parent = NULL;
1043 newnode->avl_forw = NULL;
1044 newnode->avl_back = NULL;
1045 newnode->avl_balance = AVL_BALANCE;
1046
1047 if ((np = tree->avl_root) == NULL) { /* degenerate case... */
1048 tree->avl_root = newnode;
1049 tree->avl_firstino = newnode;
1050 return newnode;
1051 }
1052
1053 if ((np = avl_insert_find_growth(tree, start, end, &growth)) == NULL) {
1054 if (start != end) { /* non-zero length range */
1055 fprintf(stderr,
1056 _("avl_insert: Warning! duplicate range [%llu,%llu]\n"),
1057 (unsigned long long)start,
1058 (unsigned long long)end);
1059 }
1060 return(NULL);
1061 }
1062
1063 avl_insert_grow(tree, np, newnode, growth);
1064 if (growth == AVL_BACK) {
1065 /*
1066 * Growing to left. if np was firstino, newnode will be firstino
1067 */
1068 if (tree->avl_firstino == np)
1069 tree->avl_firstino = newnode;
1070 }
1071 #ifdef notneeded
1072 else
1073 if (growth == AVL_FORW)
1074 /*
1075 * Cannot possibly be firstino; there is somebody to our left.
1076 */
1077 ;
1078 #endif
1079
1080 newnode->avl_parent = np;
1081 CERT(np->avl_forw == newnode || np->avl_back == newnode);
1082
1083 avl_balance(&tree->avl_root, np, growth);
1084
1085 avl_checktree(tree, tree->avl_root);
1086
1087 return newnode;
1088 }
1089
1090 /*
1091 *
1092 * avl_insert_immediate(tree, afterp, newnode):
1093 * insert newnode immediately into tree immediately after afterp.
1094 * after insertion, newnode is right child of afterp.
1095 */
1096 void
1097 avl_insert_immediate(
1098 avltree_desc_t *tree,
1099 avlnode_t *afterp,
1100 avlnode_t *newnode)
1101 {
1102 /*
1103 * Clean all pointers for sanity; some will be reset as necessary.
1104 */
1105 newnode->avl_nextino = NULL;
1106 newnode->avl_parent = NULL;
1107 newnode->avl_forw = NULL;
1108 newnode->avl_back = NULL;
1109 newnode->avl_balance = AVL_BALANCE;
1110
1111 if (afterp == NULL) {
1112 tree->avl_root = newnode;
1113 tree->avl_firstino = newnode;
1114 return;
1115 }
1116
1117 ASSERT(afterp->avl_forw == NULL);
1118 avl_insert_grow(tree, afterp, newnode, AVL_FORW); /* grow to right */
1119 CERT(afterp->avl_forw == newnode);
1120 avl_balance(&tree->avl_root, afterp, AVL_FORW);
1121 avl_checktree(tree, tree->avl_root);
1122 }
1123
1124
1125 /*
1126 * Returns first in order node
1127 */
1128 avlnode_t *
1129 avl_firstino(register avlnode_t *root)
1130 {
1131 register avlnode_t *np;
1132
1133 if ((np = root) == NULL)
1134 return NULL;
1135
1136 while (np->avl_back)
1137 np = np->avl_back;
1138 return np;
1139 }
1140
1141 /*
1142 * Returns last in order node
1143 */
1144 avlnode_t *
1145 avl_lastino(register avlnode_t *root)
1146 {
1147 register avlnode_t *np;
1148
1149 if ((np = root) == NULL)
1150 return NULL;
1151
1152 while (np->avl_forw)
1153 np = np->avl_forw;
1154 return np;
1155 }
1156
1157 void
1158 avl_init_tree(avltree_desc_t *tree, avlops_t *ops)
1159 {
1160 tree->avl_root = NULL;
1161 tree->avl_firstino = NULL;
1162 tree->avl_ops = ops;
1163 }
1164
1165 #ifdef AVL_DEBUG
1166 static void
1167 avl_printnode(avltree_desc_t *tree, avlnode_t *np, int nl)
1168 {
1169 printf("[%d-%d]%c", AVL_START(tree, np),
1170 (AVL_END(tree, np) - 1), nl ? '\n' : ' ');
1171 }
1172 #endif
1173 #ifdef STAND_ALONE_DEBUG
1174
1175 struct avl_debug_node {
1176 avlnode_t avl_node;
1177 xfs_off_t avl_start;
1178 unsigned int avl_size;
1179 }
1180
1181 avlops_t avl_debug_ops = {
1182 avl_debug_start,
1183 avl_debug_end,
1184 }
1185
1186 static __psunsigned_t
1187 avl_debug_start(avlnode_t *node)
1188 {
1189 return (__psunsigned_t)(struct avl_debug_node *)node->avl_start;
1190 }
1191
1192 static __psunsigned_t
1193 avl_debug_end(avlnode_t *node)
1194 {
1195 return (__psunsigned_t)
1196 ((struct avl_debug_node *)node->avl_start +
1197 (struct avl_debug_node *)node->avl_size);
1198 }
1199
1200 avl_debug_node freenodes[100];
1201 avl_debug_node *freehead = &freenodes[0];
1202
1203 static avlnode_t *
1204 alloc_avl_debug_node()
1205 {
1206 freehead->avl_balance = AVL_BALANCE;
1207 freehead->avl_parent = freehead->avl_forw = freehead->avl_back = NULL;
1208 return(freehead++);
1209 }
1210
1211 static void
1212 avl_print(avltree_desc_t *tree, avlnode_t *root, int depth)
1213 {
1214 int i;
1215
1216 if (!root)
1217 return;
1218 if (root->avl_forw)
1219 avl_print(tree, root->avl_forw, depth+5);
1220 for (i = 0; i < depth; i++)
1221 putchar((int) ' ');
1222 avl_printnode(tree, root,1);
1223 if (root->avl_back)
1224 avl_print(tree, root->avl_back, depth+5);
1225 }
1226
1227 main()
1228 {
1229 int i, j;
1230 avlnode_t *np;
1231 avltree_desc_t tree;
1232 char linebuf[256], cmd[256];
1233
1234 avl_init_tree(&tree, &avl_debug_ops);
1235
1236 for (i = 100; i > 0; i = i - 10)
1237 {
1238 np = alloc__debug_avlnode();
1239 ASSERT(np);
1240 np->avl_start = i;
1241 np->avl_size = 10;
1242 avl_insert(&tree, np);
1243 }
1244 avl_print(&tree, tree.avl_root, 0);
1245
1246 for (np = tree.avl_firstino; np != NULL; np = np->avl_nextino)
1247 avl_printnode(&tree, np, 0);
1248 printf("\n");
1249
1250 while (1) {
1251 printf("Command [fpdir] : ");
1252 fgets(linebuf, 256, stdin);
1253 if (feof(stdin)) break;
1254 cmd[0] = NULL;
1255 if (sscanf(linebuf, "%[fpdir]%d", cmd, &i) != 2)
1256 continue;
1257 switch (cmd[0]) {
1258 case 'd':
1259 case 'f':
1260 printf("end of range ? ");
1261 fgets(linebuf, 256, stdin);
1262 j = atoi(linebuf);
1263
1264 if (i == j) j = i+1;
1265 np = avl_findinrange(&tree,i,j);
1266 if (np) {
1267 avl_printnode(&tree, np, 1);
1268 if (cmd[0] == 'd')
1269 avl_delete(&tree, np);
1270 } else
1271 printf("Cannot find %d\n", i);
1272 break;
1273 case 'p':
1274 avl_print(&tree, tree.avl_root, 0);
1275 for (np = tree.avl_firstino;
1276 np != NULL; np = np->avl_nextino)
1277 avl_printnode(&tree, np, 0);
1278 printf("\n");
1279 break;
1280 case 'i':
1281 np = alloc_avlnode();
1282 ASSERT(np);
1283 np->avl_start = i;
1284 printf("size of range ? ");
1285 fgets(linebuf, 256, stdin);
1286 j = atoi(linebuf);
1287
1288 np->avl_size = j;
1289 avl_insert(&tree, np);
1290 break;
1291 case 'r': {
1292 avlnode_t *b, *e, *t;
1293 int checklen;
1294
1295 printf("End of range ? ");
1296 fgets(linebuf, 256, stdin);
1297 j = atoi(linebuf);
1298
1299 printf("checklen 0/1 ? ");
1300 fgets(linebuf, 256, stdin);
1301 checklen = atoi(linebuf);
1302
1303
1304 b = avl_findanyrange(&tree, i, j, checklen);
1305 if (b) {
1306 printf("Found something\n");
1307 t = b;
1308 while (t) {
1309 if (t != b &&
1310 AVL_START(&tree, t) >= j)
1311 break;
1312 avl_printnode(&tree, t, 0);
1313 t = t->avl_nextino;
1314 }
1315 printf("\n");
1316 }
1317 }
1318 }
1319 }
1320 }
1321 #endif
1322
1323 /*
1324 * Given a tree, find value; will find return range enclosing value,
1325 * or range immediately succeeding value,
1326 * or range immediately preceeding value.
1327 */
1328 avlnode_t *
1329 avl_findadjacent(
1330 register avltree_desc_t *tree,
1331 register __psunsigned_t value,
1332 register int dir)
1333 {
1334 register avlnode_t *np = tree->avl_root;
1335
1336 while (np) {
1337 if (value < AVL_START(tree, np)) {
1338 if (np->avl_back) {
1339 np = np->avl_back;
1340 continue;
1341 }
1342 /* if we were to add node with value, would
1343 * have a growth of AVL_BACK
1344 */
1345 if (dir == AVL_SUCCEED) {
1346 /* if succeeding node is needed, this is it.
1347 */
1348 return(np);
1349 }
1350 if (dir == AVL_PRECEED) {
1351 /*
1352 * find nearest ancestor with lesser value.
1353 */
1354 np = np->avl_parent;
1355 while (np) {
1356 if (AVL_END(tree, np) <= value)
1357 break;
1358 np = np->avl_parent;
1359 }
1360 return(np);
1361 }
1362 ASSERT(dir == AVL_SUCCEED || dir == AVL_PRECEED);
1363 break;
1364 }
1365 if (value >= AVL_END(tree, np)) {
1366 if (np->avl_forw) {
1367 np = np->avl_forw;
1368 continue;
1369 }
1370 /* if we were to add node with value, would
1371 * have a growth of AVL_FORW;
1372 */
1373 if (dir == AVL_SUCCEED) {
1374 /* we are looking for a succeeding node;
1375 * this is nextino.
1376 */
1377 return(np->avl_nextino);
1378 }
1379 if (dir == AVL_PRECEED) {
1380 /* looking for a preceeding node; this is it. */
1381 return(np);
1382 }
1383 ASSERT(dir == AVL_SUCCEED || dir == AVL_PRECEED);
1384 }
1385 /* AVL_START(tree, np) <= value < AVL_END(tree, np) */
1386 return(np);
1387 }
1388 return NULL;
1389 }
1390
1391
1392 /*
1393 * avl_findranges:
1394 *
1395 * Given range r [start, end), find all ranges in tree which are contained
1396 * in r. At return, startp and endp point to first and last of
1397 * a chain of elements which describe the contained ranges. Elements
1398 * in startp ... endp are in sort order, and can be accessed by
1399 * using avl_nextino.
1400 */
1401
1402 void
1403 avl_findranges(
1404 register avltree_desc_t *tree,
1405 register __psunsigned_t start,
1406 register __psunsigned_t end,
1407 avlnode_t **startp,
1408 avlnode_t **endp)
1409 {
1410 register avlnode_t *np;
1411
1412 np = avl_findadjacent(tree, start, AVL_SUCCEED);
1413 if (np == NULL /* nothing succeding start */
1414 || (np && (end <= AVL_START(tree, np))))
1415 /* something follows start,
1416 but... is entirely after end */
1417 {
1418 *startp = NULL;
1419 *endp = NULL;
1420 return;
1421 }
1422
1423 *startp = np;
1424
1425 /* see if end is in this region itself */
1426 if (end <= AVL_END(tree, np) ||
1427 np->avl_nextino == NULL ||
1428 (np->avl_nextino &&
1429 (end <= AVL_START(tree, np->avl_nextino)))) {
1430 *endp = np;
1431 return;
1432 }
1433 /* have to munge for end */
1434 /*
1435 * note: have to look for (end - 1), since
1436 * findadjacent will look for exact value, and does not
1437 * care about the fact that end is actually one more
1438 * than the value actually being looked for; thus feed it one less.
1439 */
1440 *endp = avl_findadjacent(tree, (end-1), AVL_PRECEED);
1441 ASSERT(*endp);
1442 }
Unnamed repository; edit this file 'description' to name the repository.