glib/gsequence.c

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