]> mj.ucw.cz Git - libucw.git/blob - lib/redblack-test.c
Removed duplicate definition of DEBUG and a couple of singned/unsigned
[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/conf.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         cfdeffile = 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 res UNUSED = my_delete(&t, i);
179                 ASSERT(res);
180                 my_dump(dump_fb, &t);
181         }
182         my_cleanup(&t);
183         if (verbose > 0)
184                 bputs(fb, "Sequential adding and deleting passed\n");
185
186         my_init(&t);
187         for (i=0; i<997; i++)
188         {
189                 my_new(&t, i*238 % 997)->x = i;
190                 my_dump(NULL, &t);
191         }
192         my_dump(dump_fb, &t);
193         for (i=0; i<997; i++)
194         {
195                 int res UNUSED = my_delete(&t, i*111 % 997);
196                 ASSERT(res);
197                 my_dump(NULL, &t);
198         }
199         my_dump(dump_fb, &t);
200         i = 0;
201         TREE_FOR_ALL(my, &t, n)
202         {
203                 ASSERT(n->key == i);
204                 i++;
205         }
206         TREE_END_FOR;
207         my_cleanup(&t);
208         if (verbose > 0)
209                 bputs(fb, "Complete tree passed\n");
210
211         my2_init(&t2);
212         for (i=0; i<number; i++)
213         {
214                 char txt[30];
215                 random_string(txt, 30);
216                 my2_new(&t2, txt);
217         }
218         my2_dump(dump_fb, &t2);
219         TREE_FOR_ALL(my2, &t2, n)
220         {
221                 my2_node *tmp;
222                 int count = 0;
223                 for (tmp=n; tmp; tmp = my2_find_next(tmp))
224                         count++;
225                 if (dump_fb)
226                 {
227                         char txt[20];
228                         bputs(dump_fb, n->key);
229                         sprintf(txt, ": %d\n", count);
230                         bputs(dump_fb, txt);
231                 }
232         }
233         TREE_END_FOR;
234         while (t2.count > 0)
235         {
236                 char txt[30];
237                 my2_node *n;
238                 random_string(txt, 30);
239                 n = my2_search(&t2, txt);
240                 ASSERT(n);
241                 my2_remove(&t2, n);
242         }
243         my2_dump(dump_fb, &t2);
244         my2_cleanup(&t2);
245         if (verbose > 0)
246                 bputs(fb, "String test passed\n");
247
248         bclose(fb);
249         return 0;
250 }