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