glib/gsequence.c

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