gsequence.c 49.6 KB
Newer Older
1 2 3 4 5 6 7
/* GLIB - Library of useful routines for C programming
 * Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
 * Soeren Sandmann (sandmann@daimi.au.dk)
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
8
 * version 2.1 of the License, or (at your option) any later version.
9 10 11 12 13 14 15
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * 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 20
 */

#include "config.h"

21
#include "gsequence.h"
22

23 24
#include "gmem.h"
#include "gtestutils.h"
25
#include "gslice.h"
26
/**
27
 * SECTION:sequence
28 29 30 31 32
 * @title: Sequences
 * @short_description: scalable lists
 *
 * The #GSequence data structure has the API of a list, but is
 * implemented internally with a balanced binary tree. This means that
33 34 35 36
 * it is possible to maintain a sorted list of n elements in time O(n log n).
 * The data contained in each element can be either integer values, by using
 * of the [Type Conversion Macros][glib-Type-Conversion-Macros], or simply
 * pointers to any type of data.
37
 *
38 39 40 41 42
 * A #GSequence is accessed through "iterators", represented by a
 * #GSequenceIter. An iterator represents a position between two
 * elements of the sequence. For example, the "begin" iterator
 * represents the gap immediately before the first element of the
 * sequence, and the "end" iterator represents the gap immediately
43 44 45 46 47 48 49 50 51 52 53 54
 * after the last element. In an empty sequence, the begin and end
 * iterators are the same.
 *
 * Some methods on #GSequence operate on ranges of items. For example
 * g_sequence_foreach_range() will call a user-specified function on
 * each element with the given range. The range is delimited by the
 * gaps represented by the passed-in iterators, so if you pass in the
 * begin and end iterators, the range in question is the entire
 * sequence.
 *
 * The function g_sequence_get() is used with an iterator to access the
 * element immediately following the gap that the iterator represents.
55
 * The iterator is said to "point" to that element.
56 57 58 59 60 61 62 63
 *
 * Iterators are stable across most operations on a #GSequence. For
 * example an iterator pointing to some element of a sequence will
 * continue to point to that element even after the sequence is sorted.
 * Even moving an element to another sequence using for example
 * g_sequence_move_range() will not invalidate the iterators pointing
 * to it. The only operation that will invalidate an iterator is when
 * the element it points to is removed from any sequence.
64 65 66 67 68 69
 *
 * To sort the data, either use g_sequence_insert_sorted() or
 * g_sequence_insert_sorted_iter() to add data to the #GSequence or, if
 * you want to add a large amount of data, it is more efficient to call
 * g_sequence_sort() or g_sequence_sort_iter() after doing unsorted
 * insertions.
70
 */
71 72 73 74 75 76

/**
 * GSequenceIter:
 *
 * The #GSequenceIter struct is an opaque data type representing an
 * iterator pointing into a #GSequence.
77
 */
78 79 80 81 82 83 84 85 86 87

/**
 * GSequenceIterCompareFunc:
 * @a: a #GSequenceIter
 * @b: a #GSequenceIter
 * @data: user data
 *
 * A #GSequenceIterCompareFunc is a function used to compare iterators.
 * It must return zero if the iterators compare equal, a negative value
 * if @a comes before @b, and a positive value if @b comes before @a.
88 89
 *
 * Returns: zero if the iterators are equal, a negative value if @a
90 91
 *     comes before @b, and a positive value if @b comes before @a.
 */
92

93 94
typedef struct _GSequenceNode GSequenceNode;

95 96 97 98
/**
 * GSequence:
 *
 * The #GSequence struct is an opaque data type representing a
99
 * [sequence][glib-Sequences] data type.
100
 */
101 102 103 104 105
struct _GSequence
{
  GSequenceNode *       end_node;
  GDestroyNotify        data_destroy_notify;
  gboolean              access_prohibited;
106 107

  /* The 'real_sequence' is used when temporary sequences are created
108
   * to hold nodes that are being rearranged. The 'real_sequence' of such
109 110 111 112 113
   * a temporary sequence points to the sequence that is actually being
   * manipulated. The only reason we need this is so that when the
   * sort/sort_changed/search_iter() functions call out to the application
   * g_sequence_iter_get_sequence() will return the correct sequence.
   */
114
  GSequence *           real_sequence;
115 116 117 118 119
};

struct _GSequenceNode
{
  gint                  n_nodes;
120
  GSequenceNode *       parent;
121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
  GSequenceNode *       left;
  GSequenceNode *       right;
  gpointer              data;   /* For the end node, this field points
                                 * to the sequence
                                 */
};

/*
 * Declaration of GSequenceNode methods
 */
static GSequenceNode *node_new           (gpointer                  data);
static GSequenceNode *node_get_first     (GSequenceNode            *node);
static GSequenceNode *node_get_last      (GSequenceNode            *node);
static GSequenceNode *node_get_prev      (GSequenceNode            *node);
static GSequenceNode *node_get_next      (GSequenceNode            *node);
static gint           node_get_pos       (GSequenceNode            *node);
static GSequenceNode *node_get_by_pos    (GSequenceNode            *node,
                                          gint                      pos);
139 140 141 142 143
static GSequenceNode *node_find          (GSequenceNode            *haystack,
                                          GSequenceNode            *needle,
                                          GSequenceNode            *end,
                                          GSequenceIterCompareFunc  cmp,
                                          gpointer                  user_data);
