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>
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 9c29541..8e33a25 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -110,6 +110,7 @@
struct rb_root
{
struct rb_node *rb_node;
+ void (*augment_cb)(struct rb_node *node);
};
@@ -129,7 +130,9 @@
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)