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
26typedef struct _Node Node;
27typedef struct _Aug Aug;
28
29struct _Node {
30 guint unused;
31};
32
33struct _Aug {
34 guint n_items;
35};
36
37static void
38augment (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, node: 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, node: right);
58
59 aug->n_items += right_aug->n_items;
60 }
61}
62
63static Node *
64get (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, node: 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
95static void
96add (GtkRbTree *tree,
97 guint pos)
98{
99 Node *node = get (tree, pos);
100
101 gtk_rb_tree_insert_before (tree, node);
102}
103
104static void
105delete (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
114static guint
115print_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
135static void
136print (GtkRbTree *tree)
137{
138 print_node (tree, gtk_rb_tree_get_root (tree), 0, "", 0);
139}
140#endif
141
142static void
143test_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, pos: i);
152 //print (tree);
153 delete (tree, pos: 144);
154 add (tree, pos: 56);
155 delete (tree, pos: 113);
156 delete (tree, pos: 278);
157 delete (tree, pos: 45);
158 delete (tree, pos: 108);
159 delete (tree, pos: 41);
160 add (tree, pos: 56);
161 add (tree, pos: 200);
162 delete (tree, pos: 127);
163 delete (tree, pos: 222);
164 add (tree, pos: 80);
165 add (tree, pos: 143);
166 add (tree, pos: 216);
167 delete (tree, pos: 177);
168 delete (tree, pos: 193);
169 add (tree, pos: 190);
170 delete (tree, pos: 288);
171 add (tree, pos: 45);
172 add (tree, pos: 57);
173 add (tree, pos: 211);
174 delete (tree, pos: 103);
175 add (tree, pos: 152);
176 delete (tree, pos: 60);
177 add (tree, pos: 185);
178 delete (tree, pos: 167);
179 add (tree, pos: 92);
180 delete (tree, pos: 104);
181 delete (tree, pos: 110);
182 delete (tree, pos: 115);
183 add (tree, pos: 32);
184 delete (tree, pos: 44);
185 add (tree, pos: 159);
186 add (tree, pos: 271);
187 delete (tree, pos: 35);
188 add (tree, pos: 250);
189 delete (tree, pos: 36);
190 add (tree, pos: 284);
191 delete (tree, pos: 82);
192 delete (tree, pos: 248);
193 add (tree, pos: 22);
194 delete (tree, pos: 284);
195 add (tree, pos: 88);
196 delete (tree, pos: 182);
197 add (tree, pos: 70);
198 add (tree, pos: 55);
199 delete (tree, pos: 6);
200 add (tree, pos: 85);
201 delete (tree, pos: 36);
202 delete (tree, pos: 33);
203 delete (tree, pos: 108);
204 add (tree, pos: 229);
205 delete (tree, pos: 269);
206 add (tree, pos: 20);
207 add (tree, pos: 170);
208 delete (tree, pos: 154);
209 add (tree, pos: 26);
210 add (tree, pos: 211);
211 delete (tree, pos: 167);
212 add (tree, pos: 183);
213 add (tree, pos: 292);
214 delete (tree, pos: 2);
215 add (tree, pos: 5);
216 delete (tree, pos: 14);
217 delete (tree, pos: 91);
218 add (tree, pos: 172);
219 add (tree, pos: 99);
220 delete (tree, pos: 3);
221 delete (tree, pos: 74);
222 delete (tree, pos: 122);
223 add (tree, pos: 87);
224 add (tree, pos: 176);
225 delete (tree, pos: 294);
226 add (tree, pos: 169);
227 delete (tree, pos: 41);
228 add (tree, pos: 95);
229 delete (tree, pos: 185);
230 add (tree, pos: 218);
231 delete (tree, pos: 62);
232 delete (tree, pos: 175);
233 add (tree, pos: 196);
234 delete (tree, pos: 33);
235 delete (tree, pos: 46);
236 add (tree, pos: 30);
237 add (tree, pos: 72);
238 delete (tree, pos: 196);
239 delete (tree, pos: 291);
240 add (tree, pos: 198);
241 delete (tree, pos: 181);
242 add (tree, pos: 105);
243 delete (tree, pos: 75);
244 add (tree, pos: 30);
245 add (tree, pos: 261);
246 delete (tree, pos: 284);
247 delete (tree, pos: 214);
248 delete (tree, pos: 134);
249 add (tree, pos: 153);
250 delete (tree, pos: 46);
251 add (tree, pos: 154);
252 add (tree, pos: 266);
253 delete (tree, pos: 272);
254 delete (tree, pos: 150);
255 add (tree, pos: 131);
256 delete (tree, pos: 208);
257 add (tree, pos: 241);
258 add (tree, pos: 31);
259 add (tree, pos: 151);
260 add (tree, pos: 266);
261 delete (tree, pos: 285);
262 add (tree, pos: 178);
263 add (tree, pos: 159);
264 add (tree, pos: 203);
265 delete (tree, pos: 266);
266 add (tree, pos: 52);
267 delete (tree, pos: 104);
268 add (tree, pos: 243);
269 delete (tree, pos: 12);
270 add (tree, pos: 20);
271 delete (tree, pos: 68);
272 //print (tree);
273 delete (tree, pos: 102);
274
275 gtk_rb_tree_unref (tree);
276}
277
278static void
279test_crash2 (void)
280{
281 GtkRbTree *tree;
282
283 tree = gtk_rb_tree_new (Node, Aug, augment, NULL, NULL);
284
285 add (tree, pos: 0);
286 add (tree, pos: 0);
287 add (tree, pos: 1);
288
289 gtk_rb_tree_unref (tree);
290}
291
292int
293main (int argc, char *argv[])
294{
295 (g_test_init) (argc: &argc, argv: &argv, NULL);
296 setlocale (LC_ALL, locale: "C");
297
298 g_test_add_func (testpath: "/rbtree/crash", test_func: test_crash);
299 g_test_add_func (testpath: "/rbtree/crash2", test_func: test_crash2);
300
301 return g_test_run ();
302}
303

source code of gtk/testsuite/gtk/rbtree-crash.c