gtkrbtree.c 42.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14
/* gtkrbtree.c
 * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
Javier Jardón's avatar
Javier Jardón committed
15
 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
16 17
 */

18
#include "config.h"
19
#include "gtkrbtree.h"
20
#include "gtkdebug.h"
21

22 23 24 25 26 27 28 29 30 31
static GtkRBNode * _gtk_rbnode_new                (GtkRBTree  *tree,
						   gint        height);
static void        _gtk_rbnode_free               (GtkRBNode  *node);
static void        _gtk_rbnode_rotate_left        (GtkRBTree  *tree,
						   GtkRBNode  *node);
static void        _gtk_rbnode_rotate_right       (GtkRBTree  *tree,
						   GtkRBNode  *node);
static void        _gtk_rbtree_insert_fixup       (GtkRBTree  *tree,
						   GtkRBNode  *node);
static void        _gtk_rbtree_remove_node_fixup  (GtkRBTree  *tree,
32 33
						   GtkRBNode  *node,
                                                   GtkRBNode  *parent);
34 35
static inline void _fixup_validation              (GtkRBTree  *tree,
						   GtkRBNode  *node);
36
static inline void _fixup_total_count             (GtkRBTree  *tree,
37
						   GtkRBNode  *node);
38 39 40 41 42
#ifdef G_ENABLE_DEBUG  
static void        _gtk_rbtree_test               (const gchar *where,
                                                   GtkRBTree  *tree);
static void        _gtk_rbtree_debug_spew         (GtkRBTree  *tree);
#endif
43

44 45 46 47 48
static const GtkRBNode nil = {
  /* .flags = */ GTK_RBNODE_BLACK,

  /* rest is NULL */
};
49

50 51 52 53 54
gboolean
_gtk_rbtree_is_nil (GtkRBNode *node)
{
  return node == &nil;
}
55 56 57 58 59

static GtkRBNode *
_gtk_rbnode_new (GtkRBTree *tree,
		 gint       height)
{
60
  GtkRBNode *node = g_slice_new (GtkRBNode);
61

62 63 64
  node->left = (GtkRBNode *) &nil;
  node->right = (GtkRBNode *) &nil;
  node->parent = (GtkRBNode *) &nil;
65
  node->flags = GTK_RBNODE_RED;
66
  node->total_count = 1;
67 68 69 70 71 72 73 74 75
  node->count = 1;
  node->children = NULL;
  node->offset = height;
  return node;
}

static void
_gtk_rbnode_free (GtkRBNode *node)
{
76
#ifdef G_ENABLE_DEBUG
77
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
78
    {
79
      node->left = (gpointer) 0xdeadbeef;
80 81
      node->right = (gpointer) 0xdeadbeef;
      node->parent = (gpointer) 0xdeadbeef;
82
      node->total_count = 56789;
83 84 85 86
      node->offset = 56789;
      node->count = 56789;
      node->flags = 0;
    }
87
#endif
88
  g_slice_free (GtkRBNode, node);
89 90 91 92 93 94 95
}

static void
_gtk_rbnode_rotate_left (GtkRBTree *tree,
			 GtkRBNode *node)
{
  gint node_height, right_height;
96
  GtkRBNode *right;
97

98
  g_return_if_fail (!_gtk_rbtree_is_nil (node));
99
  g_return_if_fail (!_gtk_rbtree_is_nil (node->right));
100

101 102 103 104
  right = node->right;

  node_height = GTK_RBNODE_GET_HEIGHT (node);
  right_height = GTK_RBNODE_GET_HEIGHT (right);
105
  node->right = right->left;
106
  if (!_gtk_rbtree_is_nil (right->left))
107 108
    right->left->parent = node;

109
  right->parent = node->parent;
110
  if (!_gtk_rbtree_is_nil (node->parent))
111 112 113 114 115 116 117 118 119 120
    {
      if (node == node->parent->left)
	node->parent->left = right;
      else
	node->parent->right = right;
    } else {
      tree->root = right;
    }

  right->left = node;
121 122 123 124 125 126 127 128 129
  node->parent = right;

  node->count = 1 + node->left->count + node->right->count;
  right->count = 1 + right->left->count + right->right->count;

  node->offset = node_height + node->left->offset + node->right->offset +
                 (node->children ? node->children->root->offset : 0);
  right->offset = right_height + right->left->offset + right->right->offset +
                  (right->children ? right->children->root->offset : 0);
130

131 132
  _fixup_validation (tree, node);
  _fixup_validation (tree, right);
133 134
  _fixup_total_count (tree, node);
  _fixup_total_count (tree, right);
135 136 137 138 139 140 141
}

static void
_gtk_rbnode_rotate_right (GtkRBTree *tree,
			  GtkRBNode *node)
{
  gint node_height, left_height;
142
  GtkRBNode *left;
143

144
  g_return_if_fail (!_gtk_rbtree_is_nil (node));
145
  g_return_if_fail (!_gtk_rbtree_is_nil (node->left));
146

147 148 149 150
  left = node->left;

  node_height = GTK_RBNODE_GET_HEIGHT (node);
  left_height = GTK_RBNODE_GET_HEIGHT (left);
151
  
152
  node->left = left->right;
153
  if (!_gtk_rbtree_is_nil (left->right))
154 155
    left->right->parent = node;

156
  left->parent = node->parent;
157
  if (!_gtk_rbtree_is_nil (node->parent))
158 159 160 161 162 163 164 165 166 167 168 169 170
    {
      if (node == node->parent->right)
	node->parent->right = left;
      else
	node->parent->left = left;
    }
  else
    {
      tree->root = left;
    }

  /* link node and left */
  left->right = node;
171 172 173 174 175 176 177 178 179
  node->parent = left;

  node->count = 1 + node->left->count + node->right->count;
  left->count = 1 + left->left->count + left->right->count;

  node->offset = node_height + node->left->offset + node->right->offset +
                 (node->children ? node->children->root->offset : 0);
  left->offset = left_height + left->left->offset + left->right->offset +
                 (left->children?left->children->root->offset:0);
180

181 182
  _fixup_validation (tree, node);
  _fixup_validation (tree, left);
183 184
  _fixup_total_count (tree, node);
  _fixup_total_count (tree, left);
185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253
}

