2 * Test of red-black trees
4 * (c) 2002, Robert Spalek <robert@ucw.cz>
8 #include <ucw/getopt.h>
9 #include <ucw/fastbuf.h>
19 static void my_dump_key(struct fastbuf *fb, struct my1_node *n)
22 sprintf(tmp, "key=%d ", n->key);
26 static void my_dump_data(struct fastbuf *fb, struct my1_node *n)
29 sprintf(tmp, "x=%d ", n->x);
33 #define TREE_NODE struct my1_node
34 #define TREE_PREFIX(x) my_##x
35 #define TREE_KEY_ATOMIC key
36 #define TREE_WANT_CLEANUP
37 #define TREE_WANT_LOOKUP
38 #define TREE_WANT_DELETE
39 #define TREE_WANT_ITERATOR
40 #define TREE_WANT_DUMP
41 #define TREE_CONSERVE_SPACE
44 static void my_check_order(struct fastbuf *fb, struct my_tree *t)
46 int last_key = 0x80000000;
47 TREE_FOR_ALL(my, t, n)
49 ASSERT(n->key >= last_key);
54 sprintf(tmp, "%d -> %d\n", n->key, n->x);
68 static void my2_dump_key(struct fastbuf *fb, struct my2_node *n)
75 static void my2_dump_data(struct fastbuf *fb UNUSED, struct my2_node *n UNUSED)
79 #define TREE_NODE struct my2_node
80 #define TREE_PREFIX(x) my2_##x
81 #define TREE_KEY_ENDSTRING key
83 #define TREE_WANT_CLEANUP
85 #define TREE_WANT_SEARCH
86 #define TREE_WANT_REMOVE
87 #define TREE_WANT_FIND_NEXT
88 #define TREE_WANT_ITERATOR
89 #define TREE_WANT_DUMP
90 #define TREE_CONSERVE_SPACE
93 static void random_string(char *txt, uint max_len)
95 uint len = random() % max_len;
98 txt[j] = random() % 96 + 32;
102 static char *options = CF_SHORT_OPTS "vn:a";
104 static char *help = "\
105 Usage: test1.bin <options>\n\
108 "-v\tSet verbose mode\n\
109 -n num\tNumber of inserted nodes\n\
110 -a\tProbe some ASSERTs\n\
121 main(int argc, char **argv)
123 int verbose = 0, number = 1000, asserts = 0;
125 struct fastbuf *fb, *dump_fb;
131 while ((opt = cf_getopt(argc, argv, options, CF_NO_LONG_OPTS, NULL)) >= 0)
138 number = atoi(optarg);
149 fb = bfdopen(1, 4096);
156 for (i=0; i<number; i++)
157 my_lookup(&t, random() % 1000000)->x = i;
158 my_dump(dump_fb, &t);
159 my_check_order(dump_fb, &t);
167 bputs(fb, "Load test passed\n");
170 for (i=0; i<100; i++)
172 my_new(&t, i)->x = i;
173 my_dump(dump_fb, &t);
175 for (i=0; i<100; i++)
177 int a = i/10, b = i%10, j = a*10 + (b + a) % 10;
178 int res UNUSED = my_delete(&t, j);
180 my_dump(dump_fb, &t);
184 bputs(fb, "Sequential adding and deleting passed\n");
187 for (i=0; i<997; i++)
189 my_new(&t, i*238 % 997)->x = i;
192 my_dump(dump_fb, &t);
194 TREE_FOR_ALL(my, &t, n)
201 for (i=0; i<997; i++)
203 int res UNUSED = my_delete(&t, i*111 % 997);
207 my_dump(dump_fb, &t);
210 bputs(fb, "Complete tree passed\n");
213 for (i=0; i<number; i++)
216 random_string(txt, 30);
219 my2_dump(dump_fb, &t2);
220 TREE_FOR_ALL(my2, &t2, n)
224 for (tmp=n; tmp; tmp = my2_find_next(tmp))
229 bputs(dump_fb, n->key);
230 sprintf(txt, ": %d\n", count);
239 random_string(txt, 30);
240 n = my2_search(&t2, txt);
244 my2_dump(dump_fb, &t2);
247 bputs(fb, "String test passed\n");