glib/gsequence.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
   3  * Soeren Sandmann (sandmann@daimi.au.dk)
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the
  17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18  * Boston, MA 02111-1307, USA.
  19  */
  20
  21 #include "config.h"
  22
  23 #include "glib.h"
  24 #include "galias.h"
  25
  26 typedef struct _GSequenceNode GSequenceNode;
  27
  28 struct _GSequence
  29 {
  30   GSequenceNode *       end_node;
  31   GDestroyNotify        data_destroy_notify;
  32   gboolean              access_prohibited;
  33 };
  34
  35 struct _GSequenceNode
  36 {
  37   gint                  n_nodes;
  38   GSequenceNode *       parent;
  39   GSequenceNode *       left;
  40   GSequenceNode *       right;
  41   gpointer              data;   /* For the end node, this field points
  42                                  * to the sequence
  43                                  */
  44 };
  45
  46 /*
  47  * Declaration of GSequenceNode methods
  48  */
  49 static GSequenceNode *node_new           (gpointer                  data);
  50 static GSequenceNode *node_get_first     (GSequenceNode            *node);
  51 static GSequenceNode *node_get_last      (GSequenceNode            *node);
  52 static GSequenceNode *node_get_prev      (GSequenceNode            *node);
  53 static GSequenceNode *node_get_next      (GSequenceNode            *node);
  54 static gint           node_get_pos       (GSequenceNode            *node);
  55 static GSequenceNode *node_get_by_pos    (GSequenceNode            *node,
  56                                           gint                      pos);
  57 static GSequenceNode *node_find_closest  (GSequenceNode            *haystack,
  58                                           GSequenceNode            *needle,
  59                                           GSequenceNode            *end,
  60                                           GSequenceIterCompareFunc  cmp,
  61                                           gpointer                  user_data);
  62 static gint           node_get_length    (GSequenceNode            *node);
  63 static void           node_free          (GSequenceNode            *node,
  64                                           GSequence                *seq);
  65 static void           node_cut           (GSequenceNode            *split);
  66 static void           node_insert_after  (GSequenceNode            *node,
  67                                           GSequenceNode            *second);
  68 static void           node_insert_before (GSequenceNode            *node,
  69                                           GSequenceNode            *new);
  70 static void           node_unlink        (GSequenceNode            *node);
  71 static void           node_insert_sorted (GSequenceNode            *node,
  72                                           GSequenceNode            *new,
  73                                           GSequenceNode            *end,
  74                                           GSequenceIterCompareFunc  cmp_func,
  75                                           gpointer                  cmp_data);
  76
  77 /*
  78  * Various helper functions
  79  */
  80 static void
  81 check_seq_access (GSequence *seq)
  82 {
  83   if (G_UNLIKELY (seq->access_prohibited))
  84     {
  85       g_warning ("Accessing a sequence while it is "
  86                  "being sorted or searched is not allowed");
  87     }
  88 }
  89
  90 static GSequence *
  91 get_sequence (GSequenceNode *node)
  92 {
  93   return (GSequence *)node_get_last (node)->data;
  94 }
  95
  96 static void
  97 check_iter_access (GSequenceIter *iter)
  98 {
  99   check_seq_access (get_sequence (iter));
 100 }
 101
 102 static gboolean
 103 is_end (GSequenceIter *iter)
 104 {
 105   GSequence *seq = get_sequence (iter);
 106
 107   return seq->end_node == iter;
 108 }
 109
 110 typedef struct
 111 {
 112   GCompareDataFunc  cmp_func;
 113   gpointer          cmp_data;
 114   GSequenceNode    *end_node;
 115 } SortInfo;
 116
 117 /* This function compares two iters using a normal compare
 118  * function and user_data passed in in a SortInfo struct
 119  */
 120 static gint
 121 iter_compare (GSequenceIter *node1,
 122               GSequenceIter *node2,
 123               gpointer       data)
 124 {
 125   const SortInfo *info = data;
 126   gint retval;
 127
 128   if (node1 == info->end_node)
 129     return 1;
 130
 131   if (node2 == info->end_node)
 132     return -1;
 133
 134   retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
 135
 136   return retval;
 137 }
 138
 139 /*
 140  * Public API
 141  */
 142
 143 /**
 144  * g_sequence_new:
 145  * @data_destroy: a #GDestroyNotify function, or %NULL
 146  *
 147  * Creates a new GSequence. The @data_destroy function, if non-%NULL will
 148  * be called on all items when the sequence is destroyed and on items that
 149  * are removed from the sequence.
 150  *
 151  * Return value: a new #GSequence
 152  *
 153  * Since: 2.14
 154  **/
 155 GSequence *
 156 g_sequence_new (GDestroyNotify data_destroy)
 157 {
 158   GSequence *seq = g_new (GSequence, 1);
 159   seq->data_destroy_notify = data_destroy;
 160
 161   seq->end_node = node_new (seq);
 162
 163   seq->access_prohibited = FALSE;
 164
 165   return seq;
 166 }
 167
 168 /**
 169  * g_sequence_free:
 170  * @seq: a #GSequence
 171  *
 172  * Frees the memory allocated for @seq. If @seq has a data destroy
 173  * function associated with it, that function is called on all items in
 174  * @seq.
 175  *
 176  * Since: 2.14
 177  **/
 178 void
 179 g_sequence_free (GSequence *seq)
 180 {
 181   g_return_if_fail (seq != NULL);
 182
 183   check_seq_access (seq);
 184
 185   node_free (seq->end_node, seq);
 186
 187   g_free (seq);
 188 }
 189
 190 /**
 191  * g_sequence_foreach_range:
 192  * @begin: a #GSequenceIter
 193  * @end: a #GSequenceIter
 194  * @func: a #GFunc
 195  * @user_data: user data passed to @func
 196  *
 197  * Calls @func for each item in the range (@begin, @end) passing
 198  * @user_data to the function.
 199  *
 200  * Since: 2.14
 201  **/
 202 void
 203 g_sequence_foreach_range (GSequenceIter *begin,
 204                           GSequenceIter *end,
 205                           GFunc          func,
 206                           gpointer       user_data)
 207 {
 208   GSequence *seq;
 209   GSequenceIter *iter;
 210
 211   g_return_if_fail (func != NULL);
 212   g_return_if_fail (begin != NULL);
 213   g_return_if_fail (end != NULL);
 214
 215   seq = get_sequence (begin);
 216
 217   seq->access_prohibited = TRUE;
 218
 219   iter = begin;
 220   while (iter != end)
 221     {
 222       GSequenceIter *next = node_get_next (iter);
 223
 224       func (iter->data, user_data);
 225
 226       iter = next;
 227     }
 228
 229   seq->access_prohibited = FALSE;
 230 }
 231
 232 /**
 233  * g_sequence_foreach:
 234  * @seq: a #GSequence
 235  * @func: the function to call for each item in @seq
 236  * @user_data: user data passed to @func
 237  *
 238  * Calls @func for each item in the sequence passing @user_data
 239  * to the function.
 240  *
 241  * Since: 2.14
 242  **/
 243 void
 244 g_sequence_foreach (GSequence *seq,
 245                     GFunc      func,
 246                     gpointer   user_data)
 247 {
 248   GSequenceIter *begin, *end;
 249
 250   check_seq_access (seq);
 251
 252   begin = g_sequence_get_begin_iter (seq);
 253   end   = g_sequence_get_end_iter (seq);
 254
 255   g_sequence_foreach_range (begin, end, func, user_data);
 256 }
 257
 258 /**
 259  * g_sequence_range_get_midpoint:
 260  * @begin: a #GSequenceIter
 261  * @end: a #GSequenceIter
 262  *
 263  * Finds an iterator somewhere in the range (@begin, @end). This
 264  * iterator will be close to the middle of the range, but is not
 265  * guaranteed to be <emphasis>exactly</emphasis> in the middle.
 266  *
 267  * The @begin and @end iterators must both point to the same sequence and
 268  * @begin must come before or be equal to @end in the sequence.
 269  *
 270  * Return value: A #GSequenceIter pointing somewhere in the
 271  * (@begin, @end) range.
 272  *
 273  * Since: 2.14
 274  **/
 275 GSequenceIter *
 276 g_sequence_range_get_midpoint (GSequenceIter *begin,
 277                                GSequenceIter *end)
 278 {
 279   int begin_pos, end_pos, mid_pos;
 280
 281   g_return_val_if_fail (begin != NULL, NULL);
 282   g_return_val_if_fail (end != NULL, NULL);
 283   g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
 284
 285   begin_pos = node_get_pos (begin);
 286   end_pos = node_get_pos (end);
 287
 288   g_return_val_if_fail (end_pos >= begin_pos, NULL);
 289
 290   mid_pos = begin_pos + (end_pos - begin_pos) / 2;
 291
 292   return node_get_by_pos (begin, mid_pos);
 293 }
 294
 295 /**
 296  * g_sequence_iter_compare:
 297  * @a: a #GSequenceIter
 298  * @b: a #GSequenceIter
 299  *
 300  * Returns a negative number if @a comes before @b, 0 if they are equal,
 301  * and a positive number if @a comes after @b.
 302  *
 303  * The @a and @b iterators must point into the same sequence.
 304  *
 305  * Return value: A negative number if @a comes before @b, 0 if they are
 306  * equal, and a positive number if @a comes after @b.
 307  *
 308  * Since: 2.14
 309  **/
 310 gint
 311 g_sequence_iter_compare (GSequenceIter *a,
 312                          GSequenceIter *b)
 313 {
 314   gint a_pos, b_pos;
 315
 316   g_return_val_if_fail (a != NULL, 0);
 317   g_return_val_if_fail (b != NULL, 0);
 318   g_return_val_if_fail (get_sequence (a) == get_sequence (b), 0);
 319
 320   check_iter_access (a);
 321   check_iter_access (b);
 322
 323   a_pos = node_get_pos (a);
 324   b_pos = node_get_pos (b);
 325
 326   if (a_pos == b_pos)
 327     return 0;
 328   else if (a_pos > b_pos)
 329     return 1;
 330   else
 331     return -1;
 332 }
 333
 334 /**
 335  * g_sequence_append:
 336  * @seq: a #GSequencePointer
 337  * @data: the data for the new item
 338  *
 339  * Adds a new item to the end of @seq.
 340  *
 341  * Return value: an iterator pointing to the new item
 342  *
 343  * Since: 2.14
 344  **/
 345 GSequenceIter *
 346 g_sequence_append (GSequence *seq,
 347                    gpointer   data)
 348 {
 349   GSequenceNode *node;
 350
 351   g_return_val_if_fail (seq != NULL, NULL);
 352
 353   check_seq_access (seq);
 354
 355   node = node_new (data);
 356   node_insert_before (seq->end_node, node);
 357
 358   return node;
 359 }
 360
 361 /**
 362  * g_sequence_prepend:
 363  * @seq: a #GSequence
 364  * @data: the data for the new item
 365  *
 366  * Adds a new item to the front of @seq
 367  *
 368  * Return value: an iterator pointing to the new item
 369  *
 370  * Since: 2.14
 371  **/
 372 GSequenceIter *
 373 g_sequence_prepend (GSequence *seq,
 374                     gpointer   data)
 375 {
 376   GSequenceNode *node, *first;
 377
 378   g_return_val_if_fail (seq != NULL, NULL);
 379
 380   check_seq_access (seq);
 381
 382   node = node_new (data);
 383   first = node_get_first (seq->end_node);
 384
 385   node_insert_before (first, node);
 386
 387   return node;
 388 }
 389
 390 /**
 391  * g_sequence_insert_before:
 392  * @iter: a #GSequenceIter
 393  * @data: the data for the new item
 394  *
 395  * Inserts a new item just before the item pointed to by @iter.
 396  *
 397  * Return value: an iterator pointing to the new item
 398  *
 399  * Since: 2.14
 400  **/
 401 GSequenceIter *
 402 g_sequence_insert_before (GSequenceIter *iter,
 403                           gpointer       data)
 404 {
 405   GSequenceNode *node;
 406
 407   g_return_val_if_fail (iter != NULL, NULL);
 408
 409   check_iter_access (iter);
 410
 411   node = node_new (data);
 412
 413   node_insert_before (iter, node);
 414
 415   return node;
 416 }
 417
 418 /**
 419  * g_sequence_remove:
 420  * @iter: a #GSequenceIter
 421  *
 422  * Removes the item pointed to by @iter. It is an error to pass the
 423  * end iterator to this function.
 424  *
 425  * If the sequnce has a data destroy function associated with it, this
 426  * function is called on the data for the removed item.
 427  *
 428  * Since: 2.14
 429  **/
 430 void
 431 g_sequence_remove (GSequenceIter *iter)
 432 {
 433   GSequence *seq;
 434
 435   g_return_if_fail (iter != NULL);
 436   g_return_if_fail (!is_end (iter));
 437
 438   check_iter_access (iter);
 439
 440   seq = get_sequence (iter);
 441
 442   node_unlink (iter);
 443   node_free (iter, seq);
 444 }
 445
 446 /**
 447  * g_sequence_remove_range:
 448  * @begin: a #GSequenceIter
 449  * @end: a #GSequenceIter
 450  *
 451  * Removes all items in the (@begin, @end) range.
 452  *
 453  * If the sequence has a data destroy function associated with it, this
 454  * function is called on the data for the removed items.
 455  *
 456  * Since: 2.14
 457  **/
 458 void
 459 g_sequence_remove_range (GSequenceIter *begin,
 460                          GSequenceIter *end)
 461 {
 462   g_return_if_fail (get_sequence (begin) == get_sequence (end));
 463
 464   check_iter_access (begin);
 465   check_iter_access (end);
 466
 467   g_sequence_move_range (NULL, begin, end);
 468 }
 469
 470 /**
 471  * g_sequence_move_range:
 472  * @dest: a #GSequenceIter
 473  * @begin: a #GSequenceIter
 474  * @end: a #GSequenceIter
 475  *
 476  * Inserts the (@begin, @end) range at the destination pointed to by ptr.
 477  * The @begin and @end iters must point into the same sequence. It is
 478  * allowed for @dest to point to a different sequence than the one pointed
 479  * into by @begin and @end.
 480  *
 481  * If @dest is NULL, the range indicated by @begin and @end is
 482  * removed from the sequence. If @dest iter points to a place within
 483  * the (@begin, @end) range, the range does not move.
 484  *
 485  * Since: 2.14
 486  **/
 487 void
 488 g_sequence_move_range (GSequenceIter *dest,
 489                        GSequenceIter *begin,
 490                        GSequenceIter *end)
 491 {
 492   GSequence *src_seq;
 493   GSequenceNode *first;
 494
 495   g_return_if_fail (begin != NULL);
 496   g_return_if_fail (end != NULL);
 497
 498   check_iter_access (begin);
 499   check_iter_access (end);
 500   if (dest)
 501     check_iter_access (dest);
 502
 503   src_seq = get_sequence (begin);
 504
 505   g_return_if_fail (src_seq == get_sequence (end));
 506
 507   /* Dest points to begin or end? */
 508   if (dest == begin || dest == end)
 509     return;
 510
 511   /* begin comes after end? */
 512   if (g_sequence_iter_compare (begin, end) >= 0)
 513     return;
 514
 515   /* dest points somewhere in the (begin, end) range? */
 516   if (dest && get_sequence (dest) == src_seq &&
 517       g_sequence_iter_compare (dest, begin) > 0 &&
 518       g_sequence_iter_compare (dest, end) < 0)
 519     {
 520       return;
 521     }
 522
 523   src_seq = get_sequence (begin);
 524
 525   first = node_get_first (begin);
 526
 527   node_cut (begin);
 528
 529   node_cut (end);
 530
 531   if (first != begin)
 532     node_insert_after (node_get_last (first), end);
 533
 534   if (dest)
 535     node_insert_before (dest, begin);
 536   else
 537     node_free (begin, src_seq);
 538 }
 539
 540 /**
 541  * g_sequence_sort:
 542  * @seq: a #GSequence
 543  * @cmp_func: the #GCompareDataFunc used to sort @seq. This function is
 544  *       passed two items of @seq and should return 0 if they are equal,
 545  *       a negative value fi the first comes before the second, and a
 546  *       positive value if the second comes before the first.
 547  * @cmp_data: user data passed to @cmp_func
 548  *
 549  * Sorts @seq using @cmp_func.
 550  *
 551  * Since: 2.14
 552  **/
 553 void
 554 g_sequence_sort (GSequence        *seq,
 555                  GCompareDataFunc  cmp_func,
 556                  gpointer          cmp_data)
 557 {
 558   SortInfo info = { cmp_func, cmp_data, seq->end_node };
 559
 560   check_seq_access (seq);
 561
 562   g_sequence_sort_iter (seq, iter_compare, &info);
 563 }
 564
 565 /**
 566  * g_sequence_insert_sorted:
 567  * @seq: a #GSequence
 568  * @data: the data to insert
 569  * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
 570  *     is called with two items of the @seq and @user_data. It should
 571  *     return 0 if the items are equal, a negative value if the first
 572  *     item comes before the second, and a positive value if the second
 573  *     item comes before the first.
 574  * @cmp_data: user data passed to @cmp_func.
 575  *
 576  * Inserts @data into @sequence using @func to determine the new position.
 577  * The sequence must already be sorted according to @cmp_func; otherwise the
 578  * new position of @data is undefined.
 579  *
 580  * Return value: a #GSequenceIter pointing to the new item.
 581  *
 582  * Since: 2.14
 583  **/
 584 GSequenceIter *
 585 g_sequence_insert_sorted (GSequence        *seq,
 586                           gpointer          data,
 587                           GCompareDataFunc  cmp_func,
 588                           gpointer          cmp_data)
 589 {
 590   SortInfo info = { cmp_func, cmp_data, NULL };
 591
 592   g_return_val_if_fail (seq != NULL, NULL);
 593   g_return_val_if_fail (cmp_func != NULL, NULL);
 594
 595   info.end_node = seq->end_node;
 596   check_seq_access (seq);
 597
 598   return g_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
 599 }
 600
 601 /**
 602  * g_sequence_sort_changed:
 603  * @iter: A #GSequenceIter
 604  * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
 605  *     is called with two items of the @seq and @user_data. It should
 606  *     return 0 if the items are equal, a negative value if the first
 607  *     item comes before the second, and a positive value if the second
 608  *     item comes before the first.
 609  * @cmp_data: user data passed to @cmp_func.
 610  *
 611  * Moves the data pointed to a new position as indicated by @cmp_func. This
 612  * function should be called for items in a sequence already sorted according
 613  * to @cmp_func whenever some aspect of an item changes so that @cmp_func
 614  * may return different values for that item.
 615  *
 616  * Since: 2.14
 617  **/
 618 void
 619 g_sequence_sort_changed (GSequenceIter    *iter,
 620                          GCompareDataFunc  cmp_func,
 621                          gpointer          cmp_data)
 622 {
 623   SortInfo info = { cmp_func, cmp_data, NULL };
 624
 625   g_return_if_fail (!is_end (iter));
 626
 627   info.end_node = get_sequence (iter)->end_node;
 628   check_iter_access (iter);
 629
 630   g_sequence_sort_changed_iter (iter, iter_compare, &info);
 631 }
 632
 633 /**
 634  * g_sequence_search:
 635  * @seq: a #GSequence
 636  * @data: data for the new item
 637  * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
 638  *     is called with two items of the @seq and @user_data. It should
 639  *     return 0 if the items are equal, a negative value if the first
 640  *     item comes before the second, and a positive value if the second
 641  *     item comes before the first.
 642  * @cmp_data: user data passed to @cmp_func.
 643  *
 644  * Returns an iterator pointing to the position where @data would
 645  * be inserted according to @cmp_func and @cmp_data.
 646  *
 647  * Return value: an #GSequenceIter pointing to the position where @data
 648  * would have been inserted according to @cmp_func and @cmp_data.
 649  *
 650  * Since: 2.14
 651  **/
 652 GSequenceIter *
 653 g_sequence_search (GSequence        *seq,
 654                    gpointer          data,
 655                    GCompareDataFunc  cmp_func,
 656                    gpointer          cmp_data)
 657 {
 658   SortInfo info = { cmp_func, cmp_data, NULL };
 659
 660   g_return_val_if_fail (seq != NULL, NULL);
 661
 662   info.end_node = seq->end_node;
 663   check_seq_access (seq);
 664
 665   return g_sequence_search_iter (seq, data, iter_compare, &info);
 666 }
 667
 668 /**
 669  * g_sequence_sort_iter:
 670  * @seq: a #GSequence
 671  * @cmp_func: the #GSequenceItercompare used to compare iterators in the
 672  *     sequence. It is called with two iterators pointing into @seq. It should
 673  *     return 0 if the iterators are equal, a negative value if the first
 674  *     iterator comes before the second, and a positive value if the second
 675  *     iterator comes before the first.
 676  * @cmp_data: user data passed to @cmp_func
 677  *
 678  * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
 679  * of a GCompareDataFunc as the compare function
 680  *
 681  * Since: 2.14
 682  **/
 683 void
 684 g_sequence_sort_iter (GSequence                *seq,
 685                       GSequenceIterCompareFunc  cmp_func,
 686                       gpointer                  cmp_data)
 687 {
 688   GSequence *tmp;
 689   GSequenceNode *begin, *end;
 690
 691   g_return_if_fail (seq != NULL);
 692   g_return_if_fail (cmp_func != NULL);
 693
 694   check_seq_access (seq);
 695
 696   begin = g_sequence_get_begin_iter (seq);
 697   end   = g_sequence_get_end_iter (seq);
 698
 699   tmp = g_sequence_new (NULL);
 700
 701   g_sequence_move_range (g_sequence_get_begin_iter (tmp), begin, end);
 702
 703   tmp->access_prohibited = TRUE;
 704   seq->access_prohibited = TRUE;
 705
 706   while (g_sequence_get_length (tmp) > 0)
 707     {
 708       GSequenceNode *node = g_sequence_get_begin_iter (tmp);
 709
 710       node_insert_sorted (seq->end_node, node, seq->end_node,
 711                           cmp_func, cmp_data);
 712     }
 713
 714   tmp->access_prohibited = FALSE;
 715   seq->access_prohibited = FALSE;
 716
 717   g_sequence_free (tmp);
 718 }
 719
 720 /**
 721  * g_sequence_sort_changed_iter:
 722  * @iter: a #GSequenceIter
 723  * @iter_cmp: the #GSequenceItercompare used to compare iterators in the
 724  *     sequence. It is called with two iterators pointing into @seq. It should
 725  *     return 0 if the iterators are equal, a negative value if the first
 726  *     iterator comes before the second, and a positive value if the second
 727  *     iterator comes before the first.
 728  * @cmp_data: user data passed to @cmp_func
 729  *
 730  * Like g_sequence_sort_changed(), but uses
 731  * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
 732  * the compare function.
 733  *
 734  * Since: 2.14
 735  **/
 736 void
 737 g_sequence_sort_changed_iter (GSequenceIter            *iter,
 738                               GSequenceIterCompareFunc  iter_cmp,
 739                               gpointer                  cmp_data)
 740 {
 741   GSequence *seq, *tmp_seq;
 742   GSequenceIter *next, *prev;
 743
 744   g_return_if_fail (iter != NULL);
 745   g_return_if_fail (!is_end (iter));
 746   g_return_if_fail (iter_cmp != NULL);
 747   check_iter_access (iter);
 748
 749   /* If one of the neighbours is equal to iter, then
 750    * don't move it. This ensures that sort_changed() is
 751    * a stable operation.
 752    */
 753
 754   next = node_get_next (iter);
 755   prev = node_get_prev (iter);
 756
 757   if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
 758     return;
 759
 760   if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
 761     return;
 762
 763   seq = get_sequence (iter);
 764
 765   seq->access_prohibited = TRUE;
 766
 767   tmp_seq = g_sequence_new (NULL);
 768   node_unlink (iter);
 769   node_insert_before (tmp_seq->end_node, iter);
 770
 771   node_insert_sorted (seq->end_node, iter, seq->end_node,
 772                       iter_cmp, cmp_data);
 773
 774   g_sequence_free (tmp_seq);
 775
 776   seq->access_prohibited = FALSE;
 777 }
 778
 779 /**
 780  * g_sequence_insert_sorted_iter:
 781  * @seq: a #GSequence
 782  * @data: data for the new item
 783  * @iter_cmp: the #GSequenceItercompare used to compare iterators in the
 784  *     sequence. It is called with two iterators pointing into @seq. It should
 785  *     return 0 if the iterators are equal, a negative value if the first
 786  *     iterator comes before the second, and a positive value if the second
 787  *     iterator comes before the first.
 788  * @cmp_data: user data passed to @cmp_func
 789  *
 790  * Like g_sequence_insert_sorted(), but uses
 791  * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
 792  * the compare function.
 793  *
 794  * Return value: a #GSequenceIter pointing to the new item
 795  *
 796  * Since: 2.14
 797  **/
 798 GSequenceIter *
 799 g_sequence_insert_sorted_iter (GSequence                *seq,
 800                                gpointer                  data,
 801                                GSequenceIterCompareFunc  iter_cmp,
 802                                gpointer                  cmp_data)
 803 {
 804   GSequenceNode *new_node;
 805   GSequence *tmp_seq;
 806
 807   g_return_val_if_fail (seq != NULL, NULL);
 808   g_return_val_if_fail (iter_cmp != NULL, NULL);
 809
 810   check_seq_access (seq);
 811
 812   seq->access_prohibited = TRUE;
 813
 814   /* Create a new temporary sequence and put the new node into
 815    * that. The reason for this is that the user compare function
 816    * will be called with the new node, and if it dereferences,
 817    * "is_end" will be called on it. But that will crash if the
 818    * node is not actually in a sequence.
 819    *
 820    * node_insert_sorted() makes sure the node is unlinked before
 821    * is is inserted.
 822    *
 823    * The reason we need the "iter" versions at all is that that
 824    * is the only kind of compare functions GtkTreeView can use.
 825    */
 826   tmp_seq = g_sequence_new (NULL);
 827   new_node = g_sequence_append (tmp_seq, data);
 828
 829   node_insert_sorted (seq->end_node, new_node,
 830                       seq->end_node, iter_cmp, cmp_data);
 831
 832   g_sequence_free (tmp_seq);
 833
 834   seq->access_prohibited = FALSE;
 835
 836   return new_node;
 837 }
 838
 839 /**
 840  * g_sequence_search_iter:
 841  * @seq: a #GSequence
 842  * @data: data for the new item
 843  * @iter_cmp: the #GSequenceIterCompare function used to compare iterators
 844  *     in the sequence. It is called with two iterators pointing into @seq.
 845  *     It should return 0 if the iterators are equal, a negative value if the
 846  *     first iterator comes before the second, and a positive value if the
 847  *     second iterator comes before the first.
 848  * @cmp_data: user data passed to @iter_cmp
 849  *
 850  * Like g_sequence_search(), but uses
 851  * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
 852  * the compare function.
 853  *
 854  * Return value: a #GSequenceIter pointing to the position in @seq
 855  * where @data would have been inserted according to @iter_cmp and @cmp_data.
 856  *
 857  * Since: 2.14
 858  **/
 859 GSequenceIter *
 860 g_sequence_search_iter (GSequence                *seq,
 861                         gpointer                  data,
 862                         GSequenceIterCompareFunc  iter_cmp,
 863                         gpointer                  cmp_data)
 864 {
 865   GSequenceNode *node;
 866   GSequenceNode *dummy;
 867   GSequence *tmp_seq;
 868
 869   g_return_val_if_fail (seq != NULL, NULL);
 870
 871   check_seq_access (seq);
 872
 873   seq->access_prohibited = TRUE;
 874
 875   /* Create a new temporary sequence and put the dummy node into
 876    * that. The reason for this is that the user compare function
 877    * will be called with the new node, and if it dereferences,
 878    * "is_end" will be called on it. But that will crash if the
 879    * node is not actually in a sequence.
 880    *
 881    * node_insert_sorted() makes sure the node is unlinked before
 882    * is is inserted.
 883    *
 884    * The reason we need the "iter" versions at all is that that
 885    * is the only kind of compare functions GtkTreeView can use.
 886    */
 887   tmp_seq = g_sequence_new (NULL);
 888   dummy = g_sequence_append (tmp_seq, data);
 889
 890   node = node_find_closest (seq->end_node, dummy,
 891                             seq->end_node, iter_cmp, cmp_data);
 892
 893   g_sequence_free (tmp_seq);
 894
 895   seq->access_prohibited = FALSE;
 896
 897   return node;
 898 }
 899
 900 /**
 901  * g_sequence_iter_get_sequence:
 902  * @iter: a #GSequenceIter
 903  *
 904  * Returns the #GSequence that @iter points into.
 905  *
 906  * Return value: the #GSequence that @iter points into.
 907  *
 908  * Since: 2.14
 909  **/
 910 GSequence *
 911 g_sequence_iter_get_sequence (GSequenceIter *iter)
 912 {
 913   g_return_val_if_fail (iter != NULL, NULL);
 914
 915   return get_sequence (iter);
 916 }
 917
 918 /**
 919  * g_sequence_get:
 920  * @iter: a #GSequenceIter
 921  *
 922  * Returns the data that @iter points to.
 923  *
 924  * Return value: the data that @iter points to
 925  *
 926  * Since: 2.14
 927  **/
 928 gpointer
 929 g_sequence_get (GSequenceIter *iter)
 930 {
 931   g_return_val_if_fail (iter != NULL, NULL);
 932   g_return_val_if_fail (!is_end (iter), NULL);
 933
 934   return iter->data;
 935 }
 936
 937 /**
 938  * g_sequence_set:
 939  * @iter: a #GSequenceIter
 940  * @data: new data for the item
 941  *
 942  * Changes the data for the item pointed to by @iter to be @data. If
 943  * the sequence has a data destroy function associated with it, that
 944  * function is called on the existing data that @iter pointed to.
 945  *
 946  * Since: 2.14
 947  **/
 948 void
 949 g_sequence_set (GSequenceIter *iter,
 950                 gpointer       data)
 951 {
 952   GSequence *seq;
 953
 954   g_return_if_fail (iter != NULL);
 955   g_return_if_fail (!is_end (iter));
 956
 957   seq = get_sequence (iter);
 958
 959   /* If @data is identical to iter->data, it is destroyed
 960    * here. This will work right in case of ref-counted objects. Also
 961    * it is similar to what ghashtables do.
 962    *
 963    * For non-refcounted data it's a little less convenient, but
 964    * code relying on self-setting not destroying would be
 965    * pretty dubious anyway ...
 966    */
 967
 968   if (seq->data_destroy_notify)
 969     seq->data_destroy_notify (iter->data);
 970
 971   iter->data = data;
 972 }
 973
 974 /**
 975  * g_sequence_get_length:
 976  * @seq: a #GSequence
 977  *
 978  * Returns the length of @seq
 979  *
 980  * Return value: the length of @seq
 981  *
 982  * Since: 2.14
 983  **/
 984 gint
 985 g_sequence_get_length (GSequence *seq)
 986 {
 987   return node_get_length (seq->end_node) - 1;
 988 }
 989
 990 /**
 991  * g_sequence_get_end_iter:
 992  * @seq: a #GSequence
 993  *
 994  * Returns the end iterator for @seg
 995  *
 996  * Return value: the end iterator for @seq
 997  *
 998  * Since: 2.14
 999  **/