static void
_gtk_rbtree_insert_fixup (GtkRBTree *tree,
			  GtkRBNode *node)
{

  /* check Red-Black properties */
  while (node != tree->root && GTK_RBNODE_GET_COLOR (node->parent) == GTK_RBNODE_RED)
    {
      /* we have a violation */
      if (node->parent == node->parent->parent->left)
	{
	  GtkRBNode *y = node->parent->parent->right;
	  if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
	    {
				/* uncle is GTK_RBNODE_RED */
	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
	      GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
	      GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
	      node = node->parent->parent;
	    }
	  else
	    {
				/* uncle is GTK_RBNODE_BLACK */
	      if (node == node->parent->right)
		{
		  /* make node a left child */
		  node = node->parent;
		  _gtk_rbnode_rotate_left (tree, node);
		}

				/* recolor and rotate */
	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
	      GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
	      _gtk_rbnode_rotate_right(tree, node->parent->parent);
	    }
	}
      else
	{
	  /* mirror image of above code */
	  GtkRBNode *y = node->parent->parent->left;
	  if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
	    {
				/* uncle is GTK_RBNODE_RED */
	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
	      GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
	      GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
	      node = node->parent->parent;
	    }
	  else
	    {
				/* uncle is GTK_RBNODE_BLACK */
	      if (node == node->parent->left)
		{
		  node = node->parent;
		  _gtk_rbnode_rotate_right (tree, node);
		}
	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
	      GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
	      _gtk_rbnode_rotate_left (tree, node->parent->parent);
	    }
	}
    }
  GTK_RBNODE_SET_COLOR (tree->root, GTK_RBNODE_BLACK);
}

static void
_gtk_rbtree_remove_node_fixup (GtkRBTree *tree,
254 255
			       GtkRBNode *node,
                               GtkRBNode *parent)
256 257 258
{
  while (node != tree->root && GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
    {
259
      if (node == parent->left)
260
	{
261
	  GtkRBNode *w = parent->right;
262 263 264
	  if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
	    {
	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
265 266 267
	      GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_RED);
	      _gtk_rbnode_rotate_left (tree, parent);
	      w = parent->right;
268 269 270 271
	    }
	  if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
	    {
	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
272
	      node = parent;
273 274 275 276 277 278 279 280
	    }
	  else
	    {
	      if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
		{
		  GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
		  GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
		  _gtk_rbnode_rotate_right (tree, w);
281
		  w = parent->right;
282
		}
283 284
	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (parent));
	      GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_BLACK);
285
	      GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
286
	      _gtk_rbnode_rotate_left (tree, parent);
287 288 289 290 291
	      node = tree->root;
	    }
	}
      else
	{
292
	  GtkRBNode *w = parent->left;
293 294 295
	  if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
	    {
	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
296 297 298
	      GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_RED);
	      _gtk_rbnode_rotate_right (tree, parent);
	      w = parent->left;
299 300 301 302
	    }
	  if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
	    {
	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
303
	      node = parent;
304 305 306 307 308 309 310 311
	    }
	  else
	    {
	      if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
		{
		  GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
		  GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
		  _gtk_rbnode_rotate_left (tree, w);
312
		  w = parent->left;
313
		}
314 315
	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (parent));
	      GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_BLACK);
316
	      GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
317
	      _gtk_rbnode_rotate_right (tree, parent);
318 319 320
	      node = tree->root;
	    }
	}
321 322

      parent = node->parent;
323 324 325 326 327 328 329 330 331
    }
  GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK);
}

GtkRBTree *
_gtk_rbtree_new (void)
{
  GtkRBTree *retval;

332
  retval = g_new (GtkRBTree, 1);
333 334 335
  retval->parent_tree = NULL;
  retval->parent_node = NULL;

336
  retval->root = (GtkRBNode *) &nil;
337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366

  return retval;
}

static void
_gtk_rbtree_free_helper (GtkRBTree  *tree,
			 GtkRBNode  *node,
			 gpointer    data)
{
  if (node->children)
    _gtk_rbtree_free (node->children);

  _gtk_rbnode_free (node);
}

void
_gtk_rbtree_free (GtkRBTree *tree)
{
  _gtk_rbtree_traverse (tree,
			tree->root,
			G_POST_ORDER,
			_gtk_rbtree_free_helper,
			NULL);

  if (tree->parent_node &&
      tree->parent_node->children == tree)
    tree->parent_node->children = NULL;
  g_free (tree);
}

367 368 369 370 371 372 373
static void
gtk_rbnode_adjust (GtkRBTree *tree,
                   GtkRBNode *node,
                   int        count_diff,
                   int        total_count_diff,
                   int        offset_diff)
{
374
  while (tree && node && !_gtk_rbtree_is_nil (node))
375 376 377 378 379 380 381
    {
      _fixup_validation (tree, node);
      node->offset += offset_diff;
      node->count += count_diff;
      node->total_count += total_count_diff;
      
      node = node->parent;
382
      if (_gtk_rbtree_is_nil (node))
383 384 385 386 387 388 389 390
	{
	  node = tree->parent_node;
	  tree = tree->parent_tree;
          count_diff = 0;
	}
    }
}

