kernel/tools/testing/radix-tree/linux/idr.h, branch linux-6.2.yHosts the 0x221E linux distro kernel.https://universe.0xinfinity.dev/distro/kernel/atom?h=linux-6.2.y2017-02-14T02:44:01ZReimplement IDR and IDA using the radix tree2017-02-14T02:44:01ZMatthew Wilcoxmawilcox@microsoft.com2016-12-20T15:27:56Zurn:sha1:0a835c4f090af2c76fc2932c539c3b32fd21fbbb
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: Matthew Wilcox <willy@infradead.org>
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Tested-by: Kirill 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: Andrew Morton <akpm@linux-foundation.org>