summaryrefslogtreecommitdiffstats
path: root/lib/prio_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/prio_tree.c')
-rw-r--r--lib/prio_tree.c156
1 files changed, 69 insertions, 87 deletions
diff --git a/lib/prio_tree.c b/lib/prio_tree.c
index ccfd850b0de..8d443af03b4 100644
--- a/lib/prio_tree.c
+++ b/lib/prio_tree.c
@@ -85,6 +85,17 @@ static inline unsigned long prio_tree_maxindex(unsigned int bits)
return index_bits_to_maxindex[bits - 1];
}
+static void prio_set_parent(struct prio_tree_node *parent,
+ struct prio_tree_node *child, bool left)
+{
+ if (left)
+ parent->left = child;
+ else
+ parent->right = child;
+
+ child->parent = parent;
+}
+
/*
* Extend a priority search tree so that it can store a node with heap_index
* max_heap_index. In the worst case, this algorithm takes O((log n)^2).
@@ -94,45 +105,32 @@ static inline unsigned long prio_tree_maxindex(unsigned int bits)
static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root,
struct prio_tree_node *node, unsigned long max_heap_index)
{
- struct prio_tree_node *first = NULL, *prev, *last = NULL;
+ struct prio_tree_node *prev;
if (max_heap_index > prio_tree_maxindex(root->index_bits))
root->index_bits++;
+ prev = node;
+ INIT_PRIO_TREE_NODE(node);
+
while (max_heap_index > prio_tree_maxindex(root->index_bits)) {
+ struct prio_tree_node *tmp = root->prio_tree_node;
+
root->index_bits++;
if (prio_tree_empty(root))
continue;
- if (first == NULL) {
- first = root->prio_tree_node;
- prio_tree_remove(root, root->prio_tree_node);
- INIT_PRIO_TREE_NODE(first);
- last = first;
- } else {
- prev = last;
- last = root->prio_tree_node;
- prio_tree_remove(root, root->prio_tree_node);
- INIT_PRIO_TREE_NODE(last);
- prev->left = last;
- last->parent = prev;
- }
- }
-
- INIT_PRIO_TREE_NODE(node);
-
- if (first) {
- node->left = first;
- first->parent = node;
- } else
- last = node;
+ prio_tree_remove(root, root->prio_tree_node);
+ INIT_PRIO_TREE_NODE(tmp);
- if (!prio_tree_empty(root)) {
- last->left = root->prio_tree_node;
- last->left->parent = last;
+ prio_set_parent(prev, tmp, true);
+ prev = tmp;
}
+ if (!prio_tree_empty(root))
+ prio_set_parent(prev, root->prio_tree_node, true);
+
root->prio_tree_node = node;
return node;
}
@@ -151,25 +149,15 @@ struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
* We can reduce root->index_bits here. However, it is complex
* and does not help much to improve performance (IMO).
*/
- node->parent = node;
root->prio_tree_node = node;
- } else {
- node->parent = old->parent;
- if (old->parent->left == old)
- old->parent->left = node;
- else
- old->parent->right = node;
- }
+ } else
+ prio_set_parent(old->parent, node, old->parent->left == old);
- if (!prio_tree_left_empty(old)) {
- node->left = old->left;
- old->left->parent = node;
- }
+ if (!prio_tree_left_empty(old))
+ prio_set_parent(node, old->left, true);
- if (!prio_tree_right_empty(old)) {
- node->right = old->right;
- old->right->parent = node;
- }
+ if (!prio_tree_right_empty(old))
+ prio_set_parent(node, old->right, false);
return old;
}
@@ -229,16 +217,14 @@ struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
if (index & mask) {
if (prio_tree_right_empty(cur)) {
INIT_PRIO_TREE_NODE(node);
- cur->right = node;
- node->parent = cur;
+ prio_set_parent(cur, node, false);
return res;
} else
cur = cur->right;
} else {
if (prio_tree_left_empty(cur)) {
INIT_PRIO_TREE_NODE(node);
- cur->left = node;
- node->parent = cur;
+ prio_set_parent(cur, node, true);
return res;
} else
cur = cur->left;
@@ -305,6 +291,40 @@ void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node)
cur = prio_tree_replace(root, cur->parent, cur);
}
+static void iter_walk_down(struct prio_tree_iter *iter)
+{
+ iter->mask >>= 1;
+ if (iter->mask) {
+ if (iter->size_level)
+ iter->size_level++;
+ return;
+ }
+
+ if (iter->size_level) {
+ BUG_ON(!prio_tree_left_empty(iter->cur));
+ BUG_ON(!prio_tree_right_empty(iter->cur));
+ iter->size_level++;
+ iter->mask = ULONG_MAX;
+ } else {
+ iter->size_level = 1;
+ iter->mask = 1UL << (BITS_PER_LONG - 1);
+ }
+}
+
+static void iter_walk_up(struct prio_tree_iter *iter)
+{
+ if (iter->mask == ULONG_MAX)
+ iter->mask = 1UL;
+ else if (iter->size_level == 1)
+ iter->mask = 1UL;
+ else
+ iter->mask <<= 1;
+ if (iter->size_level)
+ iter->size_level--;
+ if (!iter->size_level && (iter->value & iter->mask))
+ iter->value ^= iter->mask;
+}
+
/*
* Following functions help to enumerate all prio_tree_nodes in the tree that
* overlap with the input interval X [radix_index, heap_index]. The enumeration
@@ -323,21 +343,7 @@ static struct prio_tree_node *prio_tree_left(struct prio_tree_iter *iter,
if (iter->r_index <= *h_index) {
iter->cur = iter->cur->left;
- iter->mask >>= 1;
- if (iter->mask) {
- if (iter->size_level)
- iter->size_level++;
- } else {
- if (iter->size_level) {
- BUG_ON(!prio_tree_left_empty(iter->cur));
- BUG_ON(!prio_tree_right_empty(iter->cur));
- iter->size_level++;
- iter->mask = ULONG_MAX;
- } else {
- iter->size_level = 1;
- iter->mask = 1UL << (BITS_PER_LONG - 1);
- }
- }
+ iter_walk_down(iter);
return iter->cur;
}
@@ -364,22 +370,7 @@ static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter,
if (iter->r_index <= *h_index) {
iter->cur = iter->cur->right;
- iter->mask >>= 1;
- iter->value = value;
- if (iter->mask) {
- if (iter->size_level)
- iter->size_level++;
- } else {
- if (iter->size_level) {
- BUG_ON(!prio_tree_left_empty(iter->cur));
- BUG_ON(!prio_tree_right_empty(iter->cur));
- iter->size_level++;
- iter->mask = ULONG_MAX;
- } else {
- iter->size_level = 1;
- iter->mask = 1UL << (BITS_PER_LONG - 1);
- }
- }
+ iter_walk_down(iter);
return iter->cur;
}
@@ -389,16 +380,7 @@ static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter,
static struct prio_tree_node *prio_tree_parent(struct prio_tree_iter *iter)
{
iter->cur = iter->cur->parent;
- if (iter->mask == ULONG_MAX)
- iter->mask = 1UL;
- else if (iter->size_level == 1)
- iter->mask = 1UL;
- else
- iter->mask <<= 1;
- if (iter->size_level)
- iter->size_level--;
- if (!iter->size_level && (iter->value & iter->mask))
- iter->value ^= iter->mask;
+ iter_walk_up(iter);
return iter->cur;
}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-11-11 11:07:41 +0000