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.c57
1 files changed, 26 insertions, 31 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 88511c3805ad..1403e2c8bb3e 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -152,6 +152,20 @@ static inline int tag_get(struct radix_tree_node *node, int tag, int offset)
152} 152}
153 153
154/* 154/*
155 * Returns 1 if any slot in the node has this tag set.
156 * Otherwise returns 0.
157 */
158static inline int any_tag_set(struct radix_tree_node *node, int tag)
159{
160 int idx;
161 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
162 if (node->tags[tag][idx])
163 return 1;
164 }
165 return 0;
166}
167
168/*
155 * Return the maximum key which can be store into a 169 * Return the maximum key which can be store into a
156 * radix tree with height HEIGHT. 170 * radix tree with height HEIGHT.
157 */ 171 */
@@ -185,15 +199,9 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
185 * into the newly-pushed top-level node(s) 199 * into the newly-pushed top-level node(s)
186 */ 200 */
187 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { 201 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
188 int idx;
189
190 tags[tag] = 0; 202 tags[tag] = 0;
191 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 203 if (any_tag_set(root->rnode, tag))
192 if (root->rnode->tags[tag][idx]) { 204 tags[tag] = 1;
193 tags[tag] = 1;
194 break;
195 }
196 }
197 } 205 }
198 206
199 do { 207 do {
@@ -427,13 +435,9 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
427 goto out; 435 goto out;
428 436
429 do { 437 do {
430 int idx;
431
432 tag_clear(pathp->node, tag, pathp->offset); 438 tag_clear(pathp->node, tag, pathp->offset);
433 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 439 if (any_tag_set(pathp->node, tag))
434 if (pathp->node->tags[tag][idx]) 440 goto out;
435 goto out;
436 }
437 pathp--; 441 pathp--;
438 } while (pathp->node); 442 } while (pathp->node);
439out: 443out:
@@ -729,19 +733,14 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
729 733
730 nr_cleared_tags = RADIX_TREE_TAGS; 734 nr_cleared_tags = RADIX_TREE_TAGS;
731 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { 735 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
732 int idx;
733
734 if (tags[tag]) 736 if (tags[tag])
735 continue; 737 continue;
736 738
737 tag_clear(pathp->node, tag, pathp->offset); 739 tag_clear(pathp->node, tag, pathp->offset);
738 740
739 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 741 if (any_tag_set(pathp->node, tag)) {
740 if (pathp->node->tags[tag][idx]) { 742 tags[tag] = 1;
741 tags[tag] = 1; 743 nr_cleared_tags--;
742 nr_cleared_tags--;
743 break;
744 }
745 } 744 }
746 } 745 }
747 pathp--; 746 pathp--;
@@ -770,15 +769,11 @@ EXPORT_SYMBOL(radix_tree_delete);
770 */ 769 */
771int radix_tree_tagged(struct radix_tree_root *root, int tag) 770int radix_tree_tagged(struct radix_tree_root *root, int tag)
772{ 771{
773 int idx; 772 struct radix_tree_node *rnode;
774 773 rnode = root->rnode;
775 if (!root->rnode) 774 if (!rnode)
776 return 0; 775 return 0;
777 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 776 return any_tag_set(rnode, tag);
778 if (root->rnode->tags[tag][idx])
779 return 1;
780 }
781 return 0;
782} 777}
783EXPORT_SYMBOL(radix_tree_tagged); 778EXPORT_SYMBOL(radix_tree_tagged);
784 779