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