common/src/linux_radix.c

47 radix_max(struct radix_tree_root *root)
49 	return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL);
59 radix_tree_clean_root_node(struct radix_tree_root *root)
61 	/* Check if the root node should be freed */
62 	if (root->rnode->count == 0) {
63 		free(root->rnode, M_RADIX);
64 		root->rnode = NULL;
65 		root->height = 0;
70 radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
77 	node = root->rnode;
78 	height = root->height - 1;
79 	if (index > radix_max(root))
91 radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter,
99 	node = root->rnode;
102 	height = root->height - 1;
103 	if (height == -1 || index > radix_max(root))
130 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
139 	node = root->rnode;
140 	height = root->height - 1;
141 	if (index > radix_max(root))
163 			if (node == root->rnode) {
164 				root->rnode = NULL;
165 				root->height = 0;
177 radix_tree_iter_delete(struct radix_tree_root *root,
180 	radix_tree_delete(root, iter->index);
184 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
195 	/* get root node, if any */
196 	node = root->rnode;
198 	/* allocate root node, if any */
200 		node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
203 		root->rnode = node;
204 		root->height++;
208 	while (radix_max(root) < index) {
211 		if (root->height == RADIX_TREE_MAX_HEIGHT) {
212 			radix_tree_clean_root_node(root);
217 		 * If the root radix level is not empty, we need to
221 			node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
232 			node->slots[0] = root->rnode;
234 			root->rnode = node;
236 		root->height++;
240 	height = root->height - 1;
253 		    root->gfp_mask | M_ZERO);
257 			radix_tree_clean_root_node(root);
283 radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem)
296 		*ppitem = radix_tree_delete(root, index);
300 	/* get root node, if any */
301 	node = root->rnode;
303 	/* allocate root node, if any */
305 		node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
308 		root->rnode = node;
309 		root->height++;
313 	while (radix_max(root) < index) {
316 		if (root->height == RADIX_TREE_MAX_HEIGHT) {
317 			radix_tree_clean_root_node(root);
322 		 * If the root radix level is not empty, we need to
326 			node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
337 			node->slots[0] = root->rnode;
339 			root->rnode = node;
341 		root->height++;
345 	height = root->height - 1;
358 		    root->gfp_mask | M_ZERO);
362 			radix_tree_clean_root_node(root);