diff --git a/include/linux/rangetree.h b/include/linux/rangetree.h
new file mode 100644
index 0000000..998ebcc
--- /dev/null
+++ b/include/linux/rangetree.h
@@ -0,0 +1,35 @@
+#ifndef _LINUX_RANGETREE_H
+#define _LINUX_RANGETREE_H
+
+#include <linux/types.h>
+#include <linux/fs.h>
+
+struct range_tree_node {
+	struct range_tree_node *parent;
+	struct range_tree_node *left;
+	struct range_tree_node *right;
+	u64 start;
+	u64 end;
+};
+
+static inline void range_tree_node_init(struct range_tree_node *node)
+{
+	node->parent = NULL;
+	node->left = NULL;
+	node->right = NULL;
+	node->start = 0;
+	node->end = 0;
+}
+
+extern struct range_tree_node *range_tree_in_range(struct range_tree_node *root,
+							 u64 start, u64 end);
+extern struct range_tree_node *range_tree_in_range_adjacent(
+						struct range_tree_node *root,
+							 u64 start, u64 end);
+extern struct range_tree_node *range_tree_add(struct range_tree_node *root,
+						struct range_tree_node *node);
+extern struct range_tree_node *range_tree_remove(struct range_tree_node *root,
+						struct range_tree_node *node);
+#endif
+
+
diff --git a/lib/Makefile b/lib/Makefile
index 18515f0..f43ef0d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 idr.o int_sqrt.o extable.o prio_tree.o \
 	 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
 	 proportions.o prio_heap.o ratelimit.o show_mem.o \
