Re: [PATCH v3 33/33] Reimplement IDR and IDA using the radix tree

Andrew Morton
2016-12-06T20:45:52Z

On Mon, 28 Nov 2016 13:50:37 -0800 Matthew Wilcox <mawilcox@linuxonhyperv.com> wrote:

> 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.
>
> 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>
> ---
> include/linux/idr.h | 132 ++--
> include/linux/radix-tree.h | 5 +-
> init/main.c | 3 +-
> lib/idr.c | 1078 -------------------------------
> lib/radix-tree.c | 632 ++++++++++++++++--

hm. It's just a cosmetic issue, but perhaps the idr
wrappers-around-radix-tree code should be in a different .c file.

Before:

akpm3:/usr/src/25> size lib/idr.o lib/radix-tree.o
text data bss dec hex filename
6566 89 16 6671 1a0f lib/idr.o
11811 117 8 11936 2ea0 lib/radix-tree.o

After:

text data bss dec hex filename
14151 118 8 14277 37c5 lib/radix-tree.o

So 4500 bytes saved. Decent.