path: root/lib/rbtree_test.c
diff options
authorMichel Lespinasse <walken@google.com>2012-10-08 16:31:17 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 16:22:37 +0900
commit14b94af0b251a2c80885b60538166fb7d04a642e (patch)
treeef447d340435c441f8c3e54eb8f26f747aa73108 /lib/rbtree_test.c
parentdadf93534f125b9eda486b471446a8456a603d27 (diff)
rbtree: faster augmented rbtree manipulation
Introduce new augmented rbtree APIs that allow minimal recalculation of augmented node information. A new callback is added to the rbtree insertion and erase rebalancing functions, to be called on each tree rotations. Such rotations preserve the subtree's root augmented value, but require recalculation of the one child that was previously located at the subtree root. In the insertion case, the handcoded search phase must be updated to maintain the augmented information on insertion, and then the rbtree coloring/rebalancing algorithms keep it up to date. In the erase case, things are more complicated since it is library code that manipulates the rbtree in order to remove internal nodes. This requires a couple additional callbacks to copy a subtree's augmented value when a new root is stitched in, and to recompute augmented values down the ancestry path when a node is removed from the tree. In order to preserve maximum speed for the non-augmented case, we provide two versions of each tree manipulation function. rb_insert_augmented() is the augmented equivalent of rb_insert_color(), and rb_erase_augmented() is the augmented equivalent of rb_erase(). Signed-off-by: Michel Lespinasse <walken@google.com> Acked-by: Rik van Riel <riel@redhat.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: David Woodhouse <dwmw2@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/rbtree_test.c')
1 files changed, 44 insertions, 14 deletions
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 66e41d4bfc39..e28345df09bf 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -61,35 +61,65 @@ static inline u32 augment_recompute(struct test_node *node)
return max;
-static void augment_callback(struct rb_node *rb, void *unused)
+static void augment_propagate(struct rb_node *rb, struct rb_node *stop)
- struct test_node *node = rb_entry(rb, struct test_node, rb);
- node->augmented = augment_recompute(node);
+ while (rb != stop) {
+ struct test_node *node = rb_entry(rb, struct test_node, rb);
+ u32 augmented = augment_recompute(node);
+ if (node->augmented == augmented)
+ break;
+ node->augmented = augmented;
+ rb = rb_parent(&node->rb);
+ }
+static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new)
+ struct test_node *old = rb_entry(rb_old, struct test_node, rb);
+ struct test_node *new = rb_entry(rb_new, struct test_node, rb);
+ new->augmented = old->augmented;
+static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
+ struct test_node *old = rb_entry(rb_old, struct test_node, rb);
+ struct test_node *new = rb_entry(rb_new, struct test_node, rb);
+ /* Rotation doesn't change subtree's augmented value */
+ new->augmented = old->augmented;
+ old->augmented = augment_recompute(old);
+static const struct rb_augment_callbacks augment_callbacks = {
+ augment_propagate, augment_copy, augment_rotate
static void insert_augmented(struct test_node *node, struct rb_root *root)
- struct rb_node **new = &root->rb_node, *parent = NULL;
+ struct rb_node **new = &root->rb_node, *rb_parent = NULL;
u32 key = node->key;
+ u32 val = node->val;
+ struct test_node *parent;
while (*new) {
- parent = *new;
- if (key < rb_entry(parent, struct test_node, rb)->key)
- new = &parent->rb_left;
+ rb_parent = *new;
+ parent = rb_entry(rb_parent, struct test_node, rb);
+ if (parent->augmented < val)
+ parent->augmented = val;
+ if (key < parent->key)
+ new = &parent->rb.rb_left;
- new = &parent->rb_right;
+ new = &parent->rb.rb_right;
- rb_link_node(&node->rb, parent, new);
- rb_insert_color(&node->rb, root);
- rb_augment_insert(&node->rb, augment_callback, NULL);
+ node->augmented = val;
+ rb_link_node(&node->rb, rb_parent, new);
+ rb_insert_augmented(&node->rb, root, &augment_callbacks);
static void erase_augmented(struct test_node *node, struct rb_root *root)
- struct rb_node *deepest = rb_augment_erase_begin(&node->rb);
- rb_erase(&node->rb, root);
- rb_augment_erase_end(deepest, augment_callback, NULL);
+ rb_erase_augmented(&node->rb, root, &augment_callbacks);
static void init(void)