144 145 146 147
static GSequenceNode *node_find_closest  (GSequenceNode            *haystack,
                                          GSequenceNode            *needle,
                                          GSequenceNode            *end,
                                          GSequenceIterCompareFunc  cmp,
148
                                          gpointer                  user_data);
149 150 151 152 153 154 155
static gint           node_get_length    (GSequenceNode            *node);
static void           node_free          (GSequenceNode            *node,
                                          GSequence                *seq);
static void           node_cut           (GSequenceNode            *split);
static void           node_insert_before (GSequenceNode            *node,
                                          GSequenceNode            *new);
static void           node_unlink        (GSequenceNode            *node);
156
static void           node_join          (GSequenceNode            *left,
157
                                          GSequenceNode            *right);
158 159 160 161 162 163
static void           node_insert_sorted (GSequenceNode            *node,
                                          GSequenceNode            *new,
                                          GSequenceNode            *end,
                                          GSequenceIterCompareFunc  cmp_func,
                                          gpointer                  cmp_data);

164

165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183
/*
 * Various helper functions
 */
static void
check_seq_access (GSequence *seq)
{
  if (G_UNLIKELY (seq->access_prohibited))
    {
      g_warning ("Accessing a sequence while it is "
                 "being sorted or searched is not allowed");
    }
}

static GSequence *
get_sequence (GSequenceNode *node)
{
  return (GSequence *)node_get_last (node)->data;
}

184 185 186 187 188 189 190
static gboolean
seq_is_end (GSequence     *seq,
            GSequenceIter *iter)
{
  return seq->end_node == iter;
}

191 192 193
static gboolean
is_end (GSequenceIter *iter)
{
194
  GSequenceIter *parent = iter->parent;
195 196 197 198

  if (iter->right)
    return FALSE;

199
  if (!parent)
200 201
    return TRUE;

202 203 204 205
  while (parent->right == iter)
    {
      iter = parent;
      parent = iter->parent;
206

207 208 209
      if (!parent)
        return TRUE;
    }
210

211
  return FALSE;
212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
}

typedef struct
{
  GCompareDataFunc  cmp_func;
  gpointer          cmp_data;
  GSequenceNode    *end_node;
} SortInfo;

/* This function compares two iters using a normal compare
 * function and user_data passed in in a SortInfo struct
 */
static gint
iter_compare (GSequenceIter *node1,
              GSequenceIter *node2,
              gpointer       data)
{
  const SortInfo *info = data;
  gint retval;
231

232 233
  if (node1 == info->end_node)
    return 1;
234

235 236
  if (node2 == info->end_node)
    return -1;
237

238
  retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
239

240 241 242 243 244 245 246 247 248
  return retval;
}

/*
 * Public API
 */

/**
 * g_sequence_new:
249
 * @data_destroy: (nullable): a #GDestroyNotify function, or %NULL
250
 *
251 252 253
 * Creates a new GSequence. The @data_destroy function, if non-%NULL will
 * be called on all items when the sequence is destroyed and on items that
 * are removed from the sequence.
254
 *
255
 * Returns: (transfer full): a new #GSequence
256
 *
257 258 259 260 261 262 263
 * Since: 2.14
 **/
GSequence *
g_sequence_new (GDestroyNotify data_destroy)
{
  GSequence *seq = g_new (GSequence, 1);
  seq->data_destroy_notify = data_destroy;
264

265
  seq->end_node = node_new (seq);
266

267
  seq->access_prohibited = FALSE;
268 269

  seq->real_sequence = seq;
270

271 272 273 274 275 276
  return seq;
}

/**
 * g_sequence_free:
 * @seq: a #GSequence
277 278
 *
 * Frees the memory allocated for @seq. If @seq has a data destroy
279 280
 * function associated with it, that function is called on all items
 * in @seq.
281
 *
282
 * Since: 2.14
283
 */
284 285 286 287
void
g_sequence_free (GSequence *seq)
{
  g_return_if_fail (seq != NULL);
288

289
  check_seq_access (seq);
290

291
  node_free (seq->end_node, seq);
292

293 294 295 296 297 298 299 300 301
  g_free (seq);
}

/**
 * g_sequence_foreach_range:
 * @begin: a #GSequenceIter
 * @end: a #GSequenceIter
 * @func: a #GFunc
 * @user_data: user data passed to @func
302
 *
303
 * Calls @func for each item in the range (@begin, @end) passing
304 305
 * @user_data to the function. @func must not modify the sequence
 * itself.
306
 *
307
 * Since: 2.14
308
 */
309 310 311 312 313 314 315 316
void
g_sequence_foreach_range (GSequenceIter *begin,
                          GSequenceIter *end,
                          GFunc          func,
                          gpointer       user_data)
{
  GSequence *seq;
  GSequenceIter *iter;
317

318 319 320
  g_return_if_fail (func != NULL);
  g_return_if_fail (begin != NULL);
  g_return_if_fail (end != NULL);
321

322
  seq = get_sequence (begin);
323

324
  seq->access_prohibited = TRUE;
325

326 327 328 329
  iter = begin;
  while (iter != end)
    {
      GSequenceIter *next = node_get_next (iter);
330

331
      func (iter->data, user_data);
332

333 334
      iter = next;
    }
335

336 337 338 339 340 341 342 343
  seq->access_prohibited = FALSE;
}

