28 Jan, 2011
1 commit
-
The augmented rbtree helper functions are not exported to modules right
now.(We have started using augmented rbtrees in the upcoming version of
drbd.)Signed-off-by: Andreas Gruenbacher
Signed-off-by: Linus Torvalds
05 Jul, 2010
1 commit
-
Reimplement augmented RB-trees without sprinkling extra branches
all over the RB-tree code (which lives in the scheduler hot path).This approach is 'borrowed' from Fabio's BFQ implementation and
relies on traversing the rebalance path after the RB-tree-op to
correct the heap property for insertion/removal and make up for
the damage done by the tree rotations.For insertion the rebalance path is trivially that from the new
node upwards to the root, for removal it is that from the deepest
node in the path from the to be removed node that will still
be around after the removal.[ This patch also fixes a video driver regression reported by
Ali Gholami Rudi - the memtype->subtree_max_end was updated
incorrectly. ]Acked-by: Suresh Siddha
Acked-by: Venkatesh Pallipadi
Signed-off-by: Peter Zijlstra
Tested-by: Ali Gholami Rudi
Cc: Fabio Checconi
Cc: "H. Peter Anvin"
Cc: Andrew Morton
Cc: Linus Torvalds
LKML-Reference:
Signed-off-by: Ingo Molnar
19 Feb, 2010
1 commit
-
Add support for augmented rbtrees in core rbtree code.
This will be used in subsequent patches, in x86 PAT code, which needs
interval trees to efficiently keep track of PAT ranges.Signed-off-by: Venkatesh Pallipadi
LKML-Reference:
Signed-off-by: Suresh Siddha
Signed-off-by: H. Peter Anvin
17 Jun, 2009
3 commits
-
Furthermore, notice that the initial checks:
if (!node->rb_left)
child = node->rb_right;
else if (!node->rb_right)
child = node->rb_left;
else
{
...
}
guarantee that old->rb_right is set in the final else branch, therefore
we can omit checking that again.Signed-off-by: Wolfram Strepp
Signed-off-by: Peter Zijlstra
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
There are two cases when a node, having 2 childs, is erased:
'normal case': the successor is not the right-hand-child of the node to be erased
'special case': the successor is the right-hand child of the node to be erasedHere some ascii-art, with following symbols (referring to the code):
O: node to be deleted
N: the successor of O
P: parent of N
C: child of N
L: some other nodenormal case:
O N
/ \ / \
/ \ / \
L \ L \
/ \ P ----> / \ P
/ \ / \
/ /
N C
\ / \
\
C
/ \special case:
O|P N
/ \ / \
/ \ / \
L \ L \
/ \ N ----> / C
\ / \
\
C
/ \Notice that for the special case we don't have to reconnect C to N.
Signed-off-by: Wolfram Strepp
Signed-off-by: Peter Zijlstra
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
First, move some code around in order to make the next change more obvious.
[akpm@linux-foundation.org: coding-style fixes]
Signed-off-by: Peter Zijlstra
Signed-off-by: Wolfram Strepp
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
01 Apr, 2009
1 commit
-
Tfour 4 redundant if-conditions in function __rb_erase_color() in
lib/rbtree.c are removed.In pseudo-source-code, the structure of the code is as follows:
if ((!A || B) && (!C || D)) {
.
.
.
} else {
if (!C || D) {//if this is true, it implies: (A == true) && (B == false)
if (A) {//hence this always evaluates to 'true'...
.
}
.
//at this point, C always becomes true, because of:
__rb_rotate_right/left();
//and:
other = parent->rb_right/left;
}
.
.
if (C) {//...and this too !
.
}
}Signed-off-by: Wolfram Strepp
Acked-by: Peter Zijlstra
Cc: Andrea Arcangeli
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
10 Jan, 2009
1 commit
-
The 'rb_first()', 'rb_last()', 'rb_next()' and 'rb_prev()' calls
take a pointer to an RB node or RB root. They do not change the
pointed objects, so add a 'const' qualifier in order to make life
of the users of these functions easier.Indeed, if I have my own constant pointer &const struct my_type *p,
and I call 'rb_next(&p->rb)', I get a GCC warning:warning: passing argument 1 of ‘rb_next’ discards qualifiers from pointer target type
Signed-off-by: Artem Bityutskiy
Signed-off-by: David Woodhouse
Signed-off-by: Linus Torvalds
01 Oct, 2006
1 commit
-
The conditions got reserved. Also make rb_next() and rb_prev() check
for the empty condition.Signed-off-by: Jens Axboe
06 Jun, 2006
1 commit
-
Since rb_insert_color() is part of the _public_ API, while the others are
purely internal, switch to be consistent with that.Signed-off-by: David Woodhouse
21 Apr, 2006
2 commits
-
We only used a single bit for colour information, so having a whole
machine word of space allocated for it was a bit wasteful. Instead,
store it in the lowest bit of the 'parent' pointer, since that was
always going to be aligned anyway.Signed-off-by: David Woodhouse
-
Observe rb_erase(), when the victim node 'old' has two children so
neither of the simple cases at the beginning are taken.Observe that it effectively does an 'rb_next()' operation to find the
next (by value) node in the tree. That is; we go to the victim's
right-hand child and then follow left-hand pointers all the way
down the tree as far as we can until we find the next node 'node'. We
end up with 'node' being either the same immediate right-hand child of
'old', or one of its descendants on the far left-hand side.For a start, we _know_ that 'node' has a parent. We can drop that check.
We also know that if 'node's parent is 'old', then 'node' is the
right-hand child of its parent. And that if 'node's parent is _not_
'old', then 'node' is the left-hand child of its parent.So instead of checking for 'node->rb_parent == old' in one place and
also checking 'node's heritage separately when we're trying to change
its link from its parent, we can shuffle things around a bit and do
it like this...Signed-off-by: David Woodhouse
17 Apr, 2005
1 commit
-
Initial git repository build. I'm not bothering with the full history,
even though we have it. We can create a separate "historical" git
archive of that later if we want to, and in the meantime it's about
3.2GB when imported into git - space that would just make the early
git days unnecessarily complicated, when we don't have a lot of good
infrastructure for it.Let it rip!
