linux-toradex.git/include/linux/rbtree.h, branch v4.1.20

lib/rbtree.c: fix typo in comment

2015-02-17T22:34:52+00:00

Signed-off-by: John de la Garza 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: fix rbtree_postorder_for_each_entry_safe() iterator

2013-11-13T03:09:33+00:00

The iterator rbtree_postorder_for_each_entry_safe() relies on pointer
underflow behavior when testing for loop termination.  In particular it
expects that

  &rb_entry(NULL, type, field)->field

is NULL.  But the result of this expression is not defined by a C standard
and some gcc versions (e.g.  4.3.4) assume the above expression can never
be equal to NULL.  The net result is an oops because the iteration is not
properly terminated.

Fix the problem by modifying the iterator to avoid pointer underflows.

Signed-off-by: Jan Kara 
Signed-off-by: Cody P Schafer 
Cc: Michel Lespinasse 
Cc: "David S. Miller" 
Cc: Adrian Hunter 
Cc: Artem Bityutskiy 
Cc: David Woodhouse 
Cc: Jozsef Kadlecsik 
Cc: Pablo Neira Ayuso 
Cc: Patrick McHardy 
Cc: Paul Mundt 
Cc: Theodore Ts'o 
Cc: 		[3.12.x]
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: add rbtree_postorder_for_each_entry_safe() helper

2013-09-11T22:59:20+00:00

Because deletion (of the entire tree) is a relatively common use of the
rbtree_postorder iteration, and because doing it safely means fiddling
with temporary storage, provide a helper to simplify postorder rbtree
iteration.

Signed-off-by: Cody P Schafer 
Reviewed-by: Seth Jennings 
Cc: David Woodhouse 
Cc: Rik van Riel 
Cc: Michel Lespinasse 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: add postorder iteration functions

2013-09-11T22:59:19+00:00

Postorder iteration yields all of a node's children prior to yielding the
node itself, and this particular implementation also avoids examining the
leaf links in a node after that node has been yielded.

In what I expect will be its most common usage, postorder iteration allows
the deletion of every node in an rbtree without modifying the rbtree nodes
(no _requirement_ that they be nulled) while avoiding referencing child
nodes after they have been "deleted" (most commonly, freed).

I have only updated zswap to use this functionality at this point, but
numerous bits of code (most notably in the filesystem drivers) use a hand
rolled postorder iteration that NULLs child links as it traverses the
tree.  Each of those instances could be replaced with this common
implementation.

1 & 2 add rbtree postorder iteration functions.
3 adds testing of the iteration to the rbtree runtime tests
4 allows building the rbtree runtime tests as builtins
5 updates zswap.

This patch:

Add postorder iteration functions for rbtree.  These are useful for safely
freeing an entire rbtree without modifying the tree at all.

Signed-off-by: Cody P Schafer 
Reviewed-by: Seth Jennings 
Cc: David Woodhouse 
Cc: Rik van Riel 
Cc: Michel Lespinasse 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: move augmented rbtree functionality to rbtree_augmented.h

2012-10-09T07:22:40+00:00

Provide rb_insert_augmented() and rb_erase_augmented() through a new
rbtree_augmented.h include file.  rb_erase_augmented() is defined there as
an __always_inline function, in order to allow inlining of augmented
rbtree callbacks into it.  Since this generates a relatively large
function, each augmented rbtree user should make sure to have a single
call site.

Signed-off-by: Michel Lespinasse 
Cc: Rik van Riel 
Cc: Hillf Danton 
Cc: Peter Zijlstra 
Cc: Catalin Marinas 
Cc: Andrea Arcangeli 
Cc: David Woodhouse 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: add RB_DECLARE_CALLBACKS() macro

2012-10-09T07:22:38+00:00

As proposed by Peter Zijlstra, this makes it easier to define the augmented
rbtree callbacks.

Signed-off-by: Michel Lespinasse 
Cc: Rik van Riel 
Cc: Peter Zijlstra 
Cc: Andrea Arcangeli 
Cc: David Woodhouse 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: remove prior augmented rbtree implementation

2012-10-09T07:22:38+00:00

convert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api
and remove the old augmented rbtree implementation.

Signed-off-by: Michel Lespinasse 
Acked-by: Rik van Riel 
Cc: Peter Zijlstra 
Cc: Andrea Arcangeli 
Cc: David Woodhouse 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: faster augmented rbtree manipulation

2012-10-09T07:22:37+00:00

Introduce new augmented rbtree APIs that allow minimal recalculation of
augmented node information.

A new callback is added to the rbtree insertion and erase rebalancing
functions, to be called on each tree rotations. Such rotations preserve
the subtree's root augmented value, but require recalculation of the one
child that was previously located at the subtree root.

In the insertion case, the handcoded search phase must be updated to
maintain the augmented information on insertion, and then the rbtree
coloring/rebalancing algorithms keep it up to date.

In the erase case, things are more complicated since it is library
code that manipulates the rbtree in order to remove internal nodes.
This requires a couple additional callbacks to copy a subtree's
augmented value when a new root is stitched in, and to recompute
augmented values down the ancestry path when a node is removed from
the tree.

In order to preserve maximum speed for the non-augmented case,
we provide two versions of each tree manipulation function.
rb_insert_augmented() is the augmented equivalent of rb_insert_color(),
and rb_erase_augmented() is the augmented equivalent of rb_erase().

Signed-off-by: Michel Lespinasse 
Acked-by: Rik van Riel 
Cc: Peter Zijlstra 
Cc: Andrea Arcangeli 
Cc: David Woodhouse 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: move some implementation details from rbtree.h to rbtree.c

2012-10-09T07:22:32+00:00

rbtree users must use the documented APIs to manipulate the tree
structure.  Low-level helpers to manipulate node colors and parenthood are
not part of that API, so move them to lib/rbtree.c

[dwmw2@infradead.org: fix jffs2 build issue due to renamed __rb_parent_color field]
Signed-off-by: Michel Lespinasse 
Cc: Andrea Arcangeli 
Acked-by: David Woodhouse 
Cc: Rik van Riel 
Cc: Peter Zijlstra 
Cc: Daniel Santos 
Cc: Jens Axboe 
Cc: "Eric W. Biederman" 
Signed-off-by: David Woodhouse 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: empty nodes have no color

2012-10-09T07:22:32+00:00

Empty nodes have no color.  We can make use of this property to simplify
the code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE macros.  Also,
we can get rid of the rb_init_node function which had been introduced by
commit 88d19cf37952 ("timers: Add rb_init_node() to allow for stack
allocated rb nodes") to avoid some issue with the empty node's color not
being initialized.

I'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next() are
doing there, though.  axboe introduced them in commit 10fd48f2376d
("rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev").  The way I
see it, the 'empty node' abstraction is only used by rbtree users to
flag nodes that they haven't inserted in any rbtree, so asking the
predecessor or successor of such nodes doesn't make any sense.

One final rb_init_node() caller was recently added in sysctl code to
implement faster sysctl name lookups.  This code doesn't make use of
RB_EMPTY_NODE at all, and from what I could see it only called
rb_init_node() under the mistaken assumption that such initialization was
required before node insertion.

[sfr@canb.auug.org.au: fix net/ceph/osd_client.c build]
Signed-off-by: Michel Lespinasse 
Cc: Andrea Arcangeli 
Acked-by: David Woodhouse 
Cc: Rik van Riel 
Cc: Peter Zijlstra 
Cc: Daniel Santos 
Cc: Jens Axboe 
Cc: "Eric W. Biederman" 
Cc: John Stultz 
Signed-off-by: Stephen Rothwell 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds