aboutsummaryrefslogtreecommitdiffstats
path: root/lib/radix-tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/radix-tree.c')
-rw-r--r--lib/radix-tree.c46
1 files changed, 36 insertions, 10 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 336852f23592..c0bd4a914803 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -253,7 +253,7 @@ int radix_tree_insert(struct radix_tree_root *root,
253 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 253 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
254 254
255 offset = 0; /* uninitialised var warning */ 255 offset = 0; /* uninitialised var warning */
256 while (height > 0) { 256 do {
257 if (slot == NULL) { 257 if (slot == NULL) {
258 /* Have to add a child node. */ 258 /* Have to add a child node. */
259 if (!(slot = radix_tree_node_alloc(root))) 259 if (!(slot = radix_tree_node_alloc(root)))
@@ -271,18 +271,16 @@ int radix_tree_insert(struct radix_tree_root *root,
271 slot = node->slots[offset]; 271 slot = node->slots[offset];
272 shift -= RADIX_TREE_MAP_SHIFT; 272 shift -= RADIX_TREE_MAP_SHIFT;
273 height--; 273 height--;
274 } 274 } while (height > 0);
275 275
276 if (slot != NULL) 276 if (slot != NULL)
277 return -EEXIST; 277 return -EEXIST;
278 278
279 if (node) { 279 BUG_ON(!node);
280 node->count++; 280 node->count++;
281 node->slots[offset] = item; 281 node->slots[offset] = item;
282 BUG_ON(tag_get(node, 0, offset)); 282 BUG_ON(tag_get(node, 0, offset));
283 BUG_ON(tag_get(node, 1, offset)); 283 BUG_ON(tag_get(node, 1, offset));
284 } else
285 root->rnode = item;
286 284
287 return 0; 285 return 0;
288} 286}
@@ -680,6 +678,29 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
680EXPORT_SYMBOL(radix_tree_gang_lookup_tag); 678EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
681 679
682/** 680/**
681 * radix_tree_shrink - shrink height of a radix tree to minimal
682 * @root radix tree root
683 */
684static inline void radix_tree_shrink(struct radix_tree_root *root)
685{
686 /* try to shrink tree height */
687 while (root->height > 1 &&
688 root->rnode->count == 1 &&
689 root->rnode->slots[0]) {
690 struct radix_tree_node *to_free = root->rnode;
691
692 root->rnode = to_free->slots[0];
693 root->height--;
694 /* must only free zeroed nodes into the slab */
695 tag_clear(to_free, 0, 0);
696 tag_clear(to_free, 1, 0);
697 to_free->slots[0] = NULL;
698 to_free->count = 0;
699 radix_tree_node_free(to_free);
700 }
701}
702
703/**
683 * radix_tree_delete - delete an item from a radix tree 704 * radix_tree_delete - delete an item from a radix tree
684 * @root: radix tree root 705 * @root: radix tree root
685 * @index: index key 706 * @index: index key
@@ -755,8 +776,13 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
755 /* Now free the nodes we do not need anymore */ 776 /* Now free the nodes we do not need anymore */
756 for (pathp = orig_pathp; pathp->node; pathp--) { 777 for (pathp = orig_pathp; pathp->node; pathp--) {
757 pathp->node->slots[pathp->offset] = NULL; 778 pathp->node->slots[pathp->offset] = NULL;
758 if (--pathp->node->count) 779 pathp->node->count--;
780
781 if (pathp->node->count) {
782 if (pathp->node == root->rnode)
783 radix_tree_shrink(root);
759 goto out; 784 goto out;
785 }
760 786
761 /* Node with zero slots in use so free it */ 787 /* Node with zero slots in use so free it */
762 radix_tree_node_free(pathp->node); 788 radix_tree_node_free(pathp->node);