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