aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorXiao Guangrong <xiaoguangrong@linux.vnet.ibm.com>2012-03-23 18:02:15 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2012-03-23 19:58:36 -0400
commit742245d5c2ebd75c2a002f8fc2afbdc5c26edd8c (patch)
tree1634d6ce2eaec1c05034735b6a82f05894cfea95 /lib
parentf35368dd1cef11cdd310b07c74d74f45e3469c64 (diff)
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')
-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;