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.c49
1 files changed, 27 insertions, 22 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 1e5b17dc7e3d..7097bb239e40 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -37,7 +37,6 @@
37#else 37#else
38#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ 38#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
39#endif 39#endif
40#define RADIX_TREE_TAGS 2
41 40
42#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) 41#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
43#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) 42#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
@@ -48,7 +47,7 @@
48struct radix_tree_node { 47struct radix_tree_node {
49 unsigned int count; 48 unsigned int count;
50 void *slots[RADIX_TREE_MAP_SIZE]; 49 void *slots[RADIX_TREE_MAP_SIZE];
51 unsigned long tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS]; 50 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
52}; 51};
53 52
54struct radix_tree_path { 53struct radix_tree_path {
@@ -135,17 +134,20 @@ out:
135 return ret; 134 return ret;
136} 135}
137 136
138static inline void tag_set(struct radix_tree_node *node, int tag, int offset) 137static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
138 int offset)
139{ 139{
140 __set_bit(offset, node->tags[tag]); 140 __set_bit(offset, node->tags[tag]);
141} 141}
142 142
143static inline void tag_clear(struct radix_tree_node *node, int tag, int offset) 143static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
144 int offset)
144{ 145{
145 __clear_bit(offset, node->tags[tag]); 146 __clear_bit(offset, node->tags[tag]);
146} 147}
147 148
148static inline int tag_get(struct radix_tree_node *node, int tag, int offset) 149static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
150 int offset)
149{ 151{
150 return test_bit(offset, node->tags[tag]); 152 return test_bit(offset, node->tags[tag]);
151} 153}
@@ -154,7 +156,7 @@ static inline int tag_get(struct radix_tree_node *node, int tag, int offset)
154 * Returns 1 if any slot in the node has this tag set. 156 * Returns 1 if any slot in the node has this tag set.
155 * Otherwise returns 0. 157 * Otherwise returns 0.
156 */ 158 */
157static inline int any_tag_set(struct radix_tree_node *node, int tag) 159static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
158{ 160{
159 int idx; 161 int idx;
160 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 162 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
@@ -180,7 +182,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
180{ 182{
181 struct radix_tree_node *node; 183 struct radix_tree_node *node;
182 unsigned int height; 184 unsigned int height;
183 char tags[RADIX_TREE_TAGS]; 185 char tags[RADIX_TREE_MAX_TAGS];
184 int tag; 186 int tag;
185 187
186 /* Figure out what the height should be. */ 188 /* Figure out what the height should be. */
@@ -197,7 +199,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
197 * Prepare the tag status of the top-level node for propagation 199 * Prepare the tag status of the top-level node for propagation
198 * into the newly-pushed top-level node(s) 200 * into the newly-pushed top-level node(s)
199 */ 201 */
200 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { 202 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
201 tags[tag] = 0; 203 tags[tag] = 0;
202 if (any_tag_set(root->rnode, tag)) 204 if (any_tag_set(root->rnode, tag))
203 tags[tag] = 1; 205 tags[tag] = 1;
@@ -211,7 +213,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
211 node->slots[0] = root->rnode; 213 node->slots[0] = root->rnode;
212 214
213 /* Propagate the aggregated tag info into the new root */ 215 /* Propagate the aggregated tag info into the new root */
214 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { 216 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
215 if (tags[tag]) 217 if (tags[tag])
216 tag_set(node, tag, 0); 218 tag_set(node, tag, 0);
217 } 219 }
@@ -349,14 +351,15 @@ EXPORT_SYMBOL(radix_tree_lookup);
349 * @index: index key 351 * @index: index key
350 * @tag: tag index 352 * @tag: tag index
351 * 353 *
352 * Set the search tag corresponging to @index in the radix tree. From 354 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
355 * corresponding to @index in the radix tree. From
353 * the root all the way down to the leaf node. 356 * the root all the way down to the leaf node.
354 * 357 *
355 * Returns the address of the tagged item. Setting a tag on a not-present 358 * Returns the address of the tagged item. Setting a tag on a not-present
356 * item is a bug. 359 * item is a bug.
357 */ 360 */
358void *radix_tree_tag_set(struct radix_tree_root *root, 361void *radix_tree_tag_set(struct radix_tree_root *root,
359 unsigned long index, int tag) 362 unsigned long index, unsigned int tag)
360{ 363{
361 unsigned int height, shift; 364 unsigned int height, shift;
362 struct radix_tree_node *slot; 365 struct radix_tree_node *slot;
@@ -390,7 +393,8 @@ EXPORT_SYMBOL(radix_tree_tag_set);
390 * @index: index key 393 * @index: index key
391 * @tag: tag index 394 * @tag: tag index
392 * 395 *
393 * Clear the search tag corresponging to @index in the radix tree. If 396 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
397 * corresponding to @index in the radix tree. If
394 * this causes the leaf node to have no tags set then clear the tag in the 398 * this causes the leaf node to have no tags set then clear the tag in the
395 * next-to-leaf node, etc. 399 * next-to-leaf node, etc.
396 * 400 *
@@ -398,7 +402,7 @@ EXPORT_SYMBOL(radix_tree_tag_set);
398 * has the same return value and semantics as radix_tree_lookup(). 402 * has the same return value and semantics as radix_tree_lookup().
399 */ 403 */
400void *radix_tree_tag_clear(struct radix_tree_root *root, 404void *radix_tree_tag_clear(struct radix_tree_root *root,
401 unsigned long index, int tag) 405 unsigned long index, unsigned int tag)
402{ 406{
403 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; 407 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
404 struct radix_tree_node *slot; 408 struct radix_tree_node *slot;
@@ -450,7 +454,7 @@ EXPORT_SYMBOL(radix_tree_tag_clear);
450 * radix_tree_tag_get - get a tag on a radix tree node 454 * radix_tree_tag_get - get a tag on a radix tree node
451 * @root: radix tree root 455 * @root: radix tree root
452 * @index: index key 456 * @index: index key
453 * @tag: tag index 457 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
454 * 458 *
455 * Return values: 459 * Return values:
456 * 460 *
@@ -459,7 +463,7 @@ EXPORT_SYMBOL(radix_tree_tag_clear);
459 * -1: tag present, unset 463 * -1: tag present, unset
460 */ 464 */
461int radix_tree_tag_get(struct radix_tree_root *root, 465int radix_tree_tag_get(struct radix_tree_root *root,
462 unsigned long index, int tag) 466 unsigned long index, unsigned int tag)
463{ 467{
464 unsigned int height, shift; 468 unsigned int height, shift;
465 struct radix_tree_node *slot; 469 struct radix_tree_node *slot;
@@ -592,7 +596,7 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
592 */ 596 */
593static unsigned int 597static unsigned int
594__lookup_tag(struct radix_tree_root *root, void **results, unsigned long index, 598__lookup_tag(struct radix_tree_root *root, void **results, unsigned long index,
595 unsigned int max_items, unsigned long *next_index, int tag) 599 unsigned int max_items, unsigned long *next_index, unsigned int tag)
596{ 600{
597 unsigned int nr_found = 0; 601 unsigned int nr_found = 0;
598 unsigned int shift; 602 unsigned int shift;
@@ -646,7 +650,7 @@ out:
646 * @results: where the results of the lookup are placed 650 * @results: where the results of the lookup are placed
647 * @first_index: start the lookup from this key 651 * @first_index: start the lookup from this key
648 * @max_items: place up to this many items at *results 652 * @max_items: place up to this many items at *results
649 * @tag: the tag index 653 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
650 * 654 *
651 * Performs an index-ascending scan of the tree for present items which 655 * Performs an index-ascending scan of the tree for present items which
652 * have the tag indexed by @tag set. Places the items at *@results and 656 * have the tag indexed by @tag set. Places the items at *@results and
@@ -654,7 +658,8 @@ out:
654 */ 658 */
655unsigned int 659unsigned int
656radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, 660radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
657 unsigned long first_index, unsigned int max_items, int tag) 661 unsigned long first_index, unsigned int max_items,
662 unsigned int tag)
658{ 663{
659 const unsigned long max_index = radix_tree_maxindex(root->height); 664 const unsigned long max_index = radix_tree_maxindex(root->height);
660 unsigned long cur_index = first_index; 665 unsigned long cur_index = first_index;
@@ -716,7 +721,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
716 struct radix_tree_node *slot; 721 struct radix_tree_node *slot;
717 unsigned int height, shift; 722 unsigned int height, shift;
718 void *ret = NULL; 723 void *ret = NULL;
719 char tags[RADIX_TREE_TAGS]; 724 char tags[RADIX_TREE_MAX_TAGS];
720 int nr_cleared_tags; 725 int nr_cleared_tags;
721 int tag; 726 int tag;
722 int offset; 727 int offset;
@@ -751,7 +756,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
751 * Clear all tags associated with the just-deleted item 756 * Clear all tags associated with the just-deleted item
752 */ 757 */
753 nr_cleared_tags = 0; 758 nr_cleared_tags = 0;
754 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { 759 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
755 tags[tag] = 1; 760 tags[tag] = 1;
756 if (tag_get(pathp->node, tag, pathp->offset)) { 761 if (tag_get(pathp->node, tag, pathp->offset)) {
757 tag_clear(pathp->node, tag, pathp->offset); 762 tag_clear(pathp->node, tag, pathp->offset);
@@ -763,7 +768,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
763 } 768 }
764 769
765 for (pathp--; nr_cleared_tags && pathp->node; pathp--) { 770 for (pathp--; nr_cleared_tags && pathp->node; pathp--) {
766 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { 771 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
767 if (tags[tag]) 772 if (tags[tag])
768 continue; 773 continue;
769 774
@@ -801,7 +806,7 @@ EXPORT_SYMBOL(radix_tree_delete);
801 * @root: radix tree root 806 * @root: radix tree root
802 * @tag: tag to test 807 * @tag: tag to test
803 */ 808 */
804int radix_tree_tagged(struct radix_tree_root *root, int tag) 809int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
805{ 810{
806 struct radix_tree_node *rnode; 811 struct radix_tree_node *rnode;
807 rnode = root->rnode; 812 rnode = root->rnode;