diff options
author | Cody P Schafer <cody@linux.vnet.ibm.com> | 2013-09-11 14:25:10 -0700 |
---|---|---|
committer | Chanho Park <chanho61.park@samsung.com> | 2014-11-18 11:47:21 +0900 |
commit | cbd1cc155e81bda6e67cef97efb8acddc76504e9 (patch) | |
tree | a2a988934f4bf9d3cf99ad5f1add0385beefce0e /crypto/ripemd.h | |
parent | abcc4680cbec57757e0bdaf803b05721c6a62788 (diff) | |
download | linux-3.10-cbd1cc155e81bda6e67cef97efb8acddc76504e9.tar.gz linux-3.10-cbd1cc155e81bda6e67cef97efb8acddc76504e9.tar.bz2 linux-3.10-cbd1cc155e81bda6e67cef97efb8acddc76504e9.zip |
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.
Change-Id: Ibc97f0e13288030501b5e84defc6603eeb1adca6
Signed-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>
Reviewed-by: Seth Jennings <sjenning@linux.vnet.ibm.com>
Cc: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Michel Lespinasse <walken@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'crypto/ripemd.h')
0 files changed, 0 insertions, 0 deletions