user/sven/linux.git/include/linux/rbtree.h, branch v3.4.44

timers: Add rb_init_node() to allow for stack allocated rb nodes

2011-04-26T21:01:42Z

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

rbtree: Undo augmented trees performance damage and regression

2010-07-05T12:43:50Z

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: <1275414172.27810.27961.camel@twins> Signed-off-by: Ingo Molnar

Merge branch 'x86-pat-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip

2010-05-18T16:28:04Z

* '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

doc: fix typo in comment explaining rb_tree usage

2010-02-25T10:45:20Z

Fix typo in comment explaining rb_tree usage. s/int/in Signed-off-by: Nikanth Karthikesan Signed-off-by: Jiri Kosina

rbtree: Add support for augmented rbtrees

2010-02-18T23:40:56Z

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: <20100210232343.GA11465@linux-os.sc.intel.com> Signed-off-by: Suresh Siddha Signed-off-by: H. Peter Anvin

rbtree: add const qualifier to some functions

2009-01-10T14:04:33Z

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

[PATCH] rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev

2006-09-30T18:26:56Z

The conditions got reserved. Also make rb_next() and rb_prev() check for the empty condition. Signed-off-by: Jens Axboe

[PATCH] rbtree: support functions used by the io schedulers

2006-06-23T15:10:39Z

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

[RBTREE] Switch rb_colour() et al to en_US spelling of 'color' for consistency

2006-06-05T19:19:05Z

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

[RBTREE] Add explicit alignment to sizeof(long) for struct rb_node.

2006-04-21T22:15:39Z

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