391 392 393
void
_gtk_rbtree_remove (GtkRBTree *tree)
{
394
#ifdef G_ENABLE_DEBUG  
395
  GtkRBTree *tmp_tree;
396

397
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
398
    _gtk_rbtree_test (G_STRLOC, tree);
399
#endif
400
  
401 402 403 404
  /* ugly hack to make _fixup_validation work in the first iteration of the
   * loop below */
  GTK_RBNODE_UNSET_FLAG (tree->root, GTK_RBNODE_DESCENDANTS_INVALID);
  
405 406 407 408 409
  gtk_rbnode_adjust (tree->parent_tree, 
                     tree->parent_node,
                     0,
                     - (int) tree->root->total_count,
                     - tree->root->offset);
410

411
#ifdef G_ENABLE_DEBUG  
412
  tmp_tree = tree->parent_tree;
413 414
#endif

415
  _gtk_rbtree_free (tree);
416

417
#ifdef G_ENABLE_DEBUG  
418
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
419
    _gtk_rbtree_test (G_STRLOC, tmp_tree);
420
#endif
421 422 423 424
}


GtkRBNode *
Jonathan Blandford's avatar
Jonathan Blandford committed
425 426 427 428
_gtk_rbtree_insert_after (GtkRBTree *tree,
			  GtkRBNode *current,
			  gint       height,
			  gboolean   valid)
429 430 431 432
{
  GtkRBNode *node;
  gboolean right = TRUE;

Owen Taylor's avatar
Owen Taylor committed
433
#ifdef G_ENABLE_DEBUG  
434
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
435
    {
Owen Taylor's avatar
Owen Taylor committed
436
      g_print ("\n\n_gtk_rbtree_insert_after: %p\n", current);
437 438 439
      _gtk_rbtree_debug_spew (tree);
      _gtk_rbtree_test (G_STRLOC, tree);
    }
Owen Taylor's avatar
Owen Taylor committed
440
#endif /* G_ENABLE_DEBUG */  
441

442
  if (current != NULL && !_gtk_rbtree_is_nil (current->right))
443 444
    {
      current = current->right;
445
      while (!_gtk_rbtree_is_nil (current->left))
446 447 448 449 450 451 452 453 454
	current = current->left;
      right = FALSE;
    }
  /* setup new node */
  node = _gtk_rbnode_new (tree, height);

  /* insert node in tree */
  if (current)
    {
455
      node->parent = current;
456 457 458 459
      if (right)
	current->right = node;
      else
	current->left = node;
460 461
      gtk_rbnode_adjust (tree, node->parent,
                         1, 1, height);
462 463 464
    }
  else
    {
465
      g_assert (_gtk_rbtree_is_nil (tree->root));
466
      tree->root = node;
467 468
      gtk_rbnode_adjust (tree->parent_tree, tree->parent_node,
                         0, 1, height);
469
    }
Jonathan Blandford's avatar
Jonathan Blandford committed
470 471 472 473 474 475

  if (valid)
    _gtk_rbtree_node_mark_valid (tree, node);
  else
    _gtk_rbtree_node_mark_invalid (tree, node);

476 477
  _gtk_rbtree_insert_fixup (tree, node);

Owen Taylor's avatar
Owen Taylor committed
478
#ifdef G_ENABLE_DEBUG  
479
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
480
    {
481
      g_print ("_gtk_rbtree_insert_after finished...\n");
482
      _gtk_rbtree_debug_spew (tree);
483
      g_print ("\n\n");
484 485
      _gtk_rbtree_test (G_STRLOC, tree);
    }
Owen Taylor's avatar
Owen Taylor committed
486
#endif /* G_ENABLE_DEBUG */  
487

488 489 490 491
  return node;
}

GtkRBNode *
Jonathan Blandford's avatar
Jonathan Blandford committed
492 493 494 495
_gtk_rbtree_insert_before (GtkRBTree *tree,
			   GtkRBNode *current,
			   gint       height,
			   gboolean   valid)
496 497 498
{
  GtkRBNode *node;
  gboolean left = TRUE;
Owen Taylor's avatar
Owen Taylor committed
499 500

#ifdef G_ENABLE_DEBUG  
501
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
502
    {
Owen Taylor's avatar
Owen Taylor committed
503
      g_print ("\n\n_gtk_rbtree_insert_before: %p\n", current);
504 505 506
      _gtk_rbtree_debug_spew (tree);
      _gtk_rbtree_test (G_STRLOC, tree);
    }
Owen Taylor's avatar
Owen Taylor committed
507 508
#endif /* G_ENABLE_DEBUG */
  
509
  if (current != NULL && !_gtk_rbtree_is_nil (current->left))
510 511
    {
      current = current->left;
512
      while (!_gtk_rbtree_is_nil (current->right))
513 514 515 516 517 518 519 520 521 522
	current = current->right;
      left = FALSE;
    }

  /* setup new node */
  node = _gtk_rbnode_new (tree, height);

  /* insert node in tree */
  if (current)
    {
523
      node->parent = current;
524 525 526 527
      if (left)
	current->left = node;
      else
	current->right = node;
528 529
      gtk_rbnode_adjust (tree, node->parent,
                         1, 1, height);
530 531 532
    }
  else
    {
533
      g_assert (_gtk_rbtree_is_nil (tree->root));
534
      tree->root = node;
535 536
      gtk_rbnode_adjust (tree->parent_tree, tree->parent_node,
                         0, 1, height);
537
    }
Jonathan Blandford's avatar
Jonathan Blandford committed
538 539 540 541 542 543

  if (valid)
    _gtk_rbtree_node_mark_valid (tree, node);
  else
    _gtk_rbtree_node_mark_invalid (tree, node);

544 545
  _gtk_rbtree_insert_fixup (tree, node);

Owen Taylor's avatar
Owen Taylor committed
546
#ifdef G_ENABLE_DEBUG  
547
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
548
    {
549
      g_print ("_gtk_rbtree_insert_before finished...\n");
550
      _gtk_rbtree_debug_spew (tree);
551
      g_print ("\n\n");
552 553
      _gtk_rbtree_test (G_STRLOC, tree);
    }
Owen Taylor's avatar
Owen Taylor committed
554 555
#endif /* G_ENABLE_DEBUG */
  
556 557 558 559 560 561 562 563 564 565
  return node;
}

