Thomas Schlichter <schlicht@uni-mannheim.de> wrote:
>
> > you can just do
> >
> > if (radix_tree_delete(...) != -ENOENT)
> > list_del(...)
> >
> > + read_swap_cache_async(entry);
>
> Sorry, but I think I can not. The list_del() needs the value returned by
> radix_tree_lookup(), so I can not kick it...
OK, I'll change radix_tree_delete() to return the deleted object address if
it was found, else NULL. That's a better API.
> Do you know how expensive the radix_tree_lookup() is? O(1) or O(log(n))?? For
> my shame I do not really know that data structure... :-(
It is proportional to
log_base_64(largest index which the tree has ever stored)
log_base_64: because each node has 64 slots. Each time maxindex grows by a
factor of 64 we need to introduce a new level.
"largest index ever": because we do not (and cannot feasibly) reduce the
height when items are removed.
> > It might make sense to poke the speculative swapin code in the page-freeing
> > path too.
>
> I wanted to do this but don't know which function is the correct one for this.
> But I will search harder... or can you give me a hint?
free_pages_bulk() would probably suit.
diff -puN fs/nfs/write.c~radix_tree_delete-api-cleanup fs/nfs/write.c
diff -puN lib/radix-tree.c~radix_tree_delete-api-cleanup lib/radix-tree.c
--- 25/lib/radix-tree.c~radix_tree_delete-api-cleanup Fri Apr 11 14:30:30 2003
+++ 25-akpm/lib/radix-tree.c Fri Apr 11 14:30:30 2003
@@ -349,15 +349,18 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
* @index: index key
*
* Remove the item at @index from the radix tree rooted at @root.
+ *
+ * Returns the address of the deleted item, or NULL if it was not present.
*/
-int radix_tree_delete(struct radix_tree_root *root, unsigned long index)
+void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
unsigned int height, shift;
+ void *ret = NULL;
height = root->height;
if (index > radix_tree_maxindex(height))
- return -ENOENT;
+ goto out;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
pathp->node = NULL;
@@ -365,7 +368,7 @@ int radix_tree_delete(struct radix_tree_
while (height > 0) {
if (*pathp->slot == NULL)
- return -ENOENT;
+ goto out;
pathp[1].node = *pathp[0].slot;
pathp[1].slot = (struct radix_tree_node **)
@@ -375,8 +378,9 @@ int radix_tree_delete(struct radix_tree_
height--;
}
- if (*pathp[0].slot == NULL)
- return -ENOENT;
+ ret = *pathp[0].slot;
+ if (ret == NULL)
+ goto out;
*pathp[0].slot = NULL;
while (pathp[0].node && --pathp[0].node->count == 0) {
@@ -387,8 +391,8 @@ int radix_tree_delete(struct radix_tree_
if (root->rnode == NULL)
root->height = 0; /* Empty tree, we can reset the height */
-
- return 0;
+out:
+ return ret;
}
EXPORT_SYMBOL(radix_tree_delete);
diff -puN mm/filemap.c~radix_tree_delete-api-cleanup mm/filemap.c
diff -puN include/linux/radix-tree.h~radix_tree_delete-api-cleanup include/linux/radix-tree.h
--- 25/include/linux/radix-tree.h~radix_tree_delete-api-cleanup Fri Apr 11 14:30:30 2003
+++ 25-akpm/include/linux/radix-tree.h Fri Apr 11 14:30:30 2003
@@ -43,7 +43,7 @@ do { \
extern int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
extern void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
-extern int radix_tree_delete(struct radix_tree_root *, unsigned long);
+extern void *radix_tree_delete(struct radix_tree_root *, unsigned long);
extern unsigned int
radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
unsigned long first_index, unsigned int max_items);
_
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Tue Apr 15 2003 - 22:00:25 EST