summaryrefslogtreecommitdiffstats
path: root/src/rbtree.c
Commit message (Collapse)AuthorAgeFilesLines
* fix FSF address in sources/headersJaroslav Škarvada2015-11-121-1/+2
| | | | Signed-off-by: Jaroslav Škarvada <jskarvad@redhat.com>
* core/rbtree: remove redundant if()-condition in rb_erase()Sylvain Munaut2011-11-121-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | See kernel commit 4b324126e0c6c3a5080ca3ec0981e8766ed6f1ee ---- 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 <wstrepp@gmx.de> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> ---- Signed-off-by: Sylvain Munaut <tnt@246tNt.com>
* core/rbtree: make clear distinction between two different cases in rb_erase()Sylvain Munaut2011-11-121-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | See kernel commit 4c60117811171d867d4f27f17ea07d7419d45dae ---- 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 <wstrepp@gmx.de> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> ---- Signed-off-by: Sylvain Munaut <tnt@246tNt.com>
* core/rbtree: reorganize code in rb_erase() for additional changesSylvain Munaut2011-11-121-9/+9
| | | | | | | | | | | | | | | | | See kernel commit 16c047add3ceaf0ab882e3e094d1ec904d02312d ---- 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 <a.p.zijlstra@chello.nl> Signed-off-by: Wolfram Strepp <wstrepp@gmx.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> ---- Signed-off-by: Sylvain Munaut <tnt@246tNt.com>
* core/rbtree: optimize rb_erase()Sylvain Munaut2011-11-121-10/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | See kernel commit 55a63998b8967615a15e2211ba0ff3a84a565824 ---- 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 <wstrepp@gmx.de> Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Andrea Arcangeli <andrea@qumranet.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> ---- Signed-off-by: Sylvain Munaut <tnt@246tNt.com>
* core/rbtree: add const qualifier to some functionsSylvain Munaut2011-11-121-6/+6
| | | | | | | | | | | | | | | | | | | | | | See kernel commit f4b477c47332367d35686bd2b808c2156b96d7c7 ---- 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 ?~@~Xrb_next?~@~Y discards qualifiers from pointer target type Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com> Signed-off-by: David Woodhouse <David.Woodhouse@intel.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> ---- Signed-off-by: Sylvain Munaut <tnt@246tNt.com>
* add rb-tree implementation to libosmocorePablo Neira Ayuso2011-10-171-0/+389
This patch adds red black trees implementation to libosmocore. This data structure is very useful to search for elements in ordered sets in O(log n) instead of O(n) that lists provide. The first client of this code will be one follow up patch that implements rbtree-based timer scheduler.