Lines Matching refs:root
52 static void get_index(const struct prio_tree_root *root,
56 if (root->raw) {
94 static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root,
99 if (max_heap_index > prio_tree_maxindex(root->index_bits))
100 root->index_bits++;
102 while (max_heap_index > prio_tree_maxindex(root->index_bits)) {
103 root->index_bits++;
105 if (prio_tree_empty(root))
109 first = root->prio_tree_node;
110 prio_tree_remove(root, root->prio_tree_node);
115 last = root->prio_tree_node;
116 prio_tree_remove(root, root->prio_tree_node);
131 if (!prio_tree_empty(root)) {
132 last->left = root->prio_tree_node;
136 root->prio_tree_node = node;
143 struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
149 BUG_ON(root->prio_tree_node != old);
151 * We can reduce root->index_bits here. However, it is complex
155 root->prio_tree_node = node;
178 * Insert a prio_tree_node @node into a radix priority search tree @root. The
187 struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
195 get_index(root, node, &radix_index, &heap_index);
197 if (prio_tree_empty(root) ||
198 heap_index > prio_tree_maxindex(root->index_bits))
199 return prio_tree_expand(root, node, heap_index);
201 cur = root->prio_tree_node;
202 mask = 1UL << (root->index_bits - 1);
205 get_index(root, cur, &r_index, &h_index);
213 node = prio_tree_replace(root, cur, node);
260 * Remove a prio_tree_node @node from a radix priority search tree @root. The
264 void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node)
273 get_index(root, cur->left, &r_index, &h_index_left);
280 get_index(root, cur->right, &r_index, &h_index_right);
294 BUG_ON(root->prio_tree_node != cur);
295 __INIT_PRIO_TREE_ROOT(root, root->raw);
305 cur = prio_tree_replace(root, cur->parent, cur);
322 get_index(iter->root, iter->cur->left, r_index, h_index);
363 get_index(iter->root, iter->cur->right, r_index, h_index);
420 struct prio_tree_root *root;
425 root = iter->root;
426 if (prio_tree_empty(root))
429 get_index(root, root->prio_tree_node, &r_index, &h_index);
434 iter->mask = 1UL << (root->index_bits - 1);
435 iter->cur = root->prio_tree_node;