diff options
Diffstat (limited to 'src/tests/rbmonkey.c')
| -rw-r--r-- | src/tests/rbmonkey.c | 250 |
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; +} + |