• Matthew Wilcox's avatar
    Reimplement IDR and IDA using the radix tree · 0a835c4f
    Matthew Wilcox authored
    The IDR is very similar to the radix tree.  It has some functionality that
    the radix tree did not have (alloc next free, cyclic allocation, a
    callback-based for_each, destroy tree), which is readily implementable on
    top of the radix tree.  A few small changes were needed in order to use a
    tag to represent nodes with free space below them.  More extensive
    changes were needed to support storing NULL as a valid entry in an IDR.
    Plain radix trees still interpret NULL as a not-present entry.
    
    The IDA is reimplemented as a client of the newly enhanced radix tree.  As
    in the current implementation, it uses a bitmap at the last level of the
    tree.
    Signed-off-by: default avatarMatthew Wilcox <willy@infradead.org>
    Signed-off-by: default avatarMatthew Wilcox <mawilcox@microsoft.com>
    Tested-by: default avatarKirill A. Shutemov <kirill.shutemov@linux.intel.com>
    Cc: Konstantin Khlebnikov <koct9i@gmail.com>
    Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
    Cc: Tejun Heo <tj@kernel.org>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    0a835c4f
radix-tree.c 60.1 KB