Messages in this thread Patch in this message | | | Date | Thu, 16 Dec 2010 08:27:41 -0800 (PST) | From | Dan Magenheimer <> | 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
| |