mbox series

[v2,0/7] lib/interval_tree: add some test cases and cleanup

Message ID 20250310074938.26756-1-richard.weiyang@gmail.com (mailing list archive)
Headers show
Series lib/interval_tree: add some test cases and cleanup | expand

Message

Wei Yang March 10, 2025, 7:49 a.m. UTC 
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@gmail.com

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