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