@@ -86,6 +86,27 @@ rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree,
return leftmost ? node : NULL;
}
+static __always_inline void
+rb_add_augmented(struct rb_node *node, struct rb_root *tree,
+ bool (*less)(struct rb_node *, const struct rb_node *),
+ const struct rb_augment_callbacks *augment)
+{
+ struct rb_node **link = &tree->rb_node;
+ struct rb_node *parent = NULL;
+
+ while (*link) {
+ parent = *link;
+ if (less(node, parent))
+ link = &parent->rb_left;
+ else
+ link = &parent->rb_right;
+ }
+
+ rb_link_node(node, parent, link);
+ augment->propagate(parent, NULL);
+ rb_insert_augmented(node, tree, augment);
+}
+
/*
* Template for declaring augmented rbtree callbacks (generic case)
*
@@ -29,41 +29,19 @@ static struct test_node *nodes = NULL;
static struct rnd_state rnd;
-static void insert(struct test_node *node, struct rb_root_cached *root)
+static inline bool less(struct rb_node *a, const struct rb_node *b)
{
- struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;
- u32 key = node->key;
-
- while (*new) {
- parent = *new;
- if (key < rb_entry(parent, struct test_node, rb)->key)
- new = &parent->rb_left;
- else
- new = &parent->rb_right;
- }
+ return rb_entry(a, struct test_node, rb)->key < rb_entry(b, struct test_node, rb)->key;
+}
- rb_link_node(&node->rb, parent, new);
- rb_insert_color(&node->rb, &root->rb_root);
+static void insert(struct test_node *node, struct rb_root_cached *root)
+{
+ rb_add(&node->rb, &root->rb_root, less);
}
static void insert_cached(struct test_node *node, struct rb_root_cached *root)
{
- struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;
- u32 key = node->key;
- bool leftmost = true;
-
- while (*new) {
- parent = *new;
- if (key < rb_entry(parent, struct test_node, rb)->key)
- new = &parent->rb_left;
- else {
- new = &parent->rb_right;
- leftmost = false;
- }
- }
-
- rb_link_node(&node->rb, parent, new);
- rb_insert_color_cached(&node->rb, root, leftmost);
+ rb_add_cached(&node->rb, root, less);
}
static inline void erase(struct test_node *node, struct rb_root_cached *root)
@@ -85,53 +63,15 @@ RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
static void insert_augmented(struct test_node *node,
struct rb_root_cached *root)
{
- struct rb_node **new = &root->rb_root.rb_node, *rb_parent = NULL;
- u32 key = node->key;
- u32 val = node->val;
- struct test_node *parent;
-
- while (*new) {
- 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;
- else
- new = &parent->rb.rb_right;
- }
-
- node->augmented = val;
- rb_link_node(&node->rb, rb_parent, new);
- rb_insert_augmented(&node->rb, &root->rb_root, &augment_callbacks);
+ node->augmented = node->val;
+ rb_add_augmented(&node->rb, &root->rb_root, less, &augment_callbacks);
}
static void insert_augmented_cached(struct test_node *node,
struct rb_root_cached *root)
{
- struct rb_node **new = &root->rb_root.rb_node, *rb_parent = NULL;
- u32 key = node->key;
- u32 val = node->val;
- struct test_node *parent;
- bool leftmost = true;
-
- while (*new) {
- 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;
- else {
- new = &parent->rb.rb_right;
- leftmost = false;
- }
- }
-
- node->augmented = val;
- rb_link_node(&node->rb, rb_parent, new);
- rb_insert_augmented_cached(&node->rb, root,
- leftmost, &augment_callbacks);
+ node->augmented = node->val;
+ rb_add_augmented_cached(&node->rb, root, less, &augment_callbacks);
}