lkml.org 
[lkml]   [2010]   [Dec]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[RFC] radix_tree_destroy?
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

\
 
 \ /
  Last update: 2010-12-16 17:31    [from the cache]
©2003-2011 Jasper Spaans