HomeFreeBSD

rb_tree: test rank balance

Description

rb_tree: test rank balance

With _RB_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.

Reviewed by: markj
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36484

Details

Provenance
dougmAuthored on Sep 8 2022, 2:40 AM
Reviewer
markj
Differential Revision
D36484: rb_tree: test rank balance
Parents
rG0eb736c0f673: stand: Unbreak FAT32 in loader
Branches
Unknown
Tags
Unknown