diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/rbtree.c | 71 |
1 files changed, 0 insertions, 71 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c index a37ee7954b8f..c0088ca345f9 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c | |||
@@ -538,77 +538,6 @@ void rb_erase_augmented(struct rb_node *node, struct rb_root *root, | |||
538 | } | 538 | } |
539 | EXPORT_SYMBOL(rb_erase_augmented); | 539 | EXPORT_SYMBOL(rb_erase_augmented); |
540 | 540 | ||
541 | static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) | ||
542 | { | ||
543 | struct rb_node *parent; | ||
544 | |||
545 | up: | ||
546 | func(node, data); | ||
547 | parent = rb_parent(node); | ||
548 | if (!parent) | ||
549 | return; | ||
550 | |||
551 | if (node == parent->rb_left && parent->rb_right) | ||
552 | func(parent->rb_right, data); | ||
553 | else if (parent->rb_left) | ||
554 | func(parent->rb_left, data); | ||
555 | |||
556 | node = parent; | ||
557 | goto up; | ||
558 | } | ||
559 | |||
560 | /* | ||
561 | * after inserting @node into the tree, update the tree to account for | ||
562 | * both the new entry and any damage done by rebalance | ||
563 | */ | ||
564 | void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) | ||
565 | { | ||
566 | if (node->rb_left) | ||
567 | node = node->rb_left; | ||
568 | else if (node->rb_right) | ||
569 | node = node->rb_right; | ||
570 | |||
571 | rb_augment_path(node, func, data); | ||
572 | } | ||
573 | EXPORT_SYMBOL(rb_augment_insert); | ||
574 | |||
575 | /* | ||
576 | * before removing the node, find the deepest node on the rebalance path | ||
577 | * that will still be there after @node gets removed | ||
578 | */ | ||
579 | struct rb_node *rb_augment_erase_begin(struct rb_node *node) | ||
580 | { | ||
581 | struct rb_node *deepest; | ||
582 | |||
583 | if (!node->rb_right && !node->rb_left) | ||
584 | deepest = rb_parent(node); | ||
585 | else if (!node->rb_right) | ||
586 | deepest = node->rb_left; | ||
587 | else if (!node->rb_left) | ||
588 | deepest = node->rb_right; | ||
589 | else { | ||
590 | deepest = rb_next(node); | ||
591 | if (deepest->rb_right) | ||
592 | deepest = deepest->rb_right; | ||
593 | else if (rb_parent(deepest) != node) | ||
594 | deepest = rb_parent(deepest); | ||
595 | } | ||
596 | |||
597 | return deepest; | ||
598 | } | ||
599 | EXPORT_SYMBOL(rb_augment_erase_begin); | ||
600 | |||
601 | /* | ||
602 | * after removal, update the tree to account for the removed entry | ||
603 | * and any rebalance damage. | ||
604 | */ | ||
605 | void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) | ||
606 | { | ||
607 | if (node) | ||
608 | rb_augment_path(node, func, data); | ||
609 | } | ||
610 | EXPORT_SYMBOL(rb_augment_erase_end); | ||
611 | |||
612 | /* | 541 | /* |
613 | * This function returns the first node (in sort order) of the tree. | 542 | * This function returns the first node (in sort order) of the tree. |
614 | */ | 543 | */ |