diff options
Diffstat (limited to 'lib/prio_tree.c')
-rw-r--r-- | lib/prio_tree.c | 38 |
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) | |||
94 | static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root, | 94 | static 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; |