Radix tree replace

Replace an entry in radix tree (Note Nick Piggin has a different implementation
that allows the replacement of an element in a radix tree via a pointer.
We may have to switch to that implementation)

Signed-off-by: Mike Kravetz <kravetz@us.ibm.com>
Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.14-rc5-mm1/include/linux/radix-tree.h
===================================================================
--- linux-2.6.14-rc5-mm1.orig/include/linux/radix-tree.h	2005-10-31 14:11:10.000000000 -0800
+++ linux-2.6.14-rc5-mm1/include/linux/radix-tree.h	2005-11-02 13:29:54.000000000 -0800
@@ -48,6 +48,7 @@ int radix_tree_insert(struct radix_tree_
 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
 void *radix_tree_delete(struct radix_tree_root *, unsigned long);
+void *radix_tree_replace(struct radix_tree_root *, unsigned long, void *);
 unsigned int
 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 			unsigned long first_index, unsigned int max_items);
Index: linux-2.6.14-rc5-mm1/lib/radix-tree.c
===================================================================
--- linux-2.6.14-rc5-mm1.orig/lib/radix-tree.c	2005-10-31 14:11:10.000000000 -0800
+++ linux-2.6.14-rc5-mm1/lib/radix-tree.c	2005-11-02 13:29:54.000000000 -0800
@@ -765,6 +765,50 @@ out:
 EXPORT_SYMBOL(radix_tree_delete);
 
 /**
+ *	radix_tree_replace    -    replace an item in a radix tree
+ *	@root:		radix tree root
+ *	@index:		index key
+ *	@item:		item to insert
+ *
+ *	Replace the item at @index with @item.
+ *	Returns the address of the deleted item, or NULL if it was not present.
+ */
+void *radix_tree_replace(struct radix_tree_root *root,
+					unsigned long index, void *item)
+{
+	struct radix_tree_node *slot, *node;
+	unsigned int height, shift, offset;
+
+	height = root->height;
+	if (index > radix_tree_maxindex(height))
+		goto not_present;
+
+	node = NULL;
+	slot = root->rnode;
+	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
+
+	offset = 0;
+	while (height > 0) {
+		if (slot == NULL)
+			goto not_present;
+
+		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+		node = slot;
+		slot = slot->slots[offset];
+		shift -= RADIX_TREE_MAP_SHIFT;
+		height--;
+	}
+
+	if (node) {
+		node->slots[offset] = item;
+		return slot;
+	}
+not_present:
+	return NULL;
+}
+EXPORT_SYMBOL(radix_tree_replace);
+
+/**
  *	radix_tree_tagged - test whether any items in the tree are tagged
  *	@root:		radix tree root
  *	@tag:		tag to test