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 |
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, 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 | |
63 | static Node * |
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, 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 | |
95 | static void |
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 |
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 |
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, 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 | |
278 | static 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, pos: 0); |
286 | add (tree, pos: 0); |
287 | add (tree, pos: 1); |
288 | |
289 | gtk_rb_tree_unref (tree); |
290 | } |
291 | |
292 | int |
293 | main (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 | |