/**
 * g_sequence_foreach:
 * @seq: a #GSequence
 * @func: the function to call for each item in @seq
 * @user_data: user data passed to @func
344
 *
345
 * Calls @func for each item in the sequence passing @user_data
346
 * to the function. @func must not modify the sequence itself.
347
 *
348
 * Since: 2.14
349
 */
350 351 352 353 354 355
void
g_sequence_foreach (GSequence *seq,
                    GFunc      func,
                    gpointer   user_data)
{
  GSequenceIter *begin, *end;
356

357
  check_seq_access (seq);
358

359 360
  begin = g_sequence_get_begin_iter (seq);
  end   = g_sequence_get_end_iter (seq);
361

362 363 364 365 366 367 368
  g_sequence_foreach_range (begin, end, func, user_data);
}

/**
 * g_sequence_range_get_midpoint:
 * @begin: a #GSequenceIter
 * @end: a #GSequenceIter
369
 *
370 371
 * Finds an iterator somewhere in the range (@begin, @end). This
 * iterator will be close to the middle of the range, but is not
372
 * guaranteed to be exactly in the middle.
373
 *
374 375
 * The @begin and @end iterators must both point to the same sequence
 * and @begin must come before or be equal to @end in the sequence.
376
 *
377
 * Returns: (transfer none): a #GSequenceIter pointing somewhere in the
378
 *    (@begin, @end) range
379
 *
380
 * Since: 2.14
381
 */
382 383 384 385 386
GSequenceIter *
g_sequence_range_get_midpoint (GSequenceIter *begin,
                               GSequenceIter *end)
{
  int begin_pos, end_pos, mid_pos;
387

388 389 390
  g_return_val_if_fail (begin != NULL, NULL);
  g_return_val_if_fail (end != NULL, NULL);
  g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
391

392 393
  begin_pos = node_get_pos (begin);
  end_pos = node_get_pos (end);
394

395
  g_return_val_if_fail (end_pos >= begin_pos, NULL);
396

397
  mid_pos = begin_pos + (end_pos - begin_pos) / 2;
398

399 400 401 402 403 404 405
  return node_get_by_pos (begin, mid_pos);
}

/**
 * g_sequence_iter_compare:
 * @a: a #GSequenceIter
 * @b: a #GSequenceIter
406
 *
407 408 409 410
 * Returns a negative number if @a comes before @b, 0 if they are equal,
 * and a positive number if @a comes after @b.
 *
 * The @a and @b iterators must point into the same sequence.
411
 *
412
 * Returns: a negative number if @a comes before @b, 0 if they are
413
 *     equal, and a positive number if @a comes after @b
414
 *
415
 * Since: 2.14
416
 */
417 418 419 420 421
gint
g_sequence_iter_compare (GSequenceIter *a,
                         GSequenceIter *b)
{
  gint a_pos, b_pos;
422
  GSequence *seq_a, *seq_b;
423

424 425
  g_return_val_if_fail (a != NULL, 0);
  g_return_val_if_fail (b != NULL, 0);
426

427 428 429 430 431 432
  seq_a = get_sequence (a);
  seq_b = get_sequence (b);
  g_return_val_if_fail (seq_a == seq_b, 0);

  check_seq_access (seq_a);
  check_seq_access (seq_b);
433

434 435
  a_pos = node_get_pos (a);
  b_pos = node_get_pos (b);
436

437 438 439 440 441 442 443 444 445 446
  if (a_pos == b_pos)
    return 0;
  else if (a_pos > b_pos)
    return 1;
  else
    return -1;
}

/**
 * g_sequence_append:
Matthias Clasen's avatar
Matthias Clasen committed
447
 * @seq: a #GSequence
448
 * @data: the data for the new item
449
 *
450
 * Adds a new item to the end of @seq.
451
 *
452
 * Returns: (transfer none): an iterator pointing to the new item
453
 *
454
 * Since: 2.14
455
 */
456 457 458 459 460
GSequenceIter *
g_sequence_append (GSequence *seq,
                   gpointer   data)
{
  GSequenceNode *node;
461

462
  g_return_val_if_fail (seq != NULL, NULL);
463

464
  check_seq_access (seq);
465

466 467
  node = node_new (data);
  node_insert_before (seq->end_node, node);
468

469 470 471 472 473 474 475
  return node;
}

/**
 * g_sequence_prepend:
 * @seq: a #GSequence
 * @data: the data for the new item
476
 *
477
 * Adds a new item to the front of @seq
478
 *
479
 * Returns: (transfer none): an iterator pointing to the new item
480
 *
481
 * Since: 2.14
482
 */
483 484 485 486 487
GSequenceIter *
g_sequence_prepend (GSequence *seq,
                    gpointer   data)
{
  GSequenceNode *node, *first;
488

489
  g_return_val_if_fail (seq != NULL, NULL);
490

491
  check_seq_access (seq);
492

493 494
  node = node_new (data);
  first = node_get_first (seq->end_node);
495

496
  node_insert_before (first, node);
497

498 499 500 501 502 503 504
  return node;
}

/**
 * g_sequence_insert_before:
 * @iter: a #GSequenceIter
 * @data: the data for the new item
505
 *
506
 * Inserts a new item just before the item pointed to by @iter.
507
 *
508
 * Returns: (transfer none): an iterator pointing to the new item
509
 *
510
 * Since: 2.14
511
 */
