1 /* Copyright (c) 2007-2014 Massachusetts Institute of Technology
3 * Permission is hereby granted, free of charge, to any person obtaining
4 * a copy of this software and associated documentation files (the
5 * "Software"), to deal in the Software without restriction, including
6 * without limitation the rights to use, copy, modify, merge, publish,
7 * distribute, sublicense, and/or sell copies of the Software, and to
8 * permit persons to whom the Software is furnished to do so, subject to
9 * the following conditions:
11 * The above copyright notice and this permission notice shall be
12 * included in all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
17 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
18 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
19 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
20 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
30 /* workaround for Solaris + gcc 3.4.x bug (see configure.ac) */
31 #if defined(__GNUC__) && defined(REPLACEMENT_HUGE_VAL)
33 # define HUGE_VAL REPLACEMENT_HUGE_VAL
36 static int comp(rb_key k1, rb_key k2)
38 if (*k1 < *k2) return -1;
39 if (*k1 > *k2) return +1;
43 int main(int argc, char **argv)
53 fprintf(stderr, "Usage: redblack_test Ntest [rand seed]\n");
58 k = (int *) malloc(N * sizeof(int));
59 rb_tree_init(&t, comp);
61 srand((unsigned) (argc > 2 ? atoi(argv[2]) : time(NULL)));
62 for (i = 0; i < N; ++i) {
63 double *newk = (double *) malloc(sizeof(double));
64 *newk = (k[i] = rand() % N);
65 if (!rb_tree_insert(&t, newk)) {
66 fprintf(stderr, "error in rb_tree_insert\n");
69 if (!rb_tree_check(&t)) {
70 fprintf(stderr, "rb_tree_check_failed after insert!\n");
76 fprintf(stderr, "incorrect N (%d) in tree (vs. %d)\n", t.N, N);
80 for (i = 0; i < N; ++i) {
82 if (!rb_tree_find(&t, &kd)) {
83 fprintf(stderr, "rb_tree_find lost %d!\n", k[i]);
89 for (i = 0; i < N; ++i) {
91 fprintf(stderr, "not enough successors %d\n!", i);
94 printf("%d: %g\n", i, n->k[0]);
98 fprintf(stderr, "too many successors!\n");
103 for (i = 0; i < N; ++i) {
105 fprintf(stderr, "not enough predecessors %d\n!", i);
108 printf("%d: %g\n", i, n->k[0]);
112 fprintf(stderr, "too many predecessors!\n");
116 for (M = N; M > 0; --M) {
117 int knew = rand() % N; /* random new key */
118 j = rand() % M; /* random original key to replace */
119 for (i = 0; i < N; ++i)
125 if (!(n = rb_tree_find(&t, &kd))) {
126 fprintf(stderr, "rb_tree_find lost %d!\n", k[i]);
130 if (!rb_tree_resort(&t, n)) {
131 fprintf(stderr, "error in rb_tree_resort\n");
134 if (!rb_tree_check(&t)) {
135 fprintf(stderr, "rb_tree_check_failed after change %d!\n",
143 fprintf(stderr, "incorrect N (%d) in tree (vs. %d)\n", t.N, N);
147 for (i = 0; i < N; ++i)
148 k[i] = -1 - k[i]; /* undo negation above */
150 for (i = 0; i < N; ++i) {
153 kd = 0.01 * (rand() % (N * 150) - N*25);
154 le = rb_tree_find_le(&t, &kd);
155 gt = rb_tree_find_gt(&t, &kd);
157 lek = le ? le->k[0] : -HUGE_VAL;
158 gtk = gt ? gt->k[0] : +HUGE_VAL;
159 printf("%g <= %g < %g\n", lek, kd, gtk);
162 fprintf(stderr, "found invalid le %g for %g\n", lek, kd);
166 fprintf(stderr, "gt is not first node for k=%g\n", kd);
174 succ = rb_tree_succ(n);
175 } while (succ && succ->k[0] <= kd);
178 "rb_tree_find_le gave wrong result for k=%g\n",kd);
183 "rb_tree_find_gt gave wrong result for k=%g\n",kd);
189 for (M = N; M > 0; --M) {
191 for (i = 0; i < N; ++i)
197 if (!(n = rb_tree_find(&t, &kd))) {
198 fprintf(stderr, "rb_tree_find lost %d!\n", k[i]);
201 n = rb_tree_remove(&t, n);
204 if (!rb_tree_check(&t)) {
205 fprintf(stderr, "rb_tree_check_failed after remove!\n");
212 fprintf(stderr, "nonzero N (%d) in tree at end\n", t.N);
219 printf("SUCCESS.\n");