glib/gsequence.c

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