]>
Commit | Line | Data |
---|---|---|
2bd0ea18 NS |
1 | /************************************************************************** |
2 | * * | |
cc08d43e | 3 | * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved. |
2bd0ea18 NS |
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 | ||
2bd0ea18 NS |
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 | */ | |
27527004 | 547 | while ((back = forw->avl_forw)) |
2bd0ea18 NS |
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 */ | |
2d9475a4 NS |
1055 | fprintf(stderr, |
1056 | "avl_insert: Warning! duplicate range [%llu,%llu]\n", | |
1057 | (unsigned long long)start, | |
1058 | (unsigned long long)end); | |
2bd0ea18 NS |
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 | ||
2bd0ea18 NS |
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 | } | |
2bd0ea18 NS |
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 | ||
2bd0ea18 NS |
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 | } |