GtkRBNode *
_gtk_rbtree_find_count (GtkRBTree *tree,
			gint       count)
{
  GtkRBNode *node;

  node = tree->root;
566
  while (!_gtk_rbtree_is_nil (node) && (node->left->count + 1 != count))
567 568 569 570 571 572 573 574 575
    {
      if (node->left->count >= count)
	node = node->left;
      else
	{
	  count -= (node->left->count + 1);
	  node = node->right;
	}
    }
576
  if (_gtk_rbtree_is_nil (node))
577 578 579 580 581 582 583 584 585 586 587 588 589 590
    return NULL;
  return node;
}

void
_gtk_rbtree_node_set_height (GtkRBTree *tree,
			     GtkRBNode *node,
			     gint       height)
{
  gint diff = height - GTK_RBNODE_GET_HEIGHT (node);

  if (diff == 0)
    return;

591 592
  gtk_rbnode_adjust (tree, node, 0, 0, diff);

593
#ifdef G_ENABLE_DEBUG  
594
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
595
    _gtk_rbtree_test (G_STRLOC, tree);
596
#endif
597 598
}

599 600 601 602 603 604 605 606 607 608 609 610 611 612
void
_gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
			       GtkRBNode *node)
{
  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
    return;

  GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
  do
    {
      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
	return;
      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
      node = node->parent;
613
      if (_gtk_rbtree_is_nil (node))
614 615 616 617 618 619 620 621
	{
	  node = tree->parent_node;
	  tree = tree->parent_tree;
	}
    }
  while (node);
}

622 623 624 625 626 627 628 629 630 631 632
#if 0
/* Draconian version. */
void
_gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
			       GtkRBNode *node)
{
  GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
  do
    {
      _fixup_validation (tree, node);
      node = node->parent;
633
      if (_gtk_rbtree_is_nil (node))
634 635 636 637 638 639 640 641 642
	{
	  node = tree->parent_node;
	  tree = tree->parent_tree;
	}
    }
  while (node);
}
#endif

643 644 645 646
void
_gtk_rbtree_node_mark_valid (GtkRBTree *tree,
			     GtkRBNode *node)
{
Jonathan Blandford's avatar
Jonathan Blandford committed
647 648
  if ((!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
      (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)))
649 650 651
    return;

  GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
Jonathan Blandford's avatar
Jonathan Blandford committed
652 653
  GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);

654 655
  do
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
656 657
      if ((GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) ||
	  (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)) ||
658
	  (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)) ||
659 660
	  (GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
	  (GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))
661
	return;
Jonathan Blandford's avatar
Jonathan Blandford committed
662

663 664
      GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
      node = node->parent;
665
      if (_gtk_rbtree_is_nil (node))
666 667 668 669 670 671 672 673
	{
	  node = tree->parent_node;
	  tree = tree->parent_tree;
	}
    }
  while (node);
}

674 675 676 677 678 679 680 681
#if 0
/* Draconian version */
void
_gtk_rbtree_node_mark_valid (GtkRBTree *tree,
			     GtkRBNode *node)
{
  GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
  GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
Jonathan Blandford's avatar
Jonathan Blandford committed
682

683 684 685 686
  do
    {
      _fixup_validation (tree, node);
      node = node->parent;
687
      if (_gtk_rbtree_is_nil (node))
688 689 690 691 692 693 694 695
	{
	  node = tree->parent_node;
	  tree = tree->parent_tree;
	}
    }
  while (node);
}
#endif
Jonathan Blandford's avatar
Jonathan Blandford committed
696 697 698 699 700 701 702 703 704 705
/* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.
 */
void
_gtk_rbtree_column_invalid (GtkRBTree *tree)
{
  GtkRBNode *node;

  if (tree == NULL)
    return;

706
  node = _gtk_rbtree_first (tree);
Jonathan Blandford's avatar
Jonathan Blandford committed
707 708 709 710 711 712 713 714 715 716 717 718 719

  do
    {
      if (! (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)))
	GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);

      if (node->children)
	_gtk_rbtree_column_invalid (node->children);
    }
  while ((node = _gtk_rbtree_next (tree, node)) != NULL);
}

720 721 722 723 724 725 726 727
void
_gtk_rbtree_mark_invalid (GtkRBTree *tree)
{
  GtkRBNode *node;

  if (tree == NULL)
    return;

728
  node = _gtk_rbtree_first (tree);
729 730 731 732 733 734 735 736 737 738 739 740

  do
    {
      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);

      if (node->children)
	_gtk_rbtree_mark_invalid (node->children);
    }
  while ((node = _gtk_rbtree_next (tree, node)) != NULL);
}

741 742
void
_gtk_rbtree_set_fixed_height (GtkRBTree *tree,
743 744
			      gint       height,
			      gboolean   mark_valid)
745 746 747 748 749 750
{
  GtkRBNode *node;

  if (tree == NULL)
    return;

751
  node = _gtk_rbtree_first (tree);
752 753 754 755

  do
    {
      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
756 757 758 759 760
        {
	  _gtk_rbtree_node_set_height (tree, node, height);
	  if (mark_valid)
	    _gtk_rbtree_node_mark_valid (tree, node);
	}
761 762

      if (node->children)
763
	_gtk_rbtree_set_fixed_height (node->children, height, mark_valid);
764 765 766 767
    }
  while ((node = _gtk_rbtree_next (tree, node)) != NULL);
}

768 769 770 771
static void
reorder_prepare (GtkRBTree *tree,
                 GtkRBNode *node,
                 gpointer   data)
772
{
773 774
  node->offset -= node->left->offset + node->right->offset;
  GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
775 776
}

777 778 779 780
static void
reorder_fixup (GtkRBTree *tree,
               GtkRBNode *node,
               gpointer   data)
