27 Apr, 2011
1 commit
-
In cases where a timerqueue_node or some structure that utilizes
a timerqueue_node is allocated on the stack, gcc would give warnings
caused by the timerqueue_init()'s calling RB_CLEAR_NODE, which
self-references the nodes uninitialized data.The solution is to create an rb_init_node() function that zeros
the rb_node structure out and then calls RB_CLEAR_NODE(), and
then call the new init function from timerqueue_init().CC: Thomas Gleixner
Acked-by: Arnd Bergmann
Signed-off-by: John Stultz
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 May, 2010
1 commit
-
* 'x86-pat-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip:
x86, pat: Update the page flags for memtype atomically instead of using memtype_lock
x86, pat: In rbt_memtype_check_insert(), update new->type only if valid
x86, pat: Migrate to rbtree only backend for pat memtype management
x86, pat: Preparatory changes in pat.c for bigger rbtree change
rbtree: Add support for augmented rbtrees
25 Feb, 2010
1 commit
-
Fix typo in comment explaining rb_tree usage.
s/int/inSigned-off-by: Nikanth Karthikesan
Signed-off-by: Jiri Kosina
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
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
23 Jun, 2006
1 commit
-
They all duplicate macros to check for empty root and/or node, and
clearing a node. So put those in rbtree.h.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
22 Apr, 2006
1 commit
-
Seems like a strange requirement, but allegedly it was necessary for
struct address_space on CRIS, because it otherwise ended up being only
byte-aligned. It's harmless enough, and easier to just do it than to
prove it isn't necessary... although I really ought to dig out my etrax
board and test it some time.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
-
This is in preparation for merging those fields into a single
'unsigned long', because using a whole machine-word for a single bit
of colour information is wasteful.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!
