MIME-Version: 1.0
Message-ID: <62b1cf2f-17ec-45c9-a980-308d9b75cdc5@default>
Date: Thu, 16 Dec 2010 08:27:41 -0800 (PST)
From: Dan Magenheimer <dan.magenheimer@oracle.com>
To: linux-mm@kvack.org, linux-kernel@vger.kernel.org
Cc: dan.magenheimer@oracle.com
Subject: [RFC] radix_tree_destroy?
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 8BIT
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2260
Lines: 73

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 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/