summaryrefslogtreecommitdiff
path: root/include/linux/rbtree.h
diff options
context:
space:
mode:
authorPallipadi, Venkatesh <venkatesh.pallipadi@intel.com>2010-02-10 15:23:44 -0800
committerH. Peter Anvin <hpa@zytor.com>2010-02-18 15:40:56 -0800
commit17d9ddc72fb8bba0d4f67868c9c612e472a594a9 (patch)
tree51c5e50f91eb060e346c129aa7403624934966d8 /include/linux/rbtree.h
parent724e6d3fe8003c3f60bf404bf22e4e331327c596 (diff)
rbtree: Add support for augmented rbtrees
Add support for augmented rbtrees in core rbtree code. This will be used in subsequent patches, in x86 PAT code, which needs interval trees to efficiently keep track of PAT ranges. Signed-off-by: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com> LKML-Reference: <20100210232343.GA11465@linux-os.sc.intel.com> Signed-off-by: Suresh Siddha <suresh.b.siddha@intel.com> Signed-off-by: H. Peter Anvin <hpa@zytor.com>
Diffstat (limited to 'include/linux/rbtree.h')
-rw-r--r--include/linux/rbtree.h5
1 files changed, 4 insertions, 1 deletions
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 9c295411d01f..8e33a256ea0e 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -110,6 +110,7 @@ struct rb_node
struct rb_root
{
struct rb_node *rb_node;
+ void (*augment_cb)(struct rb_node *node);
};
@@ -129,7 +130,9 @@ static inline void rb_set_color(struct rb_node *rb, int color)
rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}
-#define RB_ROOT (struct rb_root) { NULL, }
+#define RB_ROOT (struct rb_root) { NULL, NULL, }
+#define RB_AUGMENT_ROOT(x) (struct rb_root) { NULL, x}
+
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)