512 513 514 515
GSequenceIter *
g_sequence_insert_before (GSequenceIter *iter,
                          gpointer       data)
{
516
  GSequence *seq;
517
  GSequenceNode *node;
518

519
  g_return_val_if_fail (iter != NULL, NULL);
520

521 522
  seq = get_sequence (iter);
  check_seq_access (seq);
523

524
  node = node_new (data);
525

526
  node_insert_before (iter, node);
527

528 529 530 531 532 533
  return node;
}

/**
 * g_sequence_remove:
 * @iter: a #GSequenceIter
534
 *
535 536 537
 * Removes the item pointed to by @iter. It is an error to pass the
 * end iterator to this function.
 *
538
 * If the sequence has a data destroy function associated with it, this
539
 * function is called on the data for the removed item.
540
 *
541
 * Since: 2.14
542
 */
543 544 545 546
void
g_sequence_remove (GSequenceIter *iter)
{
  GSequence *seq;
547

548
  g_return_if_fail (iter != NULL);
549 550

  seq = get_sequence (iter);
551 552
  g_return_if_fail (!seq_is_end (seq, iter));

553
  check_seq_access (seq);
554

555 556 557 558 559 560 561 562
  node_unlink (iter);
  node_free (iter, seq);
}

/**
 * g_sequence_remove_range:
 * @begin: a #GSequenceIter
 * @end: a #GSequenceIter
563
 *
564 565 566 567
 * Removes all items in the (@begin, @end) range.
 *
 * If the sequence has a data destroy function associated with it, this
 * function is called on the data for the removed items.
568
 *
569
 * Since: 2.14
570
 */
571 572 573 574
void
g_sequence_remove_range (GSequenceIter *begin,
                         GSequenceIter *end)
{
575
  GSequence *seq_begin, *seq_end;
576

577 578 579 580
  seq_begin = get_sequence (begin);
  seq_end = get_sequence (end);
  g_return_if_fail (seq_begin == seq_end);
  /* check_seq_access() calls are done by g_sequence_move_range() */
581

582 583 584 585 586 587 588 589
  g_sequence_move_range (NULL, begin, end);
}

/**
 * g_sequence_move_range:
 * @dest: a #GSequenceIter
 * @begin: a #GSequenceIter
 * @end: a #GSequenceIter
590
 *
591
 * Inserts the (@begin, @end) range at the destination pointed to by @dest.
592 593 594
 * The @begin and @end iters must point into the same sequence. It is
 * allowed for @dest to point to a different sequence than the one pointed
 * into by @begin and @end.
595
 *
596 597
 * If @dest is %NULL, the range indicated by @begin and @end is
 * removed from the sequence. If @dest points to a place within
598
 * the (@begin, @end) range, the range does not move.
599
 *
600
 * Since: 2.14
601
 */
602 603 604 605 606
void
g_sequence_move_range (GSequenceIter *dest,
                       GSequenceIter *begin,
                       GSequenceIter *end)
{
607
  GSequence *src_seq, *end_seq, *dest_seq;
608
  GSequenceNode *first;
609

610 611
  g_return_if_fail (begin != NULL);
  g_return_if_fail (end != NULL);
612

613
  src_seq = get_sequence (begin);
614 615 616 617 618 619 620 621 622 623
  check_seq_access (src_seq);

  end_seq = get_sequence (end);
  check_seq_access (end_seq);

  if (dest)
    {
      dest_seq = get_sequence (dest);
      check_seq_access (dest_seq);
    }
624

625
  g_return_if_fail (src_seq == end_seq);
626

627 628 629
  /* Dest points to begin or end? */
  if (dest == begin || dest == end)
    return;
630

631 632 633
  /* begin comes after end? */
  if (g_sequence_iter_compare (begin, end) >= 0)
    return;
634

635
  /* dest points somewhere in the (begin, end) range? */
636
  if (dest && dest_seq == src_seq &&
637 638 639 640 641
      g_sequence_iter_compare (dest, begin) > 0 &&
      g_sequence_iter_compare (dest, end) < 0)
    {
      return;
    }
642

643
  first = node_get_first (begin);
644

645
  node_cut (begin);
646

647
  node_cut (end);
648

649
  if (first != begin)
650
    node_join (first, end);
651

652
  if (dest)
653 654
    {
      first = node_get_first (dest);
655

656
      node_cut (dest);
657

658
      node_join (begin, dest);
659

660
      if (dest != first)
661
        node_join (first, begin);
662
    }
663
  else
664 665 666
    {
      node_free (begin, src_seq);
    }
667 668 669 670 671
}

/**
 * g_sequence_sort:
 * @seq: a #GSequence
Matthias Clasen's avatar
Matthias Clasen committed
672
 * @cmp_func: the function used to sort the sequence
673
 * @cmp_data: user data passed to @cmp_func
674
 *
675
 * Sorts @seq using @cmp_func.
676
 *
Matthias Clasen's avatar
Matthias Clasen committed
677 678 679 680 681
 * @cmp_func is passed two items of @seq and should
 * return 0 if they are equal, a negative value if the
 * first comes before the second, and a positive value
 * if the second comes before the first.
 *
682
 * Since: 2.14
683
 */
684 685 686 687 688
void
g_sequence_sort (GSequence        *seq,
                 GCompareDataFunc  cmp_func,
                 gpointer          cmp_data)
{
689 690 691 692 693
  SortInfo info;

  info.cmp_func = cmp_func;
  info.cmp_data = cmp_data;
  info.end_node = seq->end_node;
694

695
  check_seq_access (seq);
696

697 698 699 700 701 702 703
  g_sequence_sort_iter (seq, iter_compare, &info);
}