781
{
782 783 784 785
  node->offset += node->left->offset + node->right->offset;
  node->count = 1 + node->left->count + node->right->count;
  _fixup_validation (tree, node);
  _fixup_total_count (tree, node);
786 787
}

788
static void
789 790 791
reorder_copy_node (GtkRBTree *tree,
                   GtkRBNode *to,
                   GtkRBNode *from)
792
{
793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809
  to->flags = (to->flags & GTK_RBNODE_NON_COLORS) | GTK_RBNODE_GET_COLOR (from);

  to->left = from->left;
  if (!_gtk_rbtree_is_nil (to->left))
    to->left->parent = to;

  to->right = from->right;
  if (!_gtk_rbtree_is_nil (to->right))
    to->right->parent = to;

  to->parent = from->parent;
  if (_gtk_rbtree_is_nil (to->parent))
    tree->root = to;
  else if (to->parent->left == from)
    to->parent->left = to;
  else if (to->parent->right == from)
    to->parent->right = to;
810 811 812 813 814 815 816 817 818 819 820 821 822
}

/* It basically pulls everything out of the tree, rearranges it, and puts it
 * back together.  Our strategy is to keep the old RBTree intact, and just
 * rearrange the contents.  When that is done, we go through and update the
 * heights.  There is probably a more elegant way to write this function.  If
 * anyone wants to spend the time writing it, patches will be accepted.
 */
void
_gtk_rbtree_reorder (GtkRBTree *tree,
		     gint      *new_order,
		     gint       length)
{
823
  GtkRBNode **nodes;
824
  GtkRBNode *node;
825
  gint i, j;
826 827 828 829 830
  
  g_return_if_fail (tree != NULL);
  g_return_if_fail (length > 0);
  g_return_if_fail (tree->root->count == length);
  
831
  nodes = g_new (GtkRBNode *, length);
832

833
  _gtk_rbtree_traverse (tree, tree->root, G_PRE_ORDER, reorder_prepare, NULL);
834

835 836 837 838 839 840
  for (node = _gtk_rbtree_first (tree), i = 0;
       node;
       node = _gtk_rbtree_next (tree, node), i++)
    {
      nodes[i] = node;
    }
841 842 843

  for (i = 0; i < length; i++)
    {
844 845
      GtkRBNode tmp = { 0, };
      GSList *l, *cycle = NULL;
846

847
      tmp.offset = -1;
848

849 850 851 852 853 854
      /* already swapped */
      if (nodes[i] == NULL)
        continue;
      /* no need to swap */
      if (new_order[i] == i)
        continue;
855

856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873
      /* make a list out of the pending nodes */
      for (j = i; new_order[j] != i; j = new_order[j])
        {
          cycle = g_slist_prepend (cycle, nodes[j]);
          nodes[j] = NULL;
        }

      node = nodes[j];
      reorder_copy_node (tree, &tmp, node);
      for (l = cycle; l; l = l->next)
        {
          reorder_copy_node (tree, node, l->data);
          node = l->data;
        }

      reorder_copy_node (tree, node, &tmp);
      nodes[j] = NULL;
      g_slist_free (cycle);
874
    }
875

876 877 878
  _gtk_rbtree_traverse (tree, tree->root, G_POST_ORDER, reorder_fixup, NULL);

  g_free (nodes);
879 880
}

881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905
/**
 * _gtk_rbtree_contains:
 * @tree: a tree
 * @potential_child: a potential child of @tree
 *
 * Checks if @potential_child is a child (direct or via intermediate
 * trees) of @tree.
 *
 * Returns: %TRUE if @potentitial_child is a child of @tree.
 **/
gboolean
_gtk_rbtree_contains (GtkRBTree *tree,
                      GtkRBTree *potential_child)
{
  g_return_val_if_fail (tree != NULL, FALSE);
  g_return_val_if_fail (potential_child != NULL, FALSE);

  do {
    potential_child = potential_child->parent_tree;
    if (potential_child == tree)
      return TRUE;
  } while (potential_child != NULL);

  return FALSE;
}
906

907 908 909 910 911
gint
_gtk_rbtree_node_find_offset (GtkRBTree *tree,
			      GtkRBNode *node)
{
  GtkRBNode *last;
912 913 914 915 916 917
  gint retval;

  g_assert (node);
  g_assert (node->left);
  
  retval = node->left->offset;
918

919
  while (tree && node && !_gtk_rbtree_is_nil (node))
920 921 922
    {
      last = node;
      node = node->parent;
Havoc Pennington's avatar
Havoc Pennington committed
923 924

      /* Add left branch, plus children, iff we came from the right */
925
      if (node->right == last)
Havoc Pennington's avatar
Havoc Pennington committed
926 927
	retval += node->offset - node->right->offset;
      
928
      if (_gtk_rbtree_is_nil (node))
929 930 931
	{
	  node = tree->parent_node;
	  tree = tree->parent_tree;
Havoc Pennington's avatar
Havoc Pennington committed
932 933

          /* Add the parent node, plus the left branch. */
934
	  if (node)
Havoc Pennington's avatar
Havoc Pennington committed
935
	    retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
936 937 938 939 940
	}
    }
  return retval;
}

941 942 943
guint
_gtk_rbtree_node_get_index (GtkRBTree *tree,
                            GtkRBNode *node)
944 945
{
  GtkRBNode *last;
946
  guint retval;  
947 948 949 950
  
  g_assert (node);
  g_assert (node->left);
  
951
  retval = node->left->total_count;
952

953
  while (tree && node && !_gtk_rbtree_is_nil (node))
954 955 956 957 958 959
    {
      last = node;
      node = node->parent;

      /* Add left branch, plus children, iff we came from the right */
      if (node->right == last)
960
	retval += node->total_count - node->right->total_count;
961
      
962
      if (_gtk_rbtree_is_nil (node))
963 964 965 966 967 968
	{
	  node = tree->parent_node;
	  tree = tree->parent_tree;

          /* Add the parent node, plus the left branch. */
	  if (node)
969
	    retval += node->left->total_count + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
970 971 972
	}
    }
  
973
  return retval;
974 975
}

