1. 21 5月, 2016 1 次提交
    • R
      radix-tree: add support for multi-order iterating · 21ef5339
      Ross Zwisler 提交于
      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: NRoss Zwisler <ross.zwisler@linux.intel.com>
      Signed-off-by: NMatthew 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: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      21ef5339