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