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