rb_tree: test rank balance

[dougm]

Summary

With DIAGNOSTIC defined, provide an RB_RANK method to compute the rank of a node in an rb-tree, if the subtree rooted at that node is rank-balanced, and -1 otherwise.

In rb_test, rewrite a bit to avoid malloc/free and nondeterministic running times because of randomness. Allocate all the nodes on the stack, and shuffle a set of keys to get randomness for the testing.

Add a rank-balance check for the completed tree.

Add something to the makefile that seems likely to define DIAGNOSTIC for rb_test.

Test Plan

The kernel compiles.

The code added here has been tested elsewhere and copied into this test framework. I'm not sure how to test in this framework.

[dougm]

Prefix name## to RB_RANK calls. Which suggests that DIAGNOSTIC hasn't been defined for building the test.

[markj]

sys/sys/tree.h

434

tree.h is used outside of the kernel, so this check is sensitive to any definition of DIAGNOSTIC. An improvement would be to test _RB_DIAGNOSTIC instead and have

#if defined(_KERNEL) && defined(DIAGNOSTIC)
#define _RB_DIAGNOSTIC 1
#endif

tests/sys/sys/rb_test.c

99–100

Wouldn't it be more useful to validate RB_MIN/MAX in each iteration of the preceding loop?

[dougm]

Accept suggestions. Fix errors.

[dougm]

Take out the #include of my own personal tree.h copy.

[markj]

I'm not sure how to test in this framework.

It's rather clunky, but something like the following works:

• install tree.h to /usr/include: # cp /usr/src/sys/sys/tree.h /usr/include/sys
• build tests: # make -C /usr/src/tests/sys/sys
  • you can build just rb_test by specifying it as a target, but I don't know how to install just rb_test
• install tests to /usr/tests/sys/sys: # make -C /usr/src/tests/sys/sys install
• run RB tree tests: $ cd /usr/tests/sys/sys && kyua test rb_test

markj@nuc> cd /usr/tests/sys/sys && kyua test rb_test
rb_test:rb_test  ->  passed  [0.005s]

Results file id is usr_tests_sys_sys.20220907-214805-984250
Results saved to /home/markj/.kyua/store/results.usr_tests_sys_sys.20220907-214805-984250.db

1/1 passed (0 failed)