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