summaryrefslogtreecommitdiffstats
path: root/lib/prio_tree.c
diff options
context:
space:
mode:
authorXiao Guangrong <xiaoguangrong@linux.vnet.ibm.com>2012-03-23 15:02:15 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2012-03-23 16:58:36 -0700
commit742245d5c2ebd75c2a002f8fc2afbdc5c26edd8c (patch)
tree1634d6ce2eaec1c05034735b6a82f05894cfea95 /lib/prio_tree.c
parentf35368dd1cef11cdd310b07c74d74f45e3469c64 (diff)
downloadop-kernel-dev-742245d5c2ebd75c2a002f8fc2afbdc5c26edd8c.zip
op-kernel-dev-742245d5c2ebd75c2a002f8fc2afbdc5c26edd8c.tar.gz
prio_tree: simplify prio_tree_expand()
In current code, the deleted-node is recorded from first to last, actually, we can directly attach these node on 'node' we will insert as the left child, it can let the code more readable. Signed-off-by: Xiao Guangrong <xiaoguangrong@linux.vnet.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
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 888e8b3..928482b 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)
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);
+ prio_tree_remove(root, root->prio_tree_node);
+ INIT_PRIO_TREE_NODE(tmp);
- if (first) {
- node->left = first;
- first->parent = node;
- } else
- last = node;
+ prev->left = tmp;
+ tmp->parent = prev;
+ prev = tmp;
+ }
if (!prio_tree_empty(root)) {
- last->left = root->prio_tree_node;
- last->left->parent = last;
+ prev->left = root->prio_tree_node;
+ prev->left->parent = prev;
}
root->prio_tree_node = node;
OpenPOWER on IntegriCloud