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