1 /*
2 * ivykis, an event handling library
3 * Copyright (C) 2002, 2003, 2012 Lennert Buytenhek
4 * Dedicated to Marija Kulikova.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License version
8 * 2.1 as published by the Free Software Foundation.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Lesser General Public License version 2.1 for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License version 2.1 along with this program; if not, write to the
17 * Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 */
20
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <iv_avl.h>
24 #include <iv_list.h>
25 #include <stdarg.h>
26 #include <time.h>
27 #include <unistd.h>
28
29 struct node {
30 struct iv_avl_node an;
31 int num;
32 };
33
34 static struct iv_avl_tree x;
35
tree_node_print(int depth,const struct iv_avl_node * an)36 static void tree_node_print(int depth, const struct iv_avl_node *an)
37 {
38 struct node *f = iv_container_of(an, struct node, an);
39 int i;
40
41 for (i = 0; i < depth; i++)
42 fprintf(stderr, " ");
43 fprintf(stderr, "%p (parent=%p): %d (height %d)\n",
44 an, an->parent, f->num, f->an.height);
45
46 if (an->left != NULL)
47 tree_node_print(depth + 1, an->left);
48 if (an->right != NULL)
49 tree_node_print(depth + 1, an->right);
50 }
51
tree_print(const char * msg)52 static void tree_print(const char *msg)
53 {
54 fprintf(stderr, "%s:\n", msg);
55 if (x.root != NULL)
56 tree_node_print(0, x.root);
57 fprintf(stderr, "\n");
58 }
59
fatal(const char * fmt,...)60 static void __attribute__((noreturn)) fatal(const char *fmt, ...)
61 {
62 va_list ap;
63 char msg[1024];
64
65 va_start(ap, fmt);
66 vsnprintf(msg, sizeof(msg), fmt, ap);
67 va_end(ap);
68
69 msg[sizeof(msg) - 1] = 0;
70
71 tree_print(msg);
72
73 exit(1);
74 }
75
76 static int
tree_node_verify(const struct iv_avl_tree * this,const struct iv_avl_node * an,const struct iv_avl_node * parent,const struct iv_avl_node * min,const struct iv_avl_node * max,int * cnt)77 tree_node_verify(const struct iv_avl_tree *this, const struct iv_avl_node *an,
78 const struct iv_avl_node *parent,
79 const struct iv_avl_node *min, const struct iv_avl_node *max,
80 int *cnt)
81 {
82 int hl;
83 int hr;
84 int my;
85
86 if (an->parent != parent) {
87 fatal("parent mismatch: %p, %p versus %p",
88 an, an->parent, parent);
89 }
90
91 (*cnt)++;
92
93 if (min != NULL || max != NULL) {
94 int err;
95
96 err = 0;
97 if (min != NULL && this->compare(min, an) >= 0)
98 err++;
99 if (max != NULL && this->compare(an, max) >= 0)
100 err++;
101
102 if (err)
103 fatal("violated %p < %p < %p", min, an, max);
104 }
105
106 hl = 0;
107 if (an->left != NULL)
108 hl = tree_node_verify(this, an->left, an, min, an, cnt);
109
110 hr = 0;
111 if (an->right != NULL)
112 hr = tree_node_verify(this, an->right, an, an, max, cnt);
113
114 if (abs(hl - hr) > 1)
115 fatal("balance mismatch: %d vs %d", hl, hr);
116
117 my = 1 + ((hl > hr) ? hl : hr);
118 if (an->height != my)
119 fatal("height mismatch: %d vs %d/%d", an->height, hl, hr);
120
121 return my;
122 }
123
tree_check(const struct iv_avl_tree * this,int expected_count)124 static void tree_check(const struct iv_avl_tree *this, int expected_count)
125 {
126 int count;
127
128 count = 0;
129 if (this->root != NULL)
130 tree_node_verify(this, this->root, NULL, NULL, NULL, &count);
131
132 if (expected_count >= 0 && expected_count != count)
133 fatal("count mismatch: %d versus %d", count, expected_count);
134 }
135
136
137 #define NUM 1024
138
139 static struct node *f[NUM];
140
docomp(const struct iv_avl_node * _a,const struct iv_avl_node * _b)141 static int docomp(const struct iv_avl_node *_a, const struct iv_avl_node *_b)
142 {
143 const struct node *a = iv_container_of(_a, struct node, an);
144 const struct node *b = iv_container_of(_b, struct node, an);
145
146 if (a->num < b->num)
147 return -1;
148 if (a->num > b->num)
149 return 1;
150
151 return 0;
152 }
153
mkrand(void)154 static int mkrand(void)
155 {
156 int r;
157
158 r = rand();
159 #if RAND_MAX == 0x7fff
160 r |= rand() << 15;
161 #endif
162
163 return r;
164 }
165
main()166 int main()
167 {
168 int i;
169
170 alarm(180);
171
172 srand(time(NULL) ^ getpid());
173
174 INIT_IV_AVL_TREE(&x, docomp);
175
176 tree_check(&x, 0);
177
178 for (i = 0; i < NUM; i++) {
179 int ret;
180
181 f[i] = malloc(sizeof(struct node));
182
183 do {
184 f[i]->num = mkrand();
185 ret = iv_avl_tree_insert(&x, &f[i]->an);
186 } while (ret < 0);
187
188 tree_check(&x, i + 1);
189 }
190
191 for (i = 0; i < NUM; i++) {
192 iv_avl_tree_delete(&x, &f[i]->an);
193
194 tree_check(&x, NUM - i - 1);
195
196 free(f[i]);
197 }
198
199 return 0;
200 }
201