Update to 3.4-final.

[linux-flexiantxendom0-3.2.10.git] / lib / prio_tree.c

diff --git a/lib/prio_tree.c b/lib/prio_tree.c
index 423eba8..8d443af 100644 (file)
--- 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;
 }
@@ -152,23 +150,14 @@ struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
                 * and does not help much to improve performance (IMO).
                 */
                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;
 }
@@ -228,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;
@@ -304,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
@@ -322,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;
        }
 
@@ -363,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;
        }
 
@@ -388,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;
 }