On Mon, 2005-08-22 at 15:09 -0700, Andrew Morton wrote:
> James Bottomley <James.Bottomley@xxxxxxxxxxxx> wrote:
> >
> > Of course, if we're going to go to all this trouble, the next question
> > that arises naturally is why not just reuse the radix-tree code to
> > implement idr anyway ... ?
>
> Yes, we could probably have gone that way. radix-tree would need some
> enhancements for the find-next-above thing.
Yes, that's particularly simple (example patch below). However, radix-
tree needs to grow a bitmap index for whether its slots are occupied for
this to be made efficient (it would also help with the gang lookups
too)---at the moment it's O(N); it could be made O(log(N)).
> radix-tree has some features (tags, gang-lookup, gang-lookup-by-tag) which
> idr doesn't. Fitting them all into the one storage API would be nice, I
> guess. radix-tree does potentially use more memory, although that'll only
> be significant for collections which are both large and sparse.
And by definition, idr is trying to discourage sparsity in the
collections.
> Still, people can use either facility at present. The person who does any
> such consolidation would do the kernel-wide migration at the same time.
True. We only seem to have 8 in tree users ... that's not a huge number
to convert.
James
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -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 */
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -133,6 +133,7 @@ int radix_tree_preload(int gfp_mask)
out:
return ret;
}
+EXPORT_SYMBOL(radix_tree_preload);
static inline void tag_set(struct radix_tree_node *node, int tag, int offset)
{
@@ -483,7 +484,9 @@ __lookup(struct radix_tree_root *root, v
unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
- if (slot->slots[i] != NULL)
+ if (max_items == 0 && slot->slots[i] == NULL)
+ goto out;
+ else if (max_items != 0 && slot->slots[i] != NULL)
break;
index &= ~((1UL << shift) - 1);
index += 1UL << shift;
@@ -498,7 +501,9 @@ __lookup(struct radix_tree_root *root, v
for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
index++;
- if (slot->slots[j]) {
+ if (max_items == 0 && slot->slots[j] == NULL)
+ goto out;
+ if (max_items != 0 && slot->slots[j]) {
results[nr_found++] = slot->slots[j];
if (nr_found == max_items)
goto out;
@@ -551,6 +556,28 @@ radix_tree_gang_lookup(struct radix_tree
}
EXPORT_SYMBOL(radix_tree_gang_lookup);
+/**
+ * radix_tree_get_new_above - insert item into first available slot
+ *
+ * @root: radix tree root
+ * @item: item to insert
+ * @starting_index: index to begin the search for a new slot from
+ * @index: actual index found for inserting the item
+ *
+ * Performs an index-ascending scan of the tree for an empty slot. Places
+ * @item in the first empty slot and sets @index to its position.
+ */
+int radix_tree_get_new_above(struct radix_tree_root *root, void *item,
+ unsigned long starting_index,
+ unsigned long *index)
+{
+ if (item == NULL)
+ item = (void *)1UL;
+ __lookup(root, NULL, starting_index, 0, index);
+ return radix_tree_insert(root, *index, item);
+}
+EXPORT_SYMBOL(radix_tree_get_new_above);
+
/*
* FIXME: the two tag_get()s here should use find_next_bit() instead of
* open-coding the search.
-
: send the line "unsubscribe linux-scsi" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