-	 is_single_threaded.o plist.o decompress.o
+	 is_single_threaded.o plist.o decompress.o rangetree.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/rangetree.c b/lib/rangetree.c
new file mode 100644
index 0000000..db20665
--- /dev/null
+++ b/lib/rangetree.c
@@ -0,0 +1,325 @@
+#include <linux/rangetree.h>
+#include <linux/kernel.h>
+#include <linux/slab.h>
+
+/**
+ * rotate_right - Splay tree helper
+ * @node: node to be rotated right
+ * @root: tree root
+ *
+ * Returns the tree root after rotating the node right
+ */
+static struct range_tree_node *rotate_right(struct range_tree_node *node,
+						struct range_tree_node *root)
+{
+	struct range_tree_node *new_root, *new_right;
+
+	if (!node->left)
+		return root;
+
+	new_root = node->left;
+	new_right = node;
+
+	if (root == node)
+		root = new_root;
+
+	new_right->left = new_root->right;
+	new_root->parent = new_right->parent;
+	if (new_root->parent) {
+		if (new_root->parent->right == new_right)
+			new_root->parent->right = new_root;
+		else
+			new_root->parent->left = new_root;
+	}
+	new_right->parent = new_root;
+
+	new_root->right = new_right;
+
+	if (new_right->left)
+		new_right->left->parent = new_right;
+
+
+	/* Paranoid sanity checking */
+	if (new_root->left)
+		BUG_ON(new_root->left->parent != new_root);
+	if (new_root->right)
+		BUG_ON(new_root->right->parent != new_root);
+	if (new_right->left)
+		BUG_ON(new_right->left->parent != new_right);
+	if (new_right->right)
+		BUG_ON(new_right->right->parent != new_right);
+
+
+	return root;
+
+}
+
+/**
+ * rotate_left - Splay tree helper
+ * @node: node to be rotated left
+ * @root: tree root
+ *
+ * Returns the tree root after rotating the node left
+ */
+static struct range_tree_node *rotate_left(struct range_tree_node *node,
+						struct range_tree_node *root)
+{
+	struct range_tree_node *new_root, *new_left;
+
+	if (!node->right)
+		return root;
+
+	new_root = node->right;
+	new_left = node;
+
+	if (root == node)
+		root = new_root;
+
+	new_left->right = new_root->left;
+	if (new_left->right)
+		new_left->right->parent = new_left;
+	new_root->parent = new_left->parent;
+	if (new_root->parent) {
+		if (new_root->parent->left == new_left)
+			new_root->parent->left = new_root;
+		else
+			new_root->parent->right = new_root;
+	}
+	new_left->parent = new_root;
+	new_root->left = new_left;
+
+
+	/* Paranoid sanity checking */
+	if (new_root->left)
+		BUG_ON(new_root->left->parent != new_root);
+	if (new_root->right)
+		BUG_ON(new_root->right->parent != new_root);
+	if (new_left->left)
+		BUG_ON(new_left->left->parent != new_left);
+	if (new_left->right)
+		BUG_ON(new_left->right->parent != new_left);
+
+	return root;
+}
+
+/**
+ * splay_tree Splays a node to the top of a tree
+ * @root: root of the splay tree
+ * @node: node to be splayed to the root
+ *
+ * Returns the root of a tree after splaying
+ */
+static struct range_tree_node *splay_tree(struct range_tree_node *root,
+						struct range_tree_node *node)
+{
+restart:
+	if (root == node)
+		return root;
+
+	if (node->parent == root) {
+		if (root->left == node)
+			root = rotate_right(root, root);
+		else
+			root = rotate_left(root, root);
+		return root;
+	} else {
+		struct range_tree_node *parent, *grandparent;
+
+		parent = node->parent;
+		grandparent = parent->parent;
+
+		if ((node == parent->left) && (parent == grandparent->left)) {
+			root = rotate_right(grandparent, root);
+			root = rotate_right(parent, root);
+		} else if ((node == parent->right) &&
+					(parent == grandparent->right)) {
+			root = rotate_left(grandparent, root);
+			root = rotate_left(parent, root);
+		} else if ((node == parent->right) &&
+					(parent == grandparent->left)) {
+			root = rotate_left(parent, root);
+			root = rotate_right(grandparent, root);
+		} else if ((node == parent->left) &&
+					(parent == grandparent->right)) {
+			root = rotate_right(parent, root);
+			root = rotate_left(grandparent, root);
+		} else {
+			BUG_ON(1); /* Something is odd */
+		}
+		goto restart;
+	}
+}
+
+
+/**
+ * range_tree_in_range - Returns the first node that overlaps with the
+ *                       given range
+ * @root: range_tree root
+ * @start: range start
+ * @end: range end
+ *
+ */
+struct range_tree_node *range_tree_in_range(struct range_tree_node *root,
+						u64 start, u64 end)
+{
+	struct range_tree_node *candidate = root;
+
+	if (!candidate)
+		return 0;
+restart:
+	if (end < candidate->start) {
+		if (candidate->left) {
+			candidate = candidate->left;
+			goto restart;
+		}
+	} else if (start > candidate->end) {
+		if (candidate->right) {
+			candidate = candidate->right;
+			goto restart;
+		}
+	} else
+		return candidate;
+	return 0;
+}
+
+
+/**
+ * range_tree_in_range - Returns the first node that overlaps or is adjacent
+ *                       with the given range
+ * @root: range_tree root
+ * @start: range start
+ * @end: range end
+ *
+ */
+struct range_tree_node *range_tree_in_range_adjacent(
+					struct range_tree_node *root,
+					u64 start, u64 end)
+{
+	struct range_tree_node *candidate = root;
+
+	if (!candidate)
+		return 0;
+restart:
+	if (end + 1 < candidate->start) {
+		if (candidate->left) {
+			candidate = candidate->left;
+			goto restart;
+		}
+	} else if (start > candidate->end + 1) {
+		if (candidate->right) {
+			candidate = candidate->right;
+			goto restart;
+		}
+	} else
+		return candidate;
+	return 0;
+}
+
+/**
+ * range_tree_add - Add a node to a range tree
+ * @root: range tree to be added to
+ * @node: range_tree_node to be added
+ *
+ * Adds a node to the range tree.
+ */
+struct range_tree_node *range_tree_add(struct range_tree_node *root,
+					struct range_tree_node *node)
+{
+	struct range_tree_node *candidate;
+	/* make sure its not connected */
+	BUG_ON(node->parent || node->left || node->right);
+
+	if (!root)
+		return node;
+
+	candidate = root;
+restart:
+	if (node->start < candidate->start) {
+		if (candidate->left) {
+			candidate = candidate->left;
+			goto restart;
+		}
+		candidate->left = node;
+		node->parent = candidate;
+	} else if (node->start > candidate->start) {
+		if (candidate->right) {
+			candidate = candidate->right;
+			goto restart;
+		}
+		candidate->right = node;
+		node->parent = candidate;
+	}
+
+	root = splay_tree(root, node);
+	return root;
+}
+
+/**
+ * range_tree_merge - Helper to merge two range sub-trees
+ * @left: left subtree to be merged
+ * @right: right subtree to be merged
+ *
+ * Returns a merged range tree of two subtrees. left subtree
+ * must be all less then the right subtree.
+ */
+static struct range_tree_node *range_tree_merge(struct range_tree_node *left,
+						struct range_tree_node *right)
+{
+	struct range_tree_node *merge;
+
+	if (!left)
+		return right;
+	if (!right)
+		return left;
+
+	merge = left;
+	/* grab the right-most node on the left side */
+	while (merge->right)
+		merge = merge->right;
+	merge->right = right;
+	if (right)
+		right->parent = merge;
+
+	return left;
+}
+
+/**
+ * null_node: Helper that clears node data
+ * @node: Node to be cleared
+ */
+static void null_node(struct range_tree_node *node)
+{
+	node->left = node->right = node->parent = NULL;
+	node->start = node->end = 0;
+}
+
+/**
+ * range_tree_remove: Removes a given node from the tree
+ * @root: root of tree
+ * @node: Node to be removed
+ *
+ * Removes a node and splays the tree
+ */
+struct range_tree_node *range_tree_remove(struct range_tree_node *root,
+						struct range_tree_node *node)
+{
+	struct range_tree_node *subtree;
+
+	subtree = range_tree_merge(node->left, node->right);
+
+	if (subtree)
+		subtree->parent = node->parent;
+
+	if (node->parent && node->parent->left == node)
+		node->parent->left = subtree;
+	if (node->parent && node->parent->right == node)
+		node->parent->right = subtree;
+
+	null_node(node);
+	if (node == root)
+		return subtree;
+
+	if (subtree)
+		root = splay_tree(root, subtree);
+	return root;
+}
