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    [W:0.020 / U:121.488 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site