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