[RFC] radix_tree_destroy?

[Dan Magenheimer <dan.magenheimer@oracle.com>]

I am in need of a radix-tree routine that will efficiently
"destroy" an entire radix tree, but make callbacks to free the
slots.  Is it possible to do that (efficiently) with existing
radix-tree code?  If so, I'd appreciate some guidance.

If not, I'm thinking about submitting a patch (as part of a
larger patchset) that would look something like the patch below.
I'm uncertain of the rcu implications however... because
of the mass destruction, perhaps there could just be a
requirement that the caller must lock the entire tree
prior to the call?

Another option would be for me to do this outside of
radix-tree.c, but then I would need to move some defines and
the definition of the struct radix_tree_node from
radix-tree.c to radix-tree.h

Thanks for any advice!
Dan

P.S. I will be offline for an extended period over the holidays,
so apologies in advance if I am unable to respond quickly.

--- radix-tree.c	2010-10-20 14:30:22.000000000 -0600
+++ radix-tree.patch.c	2010-12-16 16:13:32.672039108 -0700
@@ -1318,6 +1318,42 @@ out:
 }
 EXPORT_SYMBOL(radix_tree_delete);
 
+static void
+radix_tree_node_destroy(struct radix_tree_node *node, unsigned int height,
+			void (*slot_free)(void *))
+{
+	int i;
+
+	if (height == 0)
+		return;
+	for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
+		if (node->slots[i]) {
+			if (height > 1) {
+				radix_tree_node_destroy(node->slots[i],
+					height-1, slot_free);
+				radix_tree_node_free(node->slots[i]);
+				node->slots[i] = NULL;
+			} else
+				slot_free(node->slots[i]);
+		}
+	}
+}
+
+void radix_tree_destroy(struct radix_tree_root *root, void (*slot_free)(void *))
+{
+	if (root->rnode == NULL)
+		return;
+	if (root->height == 0)
+		slot_free(root->rnode);
+	else {
+		radix_tree_node_destroy(root->rnode, root->height, slot_free);
+		radix_tree_node_free(root->rnode);
+		root->height = 0;
+	}
+	root->rnode = NULL;
+}
+EXPORT_SYMBOL(radix_tree_destroy);
+
 /**
  *	radix_tree_tagged - test whether any items in the tree are tagged
  *	@root:		radix tree root

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom policy in Canada: sign http://dissolvethecrtc.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>