All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
rbmonkey.c
Go to the documentation of this file.
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <netdb.h>
4 
5 #include <freeradius-devel/libradius.h>
6 
7 /*
8  * We need knowlege of the internal structures.
9  * This needs to be kept in lockstep with rbtree.c
10  */
11 
12 /* RED-BLACK tree description */
13 typedef enum {
17 
18 struct rbnode_t {
19  rbnode_t *left; //!< left child
20  rbnode_t *right; //!< right child
21  rbnode_t *parent; //!< Parent
22  node_colour_t colour; //!< Node colour (BLACK, RED)
23  void *data; //!< data stored in node
24 };
25 
26 struct rbtree_t {
27 #ifndef NDEBUG
28  uint32_t magic;
29 #endif
30  rbnode_t *root;
31  int num_elements;
34  bool replace;
35 #ifdef HAVE_PTHREAD_H
36  bool lock;
37  pthread_mutex_t mutex;
38 #endif
39 };
40 
41 /* Storage for the NIL pointer. */
42 static rbnode_t *NIL;
43 
44 static int comp(void const *a, void const *b)
45 {
46  if (*(uint32_t const *)a > *(uint32_t const *)b) {
47  return -1;
48  }
49 
50  if (*(uint32_t const *)a < *(uint32_t const *)b) {
51  return 1;
52  }
53  return 0;
54 }
55 
56 #if 0
57 static int print_cb(UNUSED void *ctx, void *i)
58 {
59  fprintf(stderr, "%i\n", *(int*)i);
60  return 0;
61 }
62 #endif
63 
64 #define MAXSIZE 1024
65 
66 static int r = 0;
67 static uint32_t rvals[MAXSIZE];
68 
69 static int store_cb(UNUSED void *ctx, void *i)
70 {
71  rvals[r++] = *(int const *)i;
72  return 0;
73 }
74 
75 static uint32_t mask;
76 
77 static int filter_cb(void *ctx, void *i)
78 {
79  if ((*(uint32_t *)i & mask) == (*(uint32_t *)ctx & mask)) {
80  return 2;
81  }
82  return 0;
83 }
84 
85 /*
86  * Returns the count of BLACK nodes from root to child leaves, or a
87  * negative number indicating which RED-BLACK rule was broken.
88  */
89 static int rbcount(rbtree_t *t)
90 {
91  rbnode_t *n;
92  int count, count_expect;
93 
94  count_expect = -1;
95  n = t->root;
96  if (!n || n == NIL) {
97  return 0;
98  }
99  if (n->colour != BLACK) {
100  return -2; /* root not BLACK */
101  }
102  count = 0;
103 descend:
104  while (n->left != NIL) {
105  if (n->colour == RED) {
106  if (n->left->colour != BLACK || n->right->colour != BLACK) {
107  return -4; /* Children of RED nodes must be BLACK */
108  }
109  }
110  else {
111  count++;
112  }
113  n = n->left;
114  }
115  if (n->right != NIL) {
116  if (n->colour == RED) {
117  if (n->left->colour != BLACK || n->right->colour != BLACK) {
118  return -4; /* Children of RED nodes must be BLACK */
119  }
120  }
121  else {
122  count++;
123  }
124  n = n->right;
125  }
126  if (n->left != NIL || n->right != NIL) {
127  goto descend;
128  }
129  if (count_expect < 0) {
130  count_expect = count + (n->colour == BLACK);
131  }
132  else {
133  if (count_expect != count + (n->colour == BLACK)) {
134  fprintf(stderr,"Expected %i got %i\n", count_expect, count);
135  return -5; /* All paths must traverse the same number of BLACK nodes. */
136  }
137  }
138 ascend:
139  if (!n->parent) return count_expect;
140  while (n->parent->right == n) {
141  n = n->parent;
142  if (!n->parent) return count_expect;
143  if (n->colour == BLACK) {
144  count--;
145  }
146  }
147  if (n->parent->left == n) {
148  if (n->parent->right != NIL) {
149  n = n->parent->right;
150  goto descend;
151  }
152  n = n->parent;
153  if (!n->parent) return count_expect;
154  if (n->colour == BLACK) {
155  count--;
156  }
157  }
158  goto ascend;
159 }
160 
161 #define REPS 10
162 
163 int main(UNUSED int argc, UNUSED char *argv[])
164 {
165  rbtree_t *t;
166  int i, j;
167  uint32_t thresh;
168  int n, rep;
169  uint32_t vals[MAXSIZE];
170  struct timeval now;
171  gettimeofday(&now, NULL);
172 
173  /* TODO: make starting seed and repetitions a CLI option */
174  rep = REPS;
175 
176 again:
177  if (!--rep) return 0;
178 
179  thresh = fr_rand();
180  mask = 0xff >> (fr_rand() & 7);
181  thresh &= mask;
182  n = (fr_rand() % MAXSIZE) + 1;
183 
184  fprintf(stderr, "filter = %x mask = %x n= %i\n",
185  thresh, mask, n);
186 
187  t = rbtree_create(NULL, comp, free, RBTREE_FLAG_LOCK);
188  /* Find out the value of the NIL node */
189  NIL = t->root->left;
190 
191  for (i = 0; i < n; i++) {
192  int *p;
193  p = malloc(sizeof(*p));
194  *p = fr_rand();
195  vals[i] = *p;
196  rbtree_insert(t, p);
197  }
198 
199  i = rbcount(t);
200  fprintf(stderr,"After insert rbcount is %i.\n", i);
201  if (i < 0) { return i; }
202 
203  qsort(vals, n, sizeof(int), comp);
204 
205  /*
206  * For testing deletebydata instead
207 
208  for (i = 0; i < n; i++) {
209  if (filter_cb(&vals[i], &thresh) == 2) {
210  rbtree_deletebydata(t, &vals[i]);
211  }
212  }
213 
214  *
215  */
216  (void) rbtree_walk(t, RBTREE_DELETE_ORDER, filter_cb, &thresh);
217  i = rbcount(t);
218  fprintf(stderr,"After delete rbcount is %i.\n", i);
219  if (i < 0) { return i; }
220 
221  r = 0;
223 
224  for (j = i = 0; i < n; i++) {
225  if (i && vals[i-1] == vals[i]) continue;
226  if (!filter_cb(&thresh, &vals[i])) {
227  if (vals[i] != rvals[j]) goto bad;
228  j++;
229  }
230  }
231  fprintf(stderr,"matched OK\n");
232  rbtree_free(t);
233  goto again;
234 
235 bad:
236  for (j = i = 0; i < n; i++) {
237  if (i && vals[i-1] == vals[i]) continue;
238  if (!filter_cb(&thresh, &vals[i])) {
239  fprintf(stderr, "%i: %x %x\n", j, vals[i], rvals[j]);
240  j++;
241  } else {
242  fprintf(stderr, "skipped %x\n", vals[i]);
243  }
244  }
245  return -1;
246 }
247 
uint32_t magic
Definition: rbtree.c:56
rbnode_t * left
Left child.
Definition: rbtree.c:44
void * data
data stored in node
Definition: rbtree.c:48
rbnode_t * root
Definition: rbtree.c:58
void rbtree_free(rbtree_t *tree)
Definition: rbtree.c:84
static int rbcount(rbtree_t *t)
Definition: rbmonkey.c:89
rb_comparator_t compare
Definition: rbtree.c:60
int(* rb_comparator_t)(void const *ctx, void const *data)
Definition: libradius.h:529
uint32_t fr_rand(void)
Return a 32-bit random number.
Definition: radius.c:1621
int main(UNUSED int argc, UNUSED char *argv[])
Definition: rbmonkey.c:163
#define UNUSED
Definition: libradius.h:134
rbnode_t * parent
Parent.
Definition: rbtree.c:46
node_colour_t
Definition: rbmonkey.c:13
bool replace
Definition: rbtree.c:62
static int store_cb(UNUSED void *ctx, void *i)
Definition: rbmonkey.c:69
rbtree_t * rbtree_create(TALLOC_CTX *ctx, rb_comparator_t compare, rb_free_t node_free, int flags)
Create a new RED-BLACK tree.
Definition: rbtree.c:112
static int comp(void const *a, void const *b)
Definition: rbmonkey.c:44
static uint32_t mask
Definition: rbmonkey.c:75
#define REPS
Definition: rbmonkey.c:161
int rbtree_walk(rbtree_t *tree, rb_order_t order, rb_walker_t compare, void *context)
Definition: rbtree.c:693
static rbnode_t * NIL
Definition: rbmonkey.c:42
static uint32_t rvals[MAXSIZE]
Definition: rbmonkey.c:67
#define MAXSIZE
Definition: rbmonkey.c:64
void(* rb_free_t)(void *data)
Definition: libradius.h:531
Definition: rbmonkey.c:14
node_colour_t
Definition: rbtree.c:38
bool rbtree_insert(rbtree_t *tree, void *data)
Definition: rbtree.c:329
#define RBTREE_FLAG_LOCK
Definition: libradius.h:527
static int filter_cb(void *ctx, void *i)
Definition: rbmonkey.c:77
rbnode_t * right
Right child.
Definition: rbtree.c:45
node_colour_t colour
Node colour (BLACK, RED)
Definition: rbtree.c:47
static int r
Definition: rbmonkey.c:66
rb_free_t free
Definition: rbtree.c:61
Definition: rbmonkey.c:15
int num_elements
Definition: rbtree.c:59