/**
 * g_sequence_insert_sorted:
 * @seq: a #GSequence
 * @data: the data to insert
Matthias Clasen's avatar
Matthias Clasen committed
704
 * @cmp_func: the function used to compare items in the sequence
705 706
 * @cmp_data: user data passed to @cmp_func.
 *
707
 * Inserts @data into @seq using @cmp_func to determine the new
Matthias Clasen's avatar
Matthias Clasen committed
708 709 710
 * position. The sequence must already be sorted according to @cmp_func;
 * otherwise the new position of @data is undefined.
 *
711
 * @cmp_func is called with two items of the @seq, and @cmp_data.
Matthias Clasen's avatar
Matthias Clasen committed
712 713
 * It should return 0 if the items are equal, a negative value
 * if the first item comes before the second, and a positive value
714
 * if the second item comes before the first.
715
 *
716 717 718 719
 * Note that when adding a large amount of data to a #GSequence,
 * it is more efficient to do unsorted insertions and then call
 * g_sequence_sort() or g_sequence_sort_iter().
 *
720
 * Returns: (transfer none): a #GSequenceIter pointing to the new item.
721
 *
722
 * Since: 2.14
723
 */
724 725 726 727 728 729
GSequenceIter *
g_sequence_insert_sorted (GSequence        *seq,
                          gpointer          data,
                          GCompareDataFunc  cmp_func,
                          gpointer          cmp_data)
{
730 731
  SortInfo info;

732 733
  g_return_val_if_fail (seq != NULL, NULL);
  g_return_val_if_fail (cmp_func != NULL, NULL);
734

735 736
  info.cmp_func = cmp_func;
  info.cmp_data = cmp_data;
737 738
  info.end_node = seq->end_node;
  check_seq_access (seq);
739

740 741 742 743 744 745
  return g_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
}

/**
 * g_sequence_sort_changed:
 * @iter: A #GSequenceIter
Matthias Clasen's avatar
Matthias Clasen committed
746
 * @cmp_func: the function used to compare items in the sequence
747 748
 * @cmp_data: user data passed to @cmp_func.
 *
749 750
 * Moves the data pointed to by @iter to a new position as indicated by
 * @cmp_func. This
751 752 753
 * function should be called for items in a sequence already sorted according
 * to @cmp_func whenever some aspect of an item changes so that @cmp_func
 * may return different values for that item.
754
 *
755
 * @cmp_func is called with two items of the @seq, and @cmp_data.
Matthias Clasen's avatar
Matthias Clasen committed
756 757 758 759
 * It should return 0 if the items are equal, a negative value if
 * the first item comes before the second, and a positive value if
 * the second item comes before the first.
 *
760
 * Since: 2.14
761
 */
762 763 764 765 766
void
g_sequence_sort_changed (GSequenceIter    *iter,
                         GCompareDataFunc  cmp_func,
                         gpointer          cmp_data)
{
767
  GSequence *seq;
768 769
  SortInfo info;

770
  g_return_if_fail (iter != NULL);
771

772 773
  seq = get_sequence (iter);
  /* check_seq_access() call is done by g_sequence_sort_changed_iter() */
774
  g_return_if_fail (!seq_is_end (seq, iter));
775

776 777
  info.cmp_func = cmp_func;
  info.cmp_data = cmp_data;
778
  info.end_node = seq->end_node;
779

780 781 782 783 784 785 786
  g_sequence_sort_changed_iter (iter, iter_compare, &info);
}

/**
 * g_sequence_search:
 * @seq: a #GSequence
 * @data: data for the new item
Matthias Clasen's avatar
Matthias Clasen committed
787
 * @cmp_func: the function used to compare items in the sequence
788
 * @cmp_data: user data passed to @cmp_func
789
 *
790 791
 * Returns an iterator pointing to the position where @data would
 * be inserted according to @cmp_func and @cmp_data.
792
 *
793
 * @cmp_func is called with two items of the @seq, and @cmp_data.
Matthias Clasen's avatar
Matthias Clasen committed
794 795 796 797
 * It should return 0 if the items are equal, a negative value if
 * the first item comes before the second, and a positive value if
 * the second item comes before the first.
 *
798 799 800
 * If you are simply searching for an existing element of the sequence,
 * consider using g_sequence_lookup().
 *
801
 * This function will fail if the data contained in the sequence is
802
 * unsorted.
803
 *
804
 * Returns: (transfer none): an #GSequenceIter pointing to the position where @data
805
 *     would have been inserted according to @cmp_func and @cmp_data
806
 *
807
 * Since: 2.14
808
 */
809 810 811 812 813 814
GSequenceIter *
g_sequence_search (GSequence        *seq,
                   gpointer          data,
                   GCompareDataFunc  cmp_func,
                   gpointer          cmp_data)
{
815 816
  SortInfo info;

817
  g_return_val_if_fail (seq != NULL, NULL);
818

819 820
  info.cmp_func = cmp_func;
  info.cmp_data = cmp_data;
821 822
  info.end_node = seq->end_node;
  check_seq_access (seq);
823

824 825 826
  return g_sequence_search_iter (seq, data, iter_compare, &info);
}

