glib/gsequence.c

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