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