976 977 978 979 980
static gint
gtk_rbtree_real_find_offset (GtkRBTree  *tree,
			     gint        height,
			     GtkRBTree **new_tree,
			     GtkRBNode **new_node)
981 982 983
{
  GtkRBNode *tmp_node;

Jonathan Blandford's avatar
Jonathan Blandford committed
984 985
  g_assert (tree);

986 987 988 989
  if (height < 0)
    {
      *new_tree = NULL;
      *new_node = NULL;
Jonathan Blandford's avatar
Jonathan Blandford committed
990

991 992
      return 0;
    }
Jonathan Blandford's avatar
Jonathan Blandford committed
993
  
994
    
995
  tmp_node = tree->root;
996
  while (!_gtk_rbtree_is_nil (tmp_node) &&
997 998 999 1000 1001 1002 1003 1004 1005 1006 1007
	 (tmp_node->left->offset > height ||
	  (tmp_node->offset - tmp_node->right->offset) < height))
    {
      if (tmp_node->left->offset > height)
	tmp_node = tmp_node->left;
      else
	{
	  height -= (tmp_node->offset - tmp_node->right->offset);
	  tmp_node = tmp_node->right;
	}
    }
1008
  if (_gtk_rbtree_is_nil (tmp_node))
1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023
    {
      *new_tree = NULL;
      *new_node = NULL;
      return 0;
    }
  if (tmp_node->children)
    {
      if ((tmp_node->offset -
	   tmp_node->right->offset -
	   tmp_node->children->root->offset) > height)
	{
	  *new_tree = tree;
	  *new_node = tmp_node;
	  return (height - tmp_node->left->offset);
	}
1024 1025 1026 1027 1028 1029 1030 1031
      return gtk_rbtree_real_find_offset (tmp_node->children,
					  height - tmp_node->left->offset -
					  (tmp_node->offset -
					   tmp_node->left->offset -
					   tmp_node->right->offset -
					   tmp_node->children->root->offset),
					  new_tree,
					  new_node);
1032 1033 1034 1035 1036 1037
    }
  *new_tree = tree;
  *new_node = tmp_node;
  return (height - tmp_node->left->offset);
}

Jonathan Blandford's avatar
Jonathan Blandford committed
1038 1039
gint
_gtk_rbtree_find_offset (GtkRBTree  *tree,
1040 1041 1042
			 gint        height,
			 GtkRBTree **new_tree,
			 GtkRBNode **new_node)
Jonathan Blandford's avatar
Jonathan Blandford committed
1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053
{
  g_assert (tree);

  if ((height < 0) ||
      (height >= tree->root->offset))
    {
      *new_tree = NULL;
      *new_node = NULL;

      return 0;
    }
1054
  return gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
Jonathan Blandford's avatar
Jonathan Blandford committed
1055
}
1056

1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067
gboolean
_gtk_rbtree_find_index (GtkRBTree  *tree,
                        guint       index,
                        GtkRBTree **new_tree,
                        GtkRBNode **new_node)
{
  GtkRBNode *tmp_node;

  g_assert (tree);

  tmp_node = tree->root;
1068
  while (!_gtk_rbtree_is_nil (tmp_node))
1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084
    {
      if (tmp_node->left->total_count > index)
        {
          tmp_node = tmp_node->left;
        }
      else if (tmp_node->total_count - tmp_node->right->total_count <= index)
        {
          index -= tmp_node->total_count - tmp_node->right->total_count;
          tmp_node = tmp_node->right;
        }
      else
        {
          index -= tmp_node->left->total_count;
          break;
        }
    }
1085
  if (_gtk_rbtree_is_nil (tmp_node))
1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106
    {
      *new_tree = NULL;
      *new_node = NULL;
      return FALSE;
    }

  if (index > 0)
    {
      g_assert (tmp_node->children);

      return _gtk_rbtree_find_index (tmp_node->children,
                                     index - 1,
                                     new_tree,
                                     new_node);
    }

  *new_tree = tree;
  *new_node = tmp_node;
  return TRUE;
}

