diff options
| author | Matthew Wilcox <mawilcox@microsoft.com> | 2016-12-20 16:27:56 +0100 |
|---|---|---|
| committer | Matthew Wilcox <mawilcox@microsoft.com> | 2017-02-14 03:44:01 +0100 |
| commit | 0a835c4f090af2c76fc2932c539c3b32fd21fbbb (patch) | |
| tree | 729c24514309afc323ee08e6d8336eb1e558406e /tools/testing/radix-tree/Makefile | |
| parent | radix-tree: Add radix_tree_iter_delete (diff) | |
| download | linux-0a835c4f090af2c76fc2932c539c3b32fd21fbbb.tar.xz linux-0a835c4f090af2c76fc2932c539c3b32fd21fbbb.zip | |
Reimplement IDR and IDA using the radix tree
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>
Diffstat (limited to 'tools/testing/radix-tree/Makefile')
| -rw-r--r-- | tools/testing/radix-tree/Makefile | 10 |
1 files changed, 7 insertions, 3 deletions
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 5274e88cd293..3597a3a9f269 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -2,8 +2,8 @@ CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE LDFLAGS += -lpthread -lurcu TARGETS = main -OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_bit.o \ - regression1.o regression2.o regression3.o multiorder.o \ +OFILES = main.o radix-tree.o idr.o linux.o test.o tag_check.o find_bit.o \ + regression1.o regression2.o regression3.o multiorder.o idr-test.o \ iteration_check.o benchmark.o ifdef BENCHMARK @@ -23,7 +23,11 @@ vpath %.c ../../lib $(OFILES): *.h */*.h \ ../../include/linux/*.h \ ../../include/asm/*.h \ - ../../../include/linux/radix-tree.h + ../../../include/linux/radix-tree.h \ + ../../../include/linux/idr.h radix-tree.c: ../../../lib/radix-tree.c sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@ + +idr.c: ../../../lib/idr.c + sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@ |