5 #include <freeradius-devel/libradius.h>
37 pthread_mutex_t mutex;
44 static int comp(
void const *a,
void const *b)
46 if (*(uint32_t
const *)a > *(uint32_t
const *)b) {
50 if (*(uint32_t
const *)a < *(uint32_t
const *)b) {
57 static int print_cb(
UNUSED void *ctx,
void *i)
59 fprintf(stderr,
"%i\n", *(
int*)i);
71 rvals[r++] = *(
int const *)i;
79 if ((*(uint32_t *)i & mask) == (*(uint32_t *)ctx & mask)) {
92 int count, count_expect;
104 while (n->
left != NIL) {
115 if (n->
right != NIL) {
129 if (count_expect < 0) {
133 if (count_expect != count + (n->
colour ==
BLACK)) {
134 fprintf(stderr,
"Expected %i got %i\n", count_expect, count);
139 if (!n->
parent)
return count_expect;
142 if (!n->
parent)
return count_expect;
153 if (!n->
parent)
return count_expect;
171 gettimeofday(&now, NULL);
177 if (!--rep)
return 0;
180 mask = 0xff >> (
fr_rand() & 7);
184 fprintf(stderr,
"filter = %x mask = %x n= %i\n",
191 for (i = 0; i < n; i++) {
193 p = malloc(
sizeof(*p));
200 fprintf(stderr,
"After insert rbcount is %i.\n", i);
201 if (i < 0) {
return i; }
203 qsort(vals, n,
sizeof(
int),
comp);
218 fprintf(stderr,
"After delete rbcount is %i.\n", i);
219 if (i < 0) {
return i; }
224 for (j = i = 0; i < n; i++) {
225 if (i && vals[i-1] == vals[i])
continue;
227 if (vals[i] != rvals[j])
goto bad;
231 fprintf(stderr,
"matched OK\n");
236 for (j = i = 0; i < n; i++) {
237 if (i && vals[i-1] == vals[i])
continue;
239 fprintf(stderr,
"%i: %x %x\n", j, vals[i], rvals[j]);
242 fprintf(stderr,
"skipped %x\n", vals[i]);
rbnode_t * left
Left child.
void * data
data stored in node
void rbtree_free(rbtree_t *tree)
static int rbcount(rbtree_t *t)
int(* rb_comparator_t)(void const *ctx, void const *data)
uint32_t fr_rand(void)
Return a 32-bit random number.
int main(UNUSED int argc, UNUSED char *argv[])
static int store_cb(UNUSED void *ctx, void *i)
rbtree_t * rbtree_create(TALLOC_CTX *ctx, rb_comparator_t compare, rb_free_t node_free, int flags)
Create a new RED-BLACK tree.
static int comp(void const *a, void const *b)
int rbtree_walk(rbtree_t *tree, rb_order_t order, rb_walker_t compare, void *context)
static uint32_t rvals[MAXSIZE]
void(* rb_free_t)(void *data)
bool rbtree_insert(rbtree_t *tree, void *data)
static int filter_cb(void *ctx, void *i)
rbnode_t * right
Right child.
node_colour_t colour
Node colour (BLACK, RED)