827 828 829 830
/**
 * g_sequence_lookup:
 * @seq: a #GSequence
 * @data: data to lookup
Matthias Clasen's avatar
Matthias Clasen committed
831
 * @cmp_func: the function used to compare items in the sequence
832
 * @cmp_data: user data passed to @cmp_func
833 834
 *
 * Returns an iterator pointing to the position of the first item found
Matthias Clasen's avatar
Matthias Clasen committed
835 836 837 838 839
 * equal to @data according to @cmp_func and @cmp_data. If more than one
 * item is equal, it is not guaranteed that it is the first which is
 * returned. In that case, you can use g_sequence_iter_next() and
 * g_sequence_iter_prev() to get others.
 *
840
 * @cmp_func is called with two items of the @seq, and @cmp_data.
Matthias Clasen's avatar
Matthias Clasen committed
841 842 843
 * It should return 0 if the items are equal, a negative value if
 * the first item comes before the second, and a positive value if
 * the second item comes before the first.
844
 *
845
 * This function will fail if the data contained in the sequence is
846
 * unsorted.
847
 *
848
 * Returns: (transfer none) (nullable): an #GSequenceIter pointing to the position of the
849
 *     first item found equal to @data according to @cmp_func and
850
 *     @cmp_data, or %NULL if no such item exists
851
 *
852
 * Since: 2.28
853
 */
854
GSequenceIter *
855 856 857 858
g_sequence_lookup (GSequence        *seq,
                   gpointer          data,
                   GCompareDataFunc  cmp_func,
                   gpointer          cmp_data)
859 860 861 862 863 864 865 866 867 868 869 870 871
{
  SortInfo info;

  g_return_val_if_fail (seq != NULL, NULL);

  info.cmp_func = cmp_func;
  info.cmp_data = cmp_data;
  info.end_node = seq->end_node;
  check_seq_access (seq);

  return g_sequence_lookup_iter (seq, data, iter_compare, &info);
}

872 873 874
/**
 * g_sequence_sort_iter:
 * @seq: a #GSequence
Matthias Clasen's avatar
Matthias Clasen committed
875
 * @cmp_func: the function used to compare iterators in the sequence
876 877 878
 * @cmp_data: user data passed to @cmp_func
 *
 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
879
 * of a #GCompareDataFunc as the compare function
880
 *
Matthias Clasen's avatar
Matthias Clasen committed
881 882 883 884 885
 * @cmp_func is called with two iterators pointing into @seq. It should
 * return 0 if the iterators are equal, a negative value if the first
 * iterator comes before the second, and a positive value if the second
 * iterator comes before the first.
 *
886
 * Since: 2.14
887
 */
888 889 890 891 892 893 894
void
g_sequence_sort_iter (GSequence                *seq,
                      GSequenceIterCompareFunc  cmp_func,
                      gpointer                  cmp_data)
{
  GSequence *tmp;
  GSequenceNode *begin, *end;
895

896 897
  g_return_if_fail (seq != NULL);
  g_return_if_fail (cmp_func != NULL);
898

899
  check_seq_access (seq);
900

901 902
  begin = g_sequence_get_begin_iter (seq);
  end   = g_sequence_get_end_iter (seq);
903

904
  tmp = g_sequence_new (NULL);
905
  tmp->real_sequence = seq;
906

907
  g_sequence_move_range (g_sequence_get_begin_iter (tmp), begin, end);
908

909 910
  seq->access_prohibited = TRUE;
  tmp->access_prohibited = TRUE;
911

912
  while (!g_sequence_is_empty (tmp))
913 914
    {
      GSequenceNode *node = g_sequence_get_begin_iter (tmp);
915

916
      node_insert_sorted (seq->end_node, node, seq->end_node,
917
                          cmp_func, cmp_data);
918
    }
919

920 921
  tmp->access_prohibited = FALSE;
  seq->access_prohibited = FALSE;
922

923 924 925 926 927 928
  g_sequence_free (tmp);
}

/**
 * g_sequence_sort_changed_iter:
 * @iter: a #GSequenceIter
Matthias Clasen's avatar
Matthias Clasen committed
929
 * @iter_cmp: the function used to compare iterators in the sequence
930 931 932 933 934
 * @cmp_data: user data passed to @cmp_func
 *
 * Like g_sequence_sort_changed(), but uses
 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
 * the compare function.
935
 *
936 937
 * @iter_cmp is called with two iterators pointing into the #GSequence that
 * @iter points into. It should
Matthias Clasen's avatar
Matthias Clasen committed
938 939 940 941
 * return 0 if the iterators are equal, a negative value if the first
 * iterator comes before the second, and a positive value if the second
 * iterator comes before the first.
 *
942
 * Since: 2.14
943
 */
944 945 946 947 948 949 950 951 952 953
void
g_sequence_sort_changed_iter (GSequenceIter            *iter,
                              GSequenceIterCompareFunc  iter_cmp,
                              gpointer                  cmp_data)
{
  GSequence *seq, *tmp_seq;
  GSequenceIter *next, *prev;

  g_return_if_fail (iter != NULL);
  g_return_if_fail (iter_cmp != NULL);
954 955

  seq = get_sequence (iter);
956 957
  g_return_if_fail (!seq_is_end (seq, iter));

958
  check_seq_access (seq);
959

960 961 962 963
  /* If one of the neighbours is equal to iter, then
   * don't move it. This ensures that sort_changed() is
   * a stable operation.
   */
964

965 966
  next = node_get_next (iter);
  prev = node_get_prev (iter);
967

968 969
  if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
    return;
970

971 972
  if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
    return;
973

974 975 976
  seq->access_prohibited = TRUE;

  tmp_seq = g_sequence_new (NULL);
977
  tmp_seq->real_sequence = seq;
978

979 980
  node_unlink (iter);
  node_insert_before (tmp_seq->end_node, iter);
981

982 983 984 985
  node_insert_sorted (seq->end_node, iter, seq->end_node,
                      iter_cmp, cmp_data);

  g_sequence_free (tmp_seq);
986

987 988 989 990 991 992 993
  seq->access_prohibited = FALSE;
}

