87 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,  in tag_set()  argument
90 	__set_bit(offset, node->tags[tag]);  in tag_set()
93 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,  in tag_clear()  argument
96 	__clear_bit(offset, node->tags[tag]);  in tag_clear()
99 static inline int tag_get(struct radix_tree_node *node, unsigned int tag,  in tag_get()  argument
102 	return test_bit(offset, node->tags[tag]);  in tag_get()
129 static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)  in any_tag_set()  argument
133 		if (node->tags[tag][idx])  in any_tag_set()
219 	struct radix_tree_node *node =  in radix_tree_node_rcu_free()  local
229 		tag_clear(node, i, 0);  in radix_tree_node_rcu_free()
231 	node->slots[0] = NULL;  in radix_tree_node_rcu_free()
232 	node->count = 0;  in radix_tree_node_rcu_free()
234 	kmem_cache_free(radix_tree_node_cachep, node);  in radix_tree_node_rcu_free()
238 radix_tree_node_free(struct radix_tree_node *node)  in radix_tree_node_free()  argument
240 	call_rcu(&node->rcu_head, radix_tree_node_rcu_free);  in radix_tree_node_free()
255 	struct radix_tree_node *node;  in __radix_tree_preload()  local
262 		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);  in __radix_tree_preload()
263 		if (node == NULL)  in __radix_tree_preload()
268 			rtp->nodes[rtp->nr++] = node;  in __radix_tree_preload()
270 			kmem_cache_free(radix_tree_node_cachep, node);  in __radix_tree_preload()
323 	struct radix_tree_node *node;  in radix_tree_extend()  local
340 		if (!(node = radix_tree_node_alloc(root)))  in radix_tree_extend()
346 				tag_set(node, tag, 0);  in radix_tree_extend()
352 		node->path = newheight;  in radix_tree_extend()
353 		node->count = 1;  in radix_tree_extend()
354 		node->parent = NULL;  in radix_tree_extend()
358 			slot->parent = node;  in radix_tree_extend()
360 		node->slots[0] = slot;  in radix_tree_extend()
361 		node = ptr_to_indirect(node);  in radix_tree_extend()
362 		rcu_assign_pointer(root->rnode, node);  in radix_tree_extend()
388 	struct radix_tree_node *node = NULL, *slot;  in __radix_tree_create()  local
411 			slot->parent = node;  in __radix_tree_create()
412 			if (node) {  in __radix_tree_create()
413 				rcu_assign_pointer(node->slots[offset], slot);  in __radix_tree_create()
414 				node->count++;  in __radix_tree_create()
422 		node = slot;  in __radix_tree_create()
423 		slot = node->slots[offset];  in __radix_tree_create()
429 		*nodep = node;  in __radix_tree_create()
431 		*slotp = node ? node->slots + offset : (void **)&root->rnode;  in __radix_tree_create()
446 	struct radix_tree_node *node;  in radix_tree_insert()  local
452 	error = __radix_tree_create(root, index, &node, &slot);  in radix_tree_insert()
459 	if (node) {  in radix_tree_insert()
460 		node->count++;  in radix_tree_insert()
461 		BUG_ON(tag_get(node, 0, index & RADIX_TREE_MAP_MASK));  in radix_tree_insert()
462 		BUG_ON(tag_get(node, 1, index & RADIX_TREE_MAP_MASK));  in radix_tree_insert()
489 	struct radix_tree_node *node, *parent;  in __radix_tree_lookup()  local
493 	node = rcu_dereference_raw(root->rnode);  in __radix_tree_lookup()
494 	if (node == NULL)  in __radix_tree_lookup()
497 	if (!radix_tree_is_indirect_ptr(node)) {  in __radix_tree_lookup()
505 		return node;  in __radix_tree_lookup()
507 	node = indirect_to_ptr(node);  in __radix_tree_lookup()
509 	height = node->path & RADIX_TREE_HEIGHT_MASK;  in __radix_tree_lookup()
516 		parent = node;  in __radix_tree_lookup()
517 		slot = node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK);  in __radix_tree_lookup()
518 		node = rcu_dereference_raw(*slot);  in __radix_tree_lookup()
519 		if (node == NULL)  in __radix_tree_lookup()
530 	return node;  in __radix_tree_lookup()
636 	struct radix_tree_node *node = NULL;  in radix_tree_tag_clear()  local
654 		node = slot;  in radix_tree_tag_clear()
661 	while (node) {  in radix_tree_tag_clear()
662 		if (!tag_get(node, tag, offset))  in radix_tree_tag_clear()
664 		tag_clear(node, tag, offset);  in radix_tree_tag_clear()
665 		if (any_tag_set(node, tag))  in radix_tree_tag_clear()
670 		node = node->parent;  in radix_tree_tag_clear()
701 	struct radix_tree_node *node;  in radix_tree_tag_get()  local
707 	node = rcu_dereference_raw(root->rnode);  in radix_tree_tag_get()
708 	if (node == NULL)  in radix_tree_tag_get()
711 	if (!radix_tree_is_indirect_ptr(node))  in radix_tree_tag_get()
713 	node = indirect_to_ptr(node);  in radix_tree_tag_get()
715 	height = node->path & RADIX_TREE_HEIGHT_MASK;  in radix_tree_tag_get()
724 		if (node == NULL)  in radix_tree_tag_get()
728 		if (!tag_get(node, tag, offset))  in radix_tree_tag_get()
732 		node = rcu_dereference_raw(node->slots[offset]);  in radix_tree_tag_get()
751 	struct radix_tree_node *rnode, *node;  in radix_tree_next_chunk()  local
791 	node = rnode;  in radix_tree_next_chunk()
794 				!test_bit(offset, node->tags[tag]) :  in radix_tree_next_chunk()
795 				!node->slots[offset]) {  in radix_tree_next_chunk()
802 						node->tags[tag],  in radix_tree_next_chunk()
807 					if (node->slots[offset])  in radix_tree_next_chunk()
823 		node = rcu_dereference_raw(node->slots[offset]);  in radix_tree_next_chunk()
824 		if (node == NULL)  in radix_tree_next_chunk()
840 		iter->tags = node->tags[tag][tag_long] >> tag_bit;  in radix_tree_next_chunk()
845 				iter->tags |= node->tags[tag][tag_long + 1] <<  in radix_tree_next_chunk()
852 	return node->slots + offset;  in radix_tree_next_chunk()
889 	struct radix_tree_node *node = NULL;  in radix_tree_range_tag_if_tagged()  local
925 			node = slot;  in radix_tree_range_tag_if_tagged()
936 		while (node) {  in radix_tree_range_tag_if_tagged()
941 			if (tag_get(node, settag, offset))  in radix_tree_range_tag_if_tagged()
943 			tag_set(node, settag, offset);  in radix_tree_range_tag_if_tagged()
944 			node = node->parent;  in radix_tree_range_tag_if_tagged()
954 		node = NULL;  in radix_tree_range_tag_if_tagged()
1209 	struct radix_tree_node *node;  in radix_tree_locate_item()  local
1216 		node = rcu_dereference_raw(root->rnode);  in radix_tree_locate_item()
1217 		if (!radix_tree_is_indirect_ptr(node)) {  in radix_tree_locate_item()
1219 			if (node == item)  in radix_tree_locate_item()
1224 		node = indirect_to_ptr(node);  in radix_tree_locate_item()
1225 		max_index = radix_tree_maxindex(node->path &  in radix_tree_locate_item()
1232 		cur_index = __locate(node, item, cur_index, &found_index);  in radix_tree_locate_item()
1322 			      struct radix_tree_node *node)  in __radix_tree_delete_node()  argument
1329 		if (node->count) {  in __radix_tree_delete_node()
1330 			if (node == indirect_to_ptr(root->rnode)) {  in __radix_tree_delete_node()
1338 		parent = node->parent;  in __radix_tree_delete_node()
1342 			offset = node->path >> RADIX_TREE_HEIGHT_SHIFT;  in __radix_tree_delete_node()
1351 		radix_tree_node_free(node);  in __radix_tree_delete_node()
1354 		node = parent;  in __radix_tree_delete_node()
1355 	} while (node);  in __radix_tree_delete_node()
1374 	struct radix_tree_node *node;  in radix_tree_delete_item()  local
1380 	entry = __radix_tree_lookup(root, index, &node, &slot);  in radix_tree_delete_item()
1387 	if (!node) {  in radix_tree_delete_item()
1400 		if (tag_get(node, tag, offset))  in radix_tree_delete_item()
1404 	node->slots[offset] = NULL;  in radix_tree_delete_item()
1405 	node->count--;  in radix_tree_delete_item()
1407 	__radix_tree_delete_node(root, node);  in radix_tree_delete_item()
1442 	struct radix_tree_node *node = arg;  in radix_tree_node_ctor()  local
1444 	memset(node, 0, sizeof(*node));  in radix_tree_node_ctor()
1445 	INIT_LIST_HEAD(&node->private_list);  in radix_tree_node_ctor()