| Age | Commit message (Collapse) | Author | Files | Lines | |
|---|---|---|---|---|---|
| 2016-05-20 | radix-tree: rename radix_tree_is_indirect_ptr() | Matthew Wilcox | 1 | -2/+2 | |
| As with indirect_to_ptr(), ptr_to_indirect() and RADIX_TREE_INDIRECT_PTR, change radix_tree_is_indirect_ptr() to radix_tree_is_internal_node(). Signed-off-by: Matthew Wilcox <[email protected]> Cc: Konstantin Khlebnikov <[email protected]> Cc: Kirill Shutemov <[email protected]> Cc: Jan Kara <[email protected]> Cc: Neil Brown <[email protected]> Cc: Ross Zwisler <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]> | |||||
| 2016-05-20 | radix-tree: rename indirect_to_ptr() to entry_to_node() | Matthew Wilcox | 1 | -2/+2 | |
| Mirrors the earlier commit introducing node_to_entry(). Also change the type returned to be a struct radix_tree_node pointer. That lets us simplify a couple of places in the radix tree shrink & extend paths where we could convert an entry into a pointer, modify the node, then convert the pointer back into an entry. Signed-off-by: Matthew Wilcox <[email protected]> Cc: Konstantin Khlebnikov <[email protected]> Cc: Kirill Shutemov <[email protected]> Cc: Jan Kara <[email protected]> Cc: Neil Brown <[email protected]> Cc: Ross Zwisler <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]> | |||||
| 2016-05-20 | radix tree test suite: remove dependencies on height | Matthew Wilcox | 1 | -11/+23 | |
| verify_node() can use node->shift instead of the height. tree_verify_min_height() can be converted over to using node_maxindex() and shift_maxindex() instead of radix_tree_maxindex(). Signed-off-by: Matthew Wilcox <[email protected]> Cc: Konstantin Khlebnikov <[email protected]> Cc: Kirill Shutemov <[email protected]> Cc: Jan Kara <[email protected]> Cc: Neil Brown <[email protected]> Cc: Ross Zwisler <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]> | |||||
| 2016-05-20 | radix tree test suite: start adding multiorder tests | Matthew Wilcox | 1 | -3/+10 | |
| Test suite infrastructure for working with multiorder entries. The test itself is pretty basic: Add an entry, check that all expected indices return that entry and that indices around that entry don't return an entry. Then delete the entry and check no index returns that entry. Tests a few edge conditions including the multiorder entry at index 0 and at a higher index. Also tests deleting through an alias as well as through the canonical index. Signed-off-by: Matthew Wilcox <[email protected]> Reviewed-by: Ross Zwisler <[email protected]> Cc: Konstantin Khlebnikov <[email protected]> Cc: Kirill Shutemov <[email protected]> Cc: Jan Kara <[email protected]> Cc: Neil Brown <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]> | |||||
| 2016-03-17 | radix_tree: tag all internal tree nodes as indirect pointers | Matthew Wilcox | 1 | -2/+3 | |
| Set the 'indirect_ptr' bit on all the pointers to internal nodes, not just on the root node. This enables the following patches to support multi-order entries in the radix tree. This patch is split out for ease of bisection. Signed-off-by: Matthew Wilcox <[email protected]> Cc: Johannes Weiner <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: "Kirill A. Shutemov" <[email protected]> Cc: Ross Zwisler <[email protected]> Cc: Hugh Dickins <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]> | |||||
| 2016-03-17 | radix tree test harness | Matthew Wilcox | 1 | -0/+218 | |
| This code is mostly from Andrew Morton and Nick Piggin; tarball downloaded from http://ozlabs.org/~akpm/rtth.tar.gz with sha1sum 0ce679db9ec047296b5d1ff7a1dfaa03a7bef1bd Some small modifications were necessary to the test harness to fix the build with the current Linux source code. I also made minor modifications to automatically test the radix-tree.c and radix-tree.h files that are in the current source tree, as opposed to a copied and slightly modified version. I am sure more could be done to tidy up the harness, as well as adding more tests. [[email protected]: fix compilation] Signed-off-by: Matthew Wilcox <[email protected]> Cc: Shuah Khan <[email protected]> Cc: Johannes Weiner <[email protected]> Cc: Matthew Wilcox <[email protected]> Cc: "Kirill A. Shutemov" <[email protected]> Cc: Ross Zwisler <[email protected]> Cc: Hugh Dickins <[email protected]> Signed-off-by: Konstantin Khlebnikov <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]> | |||||