88 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,  in tag_set()  argument
91 	__set_bit(offset, node->tags[tag]);  in tag_set()
94 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,  in tag_clear()  argument
97 	__clear_bit(offset, node->tags[tag]);  in tag_clear()
100 static inline int tag_get(struct radix_tree_node *node, unsigned int tag,  in tag_get()  argument
103 	return test_bit(offset, node->tags[tag]);  in tag_get()
130 static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)  in any_tag_set()  argument
134 		if (node->tags[tag][idx])  in any_tag_set()
221 	struct radix_tree_node *node =  in radix_tree_node_rcu_free()  local
231 		tag_clear(node, i, 0);  in radix_tree_node_rcu_free()
233 	node->slots[0] = NULL;  in radix_tree_node_rcu_free()
234 	node->count = 0;  in radix_tree_node_rcu_free()
236 	kmem_cache_free(radix_tree_node_cachep, node);  in radix_tree_node_rcu_free()
240 radix_tree_node_free(struct radix_tree_node *node)  in radix_tree_node_free()  argument
242 	call_rcu(&node->rcu_head, radix_tree_node_rcu_free);  in radix_tree_node_free()
257 	struct radix_tree_node *node;  in __radix_tree_preload()  local
264 		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);  in __radix_tree_preload()
265 		if (node == NULL)  in __radix_tree_preload()
270 			node->private_data = rtp->nodes;  in __radix_tree_preload()
271 			rtp->nodes = node;  in __radix_tree_preload()
274 			kmem_cache_free(radix_tree_node_cachep, node);  in __radix_tree_preload()
328 	struct radix_tree_node *node;  in radix_tree_extend()  local
345 		if (!(node = radix_tree_node_alloc(root)))  in radix_tree_extend()
351 				tag_set(node, tag, 0);  in radix_tree_extend()
357 		node->path = newheight;  in radix_tree_extend()
358 		node->count = 1;  in radix_tree_extend()
359 		node->parent = NULL;  in radix_tree_extend()
363 			slot->parent = node;  in radix_tree_extend()
365 		node->slots[0] = slot;  in radix_tree_extend()
366 		node = ptr_to_indirect(node);  in radix_tree_extend()
367 		rcu_assign_pointer(root->rnode, node);  in radix_tree_extend()
393 	struct radix_tree_node *node = NULL, *slot;  in __radix_tree_create()  local
416 			slot->parent = node;  in __radix_tree_create()
417 			if (node) {  in __radix_tree_create()
418 				rcu_assign_pointer(node->slots[offset], slot);  in __radix_tree_create()
419 				node->count++;  in __radix_tree_create()
427 		node = slot;  in __radix_tree_create()
428 		slot = node->slots[offset];  in __radix_tree_create()
434 		*nodep = node;  in __radix_tree_create()
436 		*slotp = node ? node->slots + offset : (void **)&root->rnode;  in __radix_tree_create()
451 	struct radix_tree_node *node;  in radix_tree_insert()  local
457 	error = __radix_tree_create(root, index, &node, &slot);  in radix_tree_insert()
464 	if (node) {  in radix_tree_insert()
465 		node->count++;  in radix_tree_insert()
466 		BUG_ON(tag_get(node, 0, index & RADIX_TREE_MAP_MASK));  in radix_tree_insert()
467 		BUG_ON(tag_get(node, 1, index & RADIX_TREE_MAP_MASK));  in radix_tree_insert()
494 	struct radix_tree_node *node, *parent;  in __radix_tree_lookup()  local
498 	node = rcu_dereference_raw(root->rnode);  in __radix_tree_lookup()
499 	if (node == NULL)  in __radix_tree_lookup()
502 	if (!radix_tree_is_indirect_ptr(node)) {  in __radix_tree_lookup()
510 		return node;  in __radix_tree_lookup()
512 	node = indirect_to_ptr(node);  in __radix_tree_lookup()
514 	height = node->path & RADIX_TREE_HEIGHT_MASK;  in __radix_tree_lookup()
521 		parent = node;  in __radix_tree_lookup()
522 		slot = node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK);  in __radix_tree_lookup()
523 		node = rcu_dereference_raw(*slot);  in __radix_tree_lookup()
524 		if (node == NULL)  in __radix_tree_lookup()
535 	return node;  in __radix_tree_lookup()
641 	struct radix_tree_node *node = NULL;  in radix_tree_tag_clear()  local
659 		node = slot;  in radix_tree_tag_clear()
666 	while (node) {  in radix_tree_tag_clear()
667 		if (!tag_get(node, tag, offset))  in radix_tree_tag_clear()
669 		tag_clear(node, tag, offset);  in radix_tree_tag_clear()
670 		if (any_tag_set(node, tag))  in radix_tree_tag_clear()
675 		node = node->parent;  in radix_tree_tag_clear()
706 	struct radix_tree_node *node;  in radix_tree_tag_get()  local
712 	node = rcu_dereference_raw(root->rnode);  in radix_tree_tag_get()
713 	if (node == NULL)  in radix_tree_tag_get()
716 	if (!radix_tree_is_indirect_ptr(node))  in radix_tree_tag_get()
718 	node = indirect_to_ptr(node);  in radix_tree_tag_get()
720 	height = node->path & RADIX_TREE_HEIGHT_MASK;  in radix_tree_tag_get()
729 		if (node == NULL)  in radix_tree_tag_get()
733 		if (!tag_get(node, tag, offset))  in radix_tree_tag_get()
737 		node = rcu_dereference_raw(node->slots[offset]);  in radix_tree_tag_get()
756 	struct radix_tree_node *rnode, *node;  in radix_tree_next_chunk()  local
796 	node = rnode;  in radix_tree_next_chunk()
799 				!test_bit(offset, node->tags[tag]) :  in radix_tree_next_chunk()
800 				!node->slots[offset]) {  in radix_tree_next_chunk()
807 						node->tags[tag],  in radix_tree_next_chunk()
812 					if (node->slots[offset])  in radix_tree_next_chunk()
828 		node = rcu_dereference_raw(node->slots[offset]);  in radix_tree_next_chunk()
829 		if (node == NULL)  in radix_tree_next_chunk()
845 		iter->tags = node->tags[tag][tag_long] >> tag_bit;  in radix_tree_next_chunk()
850 				iter->tags |= node->tags[tag][tag_long + 1] <<  in radix_tree_next_chunk()
857 	return node->slots + offset;  in radix_tree_next_chunk()
894 	struct radix_tree_node *node = NULL;  in radix_tree_range_tag_if_tagged()  local
930 			node = slot;  in radix_tree_range_tag_if_tagged()
941 		while (node) {  in radix_tree_range_tag_if_tagged()
946 			if (tag_get(node, settag, offset))  in radix_tree_range_tag_if_tagged()
948 			tag_set(node, settag, offset);  in radix_tree_range_tag_if_tagged()
949 			node = node->parent;  in radix_tree_range_tag_if_tagged()
959 		node = NULL;  in radix_tree_range_tag_if_tagged()
1214 	struct radix_tree_node *node;  in radix_tree_locate_item()  local
1221 		node = rcu_dereference_raw(root->rnode);  in radix_tree_locate_item()
1222 		if (!radix_tree_is_indirect_ptr(node)) {  in radix_tree_locate_item()
1224 			if (node == item)  in radix_tree_locate_item()
1229 		node = indirect_to_ptr(node);  in radix_tree_locate_item()
1230 		max_index = radix_tree_maxindex(node->path &  in radix_tree_locate_item()
1237 		cur_index = __locate(node, item, cur_index, &found_index);  in radix_tree_locate_item()
1327 			      struct radix_tree_node *node)  in __radix_tree_delete_node()  argument
1334 		if (node->count) {  in __radix_tree_delete_node()
1335 			if (node == indirect_to_ptr(root->rnode)) {  in __radix_tree_delete_node()
1343 		parent = node->parent;  in __radix_tree_delete_node()
1347 			offset = node->path >> RADIX_TREE_HEIGHT_SHIFT;  in __radix_tree_delete_node()
1356 		radix_tree_node_free(node);  in __radix_tree_delete_node()
1359 		node = parent;  in __radix_tree_delete_node()
1360 	} while (node);  in __radix_tree_delete_node()
1379 	struct radix_tree_node *node;  in radix_tree_delete_item()  local
1385 	entry = __radix_tree_lookup(root, index, &node, &slot);  in radix_tree_delete_item()
1392 	if (!node) {  in radix_tree_delete_item()
1405 		if (tag_get(node, tag, offset))  in radix_tree_delete_item()
1409 	node->slots[offset] = NULL;  in radix_tree_delete_item()
1410 	node->count--;  in radix_tree_delete_item()
1412 	__radix_tree_delete_node(root, node);  in radix_tree_delete_item()
1447 	struct radix_tree_node *node = arg;  in radix_tree_node_ctor()  local
1449 	memset(node, 0, sizeof(*node));  in radix_tree_node_ctor()
1450 	INIT_LIST_HEAD(&node->private_list);  in radix_tree_node_ctor()
1479        struct radix_tree_node *node;  in radix_tree_callback()  local
1485 			node = rtp->nodes;  in radix_tree_callback()
1486 			rtp->nodes = node->private_data;  in radix_tree_callback()
1487 			kmem_cache_free(radix_tree_node_cachep, node);  in radix_tree_callback()