/**
 * g_sequence_insert_sorted_iter:
 * @seq: a #GSequence
 * @data: data for the new item
Matthias Clasen's avatar
Matthias Clasen committed
994
 * @iter_cmp: the function used to compare iterators in the sequence
995
 * @cmp_data: user data passed to @iter_cmp
996
 *
997 998 999
 * Like g_sequence_insert_sorted(), but uses
 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
 * the compare function.
1000
 *
Matthias Clasen's avatar
Matthias Clasen committed
1001 1002 1003 1004 1005
 * @iter_cmp is called with two iterators pointing into @seq.
 * It should return 0 if the iterators are equal, a negative
 * value if the first iterator comes before the second, and a
 * positive value if the second iterator comes before the first.
 *
1006 1007 1008 1009
 * Note that when adding a large amount of data to a #GSequence,
 * it is more efficient to do unsorted insertions and then call
 * g_sequence_sort() or g_sequence_sort_iter().
 *
1010
 * Returns: (transfer none): a #GSequenceIter pointing to the new item
1011
 *
1012
 * Since: 2.14
1013
 */
1014 1015
GSequenceIter *
g_sequence_insert_sorted_iter (GSequence                *seq,
1016 1017 1018
                               gpointer                  data,
                               GSequenceIterCompareFunc  iter_cmp,
                               gpointer                  cmp_data)
1019 1020 1021 1022 1023 1024
{
  GSequenceNode *new_node;
  GSequence *tmp_seq;

  g_return_val_if_fail (seq != NULL, NULL);
  g_return_val_if_fail (iter_cmp != NULL, NULL);
1025

1026 1027 1028
  check_seq_access (seq);

  seq->access_prohibited = TRUE;
1029

1030 1031
  /* Create a new temporary sequence and put the new node into
   * that. The reason for this is that the user compare function
1032
   * will be called with the new node, and if it dereferences,
1033 1034 1035 1036
   * "is_end" will be called on it. But that will crash if the
   * node is not actually in a sequence.
   *
   * node_insert_sorted() makes sure the node is unlinked before
1037
   * it is inserted.
1038 1039 1040 1041 1042
   *
   * The reason we need the "iter" versions at all is that that
   * is the only kind of compare functions GtkTreeView can use.
   */
  tmp_seq = g_sequence_new (NULL);
1043
  tmp_seq->real_sequence = seq;
1044

1045
  new_node = g_sequence_append (tmp_seq, data);
1046

1047 1048
  node_insert_sorted (seq->end_node, new_node,
                      seq->end_node, iter_cmp, cmp_data);
1049

1050 1051 1052
  g_sequence_free (tmp_seq);

  seq->access_prohibited = FALSE;
1053

1054 1055 1056 1057 1058 1059 1060
  return new_node;
}

/**
 * g_sequence_search_iter:
 * @seq: a #GSequence
 * @data: data for the new item
Matthias Clasen's avatar
Matthias Clasen committed
1061
 * @iter_cmp: the function used to compare iterators in the sequence
1062 1063
 * @cmp_data: user data passed to @iter_cmp
 *
Matthias Clasen's avatar
Matthias Clasen committed
1064 1065 1066 1067 1068 1069 1070
 * Like g_sequence_search(), but uses a #GSequenceIterCompareFunc
 * instead of a #GCompareDataFunc as the compare function.
 *
 * @iter_cmp is called with two iterators pointing into @seq.
 * It should return 0 if the iterators are equal, a negative value
 * if the first iterator comes before the second, and a positive
 * value if the second iterator comes before the first.
1071
 *
1072 1073 1074
 * If you are simply searching for an existing element of the sequence,
 * consider using g_sequence_lookup_iter().
 *
1075
 * This function will fail if the data contained in the sequence is
1076
 * unsorted.
1077
 *
1078
 * Returns: (transfer none): a #GSequenceIter pointing to the position in @seq
Matthias Clasen's avatar
Matthias Clasen committed
1079
 *     where @data would have been inserted according to @iter_cmp
1080
 *     and @cmp_data
1081
 *
1082
 * Since: 2.14
1083
 */
1084 1085 1086 1087 1088 1089 1090 1091 1092
GSequenceIter *
g_sequence_search_iter (GSequence                *seq,
                        gpointer                  data,
                        GSequenceIterCompareFunc  iter_cmp,
                        gpointer                  cmp_data)
{
  GSequenceNode *node;
  GSequenceNode *dummy;
  GSequence *tmp_seq;
1093

1094
  g_return_val_if_fail (seq != NULL, NULL);
1095

1096
  check_seq_access (seq);
1097

1098 1099 1100
  seq->access_prohibited = TRUE;

  tmp_seq = g_sequence_new (NULL);
1101
  tmp_seq->real_sequence = seq;
1102

1103
  dummy = g_sequence_append (tmp_seq, data);
1104

1105
  node = node_find_closest (seq->end_node, dummy,
1106
                            seq->end_node, iter_cmp, cmp_data);
1107 1108

  g_sequence_free (tmp_seq);
1109

1110
  seq->access_prohibited = FALSE;
1111

1112 1113 1114
  return node;
}

