1 /* GtkRBTree tests.
2 *
3 * Copyright (C) 2011, Red Hat, Inc.
4 * Authors: Benjamin Otte <otte@gnome.org>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <locale.h>
21
22 #include <gtk/gtk.h>
23
24 #include "gtk/gtkrbtreeprivate.h"
25
26 typedef struct _Node Node;
27 typedef struct _Aug Aug;
28
29 struct _Node {
30 guint unused;
31 };
32
33 struct _Aug {
34 guint n_items;
35 };
36
37 static void
augment(GtkRbTree * tree,gpointer _aug,gpointer _node,gpointer left,gpointer right)38 augment (GtkRbTree *tree,
39 gpointer _aug,
40 gpointer _node,
41 gpointer left,
42 gpointer right)
43 {
44 Aug *aug = _aug;
45
46 aug->n_items = 1;
47
48 if (left)
49 {
50 Aug *left_aug = gtk_rb_tree_get_augment (tree, left);
51
52 aug->n_items += left_aug->n_items;
53 }
54
55 if (right)
56 {
57 Aug *right_aug = gtk_rb_tree_get_augment (tree, right);
58
59 aug->n_items += right_aug->n_items;
60 }
61 }
62
63 static Node *
get(GtkRbTree * tree,guint pos)64 get (GtkRbTree *tree,
65 guint pos)
66 {
67 Node *node, *tmp;
68
69 node = gtk_rb_tree_get_root (tree);
70
71 while (node)
72 {
73 tmp = gtk_rb_tree_node_get_left (node);
74 if (tmp)
75 {
76 Aug *aug = gtk_rb_tree_get_augment (tree, tmp);
77 if (pos < aug->n_items)
78 {
79 node = tmp;
80 continue;
81 }
82 pos -= aug->n_items;
83 }
84
85 if (pos < 1)
86 break;
87 pos--;
88
89 node = gtk_rb_tree_node_get_right (node);
90 }
91
92 return node;
93 }
94
95 static void
add(GtkRbTree * tree,guint pos)96 add (GtkRbTree *tree,
97 guint pos)
98 {
99 Node *node = get (tree, pos);
100
101 gtk_rb_tree_insert_before (tree, node);
102 }
103
104 static void
delete(GtkRbTree * tree,guint pos)105 delete (GtkRbTree *tree,
106 guint pos)
107 {
108 Node *node = get (tree, pos);
109
110 gtk_rb_tree_remove (tree, node);
111 }
112
113 #if 0
114 static guint
115 print_node (GtkRbTree *tree,
116 Node *node,
117 guint depth,
118 const char *prefix,
119 guint n)
120 {
121 Node *child;
122
123 child = gtk_rb_tree_node_get_left (node);
124 if (child)
125 n = print_node (tree, child, depth + 1, "/", n);
126 g_print ("%*s %u\n", 2 * depth, prefix, n);
127 n++;
128 child = gtk_rb_tree_node_get_right (node);
129 if (child)
130 n = print_node (tree, child, depth + 1, "\\", n);
131
132 return n;
133 }
134
135 static void
136 print (GtkRbTree *tree)
137 {
138 print_node (tree, gtk_rb_tree_get_root (tree), 0, "", 0);
139 }
140 #endif
141
142 static void
test_crash(void)143 test_crash (void)
144 {
145 GtkRbTree *tree;
146 guint i;
147
148 tree = gtk_rb_tree_new (Node, Aug, augment, NULL, NULL);
149
150 for (i = 0; i < 300; i++)
151 add (tree, i);
152 //print (tree);
153 delete (tree, 144);
154 add (tree, 56);
155 delete (tree, 113);
156 delete (tree, 278);
157 delete (tree, 45);
158 delete (tree, 108);
159 delete (tree, 41);
160 add (tree, 56);
161 add (tree, 200);
162 delete (tree, 127);
163 delete (tree, 222);
164 add (tree, 80);
165 add (tree, 143);
166 add (tree, 216);
167 delete (tree, 177);
168 delete (tree, 193);
169 add (tree, 190);
170 delete (tree, 288);
171 add (tree, 45);
172 add (tree, 57);
173 add (tree, 211);
174 delete (tree, 103);
175 add (tree, 152);
176 delete (tree, 60);
177 add (tree, 185);
178 delete (tree, 167);
179 add (tree, 92);
180 delete (tree, 104);
181 delete (tree, 110);
182 delete (tree, 115);
183 add (tree, 32);
184 delete (tree, 44);
185 add (tree, 159);
186 add (tree, 271);
187 delete (tree, 35);
188 add (tree, 250);
189 delete (tree, 36);
190 add (tree, 284);
191 delete (tree, 82);
192 delete (tree, 248);
193 add (tree, 22);
194 delete (tree, 284);
195 add (tree, 88);
196 delete (tree, 182);
197 add (tree, 70);
198 add (tree, 55);
199 delete (tree, 6);
200 add (tree, 85);
201 delete (tree, 36);
202 delete (tree, 33);
203 delete (tree, 108);
204 add (tree, 229);
205 delete (tree, 269);
206 add (tree, 20);
207 add (tree, 170);
208 delete (tree, 154);
209 add (tree, 26);
210 add (tree, 211);
211 delete (tree, 167);
212 add (tree, 183);
213 add (tree, 292);
214 delete (tree, 2);
215 add (tree, 5);
216 delete (tree, 14);
217 delete (tree, 91);
218 add (tree, 172);
219 add (tree, 99);
220 delete (tree, 3);
221 delete (tree, 74);
222 delete (tree, 122);
223 add (tree, 87);
224 add (tree, 176);
225 delete (tree, 294);
226 add (tree, 169);
227 delete (tree, 41);
228 add (tree, 95);
229 delete (tree, 185);
230 add (tree, 218);
231 delete (tree, 62);
232 delete (tree, 175);
233 add (tree, 196);
234 delete (tree, 33);
235 delete (tree, 46);
236 add (tree, 30);
237 add (tree, 72);
238 delete (tree, 196);
239 delete (tree, 291);
240 add (tree, 198);
241 delete (tree, 181);
242 add (tree, 105);
243 delete (tree, 75);
244 add (tree, 30);
245 add (tree, 261);
246 delete (tree, 284);
247 delete (tree, 214);
248 delete (tree, 134);
249 add (tree, 153);
250 delete (tree, 46);
251 add (tree, 154);
252 add (tree, 266);
253 delete (tree, 272);
254 delete (tree, 150);
255 add (tree, 131);
256 delete (tree, 208);
257 add (tree, 241);
258 add (tree, 31);
259 add (tree, 151);
260 add (tree, 266);
261 delete (tree, 285);
262 add (tree, 178);
263 add (tree, 159);
264 add (tree, 203);
265 delete (tree, 266);
266 add (tree, 52);
267 delete (tree, 104);
268 add (tree, 243);
269 delete (tree, 12);
270 add (tree, 20);
271 delete (tree, 68);
272 //print (tree);
273 delete (tree, 102);
274
275 gtk_rb_tree_unref (tree);
276 }
277
278 static void
test_crash2(void)279 test_crash2 (void)
280 {
281 GtkRbTree *tree;
282
283 tree = gtk_rb_tree_new (Node, Aug, augment, NULL, NULL);
284
285 add (tree, 0);
286 add (tree, 0);
287 add (tree, 1);
288
289 gtk_rb_tree_unref (tree);
290 }
291
292 int
main(int argc,char * argv[])293 main (int argc, char *argv[])
294 {
295 (g_test_init) (&argc, &argv, NULL);
296 setlocale (LC_ALL, "C");
297
298 g_test_add_func ("/rbtree/crash", test_crash);
299 g_test_add_func ("/rbtree/crash2", test_crash2);
300
301 return g_test_run ();
302 }
303