1000 GSequenceIter *
1001 g_sequence_get_end_iter (GSequence *seq)
1002 {
1003   g_return_val_if_fail (seq != NULL, NULL);
1004
1005   g_assert (is_end (seq->end_node));
1006
1007   return seq->end_node;
1008 }
1009
1010 /**
1011  * g_sequence_get_begin_iter:
1012  * @seq: a #GSequence
1013  *
1014  * Returns the begin iterator for @seq.
1015  *
1016  * Return value: the begin iterator for @seq.
1017  *
1018  * Since: 2.14
1019  **/
1020 GSequenceIter *
1021 g_sequence_get_begin_iter (GSequence *seq)
1022 {
1023   g_return_val_if_fail (seq != NULL, NULL);
1024   return node_get_first (seq->end_node);
1025 }
1026
1027 static int
1028 clamp_position (GSequence *seq,
1029                 int        pos)
1030 {
1031   gint len = g_sequence_get_length (seq);
1032
1033   if (pos > len || pos < 0)
1034     pos = len;
1035
1036   return pos;
1037 }
1038
1039 /*
1040  * if pos > number of items or -1, will return end pointer
1041  */
1042 /**
1043  * g_sequence_get_iter_at_pos:
1044  * @seq: a #GSequence
1045  * @pos: a position in @seq, or -1 for the end.
1046  *
1047  * Returns the iterator at position @pos. If @pos is negative or larger
1048  * than the number of items in @seq, the end iterator is returned.
1049  *
1050  * Return value: The #GSequenceIter at position @pos
1051  *
1052  * Since: 2.14
1053  **/
1054 GSequenceIter *
1055 g_sequence_get_iter_at_pos (GSequence *seq,
1056                             gint       pos)
1057 {
1058   g_return_val_if_fail (seq != NULL, NULL);
1059
1060   pos = clamp_position (seq, pos);
1061
1062   return node_get_by_pos (seq->end_node, pos);
1063 }
1064
1065 /**
1066  * g_sequence_move:
1067  * @src: a #GSequenceIter pointing to the item to move
1068  * @dest: a #GSequenceIter pointing to the position to which
1069  *        the item is moved.
1070  *
1071  * Moves the item pointed to by @src to the position indicated by @dest.
1072  * After calling this function @dest will point to the position immediately
1073  * after @src.
1074  *
1075  * Since: 2.14
1076  **/
1077 void
1078 g_sequence_move (GSequenceIter *src,
1079                  GSequenceIter *dest)
1080 {
1081   g_return_if_fail (src != NULL);
1082   g_return_if_fail (dest != NULL);
1083   g_return_if_fail (!is_end (src));
1084
1085   if (src == dest)
1086     return;
1087
1088   node_unlink (src);
1089   node_insert_before (dest, src);
1090 }
1091
1092 /* GSequenceIter */
1093
1094 /**
1095  * g_sequence_iter_is_end:
1096  * @iter: a #GSequenceIter
1097  *
1098  * Returns whether @iter is the end iterator
1099  *
1100  * Return value: Whether @iter is the end iterator.
1101  *
1102  * Since: 2.14
1103  **/
1104 gboolean
1105 g_sequence_iter_is_end (GSequenceIter *iter)
1106 {
1107   g_return_val_if_fail (iter != NULL, FALSE);
1108
1109   return is_end (iter);
1110 }
1111
1112 /**
1113  * g_sequence_iter_is_begin:
1114  * @iter: a #GSequenceIter
1115  *
1116  * Returns whether @iter is the begin iterator
1117  *
1118  * Return value: whether @iter is the begin iterator
1119  *
1120  * Since: 2.14
1121  **/
1122 gboolean
1123 g_sequence_iter_is_begin (GSequenceIter *iter)
1124 {
1125   g_return_val_if_fail (iter != NULL, FALSE);
1126
1127   return (node_get_prev (iter) == iter);
1128 }
1129
1130 /**
1131  * g_sequence_iter_get_position:
1132  * @iter: a #GSequenceIter
1133  *
1134  * Returns the position of @iter
1135  *
1136  * Return value: the position of @iter
1137  *
1138  * Since: 2.14
1139  **/
1140 gint
1141 g_sequence_iter_get_position (GSequenceIter *iter)
1142 {
1143   g_return_val_if_fail (iter != NULL, -1);
1144
1145   return node_get_pos (iter);
1146 }
1147
1148 /**
1149  * g_sequence_iter_next:
1150  * @iter: a #GSequenceIter
1151  *
1152  * Returns an iterator pointing to the next position after @iter. If
1153  * @iter is the end iterator, the end iterator is returned.
1154  *
1155  * Return value: a #GSequenceIter pointing to the next position after @iter.
1156  *
1157  * Since: 2.14
1158  **/
1159 GSequenceIter *
1160 g_sequence_iter_next (GSequenceIter *iter)
1161 {
1162   g_return_val_if_fail (iter != NULL, NULL);
1163
1164   return node_get_next (iter);
1165 }
1166
1167 /**
1168  * g_sequence_iter_prev:
1169  * @iter: a #GSequenceIter
1170  *
1171  * Returns an iterator pointing to the previous position before @iter. If
1172  * @iter is the begin iterator, the begin iterator is returned.
1173  *
1174  * Return value: a #GSequenceIter pointing to the previous position before
1175  * @iter.
1176  *
1177  * Since: 2.14
1178  **/
1179 GSequenceIter *
1180 g_sequence_iter_prev (GSequenceIter *iter)
1181 {
1182   g_return_val_if_fail (iter != NULL, NULL);
1183
1184   return node_get_prev (iter);
1185 }
1186
1187 /**
1188  * g_sequence_iter_move:
1189  * @iter: a #GSequenceIter
1190  * @delta: A positive or negative number indicating how many positions away
1191  *    from @iter the returned #GSequenceIter will be.
1192  *
1193  * Returns the #GSequenceIter which is @delta positions away from @iter.
1194  * If @iter is closer than -@delta positions to the beginning of the sequence,
1195  * the begin iterator is returned. If @iter is closer than @delta positions
1196  * to the end of the sequence, the end iterator is returned.
1197  *
1198  * Return value: a #GSequenceIter which is @delta positions away from @iter.
1199  *
1200  * Since: 2.14
1201  **/
1202 GSequenceIter *
1203 g_sequence_iter_move (GSequenceIter *iter,
1204                       gint           delta)
1205 {
1206   gint new_pos;
1207
1208   g_return_val_if_fail (iter != NULL, NULL);
1209
1210   new_pos = node_get_pos (iter) + delta;
1211
1212   new_pos = clamp_position (get_sequence (iter), new_pos);
1213
1214   return node_get_by_pos (iter, new_pos);
1215 }
1216
1217 /**
1218  * g_sequence_swap:
1219  * @a: a #GSequenceIter
1220  * @b: a #GSequenceIter
1221  *
1222  * Swaps the items pointed to by @a and @b
1223  *
1224  * Since: 2.14
1225  **/
1226 void
1227 g_sequence_swap (GSequenceIter *a,
1228                  GSequenceIter *b)
1229 {
1230   GSequenceNode *leftmost, *rightmost, *rightmost_next;
1231   int a_pos, b_pos;
1232
1233   g_return_if_fail (!g_sequence_iter_is_end (a));
1234   g_return_if_fail (!g_sequence_iter_is_end (b));
1235
1236   if (a == b)
1237     return;
1238
1239   a_pos = g_sequence_iter_get_position (a);
1240   b_pos = g_sequence_iter_get_position (b);
1241
1242   if (a_pos > b_pos)
1243     {
1244       leftmost = b;
1245       rightmost = a;
1246     }
1247   else
1248     {
1249       leftmost = a;
1250       rightmost = b;
1251     }
1252
1253   rightmost_next = node_get_next (rightmost);
1254
1255   /* The situation is now like this:
1256    *
1257    *     ..., leftmost, ......., rightmost, rightmost_next, ...
1258    *
1259    */
1260   g_sequence_move (rightmost, leftmost);
1261   g_sequence_move (leftmost, rightmost_next);
1262 }
1263
1264 /*
1265  * Implementation of the splay tree.
1266  */
1267 static void
1268 node_update_fields (GSequenceNode *node)
1269 {
1270   g_assert (node != NULL);
1271
1272   node->n_nodes = 1;
1273
1274   if (node->left)
1275     node->n_nodes += node->left->n_nodes;
1276
1277   if (node->right)
1278     node->n_nodes += node->right->n_nodes;
1279 }
1280
1281 #define NODE_LEFT_CHILD(n)  (((n)->parent) && ((n)->parent->left) == (n))
1282 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1283
1284 static void
1285 node_rotate (GSequenceNode *node)
1286 {
1287   GSequenceNode *tmp, *old;
1288
1289   g_assert (node->parent);
1290   g_assert (node->parent != node);
1291
1292   if (NODE_LEFT_CHILD (node))
1293     {
1294       /* rotate right */
1295       tmp = node->right;
1296
1297       node->right = node->parent;
1298       node->parent = node->parent->parent;
1299       if (node->parent)
1300         {
1301           if (node->parent->left == node->right)
1302             node->parent->left = node;
1303           else
1304             node->parent->right = node;
1305         }
1306
1307       g_assert (node->right);
1308
1309       node->right->parent = node;
1310       node->right->left = tmp;
1311
1312       if (node->right->left)
1313         node->right->left->parent = node->right;
1314
1315       old = node->right;
1316     }
1317   else
1318     {
1319       /* rotate left */
1320       tmp = node->left;
1321
1322       node->left = node->parent;
1323       node->parent = node->parent->parent;
1324       if (node->parent)
1325         {
1326           if (node->parent->right == node->left)
1327             node->parent->right = node;
1328           else
1329             node->parent->left = node;
1330         }
1331
1332       g_assert (node->left);
1333
1334       node->left->parent = node;
1335       node->left->right = tmp;
1336
1337       if (node->left->right)
1338         node->left->right->parent = node->left;
1339
1340       old = node->left;
1341     }
1342
1343   node_update_fields (old);
1344   node_update_fields (node);
1345 }
1346
1347 static GSequenceNode *
1348 splay (GSequenceNode *node)
1349 {
1350   while (node->parent)
1351     {
1352       if (!node->parent->parent)
1353         {
1354           /* zig */
1355           node_rotate (node);
1356         }
1357       else if ((NODE_LEFT_CHILD (node) && NODE_LEFT_CHILD (node->parent)) ||
1358                (NODE_RIGHT_CHILD (node) && NODE_RIGHT_CHILD (node->parent)))
1359         {
1360           /* zig-zig */
1361           node_rotate (node->parent);
1362           node_rotate (node);
1363         }
1364       else
1365         {
1366           /* zig-zag */
1367           node_rotate (node);
1368           node_rotate (node);
1369         }
1370     }
1371
1372   return node;
1373 }
1374
1375 static GSequenceNode *
1376 node_new (gpointer data)
1377 {
1378   GSequenceNode *node = g_slice_new0 (GSequenceNode);
1379
1380   node->parent = NULL;
1381   node->parent = NULL;
1382   node->left = NULL;
1383   node->right = NULL;
1384
1385   node->data = data;
1386   node->n_nodes = 1;
1387
1388   return node;
1389 }
1390
1391 static GSequenceNode *
1392 find_min (GSequenceNode *node)
1393 {
1394   splay (node);
1395
1396   while (node->left)
1397     node = node->left;
1398
1399   return node;
1400 }
1401
1402 static GSequenceNode *
1403 find_max (GSequenceNode *node)
1404 {
1405   splay (node);
1406
1407   while (node->right)
1408     node = node->right;
1409
1410   return node;
1411 }
1412
1413 static GSequenceNode *
1414 node_get_first (GSequenceNode *node)
1415 {
1416   return splay (find_min (node));
1417 }
1418
1419 static GSequenceNode *
1420 node_get_last (GSequenceNode *node)
1421 {
1422   return splay (find_max (node));
1423 }
1424
1425 static gint
1426 get_n_nodes (GSequenceNode *node)
1427 {
1428   if (node)
1429     return node->n_nodes;
1430   else
1431     return 0;
1432 }
1433
1434 static GSequenceNode *
1435 node_get_by_pos (GSequenceNode *node,
1436                  gint           pos)
1437 {
1438   gint i;
1439
1440   g_assert (node != NULL);
1441
1442   splay (node);
1443
1444   while ((i = get_n_nodes (node->left)) != pos)
1445     {
1446       if (i < pos)
1447         {
1448           node = node->right;
1449           pos -= (i + 1);
1450         }
1451       else
1452         {
1453           node = node->left;
1454           g_assert (node->parent != NULL);
1455         }
1456     }
1457
1458   return splay (node);
1459 }
1460
1461 static GSequenceNode *
1462 node_get_prev (GSequenceNode *node)
1463 {
1464   splay (node);
1465
1466   if (node->left)
1467     {
1468       node = node->left;
1469       while (node->right)
1470         node = node->right;
1471     }
1472
1473   return splay (node);
1474 }
1475
1476 static GSequenceNode *
1477 node_get_next (GSequenceNode *node)
1478 {
1479   splay (node);
1480
1481   if (node->right)
1482     {
1483       node = node->right;
1484       while (node->left)
1485         node = node->left;
1486    }
1487
1488   return splay (node);
1489 }
1490
1491 static gint
1492 node_get_pos (GSequenceNode *node)
1493 {
1494   splay (node);
1495
1496   return get_n_nodes (node->left);
1497 }
1498
1499 /* Return closest node _strictly_ bigger than @needle. This node
1500  * always exists because the tree has an explicit end node).
1501  * This end node of @haystack must be passed in @end.
1502  */
1503 static GSequenceNode *
1504 node_find_closest (GSequenceNode            *haystack,
1505                    GSequenceNode            *needle,
1506                    GSequenceNode            *end,
1507                    GSequenceIterCompareFunc  iter_cmp,
1508                    gpointer                  cmp_data)
1509 {
1510   GSequenceNode *best;
1511   gint c;
1512
1513   g_assert (haystack);
1514
1515   haystack = splay (haystack);
1516
1517   do
1518     {
1519       best = haystack;
1520
1521       /* iter_cmp can't be passed the end node, since the function may
1522        * be user-supplied
1523        */
1524       if (haystack == end)
1525         c = 1;
1526       else
1527         c = iter_cmp (haystack, needle, cmp_data);
1528
1529       /* In the following we don't break even if c == 0. Instaed we go on
1530        * searching along the 'bigger' nodes, so that we find the last one
1531        * that is equal to the needle.
1532        */
1533       if (c > 0)
1534         haystack = haystack->left;
1535       else
1536         haystack = haystack->right;
1537     }
1538   while (haystack != NULL);
1539
1540   /* If the best node is smaller or equal to the data, then move one step
1541    * to the right to make sure the best one is strictly bigger than the data
1542    */
1543   if (best != end && c <= 0)
1544     best = node_get_next (best);
1545
1546   return best;
1547 }
1548
1549 static void
1550 node_free (GSequenceNode *node,
1551            GSequence     *seq)
1552 {
1553   GPtrArray *stack = g_ptr_array_new ();
1554
1555   splay (node);
1556
1557   g_ptr_array_add (stack, node);
1558
1559   while (stack->len > 0)
1560     {
1561       node = g_ptr_array_remove_index (stack, stack->len - 1);
1562
1563       if (node)
1564         {
1565           g_ptr_array_add (stack, node->right);
1566           g_ptr_array_add (stack, node->left);
1567
1568           if (seq && seq->data_destroy_notify && node != seq->end_node)
1569             seq->data_destroy_notify (node->data);
1570
1571           g_slice_free (GSequenceNode, node);
1572         }
1573     }
1574
1575   g_ptr_array_free (stack, TRUE);
1576 }
1577
1578 /* Splits into two trees. @node will be part of the right tree
1579  */
1580 static void
1581 node_cut (GSequenceNode *node)
1582 {
1583   splay (node);
1584
1585   g_assert (node->parent == NULL);
1586
1587   if (node->left)
1588     node->left->parent = NULL;
1589
1590   node->left = NULL;
1591   node_update_fields (node);
1592 }
1593
1594 static void
1595 node_insert_before (GSequenceNode *node,
1596                     GSequenceNode *new)
1597 {
1598   g_assert (node != NULL);
1599   g_assert (new != NULL);
1600
1601   splay (node);
1602
1603   new = splay (find_min (new));
1604   g_assert (new->left == NULL);
1605
1606   if (node->left)
1607     node->left->parent = new;
1608
1609   new->left = node->left;
1610   new->parent = node;
1611
1612   node->left = new;
1613
1614   node_update_fields (new);
1615   node_update_fields (node);
1616 }
1617
1618 static void
1619 node_insert_after (GSequenceNode *node,
1620                    GSequenceNode *new)
1621 {
1622   g_assert (node != NULL);
1623   g_assert (new != NULL);
1624
1625   splay (node);
1626
1627   new = splay (find_max (new));
1628   g_assert (new->right == NULL);
1629   g_assert (node->parent == NULL);
1630
1631   if (node->right)
1632     node->right->parent = new;
1633
1634   new->right = node->right;
1635   new->parent = node;
1636
1637   node->right = new;
1638
1639   node_update_fields (new);
1640   node_update_fields (node);
1641 }
1642
1643 static gint
1644 node_get_length (GSequenceNode    *node)
1645 {
1646   g_assert (node != NULL);
1647
1648   splay (node);
1649   return node->n_nodes;
1650 }
1651
1652 static void
1653 node_unlink (GSequenceNode *node)
1654 {
1655   GSequenceNode *right, *left;
1656
1657   splay (node);
1658
1659   left = node->left;
1660   right = node->right;
1661
1662   node->parent = node->left = node->right = NULL;
1663   node_update_fields (node);
1664
1665   if (right)
1666     {
1667       right->parent = NULL;
1668
1669       right = node_get_first (right);
1670       g_assert (right->left == NULL);
1671
1672       right->left = left;
1673       if (left)
1674         {
1675           left->parent = right;
1676           node_update_fields (right);
1677         }
1678     }
1679   else if (left)
1680     {
1681       left->parent = NULL;
1682     }
1683 }
1684
1685 static void
1686 node_insert_sorted (GSequenceNode            *node,
1687                     GSequenceNode            *new,
1688                     GSequenceNode            *end,
1689                     GSequenceIterCompareFunc  iter_cmp,
1690                     gpointer                  cmp_data)
1691 {
1692   GSequenceNode *closest;
1693
1694   closest = node_find_closest (node, new, end, iter_cmp, cmp_data);
1695
1696   node_unlink (new);
1697
1698   node_insert_before (closest, new);
1699 }
1700
1701 static gint
1702 node_calc_height (GSequenceNode *node)
1703 {
1704   gint left_height;
1705   gint right_height;
1706
1707   if (node)
1708     {
1709       left_height = 0;
1710       right_height = 0;
1711
1712       if (node->left)
1713         left_height = node_calc_height (node->left);
1714
1715       if (node->right)
1716         right_height = node_calc_height (node->right);
1717
1718       return MAX (left_height, right_height) + 1;
1719     }
1720
1721   return 0;
1722 }
1723
1724 /* Self-test function */
1725 static void
1726 check_node (GSequenceNode *node)
1727 {
1728   if (node)
1729     {
1730       g_assert (node->parent != node);
1731       g_assert (node->n_nodes ==
1732                 1 + get_n_nodes (node->left) + get_n_nodes (node->right));
1733       check_node (node->left);
1734       check_node (node->right);
1735     }
1736 }
1737
1738 void
1739 g_sequence_self_test_internal_to_glib_dont_use (GSequence *seq)
1740 {
1741   GSequenceNode *node = splay (seq->end_node);
1742
1743   check_node (node);
1744 }
1745
1746 #define __G_SEQUENCE_C__
1747 #include "galiasdef.c"