]> mj.ucw.cz Git - libucw.git/blob - lib/redblack-test.c
80a7a000ce8711603b11fce25877ca03fb46b4bb
[libucw.git] / lib / redblack-test.c
1 /*
2  *      Test of red-black trees
3  *
4  *      (c) 2002, Robert Spalek <robert@ucw.cz>
5  */
6
7 #include "lib/lib.h"
8 #include "lib/getopt.h"
9 #include "lib/fastbuf.h"
10 #include <stdio.h>
11 #include <stdlib.h>
12
13 struct my1_node
14 {
15         int key;
16         int x;
17 };
18
19 static void my_dump_key(struct fastbuf *fb, struct my1_node *n)
20 {
21         char tmp[20];
22         sprintf(tmp, "key=%d ", n->key);
23         bputs(fb, tmp);
24 }
25
26 static void my_dump_data(struct fastbuf *fb, struct my1_node *n)
27 {
28         char tmp[20];
29         sprintf(tmp, "x=%d ", n->x);
30         bputs(fb, tmp);
31 }
32
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
42 #include "redblack.h"
43
44 static void my_check_order(struct fastbuf *fb, struct my_tree *t)
45 {
46         int last_key = 0x80000000;
47         TREE_FOR_ALL(my, t, n)
48         {
49                 ASSERT(n->key >= last_key);
50                 last_key = n->key;
51                 if (fb)
52                 {
53                         char tmp[30];
54                         sprintf(tmp, "%d -> %d\n", n->key, n->x);
55                         bputs(fb, tmp);
56                 }
57         }
58         TREE_END_FOR;
59         if (fb)
60                 bflush(fb);
61 }
62
63 struct my2_node
64 {
65         char key[1];
66 };
67
68 static void my2_dump_key(struct fastbuf *fb, struct my2_node *n)
69 {
70         bputs(fb, "key=");
71         bputs(fb, n->key);
72         bputc(fb, ' ');
73 }
74
75 static void my2_dump_data(struct fastbuf *fb UNUSED, struct my2_node *n UNUSED)
76 {
77 }
78
79 #define TREE_NODE struct my2_node
80 #define TREE_PREFIX(x) my2_##x
81 #define TREE_KEY_ENDSTRING key
82 #define TREE_NOCASE
83 #define TREE_WANT_CLEANUP
84 #define TREE_WANT_NEW
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_STATIC
91 #define TREE_CONSERVE_SPACE
92 #include "redblack.h"
93
94 static void random_string(char *txt, uns max_len)
95 {
96         uns len = random() % max_len;
97         uns j;
98         for (j=0; j<len; j++)
99                 txt[j] = random() % 96 + 32;
100         txt[len] = 0;
101 }
102
103 static char *options = CF_SHORT_OPTS "vn:a";
104
105 static char *help = "\
106 Usage: test1.bin <options>\n\
107 Options:\n"
108 CF_USAGE
109 "-v\tSet verbose mode\n\
110 -n num\tNumber of inserted nodes\n\
111 -a\tProbe some ASSERTs\n\
112 ";
113
114 static void NONRET
115 usage(void)
116 {
117         fputs(help, stderr);
118         exit(1);
119 }
120
121 int
122 main(int argc, char **argv)
123 {
124         int verbose = 0, number = 1000, asserts = 0;
125         int opt;
126         struct fastbuf *fb, *dump_fb;
127         struct my_tree t;
128         struct my2_tree t2;
129         int i;
130         cf_def_file = NULL;
131         log_init(argv[0]);
132         while ((opt = cf_getopt(argc, argv, options, CF_NO_LONG_OPTS, NULL)) >= 0)
133                 switch (opt)
134                 {
135                         case 'v':
136                                 verbose++;
137                                 break;
138                         case 'n':
139                                 number = atoi(optarg);
140                                 break;
141                         case 'a':
142                                 asserts++;
143                                 break;
144                         default:
145                                 usage();
146                                 break;
147                 }
148         if (optind < argc)
149                 usage();
150         fb = bfdopen(1, 4096);
151         if (verbose > 1)
152                 dump_fb = fb;
153         else
154                 dump_fb = NULL;
155
156         my_init(&t);
157         for (i=0; i<number; i++)
158                 my_lookup(&t, random() % 1000000)->x = i;
159         my_dump(dump_fb, &t);
160         my_check_order(dump_fb, &t);
161         if (asserts)
162         {
163                 my_new(&t, 1);
164                 my_new(&t, 1);
165         }
166         my_cleanup(&t);
167         if (verbose > 0)
168                 bputs(fb, "Load test passed\n");
169
170         my_init(&t);
171         for (i=0; i<100; i++)
172         {
173                 my_new(&t, i)->x = i;
174                 my_dump(dump_fb, &t);
175         }
176         for (i=0; i<100; i++)
177         {
178                 int a = i/10, b = i%10, j = a*10 + (b + a) % 10;
179                 int res UNUSED = my_delete(&t, j);
180                 ASSERT(res);
181                 my_dump(dump_fb, &t);
182         }
183         my_cleanup(&t);
184         if (verbose > 0)
185                 bputs(fb, "Sequential adding and deleting passed\n");
186
187         my_init(&t);
188         for (i=0; i<997; i++)
189         {
190                 my_new(&t, i*238 % 997)->x = i;
191                 my_dump(NULL, &t);
192         }
193         my_dump(dump_fb, &t);
194         i = 0;
195         TREE_FOR_ALL(my, &t, n)
196         {
197                 ASSERT(n->key == i);
198                 i++;
199         }
200         TREE_END_FOR;
201         ASSERT(i == 997);
202         for (i=0; i<997; i++)
203         {
204                 int res UNUSED = my_delete(&t, i*111 % 997);
205                 ASSERT(res);
206                 my_dump(NULL, &t);
207         }
208         my_dump(dump_fb, &t);
209         my_cleanup(&t);
210         if (verbose > 0)
211                 bputs(fb, "Complete tree passed\n");
212
213         my2_init(&t2);
214         for (i=0; i<number; i++)
215         {
216                 char txt[30];
217                 random_string(txt, 30);
218                 my2_new(&t2, txt);
219         }
220         my2_dump(dump_fb, &t2);
221         TREE_FOR_ALL(my2, &t2, n)
222         {
223                 my2_node *tmp;
224                 int count = 0;
225                 for (tmp=n; tmp; tmp = my2_find_next(tmp))
226                         count++;
227                 if (dump_fb)
228                 {
229                         char txt[20];
230                         bputs(dump_fb, n->key);
231                         sprintf(txt, ": %d\n", count);
232                         bputs(dump_fb, txt);
233                 }
234         }
235         TREE_END_FOR;
236         while (t2.count > 0)
237         {
238                 char txt[30];
239                 my2_node *n;
240                 random_string(txt, 30);
241                 n = my2_search(&t2, txt);
242                 ASSERT(n);
243                 my2_remove(&t2, n);
244         }
245         my2_dump(dump_fb, &t2);
246         my2_cleanup(&t2);
247         if (verbose > 0)
248                 bputs(fb, "String test passed\n");
249
250         bclose(fb);
251         return 0;
252 }