Lines Matching refs:root
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) {
210 if (root->height == RADIX_TREE_MAX_HEIGHT) {
211 radix_tree_clean_root_node(root);
216 * If the root radix level is not empty, we need to
220 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
231 node->slots[0] = root->rnode;
233 root->rnode = node;
235 root->height++;
239 height = root->height - 1;
252 root->gfp_mask | M_ZERO);
256 radix_tree_clean_root_node(root);
282 radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem)
295 *ppitem = radix_tree_delete(root, index);
299 /* get root node, if any */
300 node = root->rnode;
302 /* allocate root node, if any */
304 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
307 root->rnode = node;
308 root->height++;
312 while (radix_max(root) < index) {
314 if (root->height == RADIX_TREE_MAX_HEIGHT) {
315 radix_tree_clean_root_node(root);
320 * If the root radix level is not empty, we need to
324 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
335 node->slots[0] = root->rnode;
337 root->rnode = node;
339 root->height++;
343 height = root->height - 1;
356 root->gfp_mask | M_ZERO);
360 radix_tree_clean_root_node(root);