44 radix_max(struct radix_tree_root *root)  in radix_max()  argument
46 	return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL);  in radix_max()
56 radix_tree_clean_root_node(struct radix_tree_root *root)  in radix_tree_clean_root_node()  argument
58 	/* Check if the root node should be freed */  in radix_tree_clean_root_node()
59 	if (root->rnode->count == 0) {  in radix_tree_clean_root_node()
60 		free(root->rnode, M_RADIX);  in radix_tree_clean_root_node()
61 		root->rnode = NULL;  in radix_tree_clean_root_node()
62 		root->height = 0;  in radix_tree_clean_root_node()
67 radix_tree_lookup(struct radix_tree_root *root, unsigned long index)  in radix_tree_lookup()  argument
74 	node = root->rnode;  in radix_tree_lookup()
75 	height = root->height - 1;  in radix_tree_lookup()
76 	if (index > radix_max(root))  in radix_tree_lookup()
88 radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter,  in radix_tree_iter_find()  argument
96 	node = root->rnode;  in radix_tree_iter_find()
99 	height = root->height - 1;  in radix_tree_iter_find()
100 	if (height == -1 || index > radix_max(root))  in radix_tree_iter_find()
127 radix_tree_delete(struct radix_tree_root *root, unsigned long index)  in radix_tree_delete()  argument
136 	node = root->rnode;  in radix_tree_delete()
137 	height = root->height - 1;  in radix_tree_delete()
138 	if (index > radix_max(root))  in radix_tree_delete()
160 			if (node == root->rnode) {  in radix_tree_delete()
161 				root->rnode = NULL;  in radix_tree_delete()
162 				root->height = 0;  in radix_tree_delete()
174 radix_tree_iter_delete(struct radix_tree_root *root,  in radix_tree_iter_delete()  argument
177 	radix_tree_delete(root, iter->index);  in radix_tree_iter_delete()
181 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)  in radix_tree_insert()  argument
192 	/* get root node, if any */  in radix_tree_insert()
193 	node = root->rnode;  in radix_tree_insert()
195 	/* allocate root node, if any */  in radix_tree_insert()
197 		node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);  in radix_tree_insert()
200 		root->rnode = node;  in radix_tree_insert()
201 		root->height++;  in radix_tree_insert()
205 	while (radix_max(root) < index) {  in radix_tree_insert()
207 		if (root->height == RADIX_TREE_MAX_HEIGHT) {  in radix_tree_insert()
208 			radix_tree_clean_root_node(root);  in radix_tree_insert()
213 		 * If the root radix level is not empty, we need to  in radix_tree_insert()
217 			node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);  in radix_tree_insert()
228 			node->slots[0] = root->rnode;  in radix_tree_insert()
230 			root->rnode = node;  in radix_tree_insert()
232 		root->height++;  in radix_tree_insert()
236 	height = root->height - 1;  in radix_tree_insert()
249 		    root->gfp_mask | M_ZERO);  in radix_tree_insert()
253 			radix_tree_clean_root_node(root);  in radix_tree_insert()
279 radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem)  in radix_tree_store()  argument
292 		*ppitem = radix_tree_delete(root, index);  in radix_tree_store()
296 	/* get root node, if any */  in radix_tree_store()
297 	node = root->rnode;  in radix_tree_store()
299 	/* allocate root node, if any */  in radix_tree_store()
301 		node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);  in radix_tree_store()
304 		root->rnode = node;  in radix_tree_store()
305 		root->height++;  in radix_tree_store()
309 	while (radix_max(root) < index) {  in radix_tree_store()
311 		if (root->height == RADIX_TREE_MAX_HEIGHT) {  in radix_tree_store()
312 			radix_tree_clean_root_node(root);  in radix_tree_store()
317 		 * If the root radix level is not empty, we need to  in radix_tree_store()
321 			node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);  in radix_tree_store()
332 			node->slots[0] = root->rnode;  in radix_tree_store()
334 			root->rnode = node;  in radix_tree_store()
336 		root->height++;  in radix_tree_store()
340 	height = root->height - 1;  in radix_tree_store()
353 		    root->gfp_mask | M_ZERO);  in radix_tree_store()
357 			radix_tree_clean_root_node(root);  in radix_tree_store()