glib/gsequence.c

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