1115 1116 1117 1118
/**
 * g_sequence_lookup_iter:
 * @seq: a #GSequence
 * @data: data to lookup
Matthias Clasen's avatar
Matthias Clasen committed
1119
 * @iter_cmp: the function used to compare iterators in the sequence
1120 1121
 * @cmp_data: user data passed to @iter_cmp
 *
Matthias Clasen's avatar
Matthias Clasen committed
1122 1123 1124 1125 1126 1127 1128
 * Like g_sequence_lookup(), but uses a #GSequenceIterCompareFunc
 * instead of a #GCompareDataFunc as the compare function.
 *
 * @iter_cmp is called with two iterators pointing into @seq.
 * It should return 0 if the iterators are equal, a negative value
 * if the first iterator comes before the second, and a positive
 * value if the second iterator comes before the first.
1129
 *
1130
 * This function will fail if the data contained in the sequence is
1131
 * unsorted.
1132
 *
1133
 * Returns: (transfer none) (nullable): an #GSequenceIter pointing to the position of
1134
 *     the first item found equal to @data according to @iter_cmp
1135
 *     and @cmp_data, or %NULL if no such item exists
1136
 *
1137
 * Since: 2.28
1138
 */
1139
GSequenceIter *
1140 1141 1142 1143
g_sequence_lookup_iter (GSequence                *seq,
                        gpointer                  data,
                        GSequenceIterCompareFunc  iter_cmp,
                        gpointer                  cmp_data)
1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169
{
  GSequenceNode *node;
  GSequenceNode *dummy;
  GSequence *tmp_seq;

  g_return_val_if_fail (seq != NULL, NULL);

  check_seq_access (seq);

  seq->access_prohibited = TRUE;

  tmp_seq = g_sequence_new (NULL);
  tmp_seq->real_sequence = seq;

  dummy = g_sequence_append (tmp_seq, data);

  node = node_find (seq->end_node, dummy,
                    seq->end_node, iter_cmp, cmp_data);

  g_sequence_free (tmp_seq);

  seq->access_prohibited = FALSE;

  return node;
}

1170 1171 1172
/**
 * g_sequence_iter_get_sequence:
 * @iter: a #GSequenceIter
1173
 *
1174
 * Returns the #GSequence that @iter points into.
1175
 *
1176
 * Returns: (transfer none): the #GSequence that @iter points into
1177
 *
1178
 * Since: 2.14
1179
 */
1180 1181 1182
GSequence *
g_sequence_iter_get_sequence (GSequenceIter *iter)
{
1183
  GSequence *seq;
1184

1185 1186 1187 1188 1189 1190 1191 1192
  g_return_val_if_fail (iter != NULL, NULL);

  seq = get_sequence (iter);

  /* For temporary sequences, this points to the sequence that
   * is actually being manipulated
   */
  return seq->real_sequence;
1193 1194 1195 1196 1197
}

/**
 * g_sequence_get:
 * @iter: a #GSequenceIter
1198
 *
1199
 * Returns the data that @iter points to.
1200
 *
1201
 * Returns: (transfer none): the data that @iter points to
1202
 *
1203
 * Since: 2.14
1204
 */
1205 1206 1207 1208 1209
gpointer
g_sequence_get (GSequenceIter *iter)
{
  g_return_val_if_fail (iter != NULL, NULL);
  g_return_val_if_fail (!is_end (iter), NULL);
1210

1211 1212 1213 1214 1215 1216 1217
  return iter->data;
}

/**
 * g_sequence_set:
 * @iter: a #GSequenceIter
 * @data: new data for the item
1218
 *
1219 1220 1221
 * Changes the data for the item pointed to by @iter to be @data. If
 * the sequence has a data destroy function associated with it, that
 * function is called on the existing data that @iter pointed to.
1222
 *
1223
 * Since: 2.14
1224
 */
1225 1226 1227 1228 1229
void
g_sequence_set (GSequenceIter *iter,
                gpointer       data)
{
  GSequence *seq;
1230

1231
  g_return_if_fail (iter != NULL);
1232

1233
  seq = get_sequence (iter);
1234
  g_return_if_fail (!seq_is_end (seq, iter));
1235

1236 1237 1238 1239 1240 1241 1242 1243
  /* If @data is identical to iter->data, it is destroyed
   * here. This will work right in case of ref-counted objects. Also
   * it is similar to what ghashtables do.
   *
   * For non-refcounted data it's a little less convenient, but
   * code relying on self-setting not destroying would be
   * pretty dubious anyway ...
   */
1244

1245 1246
  if (seq->data_destroy_notify)
    seq->data_destroy_notify (iter->data);
1247

1248 1249 1250 1251 1252 1253
  iter->data = data;
}

/**
 * g_sequence_get_length:
 * @seq: a #GSequence
1254
 *
1255 1256 1257
 * Returns the length of @seq. Note that this method is O(h) where `h' is the
 * height of the tree. It is thus more efficient to use g_sequence_is_empty()
 * when comparing the length to zero.
1258
 *
1259
 * Returns: the length of @seq
1260
 *
1261
 * Since: 2.14
1262
 */
1263 1264 1265 1266 1267