5/5
It always really bothered me that we don't shrink the tree when
truncating it. No actual performance results (though it wouldn't
be hard to concoct some brainless microbenchmark), but it is
simply nicer to do this IMO and will result in more consistent
performance in corner cases.
--
SUSE Labs, Novell Inc.
Actually shrink the height of a radix tree when it is truncated.
Signed-off-by: Nick Piggin <[email protected]>
Index: linux-2.6/lib/radix-tree.c
===================================================================
--- linux-2.6.orig/lib/radix-tree.c
+++ linux-2.6/lib/radix-tree.c
@@ -251,7 +251,7 @@ int radix_tree_insert(struct radix_tree_
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
offset = 0; /* uninitialised var warning */
- while (height > 0) {
+ do {
if (slot == NULL) {
/* Have to add a child node. */
if (!(slot = radix_tree_node_alloc(root)))
@@ -269,18 +269,16 @@ int radix_tree_insert(struct radix_tree_
slot = node->slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
- }
+ } while (height > 0);
if (slot != NULL)
return -EEXIST;
- if (node) {
- node->count++;
- node->slots[offset] = item;
- BUG_ON(tag_get(node, 0, offset));
- BUG_ON(tag_get(node, 1, offset));
- } else
- root->rnode = item;
+ BUG_ON(!node);
+ node->count++;
+ node->slots[offset] = item;
+ BUG_ON(tag_get(node, 0, offset));
+ BUG_ON(tag_get(node, 1, offset));
return 0;
}
@@ -678,6 +676,29 @@ radix_tree_gang_lookup_tag(struct radix_
EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
/**
+ * radix_tree_shrink - shrink height of a radix tree to minimal
+ * @root radix tree root
+ */
+static inline void radix_tree_shrink(struct radix_tree_root *root)
+{
+ /* try to shrink tree height */
+ while (root->height > 1 &&
+ root->rnode->count == 1 &&
+ root->rnode->slots[0]) {
+ struct radix_tree_node *to_free = root->rnode;
+
+ root->rnode = to_free->slots[0];
+ root->height--;
+ /* must only free zeroed nodes into the slab */
+ tag_clear(to_free, 0, 0);
+ tag_clear(to_free, 1, 0);
+ to_free->slots[0] = NULL;
+ to_free->count = 0;
+ radix_tree_node_free(to_free);
+ }
+}
+
+/**
* radix_tree_delete - delete an item from a radix tree
* @root: radix tree root
* @index: index key
@@ -753,8 +774,13 @@ void *radix_tree_delete(struct radix_tre
/* Now free the nodes we do not need anymore */
for (pathp = orig_pathp; pathp->node; pathp--) {
pathp->node->slots[pathp->offset] = NULL;
- if (--pathp->node->count)
+ pathp->node->count--;
+
+ if (pathp->node->count) {
+ if (pathp->node == root->rnode)
+ radix_tree_shrink(root);
goto out;
+ }
/* Node with zero slots in use so free it */
radix_tree_node_free(pathp->node);
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
