Page MenuHomeFreeBSD
Files F176891375

D36484.1793580493.diff
No OneTemporary
Actions

Authored By
Unknown
Size
4 KB
Referenced Files
None
Subscribers
None

D36484.1793580493.diff
View Options

Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -416,6 +416,7 @@
#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 +427,12 @@
RB_PROTOTYPE_PREV(name, type, attr); \
RB_PROTOTYPE_MINMAX(name, type, attr); \
RB_PROTOTYPE_REINSERT(name, type, attr);
+#ifdef 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 +463,7 @@
#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 +475,31 @@
RB_GENERATE_MINMAX(name, type, field, attr) \
RB_GENERATE_REINSERT(name, type, field, cmp, attr)
+#ifdef 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 bits; \
+ \
+ if (elm == NULL) \
+ return (0); \
+ bits = RB_BITS(elm, field); \
+ left = RB_LEFT(elm, field); \
+ left_rank = ((bits & RB_RED_L) ? 2 : 1) + RB_RANK(left); \
+ right = RB_RIGHT(elm, field); \
+ right_rank = ((bits & RB_RED_R) ? 2 : 1) + 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) \
Index: tests/sys/sys/Makefile
===================================================================
--- tests/sys/sys/Makefile
+++ tests/sys/sys/Makefile
@@ -16,4 +16,5 @@
CFLAGS.bitstring_test= -fno-strict-overflow
.endif
+CFLAGS.rb_test= -DDIAGNOSTIC
.include <bsd.test.mk>
Index: tests/sys/sys/rb_test.c
===================================================================
--- tests/sys/sys/rb_test.c
+++ tests/sys/sys/rb_test.c
@@ -54,37 +54,47 @@
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));
}
+#ifdef DIAGNOSTIC
+ tmp = RB_ROOT(&root);
+ ATF_REQUIRE_MSG(RB_RANK(tree, tmp) >= 0, "RB rank balance error");
+#endif
ins = RB_MIN(tree, &root);
ATF_REQUIRE_MSG(ins != NULL, "RB_MIN error");
ATF_CHECK_EQ(min, ins->key);
@@ -99,7 +109,6 @@
tmp = RB_ROOT(&root);
ATF_REQUIRE_MSG(tmp != NULL, "RB_ROOT error");
ATF_CHECK_EQ(tmp, RB_REMOVE(tree, &root, tmp));
- free(tmp);
}
}

File Metadata

Mime Type
text/plain
Expires
Mon, Nov 2, 12:48 AM (16 h, 20 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
41299122
Default Alt Text
D36484.1793580493.diff (4 KB)

Event Timeline