summaryrefslogtreecommitdiffstats
path: root/src/tests/rbmonkey.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-28 09:49:46 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-28 09:49:46 +0000
commit50b37d4a27d3295a29afca2286f1a5a086142cec (patch)
tree9212f763934ee090ef72d823f559f52ce387f268 /src/tests/rbmonkey.c
parentInitial commit. (diff)
downloadfreeradius-50b37d4a27d3295a29afca2286f1a5a086142cec.tar.xz
freeradius-50b37d4a27d3295a29afca2286f1a5a086142cec.zip
Adding upstream version 3.2.1+dfsg.upstream/3.2.1+dfsgupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/tests/rbmonkey.c')
-rw-r--r--src/tests/rbmonkey.c250
1 files changed, 250 insertions, 0 deletions
diff --git a/src/tests/rbmonkey.c b/src/tests/rbmonkey.c
new file mode 100644
index 0000000..dd58ff0
--- /dev/null
+++ b/src/tests/rbmonkey.c
@@ -0,0 +1,250 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <netdb.h>
+#include <assert.h>
+
+#include <freeradius-devel/libradius.h>
+
+/*
+ * We need knowlege of the internal structures.
+ * This needs to be kept in lockstep with rbtree.c
+ */
+
+/* RED-BLACK tree description */
+typedef enum {
+ BLACK,
+ RED
+} node_colour_t;
+
+struct rbnode_t {
+ rbnode_t *left; //!< left child
+ rbnode_t *right; //!< right child
+ rbnode_t *parent; //!< Parent
+ node_colour_t colour; //!< Node colour (BLACK, RED)
+ void *data; //!< data stored in node
+};
+
+struct rbtree_t {
+#ifndef NDEBUG
+ uint32_t magic;
+#endif
+ rbnode_t *root;
+ int num_elements;
+ rb_comparator_t compare;
+ rb_free_t free;
+ bool replace;
+#ifdef HAVE_PTHREAD_H
+ bool lock;
+ pthread_mutex_t mutex;
+#endif
+};
+
+/* Storage for the NIL pointer. */
+static rbnode_t *NIL;
+
+static int comp(void const *a, void const *b)
+{
+ if (*(uint32_t const *)a > *(uint32_t const *)b) {
+ return -1;
+ }
+
+ if (*(uint32_t const *)a < *(uint32_t const *)b) {
+ return 1;
+ }
+ return 0;
+}
+
+#if 0
+static int print_cb(UNUSED void *ctx, void *i)
+{
+ fprintf(stderr, "%i\n", *(int*)i);
+ return 0;
+}
+#endif
+
+#define MAXSIZE 1024
+
+static int r = 0;
+static uint32_t rvals[MAXSIZE];
+
+static int store_cb(UNUSED void *ctx, void *i)
+{
+ rvals[r++] = *(int const *)i;
+ return 0;
+}
+
+static uint32_t mask;
+
+static int filter_cb(void *ctx, void *i)
+{
+ if ((*(uint32_t *)i & mask) == (*(uint32_t *)ctx & mask)) {
+ return 2;
+ }
+ return 0;
+}
+
+/*
+ * Returns the count of BLACK nodes from root to child leaves, or a
+ * negative number indicating which RED-BLACK rule was broken.
+ */
+static int rbcount(rbtree_t *t)
+{
+ rbnode_t *n;
+ int count, count_expect;
+
+ count_expect = -1;
+ n = t->root;
+ if (!n || n == NIL) {
+ return 0;
+ }
+ if (n->colour != BLACK) {
+ return -2; /* root not BLACK */
+ }
+ count = 0;
+descend:
+ while (n->left != NIL) {
+ if (n->colour == RED) {
+ if (n->left->colour != BLACK || n->right->colour != BLACK) {
+ return -4; /* Children of RED nodes must be BLACK */
+ }
+ }
+ else {
+ count++;
+ }
+ n = n->left;
+ }
+ if (n->right != NIL) {
+ if (n->colour == RED) {
+ if (n->left->colour != BLACK || n->right->colour != BLACK) {
+ return -4; /* Children of RED nodes must be BLACK */
+ }
+ }
+ else {
+ count++;
+ }
+ n = n->right;
+ }
+ if (n->left != NIL || n->right != NIL) {
+ goto descend;
+ }
+ if (count_expect < 0) {
+ count_expect = count + (n->colour == BLACK);
+ }
+ else {
+ if (count_expect != count + (n->colour == BLACK)) {
+ fprintf(stderr,"Expected %i got %i\n", count_expect, count);
+ return -5; /* All paths must traverse the same number of BLACK nodes. */
+ }
+ }
+ascend:
+ if (n->parent != NIL) return count_expect;
+ while (n->parent->right == n) {
+ n = n->parent;
+ if (!n->parent) return count_expect;
+ if (n->colour == BLACK) {
+ count--;
+ }
+ }
+ if (n->parent->left == n) {
+ if (n->parent->right != NIL) {
+ n = n->parent->right;
+ goto descend;
+ }
+ n = n->parent;
+ if (!n->parent) return count_expect;
+ if (n->colour == BLACK) {
+ count--;
+ }
+ }
+ goto ascend;
+}
+
+#define REPS 10
+
+int main(UNUSED int argc, UNUSED char *argv[])
+{
+ rbtree_t *t;
+ int i, j;
+ uint32_t thresh;
+ int n, rep;
+ uint32_t vals[MAXSIZE];
+ struct timeval now;
+ gettimeofday(&now, NULL);
+
+ /* TODO: make starting seed and repetitions a CLI option */
+ rep = REPS;
+
+again:
+ if (!--rep) return 0;
+
+ thresh = fr_rand();
+ mask = 0xff >> (fr_rand() & 7);
+ thresh &= mask;
+ n = (fr_rand() % MAXSIZE) + 1;
+
+ fprintf(stderr, "filter = %x mask = %x n= %i\n",
+ thresh, mask, n);
+
+ t = rbtree_create(NULL, comp, free, RBTREE_FLAG_LOCK);
+ /* Find out the value of the NIL node */
+ assert(t->root != NULL);
+ assert(t->root->parent == t->root);
+ NIL = t->root;
+
+ for (i = 0; i < n; i++) {
+ int *p;
+ p = malloc(sizeof(*p));
+ *p = fr_rand();
+ vals[i] = *p;
+ rbtree_insert(t, p);
+ }
+
+ i = rbcount(t);
+ fprintf(stderr,"After insert rbcount is %i.\n", i);
+ if (i < 0) { return i; }
+
+ qsort(vals, n, sizeof(int), comp);
+
+ /*
+ * For testing deletebydata instead
+
+ for (i = 0; i < n; i++) {
+ if (filter_cb(&vals[i], &thresh) == 2) {
+ rbtree_deletebydata(t, &vals[i]);
+ }
+ }
+
+ *
+ */
+ (void) rbtree_walk(t, RBTREE_DELETE_ORDER, filter_cb, &thresh);
+ i = rbcount(t);
+ fprintf(stderr,"After delete rbcount is %i.\n", i);
+ if (i < 0) { return i; }
+
+ r = 0;
+ rbtree_walk(t, RBTREE_IN_ORDER, &store_cb, NULL);
+
+ for (j = i = 0; i < n; i++) {
+ if (i && vals[i-1] == vals[i]) continue;
+ if (!filter_cb(&thresh, &vals[i])) {
+ if (vals[i] != rvals[j]) goto bad;
+ j++;
+ }
+ }
+ fprintf(stderr,"matched OK\n");
+ rbtree_free(t);
+ goto again;
+
+bad:
+ for (j = i = 0; i < n; i++) {
+ if (i && vals[i-1] == vals[i]) continue;
+ if (!filter_cb(&thresh, &vals[i])) {
+ fprintf(stderr, "%i: %x %x\n", j, vals[i], rvals[j]);
+ j++;
+ } else {
+ fprintf(stderr, "skipped %x\n", vals[i]);
+ }
+ }
+ return -1;
+}
+