add idr replacement functionality to radix tree

The current idr code suffers from three faults:

1) idr_pre_get() and idr_remove() take an internal lock, so can't be called from interrupt level
2) idr_pre_get is racy, so you need to check for an EAGAIN return from idr_get_new() and retry ... several callers seem to forget this
3) idr_pre_get() is a requirement, even if idr_get_new() is called from non-atomic contexts

The radix tree code avoids all of these problems and runs completely without internal locks. Since idr is also a radix tree implementation, it would be perfectly possible to graft all of the radix tree fixes into it. However, the idr API would have to change (radix tree uses per cpu arrays in its prealloc routines necessitating a radix_tree_prealloc_end ()). A better course of action seems to be to combine idr and radix tree, since they share so much code anyway, which is what this patch does.

---

A separate set of patches will be posted converting all the current idr users to be radix tree users and then removing the idr code.

Applies on top of the prior patch converting the gang lookup to bitmaps.

James

 include/linux/radix-tree.h |   10 +++
 lib/radix-tree.c           |  129 ++++++++++++++++++++++++++++++++++++++-------
 2 files changed, 120 insertions(+), 19 deletions(-)

@@ -62,10 +62,20 @@ unsigned int
 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
 		unsigned long first_index, unsigned int max_items, int tag);
 int radix_tree_tagged(struct radix_tree_root *root, int tag);
+int radix_tree_get_new_above(struct radix_tree_root *root, void *item,
+			     unsigned long starting_index,
+			     unsigned long *index);
 
 static inline void radix_tree_preload_end(void)
 {
 	preempt_enable();
 }
 
+static inline int radix_tree_get_new(struct radix_tree_root *root, void *item,
+				     unsigned long *index)
+{
+	return radix_tree_get_new_above(root, item, 0, index);
+}
+
+
 #endif /* _LINUX_RADIX_TREE_H */