summaryrefslogtreecommitdiffstats
path: root/include/linux/rbtree.h
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 16:31:33 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 16:22:40 +0900
commit9c079add0d0f45220f4bb37febf0621137ec2d38 (patch)
treece6ba6d7e2d517a2004de856c882f2a08af12be2 /include/linux/rbtree.h
parent147e615f83c2c36caf89e7a3bf78090ade6f266c (diff)
downloadlinux-9c079add0d0f45220f4bb37febf0621137ec2d38.tar.gz
linux-9c079add0d0f45220f4bb37febf0621137ec2d38.tar.bz2
linux-9c079add0d0f45220f4bb37febf0621137ec2d38.zip
rbtree: move augmented rbtree functionality to rbtree_augmented.h
Provide rb_insert_augmented() and rb_erase_augmented() through a new rbtree_augmented.h include file. rb_erase_augmented() is defined there as an __always_inline function, in order to allow inlining of augmented rbtree callbacks into it. Since this generates a relatively large function, each augmented rbtree user should make sure to have a single call site. Signed-off-by: Michel Lespinasse <walken@google.com> Cc: Rik van Riel <riel@redhat.com> Cc: Hillf Danton <dhillf@gmail.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Catalin Marinas <catalin.marinas@arm.com> 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 'include/linux/rbtree.h')
-rw-r--r--include/linux/rbtree.h48
1 files changed, 0 insertions, 48 deletions
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 8d1e83b1c87b..0022c1bb1e26 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -62,54 +62,6 @@ extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);
-struct rb_augment_callbacks {
- void (*propagate)(struct rb_node *node, struct rb_node *stop);
- void (*copy)(struct rb_node *old, struct rb_node *new);
- void (*rotate)(struct rb_node *old, struct rb_node *new);
-};
-
-extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
- void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
-extern void rb_erase_augmented(struct rb_node *node, struct rb_root *root,
- const struct rb_augment_callbacks *augment);
-static inline void
-rb_insert_augmented(struct rb_node *node, struct rb_root *root,
- const struct rb_augment_callbacks *augment)
-{
- __rb_insert_augmented(node, root, augment->rotate);
-}
-
-#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
- rbtype, rbaugmented, rbcompute) \
-static void rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
-{ \
- while (rb != stop) { \
- rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
- rbtype augmented = rbcompute(node); \
- if (node->rbaugmented == augmented) \
- break; \
- node->rbaugmented = augmented; \
- rb = rb_parent(&node->rbfield); \
- } \
-} \
-static void rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
-{ \
- rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
- rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
- new->rbaugmented = old->rbaugmented; \
-} \
-static void rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
-{ \
- rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
- rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
- new->rbaugmented = old->rbaugmented; \
- old->rbaugmented = rbcompute(old); \
-} \
-rbstatic const struct rb_augment_callbacks rbname = { \
- rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
-};
-
-
/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_next(const struct rb_node *);
extern struct rb_node *rb_prev(const struct rb_node *);