git: 6164e0292234 - stable/13 - rb_tree: test rank balance
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Sat, 01 Oct 2022 17:54:01 UTC
The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=6164e0292234c1b6901e7b892d617971d3e7abca commit 6164e0292234c1b6901e7b892d617971d3e7abca Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2022-09-08 02:40:05 +0000 Commit: Doug Moore <dougm@FreeBSD.org> CommitDate: 2022-10-01 17:50:33 +0000 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 (cherry picked from commit 2c545cf3b06310e248dd4427f31e73f0bc1ad504) --- sys/sys/tree.h | 37 ++++++++++++++++++++++++++++ tests/sys/sys/rb_test.c | 65 ++++++++++++++++++++++++++----------------------- 2 files changed, 71 insertions(+), 31 deletions(-) diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 3f1735d2a837..414a89e202a0 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -410,12 +410,17 @@ struct { \ RB_SET_PARENT(elm, tmp, field); \ } while (/*CONSTCOND*/ 0) +#if defined(_KERNEL) && defined(DIAGNOSTIC) && !defined(_RB_DIAGNOSTIC) +#define _RB_DIAGNOSTIC 1 +#endif + /* Generates prototypes and inline functions */ #define RB_PROTOTYPE(name, type, field, cmp) \ RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ + RB_PROTOTYPE_RANK(name, type, attr) \ RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ RB_PROTOTYPE_INSERT(name, type, attr); \ @@ -426,6 +431,12 @@ struct { \ RB_PROTOTYPE_PREV(name, type, attr); \ RB_PROTOTYPE_MINMAX(name, type, attr); \ RB_PROTOTYPE_REINSERT(name, type, attr); +#ifdef _RB_DIAGNOSTIC +#define RB_PROTOTYPE_RANK(name, type, attr) \ + attr int name##_RB_RANK(struct type *); +#else +#define RB_PROTOTYPE_RANK(name, type, attr) +#endif #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ attr void name##_RB_INSERT_COLOR(struct name *, struct type *) #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ @@ -456,6 +467,7 @@ struct { \ #define RB_GENERATE_STATIC(name, type, field, cmp) \ RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ + RB_GENERATE_RANK(name, type, field, attr) \ RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ RB_GENERATE_INSERT(name, type, field, cmp, attr) \ @@ -467,6 +479,31 @@ struct { \ RB_GENERATE_MINMAX(name, type, field, attr) \ RB_GENERATE_REINSERT(name, type, field, cmp, attr) +#ifdef _RB_DIAGNOSTIC +#define RB_GENERATE_RANK(name, type, field, attr) \ +attr int \ +name##_RB_RANK(struct type *elm) \ +{ \ + struct type *left, *right; \ + int left_rank, right_rank; \ + __uintptr_t bits; \ + \ + if (elm == NULL) \ + return (0); \ + bits = RB_BITS(elm, field); \ + left = RB_LEFT(elm, field); \ + left_rank = ((bits & RB_RED_L) ? 2 : 1) + name##_RB_RANK(left); \ + right = RB_RIGHT(elm, field); \ + right_rank = ((bits & RB_RED_R) ? 2 : 1) + name##_RB_RANK(right); \ + if (left_rank != right_rank || \ + (left_rank == 2 && left == NULL && right == NULL)) \ + return (-1); \ + return (left_rank); \ +} +#else +#define RB_GENERATE_RANK(name, type, field, attr) +#endif + #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ attr void \ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ diff --git a/tests/sys/sys/rb_test.c b/tests/sys/sys/rb_test.c index c558ad6098cf..149fbe052bde 100644 --- a/tests/sys/sys/rb_test.c +++ b/tests/sys/sys/rb_test.c @@ -29,6 +29,7 @@ */ #include <sys/types.h> +#define _RB_DIAGNOSTIC 1 #include <sys/tree.h> #include <stdlib.h> @@ -54,52 +55,54 @@ RB_PROTOTYPE(tree, node, node, compare); RB_GENERATE(tree, node, node, compare); #define ITER 150 -#define MIN 5 -#define MAX 5000 ATF_TC_WITHOUT_HEAD(rb_test); ATF_TC_BODY(rb_test, tc) { - struct node *tmp, *ins; - int i, max, min; + struct node *tmp, *ins, store[ITER]; + int i, j, k, max, min; - max = min = 42; /* pacify gcc */ + min = ITER; + max = -1; RB_INIT(&root); + /* Initialize keys */ + for (i = 0; i < ITER; i++) + store[i].key = i; + + /* Randomly shuffle keys */ + for (i = 0; i < ITER; i++) { + j = i + arc4random_uniform(ITER - i); + k = store[j].key; + store[j].key = store[i].key; + store[i].key = k; + } + for (i = 0; i < ITER; i++) { - tmp = malloc(sizeof(struct node)); - ATF_REQUIRE_MSG(tmp != NULL, "malloc failed"); - do { - tmp->key = arc4random_uniform(MAX-MIN); - tmp->key += MIN; - } while (RB_FIND(tree, &root, tmp) != NULL); - if (i == 0) - max = min = tmp->key; - else { - if (tmp->key > max) - max = tmp->key; - if (tmp->key < min) - min = tmp->key; + for (j = 0; j < i; ++j) { + tmp = &store[j]; + ATF_REQUIRE_EQ(tmp, RB_FIND(tree, &root, tmp)); } + tmp = &store[i]; + if (tmp->key > max) + max = tmp->key; + if (tmp->key < min) + min = tmp->key; ATF_REQUIRE_EQ(NULL, RB_INSERT(tree, &root, tmp)); + ins = RB_MIN(tree, &root); + ATF_REQUIRE_MSG(ins != NULL, "RB_MIN error"); + ATF_CHECK_EQ(min, ins->key); + ins = RB_MAX(tree, &root); + ATF_REQUIRE_MSG(ins != NULL, "RB_MAX error"); + ATF_CHECK_EQ(max, ins->key); } - - ins = RB_MIN(tree, &root); - ATF_REQUIRE_MSG(ins != NULL, "RB_MIN error"); - ATF_CHECK_EQ(min, ins->key); - tmp = ins; - ins = RB_MAX(tree, &root); - ATF_REQUIRE_MSG(ins != NULL, "RB_MAX error"); - ATF_CHECK_EQ(max, ins->key); - - ATF_CHECK_EQ(tmp, RB_REMOVE(tree, &root, tmp)); - - for (i = 0; i < ITER - 1; i++) { + tmp = RB_ROOT(&root); + ATF_REQUIRE_MSG(tree_RB_RANK(tmp) >= 0, "RB rank balance error"); + for (i = 0; i < ITER; i++) { tmp = RB_ROOT(&root); ATF_REQUIRE_MSG(tmp != NULL, "RB_ROOT error"); ATF_CHECK_EQ(tmp, RB_REMOVE(tree, &root, tmp)); - free(tmp); } }