aboutsummaryrefslogtreecommitdiffstats
path: root/lib/prio_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/prio_tree.c')
-rw-r--r--lib/prio_tree.c38
1 files changed, 14 insertions, 24 deletions
diff --git a/lib/prio_tree.c b/lib/prio_tree.c
index 888e8b3a97ea..928482bb8385 100644
--- a/lib/prio_tree.c
+++ b/lib/prio_tree.c
@@ -94,43 +94,33 @@ static inline unsigned long prio_tree_maxindex(unsigned int bits)
94static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root, 94static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root,
95 struct prio_tree_node *node, unsigned long max_heap_index) 95 struct prio_tree_node *node, unsigned long max_heap_index)
96{ 96{
97 struct prio_tree_node *first = NULL, *prev, *last = NULL; 97 struct prio_tree_node *prev;
98 98
99 if (max_heap_index > prio_tree_maxindex(root->index_bits)) 99 if (max_heap_index > prio_tree_maxindex(root->index_bits))
100 root->index_bits++; 100 root->index_bits++;
101 101
102 prev = node;
103 INIT_PRIO_TREE_NODE(node);
104
102 while (max_heap_index > prio_tree_maxindex(root->index_bits)) { 105 while (max_heap_index > prio_tree_maxindex(root->index_bits)) {
106 struct prio_tree_node *tmp = root->prio_tree_node;
107
103 root->index_bits++; 108 root->index_bits++;
104 109
105 if (prio_tree_empty(root)) 110 if (prio_tree_empty(root))
106 continue; 111 continue;
107 112
108 if (first == NULL) { 113 prio_tree_remove(root, root->prio_tree_node);
109 first = root->prio_tree_node; 114 INIT_PRIO_TREE_NODE(tmp);
110 prio_tree_remove(root, root->prio_tree_node);
111 INIT_PRIO_TREE_NODE(first);
112 last = first;
113 } else {
114 prev = last;
115 last = root->prio_tree_node;
116 prio_tree_remove(root, root->prio_tree_node);
117 INIT_PRIO_TREE_NODE(last);
118 prev->left = last;
119 last->parent = prev;
120 }
121 }
122
123 INIT_PRIO_TREE_NODE(node);
124 115
125 if (first) { 116 prev->left = tmp;
126 node->left = first; 117 tmp->parent = prev;
127 first->parent = node; 118 prev = tmp;
128 } else 119 }
129 last = node;
130 120
131 if (!prio_tree_empty(root)) { 121 if (!prio_tree_empty(root)) {
132 last->left = root->prio_tree_node; 122 prev->left = root->prio_tree_node;
133 last->left->parent = last; 123 prev->left->parent = prev;
134 } 124 }
135 125
136 root->prio_tree_node = node; 126 root->prio_tree_node = node;