rbtree: add postorder iteration functions
authorCody P Schafer <[email protected]>
Wed, 11 Sep 2013 21:25:10 +0000 (14:25 -0700)
committerLinus Torvalds <[email protected]>
Wed, 11 Sep 2013 22:59:19 +0000 (15:59 -0700)
commit9dee5c51516d2c3fff22633c1272c5652e68075a
treeb8d1811b0357a74c720008911e06559f772ce731
parentb4bc4a18a226f46fec4ef47f2df28ea209db8b5d
rbtree: add postorder iteration functions

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 <[email protected]>
Reviewed-by: Seth Jennings <[email protected]>
Cc: David Woodhouse <[email protected]>
Cc: Rik van Riel <[email protected]>
Cc: Michel Lespinasse <[email protected]>
Signed-off-by: Andrew Morton <[email protected]>
Signed-off-by: Linus Torvalds <[email protected]>
include/linux/rbtree.h
lib/rbtree.c