1107 1108 1109 1110 1111
void
_gtk_rbtree_remove_node (GtkRBTree *tree,
			 GtkRBNode *node)
{
  GtkRBNode *x, *y;
1112
  gint y_height;
1113
  guint y_total_count;
1114
  
1115 1116
  g_return_if_fail (tree != NULL);
  g_return_if_fail (node != NULL);
1117

Owen Taylor's avatar
Owen Taylor committed
1118 1119
  
#ifdef G_ENABLE_DEBUG
1120
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1121
    {
Owen Taylor's avatar
Owen Taylor committed
1122
      g_print ("\n\n_gtk_rbtree_remove_node: %p\n", node);
1123 1124 1125
      _gtk_rbtree_debug_spew (tree);
      _gtk_rbtree_test (G_STRLOC, tree);
    }
Owen Taylor's avatar
Owen Taylor committed
1126 1127
#endif /* G_ENABLE_DEBUG */
  
1128
  /* make sure we're deleting a node that's actually in the tree */
1129
  for (x = node; !_gtk_rbtree_is_nil (x->parent); x = x->parent)
1130 1131 1132
    ;
  g_return_if_fail (x == tree->root);

1133
#ifdef G_ENABLE_DEBUG  
1134
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1135
    _gtk_rbtree_test (G_STRLOC, tree);
1136 1137
#endif
  
1138 1139
  if (_gtk_rbtree_is_nil (node->left) ||
      _gtk_rbtree_is_nil (node->right))
1140 1141 1142 1143 1144 1145 1146
    {
      y = node;
    }
  else
    {
      y = node->right;

1147
      while (!_gtk_rbtree_is_nil (y->left))
1148 1149
	y = y->left;
    }
1150

1151 1152 1153
  y_height = GTK_RBNODE_GET_HEIGHT (y) 
             + (y->children ? y->children->root->offset : 0);
  y_total_count = 1 + (y->children ? y->children->root->total_count : 0);
1154

1155
  /* x is y's only child, or nil */
1156
  if (!_gtk_rbtree_is_nil (y->left))
1157 1158 1159 1160 1161
    x = y->left;
  else
    x = y->right;

  /* remove y from the parent chain */
1162
  if (!_gtk_rbtree_is_nil (x))
1163
    x->parent = y->parent;
1164
  if (!_gtk_rbtree_is_nil (y->parent))
1165 1166 1167 1168 1169 1170
    {
      if (y == y->parent->left)
	y->parent->left = x;
      else
	y->parent->right = x;
    }
1171
  else
1172 1173 1174 1175 1176 1177
    {
      tree->root = x;
    }

  /* We need to clean up the validity of the tree.
   */
1178
  gtk_rbnode_adjust (tree, y, -1, - y_total_count, - y_height);
1179

1180 1181 1182
  if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
    _gtk_rbtree_remove_node_fixup (tree, x, y->parent);

1183
  if (y != node)
1184
    {
1185
      gint node_height, node_total_count;
1186

1187 1188
      /* We want to see how much we remove from the aggregate values.
       * This is all the children we remove plus the node's values.
1189
       */
1190 1191 1192 1193
      node_height = GTK_RBNODE_GET_HEIGHT (node)
                    + (node->children ? node->children->root->offset : 0);
      node_total_count = 1
                         + (node->children ? node->children->root->total_count : 0);
1194

1195 1196
      /* Move the node over */
      if (GTK_RBNODE_GET_COLOR (node) != GTK_RBNODE_GET_COLOR (y))
1197
	y->flags ^= (GTK_RBNODE_BLACK | GTK_RBNODE_RED);
1198 1199

      y->left = node->left;
1200
      if (!_gtk_rbtree_is_nil (y->left))
1201 1202
        y->left->parent = y;
      y->right = node->right;
1203
      if (!_gtk_rbtree_is_nil (y->right))
1204 1205
        y->right->parent = y;
      y->parent = node->parent;
1206
      if (!_gtk_rbtree_is_nil (y->parent))
1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224
        {
          if (y->parent->left == node)
            y->parent->left = y;
          else
            y->parent->right = y;
        }
      else
        {
          tree->root = y;
        }
      y->count = node->count;
      y->total_count = node->total_count;
      y->offset = node->offset;

      gtk_rbnode_adjust (tree, y, 
                         0,
                         y_total_count - node_total_count,
                         y_height - node_height);
1225
    }
1226

1227
  _gtk_rbnode_free (node);
1228

Owen Taylor's avatar
Owen Taylor committed
1229
#ifdef G_ENABLE_DEBUG  
1230
  if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1231
    {
1232
      g_print ("_gtk_rbtree_remove_node finished...\n");
1233
      _gtk_rbtree_debug_spew (tree);
1234
      g_print ("\n\n");
1235 1236
      _gtk_rbtree_test (G_STRLOC, tree);
    }
Owen Taylor's avatar
Owen Taylor committed
1237
#endif /* G_ENABLE_DEBUG */  
1238 1239
}

1240 1241 1242 1243 1244 1245 1246
GtkRBNode *
_gtk_rbtree_first (GtkRBTree *tree)
{
  GtkRBNode *node;

  node = tree->root;

1247
  if (_gtk_rbtree_is_nil (node))
1248 1249
    return NULL;

1250
  while (!_gtk_rbtree_is_nil (node->left))
1251 1252 1253 1254 1255
    node = node->left;

  return node;
}

1256 1257 1258 1259 1260 1261 1262 1263
GtkRBNode *
_gtk_rbtree_next (GtkRBTree *tree,
		  GtkRBNode *node)
{
  g_return_val_if_fail (tree != NULL, NULL);
  g_return_val_if_fail (node != NULL, NULL);

  /* Case 1: the node's below us. */
1264
  if (!_gtk_rbtree_is_nil (node->right))
1265 1266
    {
      node = node->right;
1267
      while (!_gtk_rbtree_is_nil (node->left))
1268 1269 1270 1271 1272
	node = node->left;
      return node;
    }

  /* Case 2: it's an ancestor */
1273
  while (!_gtk_rbtree_is_nil (node->parent))
1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292
    {
      if (node->parent->right == node)
	node = node->parent;
      else
	return (node->parent);
    }

  /* Case 3: There is no next node */
  return NULL;
}

GtkRBNode *
_gtk_rbtree_prev (GtkRBTree *tree,
		  GtkRBNode *node)
{
  g_return_val_if_fail (tree != NULL, NULL);
  g_return_val_if_fail (node != NULL, NULL);

  /* Case 1: the node's below us. */
1293
  if (!_gtk_rbtree_is_nil (node->left))
1294 1295
    {
      node = node->left;
1296
      while (!_gtk_rbtree_is_nil (node->right))
1297 1298 1299 1300 1301
	node = node->right;
      return node;
    }

  /* Case 2: it's an ancestor */
1302
  while (!_gtk_rbtree_is_nil (node->parent))
1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328
    {
      if (node->parent->left == node)
	node = node->parent;
      else
	return (node->parent);
    }

  /* Case 3: There is no next node */
  return NULL;
}

void
_gtk_rbtree_next_full (GtkRBTree  *tree,
		       GtkRBNode  *node,
		       GtkRBTree **new_tree,
		       GtkRBNode **new_node)
{
  g_return_if_fail (tree != NULL);
  g_return_if_fail (node != NULL);
  g_return_if_fail (new_tree != NULL);
  g_return_if_fail (new_node != NULL);

  if (node->children)
    {
      *new_tree = node->children;
      *new_node = (*new_tree)->root;
1329
      while (!_gtk_rbtree_is_nil ((*new_node)->left))
1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371
	*new_node = (*new_node)->left;
      return;
    }

  *new_tree = tree;
  *new_node = _gtk_rbtree_next (tree, node);

  while ((*new_node == NULL) &&
	 (*new_tree != NULL))
    {
      *new_node = (*new_tree)->parent_node;
      *new_tree = (*new_tree)->parent_tree;
      if (*new_tree)
	*new_node = _gtk_rbtree_next (*new_tree, *new_node);
    }
}

