• Ross Zwisler's avatar
    radix-tree: add support for multi-order iterating · 21ef5339
    Ross Zwisler authored
    This enables the macros radix_tree_for_each_slot() and friends to be
    used with multi-order entries.
    
    The way that this works is that we treat all entries in a given slots[]
    array as a single chunk.  If the index given to radix_tree_next_chunk()
    happens to point us to a sibling entry, we will back up iter->index so
    that it points to the canonical entry, and that will be the place where
    we start our iteration.
    
    As we're processing a chunk in radix_tree_next_slot(), we process
    canonical entries, skip over sibling entries, and restart the chunk
    lookup if we find a non-sibling indirect pointer.  This drops back to
    the radix_tree_next_chunk() code, which will re-walk the tree and look
    for another chunk.
    
    This allows us to properly handle multi-order entries mixed with other
    entries that are at various heights in the radix tree.
    Signed-off-by: default avatarRoss Zwisler <ross.zwisler@linux.intel.com>
    Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
    Cc: Konstantin Khlebnikov <koct9i@gmail.com>
    Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
    Cc: Jan Kara <jack@suse.com>
    Cc: Neil Brown <neilb@suse.de>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    21ef5339
radix-tree.c 44.6 KB