Adding upstream version 3.2.1+dfsg.upstream/3.2.1+dfsgupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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;
+}
+