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