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