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)
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
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.
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/>.
21 #include "gsequence.h"
24 #include "gtestutils.h"
29 * @short_description: scalable lists
31 * The #GSequence data structure has the API of a list, but is
32 * implemented internally with a balanced binary tree. This means that
33 * it is possible to maintain a sorted list of n elements in time O(n
34 * log n). The data contained in each element can be either integer
35 * values, by using of the <link
36 * linkend="glib-Type-Conversion-Macros">Type Conversion Macros</link>,
37 * or simply pointers to any type of data.
39 * A #GSequence is accessed through <firstterm>iterators</firstterm>,
40 * represented by a #GSequenceIter. An iterator represents a position
41 * between two elements of the sequence. For example, the
42 * <firstterm>begin</firstterm> iterator represents the gap immediately
43 * before the first element of the sequence, and the
44 * <firstterm>end</firstterm> iterator represents the gap immediately
45 * after the last element. In an empty sequence, the begin and end
46 * iterators are the same.
48 * Some methods on #GSequence operate on ranges of items. For example
49 * g_sequence_foreach_range() will call a user-specified function on
50 * each element with the given range. The range is delimited by the
51 * gaps represented by the passed-in iterators, so if you pass in the
52 * begin and end iterators, the range in question is the entire
55 * The function g_sequence_get() is used with an iterator to access the
56 * element immediately following the gap that the iterator represents.
57 * The iterator is said to <firstterm>point</firstterm> to that element.
59 * Iterators are stable across most operations on a #GSequence. For
60 * example an iterator pointing to some element of a sequence will
61 * continue to point to that element even after the sequence is sorted.
62 * Even moving an element to another sequence using for example
63 * g_sequence_move_range() will not invalidate the iterators pointing
64 * to it. The only operation that will invalidate an iterator is when
65 * the element it points to is removed from any sequence.
71 * The #GSequenceIter struct is an opaque data type representing an
72 * iterator pointing into a #GSequence.
76 * GSequenceIterCompareFunc:
77 * @a: a #GSequenceIter
78 * @b: a #GSequenceIter
81 * A #GSequenceIterCompareFunc is a function used to compare iterators.
82 * It must return zero if the iterators compare equal, a negative value
83 * if @a comes before @b, and a positive value if @b comes before @a.
85 * Returns: zero if the iterators are equal, a negative value if @a
86 * comes before @b, and a positive value if @b comes before @a.
89 typedef struct _GSequenceNode GSequenceNode;
94 * The #GSequence struct is an opaque data type representing a
95 * <link linkend="glib-Sequences">Sequence</link> data type.
99 GSequenceNode * end_node;
100 GDestroyNotify data_destroy_notify;
101 gboolean access_prohibited;
103 /* The 'real_sequence' is used when temporary sequences are created
104 * to hold nodes that are being rearranged. The 'real_sequence' of such
105 * a temporary sequence points to the sequence that is actually being
106 * manipulated. The only reason we need this is so that when the
107 * sort/sort_changed/search_iter() functions call out to the application
108 * g_sequence_iter_get_sequence() will return the correct sequence.
110 GSequence * real_sequence;
113 struct _GSequenceNode
116 GSequenceNode * parent;
117 GSequenceNode * left;
118 GSequenceNode * right;
119 gpointer data; /* For the end node, this field points
125 * Declaration of GSequenceNode methods
127 static GSequenceNode *node_new (gpointer data);
128 static GSequenceNode *node_get_first (GSequenceNode *node);
129 static GSequenceNode *node_get_last (GSequenceNode *node);
130 static GSequenceNode *node_get_prev (GSequenceNode *node);
131 static GSequenceNode *node_get_next (GSequenceNode *node);
132 static gint node_get_pos (GSequenceNode *node);
133 static GSequenceNode *node_get_by_pos (GSequenceNode *node,
135 static GSequenceNode *node_find (GSequenceNode *haystack,
136 GSequenceNode *needle,
138 GSequenceIterCompareFunc cmp,
140 static GSequenceNode *node_find_closest (GSequenceNode *haystack,
141 GSequenceNode *needle,
143 GSequenceIterCompareFunc cmp,
145 static gint node_get_length (GSequenceNode *node);
146 static void node_free (GSequenceNode *node,
148 static void node_cut (GSequenceNode *split);
149 static void node_insert_before (GSequenceNode *node,
151 static void node_unlink (GSequenceNode *node);
152 static void node_join (GSequenceNode *left,
153 GSequenceNode *right);
154 static void node_insert_sorted (GSequenceNode *node,
157 GSequenceIterCompareFunc cmp_func,
162 * Various helper functions
165 check_seq_access (GSequence *seq)
167 if (G_UNLIKELY (seq->access_prohibited))
169 g_warning ("Accessing a sequence while it is "
170 "being sorted or searched is not allowed");
175 get_sequence (GSequenceNode *node)
177 return (GSequence *)node_get_last (node)->data;
181 check_iter_access (GSequenceIter *iter)
183 check_seq_access (get_sequence (iter));
187 is_end (GSequenceIter *iter)
197 if (iter->parent->right != iter)
200 seq = get_sequence (iter);
202 return seq->end_node == iter;
207 GCompareDataFunc cmp_func;
209 GSequenceNode *end_node;
212 /* This function compares two iters using a normal compare
213 * function and user_data passed in in a SortInfo struct
216 iter_compare (GSequenceIter *node1,
217 GSequenceIter *node2,
220 const SortInfo *info = data;
223 if (node1 == info->end_node)
226 if (node2 == info->end_node)
229 retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
240 * @data_destroy: (allow-none): a #GDestroyNotify function, or %NULL
242 * Creates a new GSequence. The @data_destroy function, if non-%NULL will
243 * be called on all items when the sequence is destroyed and on items that
244 * are removed from the sequence.
246 * Return value: a new #GSequence
251 g_sequence_new (GDestroyNotify data_destroy)
253 GSequence *seq = g_new (GSequence, 1);
254 seq->data_destroy_notify = data_destroy;
256 seq->end_node = node_new (seq);
258 seq->access_prohibited = FALSE;
260 seq->real_sequence = seq;
269 * Frees the memory allocated for @seq. If @seq has a data destroy
270 * function associated with it, that function is called on all items
276 g_sequence_free (GSequence *seq)
278 g_return_if_fail (seq != NULL);
280 check_seq_access (seq);
282 node_free (seq->end_node, seq);
288 * g_sequence_foreach_range:
289 * @begin: a #GSequenceIter
290 * @end: a #GSequenceIter
292 * @user_data: user data passed to @func
294 * Calls @func for each item in the range (@begin, @end) passing
295 * @user_data to the function.
300 g_sequence_foreach_range (GSequenceIter *begin,
308 g_return_if_fail (func != NULL);
309 g_return_if_fail (begin != NULL);
310 g_return_if_fail (end != NULL);
312 seq = get_sequence (begin);
314 seq->access_prohibited = TRUE;
319 GSequenceIter *next = node_get_next (iter);
321 func (iter->data, user_data);
326 seq->access_prohibited = FALSE;
330 * g_sequence_foreach:
332 * @func: the function to call for each item in @seq
333 * @user_data: user data passed to @func
335 * Calls @func for each item in the sequence passing @user_data
341 g_sequence_foreach (GSequence *seq,
345 GSequenceIter *begin, *end;
347 check_seq_access (seq);
349 begin = g_sequence_get_begin_iter (seq);
350 end = g_sequence_get_end_iter (seq);
352 g_sequence_foreach_range (begin, end, func, user_data);
356 * g_sequence_range_get_midpoint:
357 * @begin: a #GSequenceIter
358 * @end: a #GSequenceIter
360 * Finds an iterator somewhere in the range (@begin, @end). This
361 * iterator will be close to the middle of the range, but is not
362 * guaranteed to be exactly in the middle.
364 * The @begin and @end iterators must both point to the same sequence
365 * and @begin must come before or be equal to @end in the sequence.
367 * Return value: a #GSequenceIter pointing somewhere in the
368 * (@begin, @end) range
373 g_sequence_range_get_midpoint (GSequenceIter *begin,
376 int begin_pos, end_pos, mid_pos;
378 g_return_val_if_fail (begin != NULL, NULL);
379 g_return_val_if_fail (end != NULL, NULL);
380 g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
382 begin_pos = node_get_pos (begin);
383 end_pos = node_get_pos (end);
385 g_return_val_if_fail (end_pos >= begin_pos, NULL);
387 mid_pos = begin_pos + (end_pos - begin_pos) / 2;
389 return node_get_by_pos (begin, mid_pos);
393 * g_sequence_iter_compare:
394 * @a: a #GSequenceIter
395 * @b: a #GSequenceIter
397 * Returns a negative number if @a comes before @b, 0 if they are equal,
398 * and a positive number if @a comes after @b.
400 * The @a and @b iterators must point into the same sequence.
402 * Return value: a negative number if @a comes before @b, 0 if they are
403 * equal, and a positive number if @a comes after @b
408 g_sequence_iter_compare (GSequenceIter *a,
413 g_return_val_if_fail (a != NULL, 0);
414 g_return_val_if_fail (b != NULL, 0);
415 g_return_val_if_fail (get_sequence (a) == get_sequence (b), 0);
417 check_iter_access (a);
418 check_iter_access (b);
420 a_pos = node_get_pos (a);
421 b_pos = node_get_pos (b);
425 else if (a_pos > b_pos)
434 * @data: the data for the new item
436 * Adds a new item to the end of @seq.
438 * Return value: an iterator pointing to the new item
443 g_sequence_append (GSequence *seq,
448 g_return_val_if_fail (seq != NULL, NULL);
450 check_seq_access (seq);
452 node = node_new (data);
453 node_insert_before (seq->end_node, node);
459 * g_sequence_prepend:
461 * @data: the data for the new item
463 * Adds a new item to the front of @seq
465 * Return value: an iterator pointing to the new item
470 g_sequence_prepend (GSequence *seq,
473 GSequenceNode *node, *first;
475 g_return_val_if_fail (seq != NULL, NULL);
477 check_seq_access (seq);
479 node = node_new (data);
480 first = node_get_first (seq->end_node);
482 node_insert_before (first, node);
488 * g_sequence_insert_before:
489 * @iter: a #GSequenceIter
490 * @data: the data for the new item
492 * Inserts a new item just before the item pointed to by @iter.
494 * Return value: an iterator pointing to the new item
499 g_sequence_insert_before (GSequenceIter *iter,
504 g_return_val_if_fail (iter != NULL, NULL);
506 check_iter_access (iter);
508 node = node_new (data);
510 node_insert_before (iter, node);
517 * @iter: a #GSequenceIter
519 * Removes the item pointed to by @iter. It is an error to pass the
520 * end iterator to this function.
522 * If the sequence has a data destroy function associated with it, this
523 * function is called on the data for the removed item.
528 g_sequence_remove (GSequenceIter *iter)
532 g_return_if_fail (iter != NULL);
533 g_return_if_fail (!is_end (iter));
535 check_iter_access (iter);
537 seq = get_sequence (iter);
540 node_free (iter, seq);
544 * g_sequence_remove_range:
545 * @begin: a #GSequenceIter
546 * @end: a #GSequenceIter
548 * Removes all items in the (@begin, @end) range.
550 * If the sequence has a data destroy function associated with it, this
551 * function is called on the data for the removed items.
556 g_sequence_remove_range (GSequenceIter *begin,
559 g_return_if_fail (get_sequence (begin) == get_sequence (end));
561 check_iter_access (begin);
562 check_iter_access (end);
564 g_sequence_move_range (NULL, begin, end);
568 * g_sequence_move_range:
569 * @dest: a #GSequenceIter
570 * @begin: a #GSequenceIter
571 * @end: a #GSequenceIter
573 * Inserts the (@begin, @end) range at the destination pointed to by ptr.
574 * The @begin and @end iters must point into the same sequence. It is
575 * allowed for @dest to point to a different sequence than the one pointed
576 * into by @begin and @end.
578 * If @dest is NULL, the range indicated by @begin and @end is
579 * removed from the sequence. If @dest iter points to a place within
580 * the (@begin, @end) range, the range does not move.
585 g_sequence_move_range (GSequenceIter *dest,
586 GSequenceIter *begin,
590 GSequenceNode *first;
592 g_return_if_fail (begin != NULL);
593 g_return_if_fail (end != NULL);
595 check_iter_access (begin);
596 check_iter_access (end);
598 check_iter_access (dest);
600 src_seq = get_sequence (begin);
602 g_return_if_fail (src_seq == get_sequence (end));
604 /* Dest points to begin or end? */
605 if (dest == begin || dest == end)
608 /* begin comes after end? */
609 if (g_sequence_iter_compare (begin, end) >= 0)
612 /* dest points somewhere in the (begin, end) range? */
613 if (dest && get_sequence (dest) == src_seq &&
614 g_sequence_iter_compare (dest, begin) > 0 &&
615 g_sequence_iter_compare (dest, end) < 0)
620 src_seq = get_sequence (begin);
622 first = node_get_first (begin);
629 node_join (first, end);
633 first = node_get_first (dest);
637 node_join (begin, dest);
640 node_join (first, begin);
644 node_free (begin, src_seq);
651 * @cmp_func: the function used to sort the sequence
652 * @cmp_data: user data passed to @cmp_func
654 * Sorts @seq using @cmp_func.
656 * @cmp_func is passed two items of @seq and should
657 * return 0 if they are equal, a negative value if the
658 * first comes before the second, and a positive value
659 * if the second comes before the first.
664 g_sequence_sort (GSequence *seq,
665 GCompareDataFunc cmp_func,
670 info.cmp_func = cmp_func;
671 info.cmp_data = cmp_data;
672 info.end_node = seq->end_node;
674 check_seq_access (seq);
676 g_sequence_sort_iter (seq, iter_compare, &info);
680 * g_sequence_insert_sorted:
682 * @data: the data to insert
683 * @cmp_func: the function used to compare items in the sequence
684 * @cmp_data: user data passed to @cmp_func.
686 * Inserts @data into @sequence using @func to determine the new
687 * position. The sequence must already be sorted according to @cmp_func;
688 * otherwise the new position of @data is undefined.
690 * @cmp_func is called with two items of the @seq and @user_data.
691 * It should return 0 if the items are equal, a negative value
692 * if the first item comes before the second, and a positive value
693 * if the second item comes before the first.
695 * Return value: a #GSequenceIter pointing to the new item.
700 g_sequence_insert_sorted (GSequence *seq,
702 GCompareDataFunc cmp_func,
707 g_return_val_if_fail (seq != NULL, NULL);
708 g_return_val_if_fail (cmp_func != NULL, NULL);
710 info.cmp_func = cmp_func;
711 info.cmp_data = cmp_data;
712 info.end_node = seq->end_node;
713 check_seq_access (seq);
715 return g_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
719 * g_sequence_sort_changed:
720 * @iter: A #GSequenceIter
721 * @cmp_func: the function used to compare items in the sequence
722 * @cmp_data: user data passed to @cmp_func.
724 * Moves the data pointed to a new position as indicated by @cmp_func. This
725 * function should be called for items in a sequence already sorted according
726 * to @cmp_func whenever some aspect of an item changes so that @cmp_func
727 * may return different values for that item.
729 * @cmp_func is called with two items of the @seq and @user_data.
730 * It should return 0 if the items are equal, a negative value if
731 * the first item comes before the second, and a positive value if
732 * the second item comes before the first.
737 g_sequence_sort_changed (GSequenceIter *iter,
738 GCompareDataFunc cmp_func,
743 g_return_if_fail (!is_end (iter));
745 info.cmp_func = cmp_func;
746 info.cmp_data = cmp_data;
747 info.end_node = get_sequence (iter)->end_node;
748 check_iter_access (iter);
750 g_sequence_sort_changed_iter (iter, iter_compare, &info);
756 * @data: data for the new item
757 * @cmp_func: the function used to compare items in the sequence
758 * @cmp_data: user data passed to @cmp_func
760 * Returns an iterator pointing to the position where @data would
761 * be inserted according to @cmp_func and @cmp_data.
763 * @cmp_func is called with two items of the @seq and @user_data.
764 * It should return 0 if the items are equal, a negative value if
765 * the first item comes before the second, and a positive value if
766 * the second item comes before the first.
768 * If you are simply searching for an existing element of the sequence,
769 * consider using g_sequence_lookup().
771 * This function will fail if the data contained in the sequence is
772 * unsorted. Use g_sequence_insert_sorted() or
773 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
774 * you want to add a large amount of data, call g_sequence_sort() after
775 * doing unsorted insertions.
777 * Return value: an #GSequenceIter pointing to the position where @data
778 * would have been inserted according to @cmp_func and @cmp_data
783 g_sequence_search (GSequence *seq,
785 GCompareDataFunc cmp_func,
790 g_return_val_if_fail (seq != NULL, NULL);
792 info.cmp_func = cmp_func;
793 info.cmp_data = cmp_data;
794 info.end_node = seq->end_node;
795 check_seq_access (seq);
797 return g_sequence_search_iter (seq, data, iter_compare, &info);
803 * @data: data to lookup
804 * @cmp_func: the function used to compare items in the sequence
805 * @cmp_data: user data passed to @cmp_func
807 * Returns an iterator pointing to the position of the first item found
808 * equal to @data according to @cmp_func and @cmp_data. If more than one
809 * item is equal, it is not guaranteed that it is the first which is
810 * returned. In that case, you can use g_sequence_iter_next() and
811 * g_sequence_iter_prev() to get others.
813 * @cmp_func is called with two items of the @seq and @user_data.
814 * It should return 0 if the items are equal, a negative value if
815 * the first item comes before the second, and a positive value if
816 * the second item comes before the first.
818 * This function will fail if the data contained in the sequence is
819 * unsorted. Use g_sequence_insert_sorted() or
820 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
821 * you want to add a large amount of data, call g_sequence_sort() after
822 * doing unsorted insertions.
824 * Return value: an #GSequenceIter pointing to the position of the
825 * first item found equal to @data according to @cmp_func and
826 * @cmp_data, or %NULL if no such item exists
831 g_sequence_lookup (GSequence *seq,
833 GCompareDataFunc cmp_func,
838 g_return_val_if_fail (seq != NULL, NULL);
840 info.cmp_func = cmp_func;
841 info.cmp_data = cmp_data;
842 info.end_node = seq->end_node;
843 check_seq_access (seq);
845 return g_sequence_lookup_iter (seq, data, iter_compare, &info);
849 * g_sequence_sort_iter:
851 * @cmp_func: the function used to compare iterators in the sequence
852 * @cmp_data: user data passed to @cmp_func
854 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
855 * of a GCompareDataFunc as the compare function
857 * @cmp_func is called with two iterators pointing into @seq. It should
858 * return 0 if the iterators are equal, a negative value if the first
859 * iterator comes before the second, and a positive value if the second
860 * iterator comes before the first.
865 g_sequence_sort_iter (GSequence *seq,
866 GSequenceIterCompareFunc cmp_func,
870 GSequenceNode *begin, *end;
872 g_return_if_fail (seq != NULL);
873 g_return_if_fail (cmp_func != NULL);
875 check_seq_access (seq);
877 begin = g_sequence_get_begin_iter (seq);
878 end = g_sequence_get_end_iter (seq);
880 tmp = g_sequence_new (NULL);
881 tmp->real_sequence = seq;
883 g_sequence_move_range (g_sequence_get_begin_iter (tmp), begin, end);
885 seq->access_prohibited = TRUE;
886 tmp->access_prohibited = TRUE;
888 while (g_sequence_get_length (tmp) > 0)
890 GSequenceNode *node = g_sequence_get_begin_iter (tmp);
892 node_insert_sorted (seq->end_node, node, seq->end_node,
896 tmp->access_prohibited = FALSE;
897 seq->access_prohibited = FALSE;
899 g_sequence_free (tmp);
903 * g_sequence_sort_changed_iter:
904 * @iter: a #GSequenceIter
905 * @iter_cmp: the function used to compare iterators in the sequence
906 * @cmp_data: user data passed to @cmp_func
908 * Like g_sequence_sort_changed(), but uses
909 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
910 * the compare function.
912 * @iter_cmp is called with two iterators pointing into @seq. It should
913 * return 0 if the iterators are equal, a negative value if the first
914 * iterator comes before the second, and a positive value if the second
915 * iterator comes before the first.
920 g_sequence_sort_changed_iter (GSequenceIter *iter,
921 GSequenceIterCompareFunc iter_cmp,
924 GSequence *seq, *tmp_seq;
925 GSequenceIter *next, *prev;
927 g_return_if_fail (iter != NULL);
928 g_return_if_fail (!is_end (iter));
929 g_return_if_fail (iter_cmp != NULL);
930 check_iter_access (iter);
932 /* If one of the neighbours is equal to iter, then
933 * don't move it. This ensures that sort_changed() is
934 * a stable operation.
937 next = node_get_next (iter);
938 prev = node_get_prev (iter);
940 if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
943 if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
946 seq = get_sequence (iter);
948 seq->access_prohibited = TRUE;
950 tmp_seq = g_sequence_new (NULL);
951 tmp_seq->real_sequence = seq;
954 node_insert_before (tmp_seq->end_node, iter);
956 node_insert_sorted (seq->end_node, iter, seq->end_node,
959 g_sequence_free (tmp_seq);
961 seq->access_prohibited = FALSE;
965 * g_sequence_insert_sorted_iter:
967 * @data: data for the new item
968 * @iter_cmp: the function used to compare iterators in the sequence
969 * @cmp_data: user data passed to @cmp_func
971 * Like g_sequence_insert_sorted(), but uses
972 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
973 * the compare function.
975 * @iter_cmp is called with two iterators pointing into @seq.
976 * It should return 0 if the iterators are equal, a negative
977 * value if the first iterator comes before the second, and a
978 * positive value if the second iterator comes before the first.
980 * It is called with two iterators pointing into @seq. It should
981 * return 0 if the iterators are equal, a negative value if the
982 * first iterator comes before the second, and a positive value
983 * if the second iterator comes before the first.
985 * Return value: a #GSequenceIter pointing to the new item
990 g_sequence_insert_sorted_iter (GSequence *seq,
992 GSequenceIterCompareFunc iter_cmp,
995 GSequenceNode *new_node;
998 g_return_val_if_fail (seq != NULL, NULL);
999 g_return_val_if_fail (iter_cmp != NULL, NULL);
1001 check_seq_access (seq);
1003 seq->access_prohibited = TRUE;
1005 /* Create a new temporary sequence and put the new node into
1006 * that. The reason for this is that the user compare function
1007 * will be called with the new node, and if it dereferences,
1008 * "is_end" will be called on it. But that will crash if the
1009 * node is not actually in a sequence.
1011 * node_insert_sorted() makes sure the node is unlinked before
1014 * The reason we need the "iter" versions at all is that that
1015 * is the only kind of compare functions GtkTreeView can use.
1017 tmp_seq = g_sequence_new (NULL);
1018 tmp_seq->real_sequence = seq;
1020 new_node = g_sequence_append (tmp_seq, data);
1022 node_insert_sorted (seq->end_node, new_node,
1023 seq->end_node, iter_cmp, cmp_data);
1025 g_sequence_free (tmp_seq);
1027 seq->access_prohibited = FALSE;
1033 * g_sequence_search_iter:
1034 * @seq: a #GSequence
1035 * @data: data for the new item
1036 * @iter_cmp: the function used to compare iterators in the sequence
1037 * @cmp_data: user data passed to @iter_cmp
1039 * Like g_sequence_search(), but uses a #GSequenceIterCompareFunc
1040 * instead of a #GCompareDataFunc as the compare function.
1042 * @iter_cmp is called with two iterators pointing into @seq.
1043 * It should return 0 if the iterators are equal, a negative value
1044 * if the first iterator comes before the second, and a positive
1045 * value if the second iterator comes before the first.
1047 * If you are simply searching for an existing element of the sequence,
1048 * consider using g_sequence_lookup_iter().
1050 * This function will fail if the data contained in the sequence is
1051 * unsorted. Use g_sequence_insert_sorted() or
1052 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
1053 * you want to add a large amount of data, call g_sequence_sort() after
1054 * doing unsorted insertions.
1056 * Return value: a #GSequenceIter pointing to the position in @seq
1057 * where @data would have been inserted according to @iter_cmp
1063 g_sequence_search_iter (GSequence *seq,
1065 GSequenceIterCompareFunc iter_cmp,
1068 GSequenceNode *node;
1069 GSequenceNode *dummy;
1072 g_return_val_if_fail (seq != NULL, NULL);
1074 check_seq_access (seq);
1076 seq->access_prohibited = TRUE;
1078 tmp_seq = g_sequence_new (NULL);
1079 tmp_seq->real_sequence = seq;
1081 dummy = g_sequence_append (tmp_seq, data);
1083 node = node_find_closest (seq->end_node, dummy,
1084 seq->end_node, iter_cmp, cmp_data);
1086 g_sequence_free (tmp_seq);
1088 seq->access_prohibited = FALSE;
1094 * g_sequence_lookup_iter:
1095 * @seq: a #GSequence
1096 * @data: data to lookup
1097 * @iter_cmp: the function used to compare iterators in the sequence
1098 * @cmp_data: user data passed to @iter_cmp
1100 * Like g_sequence_lookup(), but uses a #GSequenceIterCompareFunc
1101 * instead of a #GCompareDataFunc as the compare function.
1103 * @iter_cmp is called with two iterators pointing into @seq.
1104 * It should return 0 if the iterators are equal, a negative value
1105 * if the first iterator comes before the second, and a positive
1106 * value if the second iterator comes before the first.
1108 * This function will fail if the data contained in the sequence is
1109 * unsorted. Use g_sequence_insert_sorted() or
1110 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
1111 * you want to add a large amount of data, call g_sequence_sort() after
1112 * doing unsorted insertions.
1114 * Return value: an #GSequenceIter pointing to the position of
1115 * the first item found equal to @data according to @cmp_func
1116 * and @cmp_data, or %NULL if no such item exists
1121 g_sequence_lookup_iter (GSequence *seq,
1123 GSequenceIterCompareFunc iter_cmp,
1126 GSequenceNode *node;
1127 GSequenceNode *dummy;
1130 g_return_val_if_fail (seq != NULL, NULL);
1132 check_seq_access (seq);
1134 seq->access_prohibited = TRUE;
1136 tmp_seq = g_sequence_new (NULL);
1137 tmp_seq->real_sequence = seq;
1139 dummy = g_sequence_append (tmp_seq, data);
1141 node = node_find (seq->end_node, dummy,
1142 seq->end_node, iter_cmp, cmp_data);
1144 g_sequence_free (tmp_seq);
1146 seq->access_prohibited = FALSE;
1152 * g_sequence_iter_get_sequence:
1153 * @iter: a #GSequenceIter
1155 * Returns the #GSequence that @iter points into.
1157 * Return value: the #GSequence that @iter points into
1162 g_sequence_iter_get_sequence (GSequenceIter *iter)
1166 g_return_val_if_fail (iter != NULL, NULL);
1168 seq = get_sequence (iter);
1170 /* For temporary sequences, this points to the sequence that
1171 * is actually being manipulated
1173 return seq->real_sequence;
1178 * @iter: a #GSequenceIter
1180 * Returns the data that @iter points to.
1182 * Return value: the data that @iter points to
1187 g_sequence_get (GSequenceIter *iter)
1189 g_return_val_if_fail (iter != NULL, NULL);
1190 g_return_val_if_fail (!is_end (iter), NULL);
1197 * @iter: a #GSequenceIter
1198 * @data: new data for the item
1200 * Changes the data for the item pointed to by @iter to be @data. If
1201 * the sequence has a data destroy function associated with it, that
1202 * function is called on the existing data that @iter pointed to.
1207 g_sequence_set (GSequenceIter *iter,
1212 g_return_if_fail (iter != NULL);
1213 g_return_if_fail (!is_end (iter));
1215 seq = get_sequence (iter);
1217 /* If @data is identical to iter->data, it is destroyed
1218 * here. This will work right in case of ref-counted objects. Also
1219 * it is similar to what ghashtables do.
1221 * For non-refcounted data it's a little less convenient, but
1222 * code relying on self-setting not destroying would be
1223 * pretty dubious anyway ...
1226 if (seq->data_destroy_notify)
1227 seq->data_destroy_notify (iter->data);
1233 * g_sequence_get_length:
1234 * @seq: a #GSequence
1236 * Returns the length of @seq
1238 * Return value: the length of @seq
1243 g_sequence_get_length (GSequence *seq)
1245 return node_get_length (seq->end_node) - 1;
1249 * g_sequence_get_end_iter:
1250 * @seq: a #GSequence
1252 * Returns the end iterator for @seg
1254 * Return value: the end iterator for @seq
1259 g_sequence_get_end_iter (GSequence *seq)
1261 g_return_val_if_fail (seq != NULL, NULL);
1263 return seq->end_node;
1267 * g_sequence_get_begin_iter:
1268 * @seq: a #GSequence
1270 * Returns the begin iterator for @seq.
1272 * Return value: the begin iterator for @seq.
1277 g_sequence_get_begin_iter (GSequence *seq)
1279 g_return_val_if_fail (seq != NULL, NULL);
1281 return node_get_first (seq->end_node);
1285 clamp_position (GSequence *seq,
1288 gint len = g_sequence_get_length (seq);
1290 if (pos > len || pos < 0)
1297 * if pos > number of items or -1, will return end pointer
1300 * g_sequence_get_iter_at_pos:
1301 * @seq: a #GSequence
1302 * @pos: a position in @seq, or -1 for the end
1304 * Returns the iterator at position @pos. If @pos is negative or larger
1305 * than the number of items in @seq, the end iterator is returned.
1307 * Return value: The #GSequenceIter at position @pos
1312 g_sequence_get_iter_at_pos (GSequence *seq,
1315 g_return_val_if_fail (seq != NULL, NULL);
1317 pos = clamp_position (seq, pos);
1319 return node_get_by_pos (seq->end_node, pos);
1324 * @src: a #GSequenceIter pointing to the item to move
1325 * @dest: a #GSequenceIter pointing to the position to which
1328 * Moves the item pointed to by @src to the position indicated by @dest.
1329 * After calling this function @dest will point to the position immediately
1330 * after @src. It is allowed for @src and @dest to point into different
1336 g_sequence_move (GSequenceIter *src,
1337 GSequenceIter *dest)
1339 g_return_if_fail (src != NULL);
1340 g_return_if_fail (dest != NULL);
1341 g_return_if_fail (!is_end (src));
1347 node_insert_before (dest, src);
1353 * g_sequence_iter_is_end:
1354 * @iter: a #GSequenceIter
1356 * Returns whether @iter is the end iterator
1358 * Return value: Whether @iter is the end iterator
1363 g_sequence_iter_is_end (GSequenceIter *iter)
1365 g_return_val_if_fail (iter != NULL, FALSE);
1367 return is_end (iter);
1371 * g_sequence_iter_is_begin:
1372 * @iter: a #GSequenceIter
1374 * Returns whether @iter is the begin iterator
1376 * Return value: whether @iter is the begin iterator
1381 g_sequence_iter_is_begin (GSequenceIter *iter)
1383 g_return_val_if_fail (iter != NULL, FALSE);
1385 return (node_get_prev (iter) == iter);
1389 * g_sequence_iter_get_position:
1390 * @iter: a #GSequenceIter
1392 * Returns the position of @iter
1394 * Return value: the position of @iter
1399 g_sequence_iter_get_position (GSequenceIter *iter)
1401 g_return_val_if_fail (iter != NULL, -1);
1403 return node_get_pos (iter);
1407 * g_sequence_iter_next:
1408 * @iter: a #GSequenceIter
1410 * Returns an iterator pointing to the next position after @iter.
1411 * If @iter is the end iterator, the end iterator is returned.
1413 * Return value: a #GSequenceIter pointing to the next position after @iter
1418 g_sequence_iter_next (GSequenceIter *iter)
1420 g_return_val_if_fail (iter != NULL, NULL);
1422 return node_get_next (iter);
1426 * g_sequence_iter_prev:
1427 * @iter: a #GSequenceIter
1429 * Returns an iterator pointing to the previous position before @iter.
1430 * If @iter is the begin iterator, the begin iterator is returned.
1432 * Return value: a #GSequenceIter pointing to the previous position
1438 g_sequence_iter_prev (GSequenceIter *iter)
1440 g_return_val_if_fail (iter != NULL, NULL);
1442 return node_get_prev (iter);
1446 * g_sequence_iter_move:
1447 * @iter: a #GSequenceIter
1448 * @delta: A positive or negative number indicating how many positions away
1449 * from @iter the returned #GSequenceIter will be
1451 * Returns the #GSequenceIter which is @delta positions away from @iter.
1452 * If @iter is closer than -@delta positions to the beginning of the sequence,
1453 * the begin iterator is returned. If @iter is closer than @delta positions
1454 * to the end of the sequence, the end iterator is returned.
1456 * Return value: a #GSequenceIter which is @delta positions away from @iter
1461 g_sequence_iter_move (GSequenceIter *iter,
1467 g_return_val_if_fail (iter != NULL, NULL);
1469 len = g_sequence_get_length (get_sequence (iter));
1471 new_pos = node_get_pos (iter) + delta;
1475 else if (new_pos > len)
1478 return node_get_by_pos (iter, new_pos);
1483 * @a: a #GSequenceIter
1484 * @b: a #GSequenceIter
1486 * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
1487 * to point into difference sequences.
1492 g_sequence_swap (GSequenceIter *a,
1495 GSequenceNode *leftmost, *rightmost, *rightmost_next;
1498 g_return_if_fail (!g_sequence_iter_is_end (a));
1499 g_return_if_fail (!g_sequence_iter_is_end (b));
1504 a_pos = g_sequence_iter_get_position (a);
1505 b_pos = g_sequence_iter_get_position (b);
1518 rightmost_next = node_get_next (rightmost);
1520 /* The situation is now like this:
1522 * ..., leftmost, ......., rightmost, rightmost_next, ...
1525 g_sequence_move (rightmost, leftmost);
1526 g_sequence_move (leftmost, rightmost_next);
1530 * Implementation of a treap
1535 get_priority (GSequenceNode *node)
1537 guint key = GPOINTER_TO_UINT (node);
1539 /* This hash function is based on one found on Thomas Wang's
1542 * http://www.concentric.net/~Ttwang/tech/inthash.htm
1545 key = (key << 15) - key - 1;
1546 key = key ^ (key >> 12);
1547 key = key + (key << 2);
1548 key = key ^ (key >> 4);
1549 key = key + (key << 3) + (key << 11);
1550 key = key ^ (key >> 16);
1552 /* We rely on 0 being less than all other priorities */
1553 return key? key : 1;
1556 static GSequenceNode *
1557 find_root (GSequenceNode *node)
1559 while (node->parent)
1560 node = node->parent;
1565 static GSequenceNode *
1566 node_new (gpointer data)
1568 GSequenceNode *node = g_slice_new0 (GSequenceNode);
1574 node->parent = NULL;
1579 static GSequenceNode *
1580 node_get_first (GSequenceNode *node)
1582 node = find_root (node);
1590 static GSequenceNode *
1591 node_get_last (GSequenceNode *node)
1593 node = find_root (node);
1601 #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1602 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1604 static GSequenceNode *
1605 node_get_next (GSequenceNode *node)
1607 GSequenceNode *n = node;
1617 while (NODE_RIGHT_CHILD (n))
1629 static GSequenceNode *
1630 node_get_prev (GSequenceNode *node)
1632 GSequenceNode *n = node;
1642 while (NODE_LEFT_CHILD (n))
1654 #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1657 node_get_pos (GSequenceNode *node)
1662 n_smaller = node->left->n_nodes;
1666 if (NODE_RIGHT_CHILD (node))
1667 n_smaller += N_NODES (node->parent->left) + 1;
1669 node = node->parent;
1675 static GSequenceNode *
1676 node_get_by_pos (GSequenceNode *node,
1681 node = find_root (node);
1683 while ((i = N_NODES (node->left)) != pos)
1699 static GSequenceNode *
1700 node_find (GSequenceNode *haystack,
1701 GSequenceNode *needle,
1703 GSequenceIterCompareFunc iter_cmp,
1708 haystack = find_root (haystack);
1712 /* iter_cmp can't be passed the end node, since the function may
1715 if (haystack == end)
1718 c = iter_cmp (haystack, needle, cmp_data);
1724 haystack = haystack->left;
1726 haystack = haystack->right;
1728 while (haystack != NULL);
1733 static GSequenceNode *
1734 node_find_closest (GSequenceNode *haystack,
1735 GSequenceNode *needle,
1737 GSequenceIterCompareFunc iter_cmp,
1740 GSequenceNode *best;
1743 haystack = find_root (haystack);
1749 /* iter_cmp can't be passed the end node, since the function may
1752 if (haystack == end)
1755 c = iter_cmp (haystack, needle, cmp_data);
1757 /* In the following we don't break even if c == 0. Instead we go on
1758 * searching along the 'bigger' nodes, so that we find the last one
1759 * that is equal to the needle.
1762 haystack = haystack->left;
1764 haystack = haystack->right;
1766 while (haystack != NULL);
1768 /* If the best node is smaller or equal to the data, then move one step
1769 * to the right to make sure the best one is strictly bigger than the data
1771 if (best != end && c <= 0)
1772 best = node_get_next (best);
1778 node_get_length (GSequenceNode *node)
1780 node = find_root (node);
1782 return node->n_nodes;
1786 real_node_free (GSequenceNode *node,
1791 real_node_free (node->left, seq);
1792 real_node_free (node->right, seq);
1794 if (seq && seq->data_destroy_notify && node != seq->end_node)
1795 seq->data_destroy_notify (node->data);
1797 g_slice_free (GSequenceNode, node);
1802 node_free (GSequenceNode *node,
1805 node = find_root (node);
1807 real_node_free (node, seq);
1811 node_update_fields (GSequenceNode *node)
1815 n_nodes += N_NODES (node->left);
1816 n_nodes += N_NODES (node->right);
1818 node->n_nodes = n_nodes;
1822 node_rotate (GSequenceNode *node)
1824 GSequenceNode *tmp, *old;
1826 g_assert (node->parent);
1827 g_assert (node->parent != node);
1829 if (NODE_LEFT_CHILD (node))
1834 node->right = node->parent;
1835 node->parent = node->parent->parent;
1838 if (node->parent->left == node->right)
1839 node->parent->left = node;
1841 node->parent->right = node;
1844 g_assert (node->right);
1846 node->right->parent = node;
1847 node->right->left = tmp;
1849 if (node->right->left)
1850 node->right->left->parent = node->right;
1859 node->left = node->parent;
1860 node->parent = node->parent->parent;
1863 if (node->parent->right == node->left)
1864 node->parent->right = node;
1866 node->parent->left = node;
1869 g_assert (node->left);
1871 node->left->parent = node;
1872 node->left->right = tmp;
1874 if (node->left->right)
1875 node->left->right->parent = node->left;
1880 node_update_fields (old);
1881 node_update_fields (node);
1885 node_update_fields_deep (GSequenceNode *node)
1889 node_update_fields (node);
1891 node_update_fields_deep (node->parent);
1896 rotate_down (GSequenceNode *node,
1901 left = node->left ? get_priority (node->left) : 0;
1902 right = node->right ? get_priority (node->right) : 0;
1904 while (priority < left || priority < right)
1907 node_rotate (node->left);
1909 node_rotate (node->right);
1911 left = node->left ? get_priority (node->left) : 0;
1912 right = node->right ? get_priority (node->right) : 0;
1917 node_cut (GSequenceNode *node)
1919 while (node->parent)
1923 node->left->parent = NULL;
1926 node_update_fields (node);
1928 rotate_down (node, get_priority (node));
1932 node_join (GSequenceNode *left,
1933 GSequenceNode *right)
1935 GSequenceNode *fake = node_new (NULL);
1937 fake->left = find_root (left);
1938 fake->right = find_root (right);
1939 fake->left->parent = fake;
1940 fake->right->parent = fake;
1942 node_update_fields (fake);
1946 node_free (fake, NULL);
1950 node_insert_before (GSequenceNode *node,
1953 new->left = node->left;
1955 new->left->parent = new;
1960 node_update_fields_deep (new);
1962 while (new->parent && get_priority (new) > get_priority (new->parent))
1965 rotate_down (new, get_priority (new));
1969 node_unlink (GSequenceNode *node)
1971 rotate_down (node, 0);
1973 if (NODE_RIGHT_CHILD (node))
1974 node->parent->right = NULL;
1975 else if (NODE_LEFT_CHILD (node))
1976 node->parent->left = NULL;
1979 node_update_fields_deep (node->parent);
1981 node->parent = NULL;
1985 node_insert_sorted (GSequenceNode *node,
1988 GSequenceIterCompareFunc iter_cmp,
1991 GSequenceNode *closest;
1993 closest = node_find_closest (node, new, end, iter_cmp, cmp_data);
1997 node_insert_before (closest, new);