ctkrbtree.c

Bug Summary

File:	ctk/ctkrbtree.c
Warning:	line 268, column 8 Access to field 'left' results in a dereference of a null pointer (loaded from variable 'w')
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name ctkrbtree.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/rootdir/ctk -fcoverage-compilation-dir=/rootdir/ctk -resource-dir /usr/lib/llvm-19/lib/clang/19 -D HAVE_CONFIG_H -I . -I .. -D G_LOG_DOMAIN="Ctk" -D G_LOG_USE_STRUCTURED=1 -D CTK_VERSION="3.25.5" -D CTK_BINARY_VERSION="3.0.0" -D CTK_COMPILATION -D CTK_PRINT_BACKEND_ENABLE_UNSUPPORTED -D CTK_LIBDIR="/usr/lib" -D CTK_LOCALEDIR="/usr/share/locale" -D CTK_DATADIR="/usr/share" -D CTK_DATA_PREFIX="/usr" -D CTK_SYSCONFDIR="/usr/etc" -D CTK_HOST="x86_64-pc-linux-gnu" -D CTK_PRINT_BACKENDS="file,cups" -D X11_DATA_PREFIX="/usr" -D ISO_CODES_PREFIX="" -I .. -I ../ctk -I .. -I ../cdk -I /usr/include/glib-2.0 -I /usr/lib/x86_64-linux-gnu/glib-2.0/include -I /usr/include/sysprof-6 -D G_ENABLE_DEBUG -D G_ENABLE_CONSISTENCY_CHECKS -D GLIB_MIN_REQUIRED_VERSION=GLIB_VERSION_2_66 -D GLIB_MAX_ALLOWED_VERSION=GLIB_VERSION_2_66 -I /usr/include/pango-1.0 -I /usr/include/glib-2.0 -I /usr/lib/x86_64-linux-gnu/glib-2.0/include -I /usr/include/sysprof-6 -I /usr/include/harfbuzz -I /usr/include/freetype2 -I /usr/include/libpng16 -I /usr/include/libmount -I /usr/include/blkid -I /usr/include/fribidi -I /usr/include/cairo -I /usr/include/pixman-1 -I /usr/include/atk-1.0 -I /usr/include/gdk-pixbuf-2.0 -I /usr/include/x86_64-linux-gnu -I /usr/include/webp -I /usr/include/at-spi2-atk/2.0 -I /usr/include/at-spi-2.0 -I /usr/include/dbus-1.0 -I /usr/lib/x86_64-linux-gnu/dbus-1.0/include -I /usr/include/gio-unix-2.0 -I /usr/include/harfbuzz -I /usr/include/freetype2 -I /usr/include/libpng16 -I /usr/include/glib-2.0 -I /usr/lib/x86_64-linux-gnu/glib-2.0/include -I /usr/include/sysprof-6 -I /usr/include/pango-1.0 -I /usr/include/libmount -I /usr/include/blkid -I /usr/include/fribidi -I /usr/include/cairo -I /usr/include/pixman-1 -D PIC -internal-isystem /usr/lib/llvm-19/lib/clang/19/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -ferror-limit 19 -fvisibility=hidden -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -analyzer-checker deadcode.DeadStores -analyzer-checker alpha.deadcode.UnreachableCode -analyzer-checker alpha.core.CastSize -analyzer-checker alpha.core.CastToStruct -analyzer-checker alpha.core.IdenticalExpr -analyzer-checker alpha.security.ArrayBoundV2 -analyzer-checker alpha.security.MallocOverflow -analyzer-checker alpha.security.ReturnPtrRange -analyzer-checker alpha.unix.SimpleStream -analyzer-checker alpha.unix.cstring.BufferOverlap -analyzer-checker alpha.unix.cstring.NotNullTerminated -analyzer-checker alpha.unix.cstring.OutOfBounds -analyzer-checker alpha.core.FixedAddr -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /rootdir/html-report/2024-12-19-110847-43636-1 -x c ctkrbtree.c
1/* ctkrbtree.c
2 * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
16 */
17 
18#include "config.h"
19#include "ctkrbtree.h"
20#include "ctkdebug.h"
21 
22static CtkRBNode * _ctk_rbnode_new                (CtkRBTree  *tree,
23						   gint        height);
24static void        _ctk_rbnode_free               (CtkRBNode  *node);
25static void        _ctk_rbnode_rotate_left        (CtkRBTree  *tree,
26						   CtkRBNode  *node);
27static void        _ctk_rbnode_rotate_right       (CtkRBTree  *tree,
28						   CtkRBNode  *node);
29static void        _ctk_rbtree_insert_fixup       (CtkRBTree  *tree,
30						   CtkRBNode  *node);
31static void        _ctk_rbtree_remove_node_fixup  (CtkRBTree  *tree,
32						   CtkRBNode  *node,
33                                                   CtkRBNode  *parent);
34static inline void _fixup_validation              (CtkRBTree  *tree,
35						   CtkRBNode  *node);
36static inline void _fixup_total_count             (CtkRBTree  *tree,
37						   CtkRBNode  *node);
38#ifdef G_ENABLE_DEBUG1
39static void        _ctk_rbtree_test               (const gchar *where,
40                                                   CtkRBTree  *tree);
41static void        _ctk_rbtree_debug_spew         (CtkRBTree  *tree,
42                                                   GString    *s);
43#endif
44 
45static const CtkRBNode nil = {
46  .flags = CTK_RBNODE_BLACK,
47};
48 
49gboolean
50_ctk_rbtree_is_nil (CtkRBNode *node)
51{
52  return node == &nil;
53}
54 
55static CtkRBNode *
56_ctk_rbnode_new (CtkRBTree *tree G_GNUC_UNUSED__attribute__ ((__unused__)),
57		 gint       height)
58{
59  CtkRBNode *node = g_slice_new (CtkRBNode)((CtkRBNode*) g_slice_alloc (sizeof (CtkRBNode)));
60 
61  node->left = (CtkRBNode *) &nil;
62  node->right = (CtkRBNode *) &nil;
63  node->parent = (CtkRBNode *) &nil;
64  node->flags = CTK_RBNODE_RED;
65  node->total_count = 1;
66  node->count = 1;
67  node->children = NULL((void*)0);
68  node->offset = height;
69  return node;
70}
71 
72static void
73_ctk_rbnode_free (CtkRBNode *node)
74{
75#ifdef G_ENABLE_DEBUG1
76  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
77    {
78      node->left = (gpointer) 0xdeadbeef;
79      node->right = (gpointer) 0xdeadbeef;
80      node->parent = (gpointer) 0xdeadbeef;
81      node->total_count = 56789;
82      node->offset = 56789;
83      node->count = 56789;
84      node->flags = 0;
85    }
86#endif
87  g_slice_free (CtkRBNode, node)do { if (1) g_slice_free1 (sizeof (CtkRBNode), (node)); else (
void) ((CtkRBNode*) 0 == (node)); } while (0);
88}
89 
90static void
91_ctk_rbnode_rotate_left (CtkRBTree *tree,
92			 CtkRBNode *node)
93{
94  gint node_height, right_height;
95  CtkRBNode *right;
96 
97  g_return_if_fail (!_ctk_rbtree_is_nil (node))do { if ((!_ctk_rbtree_is_nil (node))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "!_ctk_rbtree_is_nil (node)"
); return; } } while (0);
98  g_return_if_fail (!_ctk_rbtree_is_nil (node->right))do { if ((!_ctk_rbtree_is_nil (node->right))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "!_ctk_rbtree_is_nil (node->right)"
); return; } } while (0);
99 
100  right = node->right;
101 
102  node_height = CTK_RBNODE_GET_HEIGHT (node)(node->offset-(node->left->offset+node->right->
offset+(node->children?node->children->root->offset
:0)));
103  right_height = CTK_RBNODE_GET_HEIGHT (right)(right->offset-(right->left->offset+right->right->
offset+(right->children?right->children->root->offset
:0)));
104  node->right = right->left;
105  if (!_ctk_rbtree_is_nil (right->left))
106    right->left->parent = node;
107 
108  right->parent = node->parent;
109  if (!_ctk_rbtree_is_nil (node->parent))
110    {
111      if (node == node->parent->left)
112	node->parent->left = right;
113      else
114	node->parent->right = right;
115    } else {
116      tree->root = right;
117    }
118 
119  right->left = node;
120  node->parent = right;
121 
122  node->count = 1 + node->left->count + node->right->count;
123  right->count = 1 + right->left->count + right->right->count;
124 
125  node->offset = node_height + node->left->offset + node->right->offset +
126                 (node->children ? node->children->root->offset : 0);
127  right->offset = right_height + right->left->offset + right->right->offset +
128                  (right->children ? right->children->root->offset : 0);
129 
130  _fixup_validation (tree, node);
131  _fixup_validation (tree, right);
132  _fixup_total_count (tree, node);
133  _fixup_total_count (tree, right);
134}
135 
136static void
137_ctk_rbnode_rotate_right (CtkRBTree *tree,
138			  CtkRBNode *node)
139{
140  gint node_height, left_height;
141  CtkRBNode *left;
142 
143  g_return_if_fail (!_ctk_rbtree_is_nil (node))do { if ((!_ctk_rbtree_is_nil (node))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "!_ctk_rbtree_is_nil (node)"
); return; } } while (0);
144  g_return_if_fail (!_ctk_rbtree_is_nil (node->left))do { if ((!_ctk_rbtree_is_nil (node->left))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "!_ctk_rbtree_is_nil (node->left)"
); return; } } while (0);
145 
146  left = node->left;
147 
148  node_height = CTK_RBNODE_GET_HEIGHT (node)(node->offset-(node->left->offset+node->right->
offset+(node->children?node->children->root->offset
:0)));
149  left_height = CTK_RBNODE_GET_HEIGHT (left)(left->offset-(left->left->offset+left->right->
offset+(left->children?left->children->root->offset
:0)));
150  
151  node->left = left->right;
152  if (!_ctk_rbtree_is_nil (left->right))
153    left->right->parent = node;
154 
155  left->parent = node->parent;
156  if (!_ctk_rbtree_is_nil (node->parent))
157    {
158      if (node == node->parent->right)
159	node->parent->right = left;
160      else
161	node->parent->left = left;
162    }
163  else
164    {
165      tree->root = left;
166    }
167 
168  /* link node and left */
169  left->right = node;
170  node->parent = left;
171 
172  node->count = 1 + node->left->count + node->right->count;
173  left->count = 1 + left->left->count + left->right->count;
174 
175  node->offset = node_height + node->left->offset + node->right->offset +
176                 (node->children ? node->children->root->offset : 0);
177  left->offset = left_height + left->left->offset + left->right->offset +
178                 (left->children?left->children->root->offset:0);
179 
180  _fixup_validation (tree, node);
181  _fixup_validation (tree, left);
182  _fixup_total_count (tree, node);
183  _fixup_total_count (tree, left);
184}
185 
186static void
187_ctk_rbtree_insert_fixup (CtkRBTree *tree,
188			  CtkRBNode *node)
189{
190 
191  /* check Red-Black properties */
192  while (node != tree->root && CTK_RBNODE_GET_COLOR (node->parent)(node->parent?(((node->parent->flags&CTK_RBNODE_RED
)==CTK_RBNODE_RED)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK
) == CTK_RBNODE_RED)
193    {
194      /* we have a violation */
195      if (node->parent == node->parent->parent->left)
196	{
197	  CtkRBNode *y = node->parent->parent->right;
198	  if (CTK_RBNODE_GET_COLOR (y)(y?(((y->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED)?CTK_RBNODE_RED
:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_RED)
199	    {
200				/* uncle is CTK_RBNODE_RED */
201	      CTK_RBNODE_SET_COLOR (node->parent, CTK_RBNODE_BLACK)if((node->parent->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK
)node->parent->flags=node->parent->flags^(CTK_RBNODE_RED
|CTK_RBNODE_BLACK);
202	      CTK_RBNODE_SET_COLOR (y, CTK_RBNODE_BLACK)if((y->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK)y->
flags=y->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
203	      CTK_RBNODE_SET_COLOR (node->parent->parent, CTK_RBNODE_RED)if((node->parent->parent->flags&CTK_RBNODE_RED)!=
CTK_RBNODE_RED)node->parent->parent->flags=node->
parent->parent->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
204	      node = node->parent->parent;
205	    }
206	  else
207	    {
208				/* uncle is CTK_RBNODE_BLACK */
209	      if (node == node->parent->right)
210		{
211		  /* make node a left child */
212		  node = node->parent;
213		  _ctk_rbnode_rotate_left (tree, node);
214		}
215 
216				/* recolor and rotate */
217	      CTK_RBNODE_SET_COLOR (node->parent, CTK_RBNODE_BLACK)if((node->parent->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK
)node->parent->flags=node->parent->flags^(CTK_RBNODE_RED
|CTK_RBNODE_BLACK);
218	      CTK_RBNODE_SET_COLOR (node->parent->parent, CTK_RBNODE_RED)if((node->parent->parent->flags&CTK_RBNODE_RED)!=
CTK_RBNODE_RED)node->parent->parent->flags=node->
parent->parent->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
219	      _ctk_rbnode_rotate_right(tree, node->parent->parent);
220	    }
221	}
222      else
223	{
224	  /* mirror image of above code */
225	  CtkRBNode *y = node->parent->parent->left;
226	  if (CTK_RBNODE_GET_COLOR (y)(y?(((y->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED)?CTK_RBNODE_RED
:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_RED)
227	    {
228				/* uncle is CTK_RBNODE_RED */
229	      CTK_RBNODE_SET_COLOR (node->parent, CTK_RBNODE_BLACK)if((node->parent->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK
)node->parent->flags=node->parent->flags^(CTK_RBNODE_RED
|CTK_RBNODE_BLACK);
230	      CTK_RBNODE_SET_COLOR (y, CTK_RBNODE_BLACK)if((y->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK)y->
flags=y->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
231	      CTK_RBNODE_SET_COLOR (node->parent->parent, CTK_RBNODE_RED)if((node->parent->parent->flags&CTK_RBNODE_RED)!=
CTK_RBNODE_RED)node->parent->parent->flags=node->
parent->parent->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
232	      node = node->parent->parent;
233	    }
234	  else
235	    {
236				/* uncle is CTK_RBNODE_BLACK */
237	      if (node == node->parent->left)
238		{
239		  node = node->parent;
240		  _ctk_rbnode_rotate_right (tree, node);
241		}
242	      CTK_RBNODE_SET_COLOR (node->parent, CTK_RBNODE_BLACK)if((node->parent->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK
)node->parent->flags=node->parent->flags^(CTK_RBNODE_RED
|CTK_RBNODE_BLACK);
243	      CTK_RBNODE_SET_COLOR (node->parent->parent, CTK_RBNODE_RED)if((node->parent->parent->flags&CTK_RBNODE_RED)!=
CTK_RBNODE_RED)node->parent->parent->flags=node->
parent->parent->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
244	      _ctk_rbnode_rotate_left (tree, node->parent->parent);
245	    }
246	}
247    }
248  CTK_RBNODE_SET_COLOR (tree->root, CTK_RBNODE_BLACK)if((tree->root->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK
)tree->root->flags=tree->root->flags^(CTK_RBNODE_RED
|CTK_RBNODE_BLACK);
249}
250 
251static void
252_ctk_rbtree_remove_node_fixup (CtkRBTree *tree,
253			       CtkRBNode *node,
254                               CtkRBNode *parent)
255{
256  while (node != tree->root && CTK_RBNODE_GET_COLOR (node)(node?(((node->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED)?
CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_BLACK)
1
Assuming 'node' is not equal to field 'root'→
2
←
Assuming 'node' is null→
3
←
'?' condition is false→
4
←
Loop condition is true.  Entering loop body→
257    {
258      if (node == parent->left)
5
←
Assuming 'node' is equal to field 'left'→
6
←
Taking true branch→
259	{
260	  CtkRBNode *w = parent->right;
7
←
'w' initialized here→
261	  if (CTK_RBNODE_GET_COLOR (w)(w?(((w->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED)?CTK_RBNODE_RED
:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_RED)
8
←
Assuming 'w' is null→
9
←
'?' condition is false→
262	    {
263	      CTK_RBNODE_SET_COLOR (w, CTK_RBNODE_BLACK)if((w->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK)w->
flags=w->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
264	      CTK_RBNODE_SET_COLOR (parent, CTK_RBNODE_RED)if((parent->flags&CTK_RBNODE_RED)!=CTK_RBNODE_RED)parent
->flags=parent->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
265	      _ctk_rbnode_rotate_left (tree, parent);
266	      w = parent->right;
267	    }
268	  if (CTK_RBNODE_GET_COLOR (w->left)(w->left?(((w->left->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED
)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_BLACK && CTK_RBNODE_GET_COLOR (w->right)(w->right?(((w->right->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED
)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_BLACK)
10
←
Taking false branch→
11
←
Access to field 'left' results in a dereference of a null pointer (loaded from variable 'w')
269	    {
270	      CTK_RBNODE_SET_COLOR (w, CTK_RBNODE_RED)if((w->flags&CTK_RBNODE_RED)!=CTK_RBNODE_RED)w->flags
=w->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
271	      node = parent;
272	    }
273	  else
274	    {
275	      if (CTK_RBNODE_GET_COLOR (w->right)(w->right?(((w->right->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED
)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_BLACK)
276		{
277		  CTK_RBNODE_SET_COLOR (w->left, CTK_RBNODE_BLACK)if((w->left->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK
)w->left->flags=w->left->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK
);
278		  CTK_RBNODE_SET_COLOR (w, CTK_RBNODE_RED)if((w->flags&CTK_RBNODE_RED)!=CTK_RBNODE_RED)w->flags
=w->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
279		  _ctk_rbnode_rotate_right (tree, w);
280		  w = parent->right;
281		}
282	      CTK_RBNODE_SET_COLOR (w, CTK_RBNODE_GET_COLOR (parent))if((w->flags&(parent?(((parent->flags&CTK_RBNODE_RED
)==CTK_RBNODE_RED)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK
))!=(parent?(((parent->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED
)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK))w->flags
=w->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
283	      CTK_RBNODE_SET_COLOR (parent, CTK_RBNODE_BLACK)if((parent->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK)
parent->flags=parent->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK
);
284	      CTK_RBNODE_SET_COLOR (w->right, CTK_RBNODE_BLACK)if((w->right->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK
)w->right->flags=w->right->flags^(CTK_RBNODE_RED|
CTK_RBNODE_BLACK);
285	      _ctk_rbnode_rotate_left (tree, parent);
286	      node = tree->root;
287	    }
288	}
289      else
290	{
291	  CtkRBNode *w = parent->left;
292	  if (CTK_RBNODE_GET_COLOR (w)(w?(((w->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED)?CTK_RBNODE_RED
:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_RED)
293	    {
294	      CTK_RBNODE_SET_COLOR (w, CTK_RBNODE_BLACK)if((w->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK)w->
flags=w->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
295	      CTK_RBNODE_SET_COLOR (parent, CTK_RBNODE_RED)if((parent->flags&CTK_RBNODE_RED)!=CTK_RBNODE_RED)parent
->flags=parent->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
296	      _ctk_rbnode_rotate_right (tree, parent);
297	      w = parent->left;
298	    }
299	  if (CTK_RBNODE_GET_COLOR (w->right)(w->right?(((w->right->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED
)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_BLACK && CTK_RBNODE_GET_COLOR (w->left)(w->left?(((w->left->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED
)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_BLACK)
300	    {
301	      CTK_RBNODE_SET_COLOR (w, CTK_RBNODE_RED)if((w->flags&CTK_RBNODE_RED)!=CTK_RBNODE_RED)w->flags
=w->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
302	      node = parent;
303	    }
304	  else
305	    {
306	      if (CTK_RBNODE_GET_COLOR (w->left)(w->left?(((w->left->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED
)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_BLACK)
307		{
308		  CTK_RBNODE_SET_COLOR (w->right, CTK_RBNODE_BLACK)if((w->right->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK
)w->right->flags=w->right->flags^(CTK_RBNODE_RED|
CTK_RBNODE_BLACK);
309		  CTK_RBNODE_SET_COLOR (w, CTK_RBNODE_RED)if((w->flags&CTK_RBNODE_RED)!=CTK_RBNODE_RED)w->flags
=w->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
310		  _ctk_rbnode_rotate_left (tree, w);
311		  w = parent->left;
312		}
313	      CTK_RBNODE_SET_COLOR (w, CTK_RBNODE_GET_COLOR (parent))if((w->flags&(parent?(((parent->flags&CTK_RBNODE_RED
)==CTK_RBNODE_RED)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK
))!=(parent?(((parent->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED
)?CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK))w->flags
=w->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
314	      CTK_RBNODE_SET_COLOR (parent, CTK_RBNODE_BLACK)if((parent->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK)
parent->flags=parent->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK
);
315	      CTK_RBNODE_SET_COLOR (w->left, CTK_RBNODE_BLACK)if((w->left->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK
)w->left->flags=w->left->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK
);
316	      _ctk_rbnode_rotate_right (tree, parent);
317	      node = tree->root;
318	    }
319	}
320 
321      parent = node->parent;
322    }
323  CTK_RBNODE_SET_COLOR (node, CTK_RBNODE_BLACK)if((node->flags&CTK_RBNODE_BLACK)!=CTK_RBNODE_BLACK)node
->flags=node->flags^(CTK_RBNODE_RED|CTK_RBNODE_BLACK);
324}
325 
326CtkRBTree *
327_ctk_rbtree_new (void)
328{
329  CtkRBTree *retval;
330 
331  retval = g_new (CtkRBTree, 1)((CtkRBTree *) g_malloc_n ((1), sizeof (CtkRBTree)));
332  retval->parent_tree = NULL((void*)0);
333  retval->parent_node = NULL((void*)0);
334 
335  retval->root = (CtkRBNode *) &nil;
336 
337  return retval;
338}
339 
340static void
341_ctk_rbtree_free_helper (CtkRBTree  *tree G_GNUC_UNUSED__attribute__ ((__unused__)),
342			 CtkRBNode  *node,
343			 gpointer    data G_GNUC_UNUSED__attribute__ ((__unused__)))
344{
345  if (node->children)
346    _ctk_rbtree_free (node->children);
347 
348  _ctk_rbnode_free (node);
349}
350 
351void
352_ctk_rbtree_free (CtkRBTree *tree)
353{
354  _ctk_rbtree_traverse (tree,
355			tree->root,
356			G_POST_ORDER,
357			_ctk_rbtree_free_helper,
358			NULL((void*)0));
359 
360  if (tree->parent_node &&
361      tree->parent_node->children == tree)
362    tree->parent_node->children = NULL((void*)0);
363  g_free (tree);
364}
365 
366static void
367ctk_rbnode_adjust (CtkRBTree *tree,
368                   CtkRBNode *node,
369                   int        count_diff,
370                   int        total_count_diff,
371                   int        offset_diff)
372{
373  while (tree && node && !_ctk_rbtree_is_nil (node))
374    {
375      _fixup_validation (tree, node);
376      node->offset += offset_diff;
377      node->count += count_diff;
378      node->total_count += total_count_diff;
379      
380      node = node->parent;
381      if (_ctk_rbtree_is_nil (node))
382	{
383	  node = tree->parent_node;
384	  tree = tree->parent_tree;
385          count_diff = 0;
386	}
387    }
388}
389 
390void
391_ctk_rbtree_remove (CtkRBTree *tree)
392{
393#ifdef G_ENABLE_DEBUG1
394  CtkRBTree *tmp_tree;
395 
396  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
397    _ctk_rbtree_test (G_STRLOC"ctkrbtree.c" ":" "397", tree);
398#endif
399  
400  /* ugly hack to make _fixup_validation work in the first iteration of the
401   * loop below */
402  CTK_RBNODE_UNSET_FLAG (tree->root, CTK_RBNODE_DESCENDANTS_INVALID)do{ (tree->root->flags&=~(CTK_RBNODE_DESCENDANTS_INVALID
)); }while (0);
403  
404  ctk_rbnode_adjust (tree->parent_tree, 
405                     tree->parent_node,
406                     0,
407                     - (int) tree->root->total_count,
408                     - tree->root->offset);
409 
410#ifdef G_ENABLE_DEBUG1
411  tmp_tree = tree->parent_tree;
412#endif
413 
414  _ctk_rbtree_free (tree);
415 
416#ifdef G_ENABLE_DEBUG1
417  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
418    _ctk_rbtree_test (G_STRLOC"ctkrbtree.c" ":" "418", tmp_tree);
419#endif
420}
421 
422 
423CtkRBNode *
424_ctk_rbtree_insert_after (CtkRBTree *tree,
425			  CtkRBNode *current,
426			  gint       height,
427			  gboolean   valid)
428{
429  CtkRBNode *node;
430  gboolean right = TRUE(!(0));
431 
432#ifdef G_ENABLE_DEBUG1
433  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
434    {
435      GString *s;
436 
437      s = g_string_new ("");
438      g_string_append_printf (s, "_ctk_rbtree_insert_after: %p\n", current);
439      _ctk_rbtree_debug_spew (tree, s);
440      g_message ("%s", s->str);
441      g_string_free (s, TRUE)(__builtin_constant_p ((!(0))) ? (((!(0))) ? (g_string_free) (
(s), ((!(0)))) : g_string_free_and_steal (s)) : (g_string_free
) ((s), ((!(0)))));
442      _ctk_rbtree_test (G_STRLOC"ctkrbtree.c" ":" "442", tree);
443    }
444#endif
445 
446  if (current != NULL((void*)0) && !_ctk_rbtree_is_nil (current->right))
447    {
448      current = current->right;
449      while (!_ctk_rbtree_is_nil (current->left))
450	current = current->left;
451      right = FALSE(0);
452    }
453  /* setup new node */
454  node = _ctk_rbnode_new (tree, height);
455 
456  /* insert node in tree */
457  if (current)
458    {
459      node->parent = current;
460      if (right)
461	current->right = node;
462      else
463	current->left = node;
464      ctk_rbnode_adjust (tree, node->parent,
465                         1, 1, height);
466    }
467  else
468    {
469      g_assert (_ctk_rbtree_is_nil (tree->root))do { if (_ctk_rbtree_is_nil (tree->root)) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 469, ((const char*) (__func__)), "_ctk_rbtree_is_nil (tree->root)"
); } while (0);
470      tree->root = node;
471      ctk_rbnode_adjust (tree->parent_tree, tree->parent_node,
472                         0, 1, height);
473    }
474 
475  if (valid)
476    _ctk_rbtree_node_mark_valid (tree, node);
477  else
478    _ctk_rbtree_node_mark_invalid (tree, node);
479 
480  _ctk_rbtree_insert_fixup (tree, node);
481 
482#ifdef G_ENABLE_DEBUG1
483  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
484    {
485      GString *s;
486 
487      s = g_string_new ("_ctk_rbtree_insert_after finished...\n");
488      _ctk_rbtree_debug_spew (tree, s);
489      g_message ("%s", s->str);
490      g_string_free (s, TRUE)(__builtin_constant_p ((!(0))) ? (((!(0))) ? (g_string_free) (
(s), ((!(0)))) : g_string_free_and_steal (s)) : (g_string_free
) ((s), ((!(0)))));
491      _ctk_rbtree_test (G_STRLOC"ctkrbtree.c" ":" "491", tree);
492    }
493#endif
494 
495  return node;
496}
497 
498CtkRBNode *
499_ctk_rbtree_insert_before (CtkRBTree *tree,
500			   CtkRBNode *current,
501			   gint       height,
502			   gboolean   valid)
503{
504  CtkRBNode *node;
505  gboolean left = TRUE(!(0));
506 
507#ifdef G_ENABLE_DEBUG1
508  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
509    {
510      GString *s;
511 
512      s = g_string_new ("");
513      g_string_append_printf (s, "_ctk_rbtree_insert_before: %p\n", current);
514      _ctk_rbtree_debug_spew (tree, s);
515      g_message ("%s", s->str);
516      g_string_free (s, TRUE)(__builtin_constant_p ((!(0))) ? (((!(0))) ? (g_string_free) (
(s), ((!(0)))) : g_string_free_and_steal (s)) : (g_string_free
) ((s), ((!(0)))));
517      _ctk_rbtree_test (G_STRLOC"ctkrbtree.c" ":" "517", tree);
518    }
519#endif
520 
521  if (current != NULL((void*)0) && !_ctk_rbtree_is_nil (current->left))
522    {
523      current = current->left;
524      while (!_ctk_rbtree_is_nil (current->right))
525	current = current->right;
526      left = FALSE(0);
527    }
528 
529  /* setup new node */
530  node = _ctk_rbnode_new (tree, height);
531 
532  /* insert node in tree */
533  if (current)
534    {
535      node->parent = current;
536      if (left)
537	current->left = node;
538      else
539	current->right = node;
540      ctk_rbnode_adjust (tree, node->parent,
541                         1, 1, height);
542    }
543  else
544    {
545      g_assert (_ctk_rbtree_is_nil (tree->root))do { if (_ctk_rbtree_is_nil (tree->root)) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 545, ((const char*) (__func__)), "_ctk_rbtree_is_nil (tree->root)"
); } while (0);
546      tree->root = node;
547      ctk_rbnode_adjust (tree->parent_tree, tree->parent_node,
548                         0, 1, height);
549    }
550 
551  if (valid)
552    _ctk_rbtree_node_mark_valid (tree, node);
553  else
554    _ctk_rbtree_node_mark_invalid (tree, node);
555 
556  _ctk_rbtree_insert_fixup (tree, node);
557 
558#ifdef G_ENABLE_DEBUG1
559  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
560    {
561      GString *s;
562 
563      s = g_string_new ("_ctk_rbtree_insert_before finished...\n");
564      _ctk_rbtree_debug_spew (tree, s);
565      g_message ("%s", s->str);
566      g_string_free (s, TRUE)(__builtin_constant_p ((!(0))) ? (((!(0))) ? (g_string_free) (
(s), ((!(0)))) : g_string_free_and_steal (s)) : (g_string_free
) ((s), ((!(0)))));
567      _ctk_rbtree_test (G_STRLOC"ctkrbtree.c" ":" "567", tree);
568    }
569#endif
570 
571  return node;
572}
573 
574CtkRBNode *
575_ctk_rbtree_find_count (CtkRBTree *tree,
576			gint       count)
577{
578  CtkRBNode *node;
579 
580  node = tree->root;
581  while (!_ctk_rbtree_is_nil (node) && (node->left->count + 1 != count))
582    {
583      if (node->left->count >= count)
584	node = node->left;
585      else
586	{
587	  count -= (node->left->count + 1);
588	  node = node->right;
589	}
590    }
591  if (_ctk_rbtree_is_nil (node))
592    return NULL((void*)0);
593  return node;
594}
595 
596void
597_ctk_rbtree_node_set_height (CtkRBTree *tree,
598			     CtkRBNode *node,
599			     gint       height)
600{
601  gint diff = height - CTK_RBNODE_GET_HEIGHT (node)(node->offset-(node->left->offset+node->right->
offset+(node->children?node->children->root->offset
:0)));
602 
603  if (diff == 0)
604    return;
605 
606  ctk_rbnode_adjust (tree, node, 0, 0, diff);
607 
608#ifdef G_ENABLE_DEBUG1
609  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
610    _ctk_rbtree_test (G_STRLOC"ctkrbtree.c" ":" "610", tree);
611#endif
612}
613 
614void
615_ctk_rbtree_node_mark_invalid (CtkRBTree *tree,
616			       CtkRBNode *node)
617{
618  if (CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID)(node?(((node->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID
)?(!(0)):(0)):(0)))
619    return;
620 
621  CTK_RBNODE_SET_FLAG (node, CTK_RBNODE_INVALID)do{ (node->flags|=CTK_RBNODE_INVALID); }while (0);
622  do
623    {
624      if (CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_DESCENDANTS_INVALID)(node?(((node->flags&CTK_RBNODE_DESCENDANTS_INVALID)==
CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0)))
625	return;
626      CTK_RBNODE_SET_FLAG (node, CTK_RBNODE_DESCENDANTS_INVALID)do{ (node->flags|=CTK_RBNODE_DESCENDANTS_INVALID); }while (
0);
627      node = node->parent;
628      if (_ctk_rbtree_is_nil (node))
629	{
630	  node = tree->parent_node;
631	  tree = tree->parent_tree;
632	}
633    }
634  while (node);
635}
636 
637#if 0
638/* Draconian version. */
639void
640_ctk_rbtree_node_mark_invalid (CtkRBTree *tree,
641			       CtkRBNode *node)
642{
643  CTK_RBNODE_SET_FLAG (node, CTK_RBNODE_INVALID)do{ (node->flags|=CTK_RBNODE_INVALID); }while (0);
644  do
645    {
646      _fixup_validation (tree, node);
647      node = node->parent;
648      if (_ctk_rbtree_is_nil (node))
649	{
650	  node = tree->parent_node;
651	  tree = tree->parent_tree;
652	}
653    }
654  while (node);
655}
656#endif
657 
658void
659_ctk_rbtree_node_mark_valid (CtkRBTree *tree,
660			     CtkRBNode *node)
661{
662  if ((!CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID)(node?(((node->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID
)?(!(0)):(0)):(0))) &&
663      (!CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID)(node?(((node->flags&CTK_RBNODE_COLUMN_INVALID)==CTK_RBNODE_COLUMN_INVALID
)?(!(0)):(0)):(0))))
664    return;
665 
666  CTK_RBNODE_UNSET_FLAG (node, CTK_RBNODE_INVALID)do{ (node->flags&=~(CTK_RBNODE_INVALID)); }while (0);
667  CTK_RBNODE_UNSET_FLAG (node, CTK_RBNODE_COLUMN_INVALID)do{ (node->flags&=~(CTK_RBNODE_COLUMN_INVALID)); }while
 (0);
668 
669  do
670    {
671      if ((CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID)(node?(((node->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID
)?(!(0)):(0)):(0))) ||
672	  (CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID)(node?(((node->flags&CTK_RBNODE_COLUMN_INVALID)==CTK_RBNODE_COLUMN_INVALID
)?(!(0)):(0)):(0))) ||
673	  (node->children && CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID)(node->children->root?(((node->children->root->
flags&CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0))) ||
674	  (CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID)(node->left?(((node->left->flags&CTK_RBNODE_DESCENDANTS_INVALID
)==CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0))) ||
675	  (CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID)(node->right?(((node->right->flags&CTK_RBNODE_DESCENDANTS_INVALID
)==CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0))))
676	return;
677 
678      CTK_RBNODE_UNSET_FLAG (node, CTK_RBNODE_DESCENDANTS_INVALID)do{ (node->flags&=~(CTK_RBNODE_DESCENDANTS_INVALID)); }
while (0);
679      node = node->parent;
680      if (_ctk_rbtree_is_nil (node))
681	{
682	  node = tree->parent_node;
683	  tree = tree->parent_tree;
684	}
685    }
686  while (node);
687}
688 
689#if 0
690/* Draconian version */
691void
692_ctk_rbtree_node_mark_valid (CtkRBTree *tree,
693			     CtkRBNode *node)
694{
695  CTK_RBNODE_UNSET_FLAG (node, CTK_RBNODE_INVALID)do{ (node->flags&=~(CTK_RBNODE_INVALID)); }while (0);
696  CTK_RBNODE_UNSET_FLAG (node, CTK_RBNODE_COLUMN_INVALID)do{ (node->flags&=~(CTK_RBNODE_COLUMN_INVALID)); }while
 (0);
697 
698  do
699    {
700      _fixup_validation (tree, node);
701      node = node->parent;
702      if (_ctk_rbtree_is_nil (node))
703	{
704	  node = tree->parent_node;
705	  tree = tree->parent_tree;
706	}
707    }
708  while (node);
709}
710#endif
711/* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.
712 */
713void
714_ctk_rbtree_column_invalid (CtkRBTree *tree)
715{
716  CtkRBNode *node;
717 
718  if (tree == NULL((void*)0))
719    return;
720 
721  node = _ctk_rbtree_first (tree);
722 
723  do
724    {
725      if (! (CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID)(node?(((node->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID
)?(!(0)):(0)):(0))))
726	CTK_RBNODE_SET_FLAG (node, CTK_RBNODE_COLUMN_INVALID)do{ (node->flags|=CTK_RBNODE_COLUMN_INVALID); }while (0);
727      CTK_RBNODE_SET_FLAG (node, CTK_RBNODE_DESCENDANTS_INVALID)do{ (node->flags|=CTK_RBNODE_DESCENDANTS_INVALID); }while (
0);
728 
729      if (node->children)
730	_ctk_rbtree_column_invalid (node->children);
731    }
732  while ((node = _ctk_rbtree_next (tree, node)) != NULL((void*)0));
733}
734 
735void
736_ctk_rbtree_mark_invalid (CtkRBTree *tree)
737{
738  CtkRBNode *node;
739 
740  if (tree == NULL((void*)0))
741    return;
742 
743  node = _ctk_rbtree_first (tree);
744 
745  do
746    {
747      CTK_RBNODE_SET_FLAG (node, CTK_RBNODE_INVALID)do{ (node->flags|=CTK_RBNODE_INVALID); }while (0);
748      CTK_RBNODE_SET_FLAG (node, CTK_RBNODE_DESCENDANTS_INVALID)do{ (node->flags|=CTK_RBNODE_DESCENDANTS_INVALID); }while (
0);
749 
750      if (node->children)
751	_ctk_rbtree_mark_invalid (node->children);
752    }
753  while ((node = _ctk_rbtree_next (tree, node)) != NULL((void*)0));
754}
755 
756void
757_ctk_rbtree_set_fixed_height (CtkRBTree *tree,
758			      gint       height,
759			      gboolean   mark_valid)
760{
761  CtkRBNode *node;
762 
763  if (tree == NULL((void*)0))
764    return;
765 
766  node = _ctk_rbtree_first (tree);
767 
768  do
769    {
770      if (CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID)(node?(((node->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID
)?(!(0)):(0)):(0)))
771        {
772	  _ctk_rbtree_node_set_height (tree, node, height);
773	  if (mark_valid)
774	    _ctk_rbtree_node_mark_valid (tree, node);
775	}
776 
777      if (node->children)
778	_ctk_rbtree_set_fixed_height (node->children, height, mark_valid);
779    }
780  while ((node = _ctk_rbtree_next (tree, node)) != NULL((void*)0));
781}
782 
783static void
784reorder_prepare (CtkRBTree *tree G_GNUC_UNUSED__attribute__ ((__unused__)),
785                 CtkRBNode *node,
786                 gpointer   data G_GNUC_UNUSED__attribute__ ((__unused__)))
787{
788  node->offset -= node->left->offset + node->right->offset;
789  CTK_RBNODE_UNSET_FLAG (node, CTK_RBNODE_DESCENDANTS_INVALID)do{ (node->flags&=~(CTK_RBNODE_DESCENDANTS_INVALID)); }
while (0);
790}
791 
792static void
793reorder_fixup (CtkRBTree *tree,
794               CtkRBNode *node,
795               gpointer   data G_GNUC_UNUSED__attribute__ ((__unused__)))
796{
797  node->offset += node->left->offset + node->right->offset;
798  node->count = 1 + node->left->count + node->right->count;
799  _fixup_validation (tree, node);
800  _fixup_total_count (tree, node);
801}
802 
803static void
804reorder_copy_node (CtkRBTree *tree,
805                   CtkRBNode *to,
806                   CtkRBNode *from)
807{
808  to->flags = (to->flags & CTK_RBNODE_NON_COLORS) | CTK_RBNODE_GET_COLOR (from)(from?(((from->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED)?
CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK);
809 
810  to->left = from->left;
811  if (!_ctk_rbtree_is_nil (to->left))
812    to->left->parent = to;
813 
814  to->right = from->right;
815  if (!_ctk_rbtree_is_nil (to->right))
816    to->right->parent = to;
817 
818  to->parent = from->parent;
819  if (_ctk_rbtree_is_nil (to->parent))
820    tree->root = to;
821  else if (to->parent->left == from)
822    to->parent->left = to;
823  else if (to->parent->right == from)
824    to->parent->right = to;
825}
826 
827/* It basically pulls everything out of the tree, rearranges it, and puts it
828 * back together.  Our strategy is to keep the old RBTree intact, and just
829 * rearrange the contents.  When that is done, we go through and update the
830 * heights.  There is probably a more elegant way to write this function.  If
831 * anyone wants to spend the time writing it, patches will be accepted.
832 */
833void
834_ctk_rbtree_reorder (CtkRBTree *tree,
835		     gint      *new_order,
836		     gint       length)
837{
838  CtkRBNode **nodes;
839  CtkRBNode *node;
840  gint i, j;
841  
842  g_return_if_fail (tree != NULL)do { if ((tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "tree != NULL"); return;
 } } while (0);
843  g_return_if_fail (length > 0)do { if ((length > 0)) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "length > 0"); return
; } } while (0);
844  g_return_if_fail (tree->root->count == length)do { if ((tree->root->count == length)) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "tree->root->count == length"
); return; } } while (0);
845  
846  nodes = g_new (CtkRBNode *, length)((CtkRBNode * *) g_malloc_n ((length), sizeof (CtkRBNode *)));
847 
848  _ctk_rbtree_traverse (tree, tree->root, G_PRE_ORDER, reorder_prepare, NULL((void*)0));
849 
850  for (node = _ctk_rbtree_first (tree), i = 0;
851       node;
852       node = _ctk_rbtree_next (tree, node), i++)
853    {
854      nodes[i] = node;
855    }
856 
857  for (i = 0; i < length; i++)
858    {
859      CtkRBNode tmp = { 0, };
860      GSList *l, *cycle = NULL((void*)0);
861 
862      tmp.offset = -1;
863 
864      /* already swapped */
865      if (nodes[i] == NULL((void*)0))
866        continue;
867      /* no need to swap */
868      if (new_order[i] == i)
869        continue;
870 
871      /* make a list out of the pending nodes */
872      for (j = i; new_order[j] != i; j = new_order[j])
873        {
874          cycle = g_slist_prepend (cycle, nodes[j]);
875          nodes[j] = NULL((void*)0);
876        }
877 
878      node = nodes[j];
879      reorder_copy_node (tree, &tmp, node);
880      for (l = cycle; l; l = l->next)
881        {
882          reorder_copy_node (tree, node, l->data);
883          node = l->data;
884        }
885 
886      reorder_copy_node (tree, node, &tmp);
887      nodes[j] = NULL((void*)0);
888      g_slist_free (cycle);
889    }
890 
891  _ctk_rbtree_traverse (tree, tree->root, G_POST_ORDER, reorder_fixup, NULL((void*)0));
892 
893  g_free (nodes);
894}
895 
896/**
897 * _ctk_rbtree_contains:
898 * @tree: a tree
899 * @potential_child: a potential child of @tree
900 *
901 * Checks if @potential_child is a child (direct or via intermediate
902 * trees) of @tree.
903 *
904 * Returns: %TRUE if @potentitial_child is a child of @tree.
905 **/
906gboolean
907_ctk_rbtree_contains (CtkRBTree *tree,
908                      CtkRBTree *potential_child)
909{
910  g_return_val_if_fail (tree != NULL, FALSE)do { if ((tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "tree != NULL"); return (
(0)); } } while (0);
911  g_return_val_if_fail (potential_child != NULL, FALSE)do { if ((potential_child != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "potential_child != NULL"
); return ((0)); } } while (0);
912 
913  do {
914    potential_child = potential_child->parent_tree;
915    if (potential_child == tree)
916      return TRUE(!(0));
917  } while (potential_child != NULL((void*)0));
918 
919  return FALSE(0);
920}
921 
922gint
923_ctk_rbtree_node_find_offset (CtkRBTree *tree,
924			      CtkRBNode *node)
925{
926  gint retval;
927 
928  g_assert (node)do { if (node) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 928, ((const char*) (__func__)), "node"); } while (0);
929  g_assert (node->left)do { if (node->left) ; else g_assertion_message_expr ("Ctk"
, "ctkrbtree.c", 929, ((const char*) (__func__)), "node->left"
); } while (0);
930  
931  retval = node->left->offset;
932 
933  while (tree && node && !_ctk_rbtree_is_nil (node))
934    {
935      CtkRBNode *last;
936 
937      last = node;
938      node = node->parent;
939 
940      /* Add left branch, plus children, iff we came from the right */
941      if (node->right == last)
942	retval += node->offset - node->right->offset;
943      
944      if (_ctk_rbtree_is_nil (node))
945	{
946	  node = tree->parent_node;
947	  tree = tree->parent_tree;
948 
949          /* Add the parent node, plus the left branch. */
950	  if (node)
951	    retval += node->left->offset + CTK_RBNODE_GET_HEIGHT (node)(node->offset-(node->left->offset+node->right->
offset+(node->children?node->children->root->offset
:0)));
952	}
953    }
954  return retval;
955}
956 
957guint
958_ctk_rbtree_node_get_index (CtkRBTree *tree,
959                            CtkRBNode *node)
960{
961  guint retval;  
962  
963  g_assert (node)do { if (node) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 963, ((const char*) (__func__)), "node"); } while (0);
964  g_assert (node->left)do { if (node->left) ; else g_assertion_message_expr ("Ctk"
, "ctkrbtree.c", 964, ((const char*) (__func__)), "node->left"
); } while (0);
965  
966  retval = node->left->total_count;
967 
968  while (tree && node && !_ctk_rbtree_is_nil (node))
969    {
970      CtkRBNode *last;
971 
972      last = node;
973      node = node->parent;
974 
975      /* Add left branch, plus children, iff we came from the right */
976      if (node->right == last)
977	retval += node->total_count - node->right->total_count;
978      
979      if (_ctk_rbtree_is_nil (node))
980	{
981	  node = tree->parent_node;
982	  tree = tree->parent_tree;
983 
984          /* Add the parent node, plus the left branch. */
985	  if (node)
986	    retval += node->left->total_count + 1; /* 1 == CTK_RBNODE_GET_PARITY() */
987	}
988    }
989  
990  return retval;
991}
992 
993static gint
994ctk_rbtree_real_find_offset (CtkRBTree  *tree,
995			     gint        height,
996			     CtkRBTree **new_tree,
997			     CtkRBNode **new_node)
998{
999  CtkRBNode *tmp_node;
1000 
1001  g_assert (tree)do { if (tree) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1001, ((const char*) (__func__)), "tree"); } while (0);
1002 
1003  if (height < 0)
1004    {
1005      *new_tree = NULL((void*)0);
1006      *new_node = NULL((void*)0);
1007 
1008      return 0;
1009    }
1010  
1011    
1012  tmp_node = tree->root;
1013  while (!_ctk_rbtree_is_nil (tmp_node) &&
1014	 (tmp_node->left->offset > height ||
1015	  (tmp_node->offset - tmp_node->right->offset) < height))
1016    {
1017      if (tmp_node->left->offset > height)
1018	tmp_node = tmp_node->left;
1019      else
1020	{
1021	  height -= (tmp_node->offset - tmp_node->right->offset);
1022	  tmp_node = tmp_node->right;
1023	}
1024    }
1025  if (_ctk_rbtree_is_nil (tmp_node))
1026    {
1027      *new_tree = NULL((void*)0);
1028      *new_node = NULL((void*)0);
1029      return 0;
1030    }
1031  if (tmp_node->children)
1032    {
1033      if ((tmp_node->offset -
1034	   tmp_node->right->offset -
1035	   tmp_node->children->root->offset) > height)
1036	{
1037	  *new_tree = tree;
1038	  *new_node = tmp_node;
1039	  return (height - tmp_node->left->offset);
1040	}
1041      return ctk_rbtree_real_find_offset (tmp_node->children,
1042					  height - tmp_node->left->offset -
1043					  (tmp_node->offset -
1044					   tmp_node->left->offset -
1045					   tmp_node->right->offset -
1046					   tmp_node->children->root->offset),
1047					  new_tree,
1048					  new_node);
1049    }
1050  *new_tree = tree;
1051  *new_node = tmp_node;
1052  return (height - tmp_node->left->offset);
1053}
1054 
1055gint
1056_ctk_rbtree_find_offset (CtkRBTree  *tree,
1057			 gint        height,
1058			 CtkRBTree **new_tree,
1059			 CtkRBNode **new_node)
1060{
1061  g_assert (tree)do { if (tree) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1061, ((const char*) (__func__)), "tree"); } while (0);
1062 
1063  if ((height < 0) ||
1064      (height >= tree->root->offset))
1065    {
1066      *new_tree = NULL((void*)0);
1067      *new_node = NULL((void*)0);
1068 
1069      return 0;
1070    }
1071  return ctk_rbtree_real_find_offset (tree, height, new_tree, new_node);
1072}
1073 
1074gboolean
1075_ctk_rbtree_find_index (CtkRBTree  *tree,
1076                        guint       index,
1077                        CtkRBTree **new_tree,
1078                        CtkRBNode **new_node)
1079{
1080  CtkRBNode *tmp_node;
1081 
1082  g_assert (tree)do { if (tree) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1082, ((const char*) (__func__)), "tree"); } while (0);
1083 
1084  tmp_node = tree->root;
1085  while (!_ctk_rbtree_is_nil (tmp_node))
1086    {
1087      if (tmp_node->left->total_count > index)
1088        {
1089          tmp_node = tmp_node->left;
1090        }
1091      else if (tmp_node->total_count - tmp_node->right->total_count <= index)
1092        {
1093          index -= tmp_node->total_count - tmp_node->right->total_count;
1094          tmp_node = tmp_node->right;
1095        }
1096      else
1097        {
1098          index -= tmp_node->left->total_count;
1099          break;
1100        }
1101    }
1102  if (_ctk_rbtree_is_nil (tmp_node))
1103    {
1104      *new_tree = NULL((void*)0);
1105      *new_node = NULL((void*)0);
1106      return FALSE(0);
1107    }
1108 
1109  if (index > 0)
1110    {
1111      g_assert (tmp_node->children)do { if (tmp_node->children) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1111, ((const char*) (__func__)), "tmp_node->children"
); } while (0);
1112 
1113      return _ctk_rbtree_find_index (tmp_node->children,
1114                                     index - 1,
1115                                     new_tree,
1116                                     new_node);
1117    }
1118 
1119  *new_tree = tree;
1120  *new_node = tmp_node;
1121  return TRUE(!(0));
1122}
1123 
1124void
1125_ctk_rbtree_remove_node (CtkRBTree *tree,
1126			 CtkRBNode *node)
1127{
1128  CtkRBNode *x, *y;
1129  gint y_height;
1130  guint y_total_count;
1131  
1132  g_return_if_fail (tree != NULL)do { if ((tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "tree != NULL"); return;
 } } while (0);
1133  g_return_if_fail (node != NULL)do { if ((node != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "node != NULL"); return;
 } } while (0);
1134 
1135  
1136#ifdef G_ENABLE_DEBUG1
1137  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
1138    {
1139      GString *s;
1140 
1141      s = g_string_new ("");
1142      g_string_append_printf (s, "_ctk_rbtree_remove_node: %p\n", node);
1143      _ctk_rbtree_debug_spew (tree, s);
1144      g_message ("%s", s->str);
1145      g_string_free (s, TRUE)(__builtin_constant_p ((!(0))) ? (((!(0))) ? (g_string_free) (
(s), ((!(0)))) : g_string_free_and_steal (s)) : (g_string_free
) ((s), ((!(0)))));
1146      _ctk_rbtree_test (G_STRLOC"ctkrbtree.c" ":" "1146", tree);
1147    }
1148#endif
1149  
1150  /* make sure we're deleting a node that's actually in the tree */
1151  for (x = node; !_ctk_rbtree_is_nil (x->parent); x = x->parent)
1152    ;
1153  g_return_if_fail (x == tree->root)do { if ((x == tree->root)) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "x == tree->root"); return
; } } while (0);
1154 
1155#ifdef G_ENABLE_DEBUG1
1156  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
1157    _ctk_rbtree_test (G_STRLOC"ctkrbtree.c" ":" "1157", tree);
1158#endif
1159  
1160  if (_ctk_rbtree_is_nil (node->left) ||
1161      _ctk_rbtree_is_nil (node->right))
1162    {
1163      y = node;
1164    }
1165  else
1166    {
1167      y = node->right;
1168 
1169      while (!_ctk_rbtree_is_nil (y->left))
1170	y = y->left;
1171    }
1172 
1173  y_height = CTK_RBNODE_GET_HEIGHT (y)(y->offset-(y->left->offset+y->right->offset+(
y->children?y->children->root->offset:0))) 
1174             + (y->children ? y->children->root->offset : 0);
1175  y_total_count = 1 + (y->children ? y->children->root->total_count : 0);
1176 
1177  /* x is y's only child, or nil */
1178  if (!_ctk_rbtree_is_nil (y->left))
1179    x = y->left;
1180  else
1181    x = y->right;
1182 
1183  /* remove y from the parent chain */
1184  if (!_ctk_rbtree_is_nil (x))
1185    x->parent = y->parent;
1186  if (!_ctk_rbtree_is_nil (y->parent))
1187    {
1188      if (y == y->parent->left)
1189	y->parent->left = x;
1190      else
1191	y->parent->right = x;
1192    }
1193  else
1194    {
1195      tree->root = x;
1196    }
1197 
1198  /* We need to clean up the validity of the tree.
1199   */
1200  ctk_rbnode_adjust (tree, y, -1, - y_total_count, - y_height);
1201 
1202  if (CTK_RBNODE_GET_COLOR (y)(y?(((y->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED)?CTK_RBNODE_RED
:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_BLACK)
1203    _ctk_rbtree_remove_node_fixup (tree, x, y->parent);
1204 
1205  if (y != node)
1206    {
1207      gint node_height, node_total_count;
1208 
1209      /* We want to see how much we remove from the aggregate values.
1210       * This is all the children we remove plus the node's values.
1211       */
1212      node_height = CTK_RBNODE_GET_HEIGHT (node)(node->offset-(node->left->offset+node->right->
offset+(node->children?node->children->root->offset
:0)))
1213                    + (node->children ? node->children->root->offset : 0);
1214      node_total_count = 1
1215                         + (node->children ? node->children->root->total_count : 0);
1216 
1217      /* Move the node over */
1218      if (CTK_RBNODE_GET_COLOR (node)(node?(((node->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED)?
CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) != CTK_RBNODE_GET_COLOR (y)(y?(((y->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED)?CTK_RBNODE_RED
:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK))
1219	y->flags ^= (CTK_RBNODE_BLACK | CTK_RBNODE_RED);
1220 
1221      y->left = node->left;
1222      if (!_ctk_rbtree_is_nil (y->left))
1223        y->left->parent = y;
1224      y->right = node->right;
1225      if (!_ctk_rbtree_is_nil (y->right))
1226        y->right->parent = y;
1227      y->parent = node->parent;
1228      if (!_ctk_rbtree_is_nil (y->parent))
1229        {
1230          if (y->parent->left == node)
1231            y->parent->left = y;
1232          else
1233            y->parent->right = y;
1234        }
1235      else
1236        {
1237          tree->root = y;
1238        }
1239      y->count = node->count;
1240      y->total_count = node->total_count;
1241      y->offset = node->offset;
1242 
1243      ctk_rbnode_adjust (tree, y, 
1244                         0,
1245                         y_total_count - node_total_count,
1246                         y_height - node_height);
1247    }
1248 
1249  _ctk_rbnode_free (node);
1250 
1251#ifdef G_ENABLE_DEBUG1
1252  if (CTK_DEBUG_CHECK (TREE)(ctk_get_debug_flags () & CTK_DEBUG_TREE))
1253    {
1254      GString *s;
1255 
1256      s = g_string_new ("_ctk_rbtree_remove_node finished...\n");
1257      _ctk_rbtree_debug_spew (tree, s);
1258      g_message ("%s", s->str);
1259      g_string_free (s, TRUE)(__builtin_constant_p ((!(0))) ? (((!(0))) ? (g_string_free) (
(s), ((!(0)))) : g_string_free_and_steal (s)) : (g_string_free
) ((s), ((!(0)))));
1260      _ctk_rbtree_test (G_STRLOC"ctkrbtree.c" ":" "1260", tree);
1261    }
1262#endif
1263}
1264 
1265CtkRBNode *
1266_ctk_rbtree_first (CtkRBTree *tree)
1267{
1268  CtkRBNode *node;
1269 
1270  node = tree->root;
1271 
1272  if (_ctk_rbtree_is_nil (node))
1273    return NULL((void*)0);
1274 
1275  while (!_ctk_rbtree_is_nil (node->left))
1276    node = node->left;
1277 
1278  return node;
1279}
1280 
1281CtkRBNode *
1282_ctk_rbtree_next (CtkRBTree *tree,
1283		  CtkRBNode *node)
1284{
1285  g_return_val_if_fail (tree != NULL, NULL)do { if ((tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "tree != NULL"); return (
((void*)0)); } } while (0);
1286  g_return_val_if_fail (node != NULL, NULL)do { if ((node != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "node != NULL"); return (
((void*)0)); } } while (0);
1287 
1288  /* Case 1: the node's below us. */
1289  if (!_ctk_rbtree_is_nil (node->right))
1290    {
1291      node = node->right;
1292      while (!_ctk_rbtree_is_nil (node->left))
1293	node = node->left;
1294      return node;
1295    }
1296 
1297  /* Case 2: it's an ancestor */
1298  while (!_ctk_rbtree_is_nil (node->parent))
1299    {
1300      if (node->parent->right == node)
1301	node = node->parent;
1302      else
1303	return (node->parent);
1304    }
1305 
1306  /* Case 3: There is no next node */
1307  return NULL((void*)0);
1308}
1309 
1310CtkRBNode *
1311_ctk_rbtree_prev (CtkRBTree *tree,
1312		  CtkRBNode *node)
1313{
1314  g_return_val_if_fail (tree != NULL, NULL)do { if ((tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "tree != NULL"); return (
((void*)0)); } } while (0);
1315  g_return_val_if_fail (node != NULL, NULL)do { if ((node != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "node != NULL"); return (
((void*)0)); } } while (0);
1316 
1317  /* Case 1: the node's below us. */
1318  if (!_ctk_rbtree_is_nil (node->left))
1319    {
1320      node = node->left;
1321      while (!_ctk_rbtree_is_nil (node->right))
1322	node = node->right;
1323      return node;
1324    }
1325 
1326  /* Case 2: it's an ancestor */
1327  while (!_ctk_rbtree_is_nil (node->parent))
1328    {
1329      if (node->parent->left == node)
1330	node = node->parent;
1331      else
1332	return (node->parent);
1333    }
1334 
1335  /* Case 3: There is no next node */
1336  return NULL((void*)0);
1337}
1338 
1339void
1340_ctk_rbtree_next_full (CtkRBTree  *tree,
1341		       CtkRBNode  *node,
1342		       CtkRBTree **new_tree,
1343		       CtkRBNode **new_node)
1344{
1345  g_return_if_fail (tree != NULL)do { if ((tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "tree != NULL"); return;
 } } while (0);
1346  g_return_if_fail (node != NULL)do { if ((node != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "node != NULL"); return;
 } } while (0);
1347  g_return_if_fail (new_tree != NULL)do { if ((new_tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "new_tree != NULL"); return
; } } while (0);
1348  g_return_if_fail (new_node != NULL)do { if ((new_node != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "new_node != NULL"); return
; } } while (0);
1349 
1350  if (node->children)
1351    {
1352      *new_tree = node->children;
1353      *new_node = (*new_tree)->root;
1354      while (!_ctk_rbtree_is_nil ((*new_node)->left))
1355	*new_node = (*new_node)->left;
1356      return;
1357    }
1358 
1359  *new_tree = tree;
1360  *new_node = _ctk_rbtree_next (tree, node);
1361 
1362  while ((*new_node == NULL((void*)0)) &&
1363	 (*new_tree != NULL((void*)0)))
1364    {
1365      *new_node = (*new_tree)->parent_node;
1366      *new_tree = (*new_tree)->parent_tree;
1367      if (*new_tree)
1368	*new_node = _ctk_rbtree_next (*new_tree, *new_node);
1369    }
1370}
1371 
1372void
1373_ctk_rbtree_prev_full (CtkRBTree  *tree,
1374		       CtkRBNode  *node,
1375		       CtkRBTree **new_tree,
1376		       CtkRBNode **new_node)
1377{
1378  g_return_if_fail (tree != NULL)do { if ((tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "tree != NULL"); return;
 } } while (0);
1379  g_return_if_fail (node != NULL)do { if ((node != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "node != NULL"); return;
 } } while (0);
1380  g_return_if_fail (new_tree != NULL)do { if ((new_tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "new_tree != NULL"); return
; } } while (0);
1381  g_return_if_fail (new_node != NULL)do { if ((new_node != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "new_node != NULL"); return
; } } while (0);
1382 
1383  *new_tree = tree;
1384  *new_node = _ctk_rbtree_prev (tree, node);
1385 
1386  if (*new_node == NULL((void*)0))
1387    {
1388      *new_node = (*new_tree)->parent_node;
1389      *new_tree = (*new_tree)->parent_tree;
1390    }
1391  else
1392    {
1393      while ((*new_node)->children)
1394	{
1395	  *new_tree = (*new_node)->children;
1396	  *new_node = (*new_tree)->root;
1397          while (!_ctk_rbtree_is_nil ((*new_node)->right))
1398	    *new_node = (*new_node)->right;
1399	}
1400    }
1401}
1402 
1403gint
1404_ctk_rbtree_get_depth (CtkRBTree *tree)
1405{
1406  CtkRBTree *tmp_tree;
1407  gint depth = 0;
1408 
1409  tmp_tree = tree->parent_tree;
1410  while (tmp_tree)
1411    {
1412      ++depth;
1413      tmp_tree = tmp_tree->parent_tree;
1414    }
1415 
1416  return depth;
1417}
1418 
1419static void
1420_ctk_rbtree_traverse_pre_order (CtkRBTree             *tree,
1421				CtkRBNode             *node,
1422				CtkRBTreeTraverseFunc  func,
1423				gpointer               data)
1424{
1425  if (_ctk_rbtree_is_nil (node))
1426    return;
1427 
1428  (* func) (tree, node, data);
1429  _ctk_rbtree_traverse_pre_order (tree, node->left, func, data);
1430  _ctk_rbtree_traverse_pre_order (tree, node->right, func, data);
1431}
1432 
1433static void
1434_ctk_rbtree_traverse_post_order (CtkRBTree             *tree,
1435				 CtkRBNode             *node,
1436				 CtkRBTreeTraverseFunc  func,
1437				 gpointer               data)
1438{
1439  if (_ctk_rbtree_is_nil (node))
1440    return;
1441 
1442  _ctk_rbtree_traverse_post_order (tree, node->left, func, data);
1443  _ctk_rbtree_traverse_post_order (tree, node->right, func, data);
1444  (* func) (tree, node, data);
1445}
1446 
1447void
1448_ctk_rbtree_traverse (CtkRBTree             *tree,
1449		      CtkRBNode             *node,
1450		      GTraverseType          order,
1451		      CtkRBTreeTraverseFunc  func,
1452		      gpointer               data)
1453{
1454  g_return_if_fail (tree != NULL)do { if ((tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "tree != NULL"); return;
 } } while (0);
1455  g_return_if_fail (node != NULL)do { if ((node != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "node != NULL"); return;
 } } while (0);
1456  g_return_if_fail (func != NULL)do { if ((func != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "func != NULL"); return;
 } } while (0);
1457  g_return_if_fail (order <= G_LEVEL_ORDER)do { if ((order <= G_LEVEL_ORDER)) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "order <= G_LEVEL_ORDER"
); return; } } while (0);
1458 
1459  switch (order)
1460    {
1461    case G_PRE_ORDER:
1462      _ctk_rbtree_traverse_pre_order (tree, node, func, data);
1463      break;
1464    case G_POST_ORDER:
1465      _ctk_rbtree_traverse_post_order (tree, node, func, data);
1466      break;
1467    case G_IN_ORDER:
1468    case G_LEVEL_ORDER:
1469    default:
1470      g_warning ("unsupported traversal order.");
1471      break;
1472    }
1473}
1474 
1475static inline
1476void _fixup_validation (CtkRBTree *tree G_GNUC_UNUSED__attribute__ ((__unused__)),
1477			CtkRBNode *node)
1478{
1479  if (CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID)(node?(((node->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID
)?(!(0)):(0)):(0)) ||
1480      CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID)(node?(((node->flags&CTK_RBNODE_COLUMN_INVALID)==CTK_RBNODE_COLUMN_INVALID
)?(!(0)):(0)):(0)) ||
1481      CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID)(node->left?(((node->left->flags&CTK_RBNODE_DESCENDANTS_INVALID
)==CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0)) ||
1482      CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID)(node->right?(((node->right->flags&CTK_RBNODE_DESCENDANTS_INVALID
)==CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0)) ||
1483      (node->children != NULL((void*)0) && CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID)(node->children->root?(((node->children->root->
flags&CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0))))
1484    {
1485      CTK_RBNODE_SET_FLAG (node, CTK_RBNODE_DESCENDANTS_INVALID)do{ (node->flags|=CTK_RBNODE_DESCENDANTS_INVALID); }while (
0);
1486    }
1487  else
1488    {
1489      CTK_RBNODE_UNSET_FLAG (node, CTK_RBNODE_DESCENDANTS_INVALID)do{ (node->flags&=~(CTK_RBNODE_DESCENDANTS_INVALID)); }
while (0);
1490    }
1491}
1492 
1493static inline
1494void _fixup_total_count (CtkRBTree *tree G_GNUC_UNUSED__attribute__ ((__unused__)),
1495			 CtkRBNode *node)
1496{
1497  node->total_count = 1 +
1498    (node->children != NULL((void*)0) ? node->children->root->total_count : 0) + 
1499    node->left->total_count + node->right->total_count;
1500}
1501 
1502#ifdef G_ENABLE_DEBUG1
1503static guint
1504get_total_count (CtkRBNode *node)
1505{
1506  guint child_total = 0;
1507 
1508  child_total += (guint) node->left->total_count;
1509  child_total += (guint) node->right->total_count;
1510 
1511  if (node->children)
1512    child_total += (guint) node->children->root->total_count;
1513 
1514  return child_total + 1;
1515}
1516 
1517static guint
1518count_total (CtkRBTree *tree,
1519             CtkRBNode *node)
1520{
1521  guint res;
1522  
1523  if (_ctk_rbtree_is_nil (node))
1524    return 0;
1525  
1526  res =
1527    count_total (tree, node->left) +
1528    count_total (tree, node->right) +
1529    (guint)1 +
1530    (node->children ? count_total (node->children, node->children->root) : 0);
1531 
1532  if (res != node->total_count)
1533    g_error ("total count incorrect for node");
1534 
1535  if (get_total_count (node) != node->total_count)
1536    g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
1537  
1538  return res;
1539}
1540 
1541static gint
1542_count_nodes (CtkRBTree *tree,
1543              CtkRBNode *node)
1544{
1545  gint res;
1546  if (_ctk_rbtree_is_nil (node))
1547    return 0;
1548 
1549  g_assert (node->left)do { if (node->left) ; else g_assertion_message_expr ("Ctk"
, "ctkrbtree.c", 1549, ((const char*) (__func__)), "node->left"
); } while (0);
1550  g_assert (node->right)do { if (node->right) ; else g_assertion_message_expr ("Ctk"
, "ctkrbtree.c", 1550, ((const char*) (__func__)), "node->right"
); } while (0);
1551 
1552  res = (_count_nodes (tree, node->left) +
1553         _count_nodes (tree, node->right) + 1);
1554 
1555  if (res != node->count)
1556    g_error ("Tree failed");
1557  return res;
1558}
1559 
1560static void
1561_ctk_rbtree_test_height (CtkRBTree *tree,
1562                         CtkRBNode *node)
1563{
1564  gint computed_offset = 0;
1565 
1566  /* This whole test is sort of a useless truism. */
1567  
1568  if (!_ctk_rbtree_is_nil (node->left))
1569    computed_offset += node->left->offset;
1570 
1571  if (!_ctk_rbtree_is_nil (node->right))
1572    computed_offset += node->right->offset;
1573 
1574  if (node->children && !_ctk_rbtree_is_nil (node->children->root))
1575    computed_offset += node->children->root->offset;
1576 
1577  if (CTK_RBNODE_GET_HEIGHT (node)(node->offset-(node->left->offset+node->right->
offset+(node->children?node->children->root->offset
:0))) + computed_offset != node->offset)
1578    g_error ("node has broken offset");
1579 
1580  if (!_ctk_rbtree_is_nil (node->left))
1581    _ctk_rbtree_test_height (tree, node->left);
1582 
1583  if (!_ctk_rbtree_is_nil (node->right))
1584    _ctk_rbtree_test_height (tree, node->right);
1585 
1586  if (node->children && !_ctk_rbtree_is_nil (node->children->root))
1587    _ctk_rbtree_test_height (node->children, node->children->root);
1588}
1589 
1590static void
1591_ctk_rbtree_test_dirty (CtkRBTree *tree,
1592			CtkRBNode *node,
1593			 gint      expected_dirtyness)
1594{
1595 
1596  if (expected_dirtyness)
1597    {
1598      g_assert (CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID) ||do { if ((node?(((node->flags&CTK_RBNODE_COLUMN_INVALID
)==CTK_RBNODE_COLUMN_INVALID)?(!(0)):(0)):(0)) || (node?(((node
->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID)?(!(0)
):(0)):(0)) || (node->left?(((node->left->flags&
CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)) || (node->right?(((node->right->flags
&CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)) || (node->children && (node->
children->root?(((node->children->root->flags&
CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)))) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1602, ((const char*) (__func__)), "CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID) || CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID) || CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID) || CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID) || (node->children && CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID))"
); } while (0)
1599		CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID) ||do { if ((node?(((node->flags&CTK_RBNODE_COLUMN_INVALID
)==CTK_RBNODE_COLUMN_INVALID)?(!(0)):(0)):(0)) || (node?(((node
->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID)?(!(0)
):(0)):(0)) || (node->left?(((node->left->flags&
CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)) || (node->right?(((node->right->flags
&CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)) || (node->children && (node->
children->root?(((node->children->root->flags&
CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)))) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1602, ((const char*) (__func__)), "CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID) || CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID) || CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID) || CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID) || (node->children && CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID))"
); } while (0)
1600		CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID) ||do { if ((node?(((node->flags&CTK_RBNODE_COLUMN_INVALID
)==CTK_RBNODE_COLUMN_INVALID)?(!(0)):(0)):(0)) || (node?(((node
->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID)?(!(0)
):(0)):(0)) || (node->left?(((node->left->flags&
CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)) || (node->right?(((node->right->flags
&CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)) || (node->children && (node->
children->root?(((node->children->root->flags&
CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)))) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1602, ((const char*) (__func__)), "CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID) || CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID) || CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID) || CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID) || (node->children && CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID))"
); } while (0)
1601		CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID) ||do { if ((node?(((node->flags&CTK_RBNODE_COLUMN_INVALID
)==CTK_RBNODE_COLUMN_INVALID)?(!(0)):(0)):(0)) || (node?(((node
->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID)?(!(0)
):(0)):(0)) || (node->left?(((node->left->flags&
CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)) || (node->right?(((node->right->flags
&CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)) || (node->children && (node->
children->root?(((node->children->root->flags&
CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)))) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1602, ((const char*) (__func__)), "CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID) || CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID) || CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID) || CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID) || (node->children && CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID))"
); } while (0)
1602		(node->children && CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID)))do { if ((node?(((node->flags&CTK_RBNODE_COLUMN_INVALID
)==CTK_RBNODE_COLUMN_INVALID)?(!(0)):(0)):(0)) || (node?(((node
->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID)?(!(0)
):(0)):(0)) || (node->left?(((node->left->flags&
CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)) || (node->right?(((node->right->flags
&CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)) || (node->children && (node->
children->root?(((node->children->root->flags&
CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)))) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1602, ((const char*) (__func__)), "CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID) || CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID) || CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID) || CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID) || (node->children && CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID))"
); } while (0);
1603    }
1604  else
1605    {
1606      g_assert (! CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID) &&do { if (! (node?(((node->flags&CTK_RBNODE_COLUMN_INVALID
)==CTK_RBNODE_COLUMN_INVALID)?(!(0)):(0)):(0)) && ! (
node?(((node->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID
)?(!(0)):(0)):(0))) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1607, ((const char*) (__func__)), "! CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID) && ! CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID)"
); } while (0)
1607		! CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID))do { if (! (node?(((node->flags&CTK_RBNODE_COLUMN_INVALID
)==CTK_RBNODE_COLUMN_INVALID)?(!(0)):(0)):(0)) && ! (
node?(((node->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID
)?(!(0)):(0)):(0))) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1607, ((const char*) (__func__)), "! CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID) && ! CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID)"
); } while (0);
1608      if (!_ctk_rbtree_is_nil (node->left))
1609	g_assert (! CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID))do { if (! (node->left?(((node->left->flags&CTK_RBNODE_DESCENDANTS_INVALID
)==CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0))) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1609, ((const char*) (__func__)), "! CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID)"
); } while (0);
1610      if (!_ctk_rbtree_is_nil (node->right))
1611	g_assert (! CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID))do { if (! (node->right?(((node->right->flags&CTK_RBNODE_DESCENDANTS_INVALID
)==CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0))) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1611, ((const char*) (__func__)), "! CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID)"
); } while (0);
1612      if (node->children != NULL((void*)0))
1613	g_assert (! CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID))do { if (! (node->children->root?(((node->children->
root->flags&CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0))) ; else g_assertion_message_expr ("Ctk", "ctkrbtree.c"
, 1613, ((const char*) (__func__)), "! CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID)"
); } while (0);
1614    }
1615 
1616  if (!_ctk_rbtree_is_nil (node->left))
1617    _ctk_rbtree_test_dirty (tree, node->left, CTK_RBNODE_FLAG_SET (node->left, CTK_RBNODE_DESCENDANTS_INVALID)(node->left?(((node->left->flags&CTK_RBNODE_DESCENDANTS_INVALID
)==CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0)));
1618  if (!_ctk_rbtree_is_nil (node->right))
1619    _ctk_rbtree_test_dirty (tree, node->right, CTK_RBNODE_FLAG_SET (node->right, CTK_RBNODE_DESCENDANTS_INVALID)(node->right?(((node->right->flags&CTK_RBNODE_DESCENDANTS_INVALID
)==CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0)));
1620  if (node->children != NULL((void*)0) && !_ctk_rbtree_is_nil (node->children->root))
1621    _ctk_rbtree_test_dirty (node->children, node->children->root, CTK_RBNODE_FLAG_SET (node->children->root, CTK_RBNODE_DESCENDANTS_INVALID)(node->children->root?(((node->children->root->
flags&CTK_RBNODE_DESCENDANTS_INVALID)==CTK_RBNODE_DESCENDANTS_INVALID
)?(!(0)):(0)):(0)));
1622}
1623 
1624static void _ctk_rbtree_test_structure (CtkRBTree *tree);
1625 
1626static void
1627_ctk_rbtree_test_structure_helper (CtkRBTree *tree,
1628				   CtkRBNode *node)
1629{
1630  g_assert (!_ctk_rbtree_is_nil (node))do { if (!_ctk_rbtree_is_nil (node)) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1630, ((const char*) (__func__)), "!_ctk_rbtree_is_nil (node)"
); } while (0);
1631 
1632  g_assert (node->left != NULL)do { if (node->left != ((void*)0)) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1632, ((const char*) (__func__)), "node->left != NULL"
); } while (0);
1633  g_assert (node->right != NULL)do { if (node->right != ((void*)0)) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1633, ((const char*) (__func__)), "node->right != NULL"
); } while (0);
1634  g_assert (node->parent != NULL)do { if (node->parent != ((void*)0)) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1634, ((const char*) (__func__)), "node->parent != NULL"
); } while (0);
1635 
1636  if (!_ctk_rbtree_is_nil (node->left))
1637    {
1638      g_assert (node->left->parent == node)do { if (node->left->parent == node) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1638, ((const char*) (__func__)), "node->left->parent == node"
); } while (0);
1639      _ctk_rbtree_test_structure_helper (tree, node->left);
1640    }
1641  if (!_ctk_rbtree_is_nil (node->right))
1642    {
1643      g_assert (node->right->parent == node)do { if (node->right->parent == node) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1643, ((const char*) (__func__)), "node->right->parent == node"
); } while (0);
1644      _ctk_rbtree_test_structure_helper (tree, node->right);
1645    }
1646 
1647  if (node->children != NULL((void*)0))
1648    {
1649      g_assert (node->children->parent_tree == tree)do { if (node->children->parent_tree == tree) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1649, ((const char*) (__func__)), "node->children->parent_tree == tree"
); } while (0);
1650      g_assert (node->children->parent_node == node)do { if (node->children->parent_node == node) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1650, ((const char*) (__func__)), "node->children->parent_node == node"
); } while (0);
1651 
1652      _ctk_rbtree_test_structure (node->children);
1653    }
1654}
1655static void
1656_ctk_rbtree_test_structure (CtkRBTree *tree)
1657{
1658  g_assert (tree->root)do { if (tree->root) ; else g_assertion_message_expr ("Ctk"
, "ctkrbtree.c", 1658, ((const char*) (__func__)), "tree->root"
); } while (0);
1659  if (_ctk_rbtree_is_nil (tree->root))
1660    return;
1661 
1662  g_assert (_ctk_rbtree_is_nil (tree->root->parent))do { if (_ctk_rbtree_is_nil (tree->root->parent)) ; else
 g_assertion_message_expr ("Ctk", "ctkrbtree.c", 1662, ((const
 char*) (__func__)), "_ctk_rbtree_is_nil (tree->root->parent)"
); } while (0);
1663  _ctk_rbtree_test_structure_helper (tree, tree->root);
1664}
1665 
1666static void
1667_ctk_rbtree_test (const gchar *where G_GNUC_UNUSED__attribute__ ((__unused__)),
1668                  CtkRBTree   *tree)
1669{
1670  CtkRBTree *tmp_tree;
1671 
1672  if (tree == NULL((void*)0))
1673    return;
1674 
1675  /* Test the entire tree */
1676  tmp_tree = tree;
1677  while (tmp_tree->parent_tree)
1678    tmp_tree = tmp_tree->parent_tree;
1679  
1680  if (_ctk_rbtree_is_nil (tmp_tree->root))
1681    return;
1682 
1683  _ctk_rbtree_test_structure (tmp_tree);
1684 
1685  g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +do { if ((_count_nodes (tmp_tree, tmp_tree->root->left)
 + _count_nodes (tmp_tree, tmp_tree->root->right) + 1) ==
 tmp_tree->root->count) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1686, ((const char*) (__func__)), "(_count_nodes (tmp_tree, tmp_tree->root->left) + _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count"
); } while (0)
1686	     _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count)do { if ((_count_nodes (tmp_tree, tmp_tree->root->left)
 + _count_nodes (tmp_tree, tmp_tree->root->right) + 1) ==
 tmp_tree->root->count) ; else g_assertion_message_expr
 ("Ctk", "ctkrbtree.c", 1686, ((const char*) (__func__)), "(_count_nodes (tmp_tree, tmp_tree->root->left) + _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count"
); } while (0);
1687      
1688      
1689  _ctk_rbtree_test_height (tmp_tree, tmp_tree->root);
1690  _ctk_rbtree_test_dirty (tmp_tree, tmp_tree->root, CTK_RBNODE_FLAG_SET (tmp_tree->root, CTK_RBNODE_DESCENDANTS_INVALID)(tmp_tree->root?(((tmp_tree->root->flags&CTK_RBNODE_DESCENDANTS_INVALID
)==CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0)));
1691  g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count)do { if (count_total (tmp_tree, tmp_tree->root) == tmp_tree
->root->total_count) ; else g_assertion_message_expr ("Ctk"
, "ctkrbtree.c", 1691, ((const char*) (__func__)), "count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count"
); } while (0);
1692}
1693 
1694static void
1695_ctk_rbtree_debug_spew_helper (CtkRBTree *tree,
1696			       CtkRBNode *node,
1697                               GString   *s,
1698			       gint       depth)
1699{
1700  gint i;
1701  for (i = 0; i < depth; i++)
1702    g_string_append (s, "\t")(__builtin_constant_p ("\t") ? __extension__ ({ const char * const
 __val = ("\t"); g_string_append_len_inline (s, __val, (__val
 != ((void*)0)) ? (gssize) strlen (((__val) + !(__val))) : (gssize
) -1); }) : g_string_append_len_inline (s, "\t", (gssize) -1)
);
1703 
1704  g_string_append_printf (s, "(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
1705	   node,
1706	   (CTK_RBNODE_GET_COLOR (node)(node?(((node->flags&CTK_RBNODE_RED)==CTK_RBNODE_RED)?
CTK_RBNODE_RED:CTK_RBNODE_BLACK):CTK_RBNODE_BLACK) == CTK_RBNODE_BLACK)?"BLACK":" RED ",
1707	   node->offset,
1708	   node->total_count,
1709	   (CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_DESCENDANTS_INVALID)(node?(((node->flags&CTK_RBNODE_DESCENDANTS_INVALID)==
CTK_RBNODE_DESCENDANTS_INVALID)?(!(0)):(0)):(0)))?1:0,
1710	   (CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_INVALID)(node?(((node->flags&CTK_RBNODE_INVALID)==CTK_RBNODE_INVALID
)?(!(0)):(0)):(0)))?1:0,
1711	   (CTK_RBNODE_FLAG_SET (node, CTK_RBNODE_COLUMN_INVALID)(node?(((node->flags&CTK_RBNODE_COLUMN_INVALID)==CTK_RBNODE_COLUMN_INVALID
)?(!(0)):(0)):(0)))?1:0);
1712  if (node->children != NULL((void*)0))
1713    {
1714      g_string_append (s, "Looking at child.\n")(__builtin_constant_p ("Looking at child.\n") ? __extension__
 ({ const char * const __val = ("Looking at child.\n"); g_string_append_len_inline
 (s, __val, (__val != ((void*)0)) ? (gssize) strlen (((__val)
 + !(__val))) : (gssize) -1); }) : g_string_append_len_inline
 (s, "Looking at child.\n", (gssize) -1));
1715      _ctk_rbtree_debug_spew (node->children, s);
1716      g_string_append (s, "Done looking at child.\n")(__builtin_constant_p ("Done looking at child.\n") ? __extension__
 ({ const char * const __val = ("Done looking at child.\n"); g_string_append_len_inline
 (s, __val, (__val != ((void*)0)) ? (gssize) strlen (((__val)
 + !(__val))) : (gssize) -1); }) : g_string_append_len_inline
 (s, "Done looking at child.\n", (gssize) -1));
1717    }
1718  if (!_ctk_rbtree_is_nil (node->left))
1719    {
1720      _ctk_rbtree_debug_spew_helper (tree, node->left, s, depth + 1);
1721    }
1722  if (!_ctk_rbtree_is_nil (node->right))
1723    {
1724      _ctk_rbtree_debug_spew_helper (tree, node->right, s, depth + 1);
1725    }
1726}
1727 
1728static void
1729_ctk_rbtree_debug_spew (CtkRBTree *tree, GString *s)
1730{
1731  g_return_if_fail (tree != NULL)do { if ((tree != ((void*)0))) { } else { g_return_if_fail_warning
 ("Ctk", ((const char*) (__func__)), "tree != NULL"); return;
 } } while (0);
1732 
1733  if (_ctk_rbtree_is_nil (tree->root))
1734    g_string_append (s, "Empty tree...")(__builtin_constant_p ("Empty tree...") ? __extension__ ({ const
 char * const __val = ("Empty tree..."); g_string_append_len_inline
 (s, __val, (__val != ((void*)0)) ? (gssize) strlen (((__val)
 + !(__val))) : (gssize) -1); }) : g_string_append_len_inline
 (s, "Empty tree...", (gssize) -1));
1735  else
1736    _ctk_rbtree_debug_spew_helper (tree, tree->root, s, 0);
1737}
1738#endif /* G_ENABLE_DEBUG */