void
_gtk_rbtree_prev_full (GtkRBTree  *tree,
		       GtkRBNode  *node,
		       GtkRBTree **new_tree,
		       GtkRBNode **new_node)
{
  g_return_if_fail (tree != NULL);
  g_return_if_fail (node != NULL);
  g_return_if_fail (new_tree != NULL);
  g_return_if_fail (new_node != NULL);

  *new_tree = tree;
  *new_node = _gtk_rbtree_prev (tree, node);

  if (*new_node == NULL)
    {
      *new_node = (*new_tree)->parent_node;
      *new_tree = (*new_tree)->parent_tree;
    }
  else
    {
      while ((*new_node)->children)
	{
	  *new_tree = (*new_node)->children;
	  *new_node = (*new_tree)->root;
1372
          while (!_gtk_rbtree_is_nil ((*new_node)->right))
1373 1374 1375 1376 1377
	    *new_node = (*new_node)->right;
	}
    }
}

1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393
gint
_gtk_rbtree_get_depth (GtkRBTree *tree)
{
  GtkRBTree *tmp_tree;
  gint depth = 0;

  tmp_tree = tree->parent_tree;
  while (tmp_tree)
    {
      ++depth;
      tmp_tree = tmp_tree->parent_tree;
    }

  return depth;
}

1394 1395 1396 1397 1398 1399
static void
_gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
				GtkRBNode             *node,
				GtkRBTreeTraverseFunc  func,
				gpointer               data)
{
1400
  if (_gtk_rbtree_is_nil (node))
1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413
    return;

  (* func) (tree, node, data);
  _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
  _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
}

static void
_gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
				 GtkRBNode             *node,
				 GtkRBTreeTraverseFunc  func,
				 gpointer               data)
{
1414
  if (_gtk_rbtree_is_nil (node))
1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449
    return;

  _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
  _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
  (* func) (tree, node, data);
}

void
_gtk_rbtree_traverse (GtkRBTree             *tree,
		      GtkRBNode             *node,
		      GTraverseType          order,
		      GtkRBTreeTraverseFunc  func,
		      gpointer               data)
{
  g_return_if_fail (tree != NULL);
  g_return_if_fail (node != NULL);
  g_return_if_fail (func != NULL);
  g_return_if_fail (order <= G_LEVEL_ORDER);

  switch (order)
    {
    case G_PRE_ORDER:
      _gtk_rbtree_traverse_pre_order (tree, node, func, data);
      break;
    case G_POST_ORDER:
      _gtk_rbtree_traverse_post_order (tree, node, func, data);
      break;
    case G_IN_ORDER:
    case G_LEVEL_ORDER:
    default:
      g_warning ("unsupported traversal order.");
      break;
    }
}

1450 1451 1452 1453 1454 1455
static inline
void _fixup_validation (GtkRBTree *tree,
			GtkRBNode *node)
{
  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
      GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1456 1457
      GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) ||
      GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID) ||
1458 1459 1460 1461 1462 1463 1464 1465 1466 1467
      (node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
    {
      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
    }
  else
    {
      GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
    }
}

1468
static inline
1469
void _fixup_total_count (GtkRBTree *tree,
1470 1471
		    GtkRBNode *node)
{
1472 1473 1474
  node->total_count = 1 +
    (node->children != NULL ? node->children->root->total_count : 0) + 
    node->left->total_count + node->right->total_count;
1475 1476
}

Owen Taylor's avatar
Owen Taylor committed
1477
#ifdef G_ENABLE_DEBUG
1478
static guint
1479
get_total_count (GtkRBNode *node)
1480
{
1481 1482
  guint child_total = 0;

1483 1484
  child_total += (guint) node->left->total_count;
  child_total += (guint) node->right->total_count;
1485 1486

  if (node->children)
1487
    child_total += (guint) node->children->root->total_count;
1488

1489
  return child_total + 1;
1490
}
1491

1492
static guint
1493 1494
count_total (GtkRBTree *tree,
             GtkRBNode *node)
1495 1496 1497
{
  guint res;
  
1498
  if (_gtk_rbtree_is_nil (node))
1499 1500 1501
    return 0;
  
  res =
1502 1503
    count_total (tree, node->left) +
    count_total (tree, node->right) +
1504
    (guint)1 +
1505
    (node->children ? count_total (node->children, node->children->root) : 0);
1506

1507 1508
  if (res != node->total_count)
    g_print ("total count incorrect for node\n");
1509

1510 1511
  if (get_total_count (node) != node->total_count)
    g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
1512 1513
  
  return res;
1514 1515
}

1516 1517 1518 1519 1520
static gint
_count_nodes (GtkRBTree *tree,
              GtkRBNode *node)
{
  gint res;
1521
  if (_gtk_rbtree_is_nil (node))
1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534
    return 0;

  g_assert (node->left);
  g_assert (node->right);

  res = (_count_nodes (tree, node->left) +
         _count_nodes (tree, node->right) + 1);

  if (res != node->count)
    g_print ("Tree failed\n");
  return res;
}

1535
static void
1536 1537
_gtk_rbtree_test_height (GtkRBTree *tree,
                         GtkRBNode *node)
1538
{
1539
  gint computed_offset = 0;
1540

1541 1542
  /* This whole test is sort of a useless truism. */
  
1543
  if (!_gtk_rbtree_is_nil (node->left))
1544
    computed_offset += node->left->offset;
1545