Originally, I sent an interval tree cleanup[1], but lack of reasonable test.
As Matthew suggested, this patch set includes proper test to exercise the
change in interval tree.
Since rbtree/augmented tree/interval tree share similar data structure,
besides new cases for interval tree, this patch set also does cleanup for
others.
Patch 1: There are test cases as kernel module, this patch enable them in
userland. This would help for testing and debugging.
Patch 2: Split cases for better reading. And prepare for new cases adding.
Patch 3: Add random seed to cover different situations
Patch 4: Add case for interval_tree_iter_xxx() helper
Patch 5: Add case for span iteration
Patch 6: is the original cleanup
Patch 7: fix the comment of interval_tree_span_iter_next_gap()
v2:
* move definition of container_of() into container_of.h
* fix compile warning by defining seed with ullong
[1]: https://lkml.kernel.org/r/20250224022239.21976-1-richard.weiyang@xxxxxxxxx
Wei Yang (7):
lib/rbtree: enable userland test suite for rbtree related data
structure
lib/rbtree: split tests
lib/rbtree: add random seed
lib/interval_tree: add test case for interval_tree_iter_xxx() helpers
lib/interval_tree: add test case for span iteration
lib/interval_tree: skip the check before go to the right subtree
lib/interval_tree: fix the comment of
interval_tree_span_iter_next_gap()
include/linux/interval_tree_generic.h | 8 +-
include/linux/types.h | 1 +
lib/interval_tree.c | 12 +-
lib/interval_tree_test.c | 237 ++++++++++++++++--
lib/rbtree_test.c | 30 ++-
tools/include/asm/timex.h | 13 +
tools/include/linux/bitmap.h | 21 ++
tools/include/linux/container_of.h | 18 ++
tools/include/linux/kernel.h | 14 +-
tools/include/linux/math64.h | 5 +
tools/include/linux/moduleparam.h | 7 +
tools/include/linux/prandom.h | 51 ++++
tools/include/linux/slab.h | 1 +
tools/include/linux/types.h | 2 +
tools/lib/bitmap.c | 20 ++
tools/lib/slab.c | 16 ++
tools/testing/rbtree/Makefile | 33 +++
tools/testing/rbtree/interval_tree_test.c | 58 +++++
tools/testing/rbtree/rbtree_test.c | 48 ++++
tools/testing/rbtree/test.h | 4 +
tools/testing/shared/interval_tree-shim.c | 5 +
tools/testing/shared/linux/interval_tree.h | 7 +
.../shared/linux/interval_tree_generic.h | 2 +
tools/testing/shared/linux/rbtree.h | 8 +
tools/testing/shared/linux/rbtree_augmented.h | 7 +
tools/testing/shared/linux/rbtree_types.h | 8 +
tools/testing/shared/rbtree-shim.c | 6 +
27 files changed, 600 insertions(+), 42 deletions(-)
create mode 100644 tools/include/asm/timex.h
create mode 100644 tools/include/linux/container_of.h
create mode 100644 tools/include/linux/moduleparam.h
create mode 100644 tools/include/linux/prandom.h
create mode 100644 tools/testing/rbtree/Makefile
create mode 100644 tools/testing/rbtree/interval_tree_test.c
create mode 100644 tools/testing/rbtree/rbtree_test.c
create mode 100644 tools/testing/rbtree/test.h
create mode 100644 tools/testing/shared/interval_tree-shim.c
create mode 100644 tools/testing/shared/linux/interval_tree.h
create mode 100644 tools/testing/shared/linux/interval_tree_generic.h
create mode 100644 tools/testing/shared/linux/rbtree.h
create mode 100644 tools/testing/shared/linux/rbtree_augmented.h
create mode 100644 tools/testing/shared/linux/rbtree_types.h
create mode 100644 tools/testing/shared/rbtree-shim.c
--
2.34.1
