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