summaryrefslogtreecommitdiff
path: root/lib/rbtree.c
AgeCommit message (Collapse)AuthorFilesLines
2006-09-30[PATCH] rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prevJens Axboe1-0/+6
The conditions got reserved. Also make rb_next() and rb_prev() check for the empty condition. Signed-off-by: Jens Axboe <axboe@suse.de>
2006-06-05[RBTREE] Switch rb_colour() et al to en_US spelling of 'color' for consistencyDavid Woodhouse1-5/+5
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 <dwmw2@infradead.org>
2006-04-21[RBTREE] Merge colour and parent fields of struct rb_node.David Woodhouse1-88/+90
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 <dwmw2@infradead.org>
2006-04-21[RBTREE] Remove dead code in rb_erase()David Woodhouse1-10/+5
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 <dwmw2@infradead.org>
2005-04-16Linux-2.6.12-rc2v2.6.12-rc2Linus Torvalds1-0/+394
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!