user/sven/linux.git/lib/rbtree.c, branch v3.2.11

Export the augmented rbtree helper functions

2011-01-28T02:16:59Z

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

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

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

rb_tree: remove redundant if()-condition in rb_erase()

2009-06-17T02:47:56Z

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

rb_tree: make clear distinction between two different cases in rb_erase()

2009-06-17T02:47:56Z

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 erased Here 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 node normal 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

rb_tree: reorganize code in rb_erase() for additional changes

2009-06-17T02:47:56Z

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

lib/rbtree.c: optimize rb_erase()

2009-04-01T15:59:17Z

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

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

[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