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, write to the
17 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 * Boston, MA 02111-1307, USA.
23 #include "gsequence.h"
26 #include "gtestutils.h"
31 * @short_description: scalable lists
33 * The #GSequence data structure has the API of a list, but is
34 * implemented internally with a balanced binary tree. This means that
35 * it is possible to maintain a sorted list of n elements in time O(n
36 * log n). The data contained in each element can be either integer
37 * values, by using of the <link
38 * linkend="glib-Type-Conversion-Macros">Type Conversion Macros</link>,
39 * or simply pointers to any type of data.
41 * A #GSequence is accessed through <firstterm>iterators</firstterm>,
42 * represented by a #GSequenceIter. An iterator represents a position
43 * between two elements of the sequence. For example, the
44 * <firstterm>begin</firstterm> iterator represents the gap immediately
45 * before the first element of the sequence, and the
46 * <firstterm>end</firstterm> iterator represents the gap immediately
47 * after the last element. In an empty sequence, the begin and end
48 * iterators are the same.
50 * Some methods on #GSequence operate on ranges of items. For example
51 * g_sequence_foreach_range() will call a user-specified function on
52 * each element with the given range. The range is delimited by the
53 * gaps represented by the passed-in iterators, so if you pass in the
54 * begin and end iterators, the range in question is the entire
57 * The function g_sequence_get() is used with an iterator to access the
58 * element immediately following the gap that the iterator represents.
59 * The iterator is said to <firstterm>point</firstterm> to that element.
61 * Iterators are stable across most operations on a #GSequence. For
62 * example an iterator pointing to some element of a sequence will
63 * continue to point to that element even after the sequence is sorted.
64 * Even moving an element to another sequence using for example
65 * g_sequence_move_range() will not invalidate the iterators pointing
66 * to it. The only operation that will invalidate an iterator is when
67 * the element it points to is removed from any sequence.
73 * The #GSequenceIter struct is an opaque data type representing an
74 * iterator pointing into a #GSequence.
78 * GSequenceIterCompareFunc:
79 * @a: a #GSequenceIter
80 * @b: a #GSequenceIter
83 * A #GSequenceIterCompareFunc is a function used to compare iterators.
84 * It must return zero if the iterators compare equal, a negative value
85 * if @a comes before @b, and a positive value if @b comes before @a.
87 * Returns: zero if the iterators are equal, a negative value if @a
88 * comes before @b, and a positive value if @b comes before
92 typedef struct _GSequenceNode GSequenceNode;
97 * The #GSequence struct is an opaque data type representing a
98 * <link linkend="glib-Sequences">Sequence</link> data type.
102 GSequenceNode * end_node;
103 GDestroyNotify data_destroy_notify;
104 gboolean access_prohibited;
106 /* The 'real_sequence' is used when temporary sequences are created
107 * to hold nodes that are being rearranged. The 'real_sequence' of such
108 * a temporary sequence points to the sequence that is actually being
109 * manipulated. The only reason we need this is so that when the
110 * sort/sort_changed/search_iter() functions call out to the application
111 * g_sequence_iter_get_sequence() will return the correct sequence.
113 GSequence * real_sequence;
116 struct _GSequenceNode
119 GSequenceNode * parent;
120 GSequenceNode * left;
121 GSequenceNode * right;
122 gpointer data; /* For the end node, this field points
128 * Declaration of GSequenceNode methods
130 static GSequenceNode *node_new (gpointer data);
131 static GSequenceNode *node_get_first (GSequenceNode *node);
132 static GSequenceNode *node_get_last (GSequenceNode *node);
133 static GSequenceNode *node_get_prev (GSequenceNode *node);
134 static GSequenceNode *node_get_next (GSequenceNode *node);
135 static gint node_get_pos (GSequenceNode *node);
136 static GSequenceNode *node_get_by_pos (GSequenceNode *node,
138 static GSequenceNode *node_find (GSequenceNode *haystack,
139 GSequenceNode *needle,
141 GSequenceIterCompareFunc cmp,
143 static GSequenceNode *node_find_closest (GSequenceNode *haystack,
144 GSequenceNode *needle,
146 GSequenceIterCompareFunc cmp,
148 static gint node_get_length (GSequenceNode *node);
149 static void node_free (GSequenceNode *node,
151 static void node_cut (GSequenceNode *split);
152 static void node_insert_before (GSequenceNode *node,
154 static void node_unlink (GSequenceNode *node);
155 static void node_join (GSequenceNode *left,
156 GSequenceNode *right);
157 static void node_insert_sorted (GSequenceNode *node,
160 GSequenceIterCompareFunc cmp_func,
165 * Various helper functions
168 check_seq_access (GSequence *seq)
170 if (G_UNLIKELY (seq->access_prohibited))
172 g_warning ("Accessing a sequence while it is "
173 "being sorted or searched is not allowed");
178 get_sequence (GSequenceNode *node)
180 return (GSequence *)node_get_last (node)->data;
184 check_iter_access (GSequenceIter *iter)
186 check_seq_access (get_sequence (iter));
190 is_end (GSequenceIter *iter)
200 if (iter->parent->right != iter)
203 seq = get_sequence (iter);
205 return seq->end_node == iter;
210 GCompareDataFunc cmp_func;
212 GSequenceNode *end_node;
215 /* This function compares two iters using a normal compare
216 * function and user_data passed in in a SortInfo struct
219 iter_compare (GSequenceIter *node1,
220 GSequenceIter *node2,
223 const SortInfo *info = data;
226 if (node1 == info->end_node)
229 if (node2 == info->end_node)
232 retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
243 * @data_destroy: (allow-none): a #GDestroyNotify function, or %NULL
245 * Creates a new GSequence. The @data_destroy function, if non-%NULL will
246 * be called on all items when the sequence is destroyed and on items that
247 * are removed from the sequence.
249 * Return value: a new #GSequence
254 g_sequence_new (GDestroyNotify data_destroy)
256 GSequence *seq = g_new (GSequence, 1);
257 seq->data_destroy_notify = data_destroy;
259 seq->end_node = node_new (seq);
261 seq->access_prohibited = FALSE;
263 seq->real_sequence = seq;
272 * Frees the memory allocated for @seq. If @seq has a data destroy
273 * function associated with it, that function is called on all items in
279 g_sequence_free (GSequence *seq)
281 g_return_if_fail (seq != NULL);
283 check_seq_access (seq);
285 node_free (seq->end_node, seq);
291 * g_sequence_foreach_range:
292 * @begin: a #GSequenceIter
293 * @end: a #GSequenceIter
295 * @user_data: user data passed to @func
297 * Calls @func for each item in the range (@begin, @end) passing
298 * @user_data to the function.
303 g_sequence_foreach_range (GSequenceIter *begin,
311 g_return_if_fail (func != NULL);
312 g_return_if_fail (begin != NULL);
313 g_return_if_fail (end != NULL);
315 seq = get_sequence (begin);
317 seq->access_prohibited = TRUE;
322 GSequenceIter *next = node_get_next (iter);
324 func (iter->data, user_data);
329 seq->access_prohibited = FALSE;
333 * g_sequence_foreach:
335 * @func: the function to call for each item in @seq
336 * @user_data: user data passed to @func
338 * Calls @func for each item in the sequence passing @user_data
344 g_sequence_foreach (GSequence *seq,
348 GSequenceIter *begin, *end;
350 check_seq_access (seq);
352 begin = g_sequence_get_begin_iter (seq);
353 end = g_sequence_get_end_iter (seq);
355 g_sequence_foreach_range (begin, end, func, user_data);
359 * g_sequence_range_get_midpoint:
360 * @begin: a #GSequenceIter
361 * @end: a #GSequenceIter
363 * Finds an iterator somewhere in the range (@begin, @end). This
364 * iterator will be close to the middle of the range, but is not
365 * guaranteed to be <emphasis>exactly</emphasis> in the middle.
367 * The @begin and @end iterators must both point to the same sequence and
368 * @begin must come before or be equal to @end in the sequence.
370 * Return value: A #GSequenceIter pointing somewhere in the
371 * (@begin, @end) range.
376 g_sequence_range_get_midpoint (GSequenceIter *begin,
379 int begin_pos, end_pos, mid_pos;
381 g_return_val_if_fail (begin != NULL, NULL);
382 g_return_val_if_fail (end != NULL, NULL);
383 g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
385 begin_pos = node_get_pos (begin);
386 end_pos = node_get_pos (end);
388 g_return_val_if_fail (end_pos >= begin_pos, NULL);
390 mid_pos = begin_pos + (end_pos - begin_pos) / 2;
392 return node_get_by_pos (begin, mid_pos);
396 * g_sequence_iter_compare:
397 * @a: a #GSequenceIter
398 * @b: a #GSequenceIter
400 * Returns a negative number if @a comes before @b, 0 if they are equal,
401 * and a positive number if @a comes after @b.
403 * The @a and @b iterators must point into the same sequence.
405 * Return value: A negative number if @a comes before @b, 0 if they are
406 * equal, and a positive number if @a comes after @b.
411 g_sequence_iter_compare (GSequenceIter *a,
416 g_return_val_if_fail (a != NULL, 0);
417 g_return_val_if_fail (b != NULL, 0);
418 g_return_val_if_fail (get_sequence (a) == get_sequence (b), 0);
420 check_iter_access (a);
421 check_iter_access (b);
423 a_pos = node_get_pos (a);
424 b_pos = node_get_pos (b);
428 else if (a_pos > b_pos)
437 * @data: the data for the new item
439 * Adds a new item to the end of @seq.
441 * Return value: an iterator pointing to the new item
446 g_sequence_append (GSequence *seq,
451 g_return_val_if_fail (seq != NULL, NULL);
453 check_seq_access (seq);
455 node = node_new (data);
456 node_insert_before (seq->end_node, node);
462 * g_sequence_prepend:
464 * @data: the data for the new item
466 * Adds a new item to the front of @seq
468 * Return value: an iterator pointing to the new item
473 g_sequence_prepend (GSequence *seq,
476 GSequenceNode *node, *first;
478 g_return_val_if_fail (seq != NULL, NULL);
480 check_seq_access (seq);
482 node = node_new (data);
483 first = node_get_first (seq->end_node);
485 node_insert_before (first, node);
491 * g_sequence_insert_before:
492 * @iter: a #GSequenceIter
493 * @data: the data for the new item
495 * Inserts a new item just before the item pointed to by @iter.
497 * Return value: an iterator pointing to the new item
502 g_sequence_insert_before (GSequenceIter *iter,
507 g_return_val_if_fail (iter != NULL, NULL);
509 check_iter_access (iter);
511 node = node_new (data);
513 node_insert_before (iter, node);
520 * @iter: a #GSequenceIter
522 * Removes the item pointed to by @iter. It is an error to pass the
523 * end iterator to this function.
525 * If the sequence has a data destroy function associated with it, this
526 * function is called on the data for the removed item.
531 g_sequence_remove (GSequenceIter *iter)
535 g_return_if_fail (iter != NULL);
536 g_return_if_fail (!is_end (iter));
538 check_iter_access (iter);
540 seq = get_sequence (iter);
543 node_free (iter, seq);
547 * g_sequence_remove_range:
548 * @begin: a #GSequenceIter
549 * @end: a #GSequenceIter
551 * Removes all items in the (@begin, @end) range.
553 * If the sequence has a data destroy function associated with it, this
554 * function is called on the data for the removed items.
559 g_sequence_remove_range (GSequenceIter *begin,
562 g_return_if_fail (get_sequence (begin) == get_sequence (end));
564 check_iter_access (begin);
565 check_iter_access (end);
567 g_sequence_move_range (NULL, begin, end);
571 * g_sequence_move_range:
572 * @dest: a #GSequenceIter
573 * @begin: a #GSequenceIter
574 * @end: a #GSequenceIter
576 * Inserts the (@begin, @end) range at the destination pointed to by ptr.
577 * The @begin and @end iters must point into the same sequence. It is
578 * allowed for @dest to point to a different sequence than the one pointed
579 * into by @begin and @end.
581 * If @dest is NULL, the range indicated by @begin and @end is
582 * removed from the sequence. If @dest iter points to a place within
583 * the (@begin, @end) range, the range does not move.
588 g_sequence_move_range (GSequenceIter *dest,
589 GSequenceIter *begin,
593 GSequenceNode *first;
595 g_return_if_fail (begin != NULL);
596 g_return_if_fail (end != NULL);
598 check_iter_access (begin);
599 check_iter_access (end);
601 check_iter_access (dest);
603 src_seq = get_sequence (begin);
605 g_return_if_fail (src_seq == get_sequence (end));
607 /* Dest points to begin or end? */
608 if (dest == begin || dest == end)
611 /* begin comes after end? */
612 if (g_sequence_iter_compare (begin, end) >= 0)
615 /* dest points somewhere in the (begin, end) range? */
616 if (dest && get_sequence (dest) == src_seq &&
617 g_sequence_iter_compare (dest, begin) > 0 &&
618 g_sequence_iter_compare (dest, end) < 0)
623 src_seq = get_sequence (begin);
625 first = node_get_first (begin);
632 node_join (first, end);
636 first = node_get_first (dest);
640 node_join (begin, dest);
643 node_join (first, begin);
647 node_free (begin, src_seq);
654 * @cmp_func: the function used to sort the sequence
655 * @cmp_data: user data passed to @cmp_func
657 * Sorts @seq using @cmp_func.
659 * @cmp_func is passed two items of @seq and should
660 * return 0 if they are equal, a negative value if the
661 * first comes before the second, and a positive value
662 * if the second comes before the first.
667 g_sequence_sort (GSequence *seq,
668 GCompareDataFunc cmp_func,
673 info.cmp_func = cmp_func;
674 info.cmp_data = cmp_data;
675 info.end_node = seq->end_node;
677 check_seq_access (seq);
679 g_sequence_sort_iter (seq, iter_compare, &info);
683 * g_sequence_insert_sorted:
685 * @data: the data to insert
686 * @cmp_func: the function used to compare items in the sequence
687 * @cmp_data: user data passed to @cmp_func.
689 * Inserts @data into @sequence using @func to determine the new
690 * position. The sequence must already be sorted according to @cmp_func;
691 * otherwise the new position of @data is undefined.
693 * @cmp_func is called with two items of the @seq and @user_data.
694 * It should return 0 if the items are equal, a negative value
695 * if the first item comes before the second, and a positive value
696 * if the second item comes before the first.
698 * Return value: a #GSequenceIter pointing to the new item.
703 g_sequence_insert_sorted (GSequence *seq,
705 GCompareDataFunc cmp_func,
710 g_return_val_if_fail (seq != NULL, NULL);
711 g_return_val_if_fail (cmp_func != NULL, NULL);
713 info.cmp_func = cmp_func;
714 info.cmp_data = cmp_data;
715 info.end_node = seq->end_node;
716 check_seq_access (seq);
718 return g_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
722 * g_sequence_sort_changed:
723 * @iter: A #GSequenceIter
724 * @cmp_func: the function used to compare items in the sequence
725 * @cmp_data: user data passed to @cmp_func.
727 * Moves the data pointed to a new position as indicated by @cmp_func. This
728 * function should be called for items in a sequence already sorted according
729 * to @cmp_func whenever some aspect of an item changes so that @cmp_func
730 * may return different values for that item.
732 * @cmp_func is called with two items of the @seq and @user_data.
733 * It should return 0 if the items are equal, a negative value if
734 * the first item comes before the second, and a positive value if
735 * the second item comes before the first.
740 g_sequence_sort_changed (GSequenceIter *iter,
741 GCompareDataFunc cmp_func,
746 g_return_if_fail (!is_end (iter));
748 info.cmp_func = cmp_func;
749 info.cmp_data = cmp_data;
750 info.end_node = get_sequence (iter)->end_node;
751 check_iter_access (iter);
753 g_sequence_sort_changed_iter (iter, iter_compare, &info);
759 * @data: data for the new item
760 * @cmp_func: the function used to compare items in the sequence
761 * @cmp_data: user data passed to @cmp_func.
763 * Returns an iterator pointing to the position where @data would
764 * be inserted according to @cmp_func and @cmp_data.
766 * @cmp_func is called with two items of the @seq and @user_data.
767 * It should return 0 if the items are equal, a negative value if
768 * the first item comes before the second, and a positive value if
769 * the second item comes before the first.
771 * If you are simply searching for an existing element of the sequence,
772 * consider using g_sequence_lookup().
775 * This function will fail if the data contained in the sequence is
776 * unsorted. Use g_sequence_insert_sorted() or
777 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
778 * you want to add a large amount of data, call g_sequence_sort() after
779 * doing unsorted insertions.
782 * Return value: an #GSequenceIter pointing to the position where @data
783 * would have been inserted according to @cmp_func and @cmp_data.
788 g_sequence_search (GSequence *seq,
790 GCompareDataFunc cmp_func,
795 g_return_val_if_fail (seq != NULL, NULL);
797 info.cmp_func = cmp_func;
798 info.cmp_data = cmp_data;
799 info.end_node = seq->end_node;
800 check_seq_access (seq);
802 return g_sequence_search_iter (seq, data, iter_compare, &info);
808 * @data: data to lookup
809 * @cmp_func: the function used to compare items in the sequence
810 * @cmp_data: user data passed to @cmp_func.
812 * Returns an iterator pointing to the position of the first item found
813 * equal to @data according to @cmp_func and @cmp_data. If more than one
814 * item is equal, it is not guaranteed that it is the first which is
815 * returned. In that case, you can use g_sequence_iter_next() and
816 * g_sequence_iter_prev() to get others.
818 * @cmp_func is called with two items of the @seq and @user_data.
819 * It should return 0 if the items are equal, a negative value if
820 * the first item comes before the second, and a positive value if
821 * the second item comes before the first.
824 * This function will fail if the data contained in the sequence is
825 * unsorted. Use g_sequence_insert_sorted() or
826 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
827 * you want to add a large amount of data, call g_sequence_sort() after
828 * doing unsorted insertions.
831 * Return value: an #GSequenceIter pointing to the position of the
832 * first item found equal to @data according to @cmp_func and @cmp_data.
837 g_sequence_lookup (GSequence *seq,
839 GCompareDataFunc cmp_func,
844 g_return_val_if_fail (seq != NULL, NULL);
846 info.cmp_func = cmp_func;
847 info.cmp_data = cmp_data;
848 info.end_node = seq->end_node;
849 check_seq_access (seq);
851 return g_sequence_lookup_iter (seq, data, iter_compare, &info);
855 * g_sequence_sort_iter:
857 * @cmp_func: the function used to compare iterators in the sequence
858 * @cmp_data: user data passed to @cmp_func
860 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
861 * of a GCompareDataFunc as the compare function
863 * @cmp_func is called with two iterators pointing into @seq. It should
864 * return 0 if the iterators are equal, a negative value if the first
865 * iterator comes before the second, and a positive value if the second
866 * iterator comes before the first.
871 g_sequence_sort_iter (GSequence *seq,
872 GSequenceIterCompareFunc cmp_func,
876 GSequenceNode *begin, *end;
878 g_return_if_fail (seq != NULL);
879 g_return_if_fail (cmp_func != NULL);
881 check_seq_access (seq);
883 begin = g_sequence_get_begin_iter (seq);
884 end = g_sequence_get_end_iter (seq);
886 tmp = g_sequence_new (NULL);
887 tmp->real_sequence = seq;
889 g_sequence_move_range (g_sequence_get_begin_iter (tmp), begin, end);
891 seq->access_prohibited = TRUE;
892 tmp->access_prohibited = TRUE;
894 while (g_sequence_get_length (tmp) > 0)
896 GSequenceNode *node = g_sequence_get_begin_iter (tmp);
898 node_insert_sorted (seq->end_node, node, seq->end_node,
902 tmp->access_prohibited = FALSE;
903 seq->access_prohibited = FALSE;
905 g_sequence_free (tmp);
909 * g_sequence_sort_changed_iter:
910 * @iter: a #GSequenceIter
911 * @iter_cmp: the function used to compare iterators in the sequence
912 * @cmp_data: user data passed to @cmp_func
914 * Like g_sequence_sort_changed(), but uses
915 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
916 * the compare function.
918 * @iter_cmp is called with two iterators pointing into @seq. It should
919 * return 0 if the iterators are equal, a negative value if the first
920 * iterator comes before the second, and a positive value if the second
921 * iterator comes before the first.
926 g_sequence_sort_changed_iter (GSequenceIter *iter,
927 GSequenceIterCompareFunc iter_cmp,
930 GSequence *seq, *tmp_seq;
931 GSequenceIter *next, *prev;
933 g_return_if_fail (iter != NULL);
934 g_return_if_fail (!is_end (iter));
935 g_return_if_fail (iter_cmp != NULL);
936 check_iter_access (iter);
938 /* If one of the neighbours is equal to iter, then
939 * don't move it. This ensures that sort_changed() is
940 * a stable operation.
943 next = node_get_next (iter);
944 prev = node_get_prev (iter);
946 if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
949 if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
952 seq = get_sequence (iter);
954 seq->access_prohibited = TRUE;
956 tmp_seq = g_sequence_new (NULL);
957 tmp_seq->real_sequence = seq;
960 node_insert_before (tmp_seq->end_node, iter);
962 node_insert_sorted (seq->end_node, iter, seq->end_node,
965 g_sequence_free (tmp_seq);
967 seq->access_prohibited = FALSE;
971 * g_sequence_insert_sorted_iter:
973 * @data: data for the new item
974 * @iter_cmp: the function used to compare iterators in the sequence
975 * @cmp_data: user data passed to @cmp_func
977 * Like g_sequence_insert_sorted(), but uses
978 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
979 * the compare function.
981 * @iter_cmp is called with two iterators pointing into @seq.
982 * It should return 0 if the iterators are equal, a negative
983 * value if the first iterator comes before the second, and a
984 * positive value if the second iterator comes before the first.
986 * It is called with two iterators pointing into @seq. It should
987 * return 0 if the iterators are equal, a negative value if the
988 * first iterator comes before the second, and a positive value
989 * if the second iterator comes before the first.
991 * Return value: a #GSequenceIter pointing to the new item
996 g_sequence_insert_sorted_iter (GSequence *seq,
998 GSequenceIterCompareFunc iter_cmp,
1001 GSequenceNode *new_node;
1004 g_return_val_if_fail (seq != NULL, NULL);
1005 g_return_val_if_fail (iter_cmp != NULL, NULL);
1007 check_seq_access (seq);
1009 seq->access_prohibited = TRUE;
1011 /* Create a new temporary sequence and put the new node into
1012 * that. The reason for this is that the user compare function
1013 * will be called with the new node, and if it dereferences,
1014 * "is_end" will be called on it. But that will crash if the
1015 * node is not actually in a sequence.
1017 * node_insert_sorted() makes sure the node is unlinked before
1020 * The reason we need the "iter" versions at all is that that
1021 * is the only kind of compare functions GtkTreeView can use.
1023 tmp_seq = g_sequence_new (NULL);
1024 tmp_seq->real_sequence = seq;
1026 new_node = g_sequence_append (tmp_seq, data);
1028 node_insert_sorted (seq->end_node, new_node,
1029 seq->end_node, iter_cmp, cmp_data);
1031 g_sequence_free (tmp_seq);
1033 seq->access_prohibited = FALSE;
1039 * g_sequence_search_iter:
1040 * @seq: a #GSequence
1041 * @data: data for the new item
1042 * @iter_cmp: the function used to compare iterators in the sequence
1043 * @cmp_data: user data passed to @iter_cmp
1045 * Like g_sequence_search(), but uses a #GSequenceIterCompareFunc
1046 * instead of a #GCompareDataFunc as the compare function.
1048 * @iter_cmp is called with two iterators pointing into @seq.
1049 * It should return 0 if the iterators are equal, a negative value
1050 * if the first iterator comes before the second, and a positive
1051 * value if the second iterator comes before the first.
1053 * If you are simply searching for an existing element of the sequence,
1054 * consider using g_sequence_lookup_iter().
1057 * This function will fail if the data contained in the sequence is
1058 * unsorted. Use g_sequence_insert_sorted() or
1059 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
1060 * you want to add a large amount of data, call g_sequence_sort() after
1061 * doing unsorted insertions.
1064 * Return value: a #GSequenceIter pointing to the position in @seq
1065 * where @data would have been inserted according to @iter_cmp
1071 g_sequence_search_iter (GSequence *seq,
1073 GSequenceIterCompareFunc iter_cmp,
1076 GSequenceNode *node;
1077 GSequenceNode *dummy;
1080 g_return_val_if_fail (seq != NULL, NULL);
1082 check_seq_access (seq);
1084 seq->access_prohibited = TRUE;
1086 tmp_seq = g_sequence_new (NULL);
1087 tmp_seq->real_sequence = seq;
1089 dummy = g_sequence_append (tmp_seq, data);
1091 node = node_find_closest (seq->end_node, dummy,
1092 seq->end_node, iter_cmp, cmp_data);
1094 g_sequence_free (tmp_seq);
1096 seq->access_prohibited = FALSE;
1102 * g_sequence_lookup_iter:
1103 * @seq: a #GSequence
1104 * @data: data to lookup
1105 * @iter_cmp: the function used to compare iterators in the sequence
1106 * @cmp_data: user data passed to @iter_cmp
1108 * Like g_sequence_lookup(), but uses a #GSequenceIterCompareFunc
1109 * instead of a #GCompareDataFunc as the compare function.
1111 * @iter_cmp is called with two iterators pointing into @seq.
1112 * It should return 0 if the iterators are equal, a negative value
1113 * if the first iterator comes before the second, and a positive
1114 * value if the second iterator comes before the first.
1117 * This function will fail if the data contained in the sequence is
1118 * unsorted. Use g_sequence_insert_sorted() or
1119 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
1120 * you want to add a large amount of data, call g_sequence_sort() after
1121 * doing unsorted insertions.
1124 * Return value: an #GSequenceIter pointing to the position of
1125 * the first item found equal to @data according to @cmp_func
1131 g_sequence_lookup_iter (GSequence *seq,
1133 GSequenceIterCompareFunc iter_cmp,
1136 GSequenceNode *node;
1137 GSequenceNode *dummy;
1140 g_return_val_if_fail (seq != NULL, NULL);
1142 check_seq_access (seq);
1144 seq->access_prohibited = TRUE;
1146 tmp_seq = g_sequence_new (NULL);
1147 tmp_seq->real_sequence = seq;
1149 dummy = g_sequence_append (tmp_seq, data);
1151 node = node_find (seq->end_node, dummy,
1152 seq->end_node, iter_cmp, cmp_data);
1154 g_sequence_free (tmp_seq);
1156 seq->access_prohibited = FALSE;
1162 * g_sequence_iter_get_sequence:
1163 * @iter: a #GSequenceIter
1165 * Returns the #GSequence that @iter points into.
1167 * Return value: the #GSequence that @iter points into.
1172 g_sequence_iter_get_sequence (GSequenceIter *iter)
1176 g_return_val_if_fail (iter != NULL, NULL);
1178 seq = get_sequence (iter);
1180 /* For temporary sequences, this points to the sequence that
1181 * is actually being manipulated
1183 return seq->real_sequence;
1188 * @iter: a #GSequenceIter
1190 * Returns the data that @iter points to.
1192 * Return value: the data that @iter points to
1197 g_sequence_get (GSequenceIter *iter)
1199 g_return_val_if_fail (iter != NULL, NULL);
1200 g_return_val_if_fail (!is_end (iter), NULL);
1207 * @iter: a #GSequenceIter
1208 * @data: new data for the item
1210 * Changes the data for the item pointed to by @iter to be @data. If
1211 * the sequence has a data destroy function associated with it, that
1212 * function is called on the existing data that @iter pointed to.
1217 g_sequence_set (GSequenceIter *iter,
1222 g_return_if_fail (iter != NULL);
1223 g_return_if_fail (!is_end (iter));
1225 seq = get_sequence (iter);
1227 /* If @data is identical to iter->data, it is destroyed
1228 * here. This will work right in case of ref-counted objects. Also
1229 * it is similar to what ghashtables do.
1231 * For non-refcounted data it's a little less convenient, but
1232 * code relying on self-setting not destroying would be
1233 * pretty dubious anyway ...
1236 if (seq->data_destroy_notify)
1237 seq->data_destroy_notify (iter->data);
1243 * g_sequence_get_length:
1244 * @seq: a #GSequence
1246 * Returns the length of @seq
1248 * Return value: the length of @seq
1253 g_sequence_get_length (GSequence *seq)
1255 return node_get_length (seq->end_node) - 1;
1259 * g_sequence_get_end_iter:
1260 * @seq: a #GSequence
1262 * Returns the end iterator for @seg
1264 * Return value: the end iterator for @seq
1269 g_sequence_get_end_iter (GSequence *seq)
1271 g_return_val_if_fail (seq != NULL, NULL);
1273 return seq->end_node;
1277 * g_sequence_get_begin_iter:
1278 * @seq: a #GSequence
1280 * Returns the begin iterator for @seq.
1282 * Return value: the begin iterator for @seq.
1287 g_sequence_get_begin_iter (GSequence *seq)
1289 g_return_val_if_fail (seq != NULL, NULL);
1291 return node_get_first (seq->end_node);
1295 clamp_position (GSequence *seq,
1298 gint len = g_sequence_get_length (seq);
1300 if (pos > len || pos < 0)
1307 * if pos > number of items or -1, will return end pointer
1310 * g_sequence_get_iter_at_pos:
1311 * @seq: a #GSequence
1312 * @pos: a position in @seq, or -1 for the end.
1314 * Returns the iterator at position @pos. If @pos is negative or larger
1315 * than the number of items in @seq, the end iterator is returned.
1317 * Return value: The #GSequenceIter at position @pos
1322 g_sequence_get_iter_at_pos (GSequence *seq,
1325 g_return_val_if_fail (seq != NULL, NULL);
1327 pos = clamp_position (seq, pos);
1329 return node_get_by_pos (seq->end_node, pos);
1334 * @src: a #GSequenceIter pointing to the item to move
1335 * @dest: a #GSequenceIter pointing to the position to which
1336 * the item is moved.
1338 * Moves the item pointed to by @src to the position indicated by @dest.
1339 * After calling this function @dest will point to the position immediately
1340 * after @src. It is allowed for @src and @dest to point into different
1346 g_sequence_move (GSequenceIter *src,
1347 GSequenceIter *dest)
1349 g_return_if_fail (src != NULL);
1350 g_return_if_fail (dest != NULL);
1351 g_return_if_fail (!is_end (src));
1357 node_insert_before (dest, src);
1363 * g_sequence_iter_is_end:
1364 * @iter: a #GSequenceIter
1366 * Returns whether @iter is the end iterator
1368 * Return value: Whether @iter is the end iterator.
1373 g_sequence_iter_is_end (GSequenceIter *iter)
1375 g_return_val_if_fail (iter != NULL, FALSE);
1377 return is_end (iter);
1381 * g_sequence_iter_is_begin:
1382 * @iter: a #GSequenceIter
1384 * Returns whether @iter is the begin iterator
1386 * Return value: whether @iter is the begin iterator
1391 g_sequence_iter_is_begin (GSequenceIter *iter)
1393 g_return_val_if_fail (iter != NULL, FALSE);
1395 return (node_get_prev (iter) == iter);
1399 * g_sequence_iter_get_position:
1400 * @iter: a #GSequenceIter
1402 * Returns the position of @iter
1404 * Return value: the position of @iter
1409 g_sequence_iter_get_position (GSequenceIter *iter)
1411 g_return_val_if_fail (iter != NULL, -1);
1413 return node_get_pos (iter);
1417 * g_sequence_iter_next:
1418 * @iter: a #GSequenceIter
1420 * Returns an iterator pointing to the next position after @iter. If
1421 * @iter is the end iterator, the end iterator is returned.
1423 * Return value: a #GSequenceIter pointing to the next position after @iter.
1428 g_sequence_iter_next (GSequenceIter *iter)
1430 g_return_val_if_fail (iter != NULL, NULL);
1432 return node_get_next (iter);
1436 * g_sequence_iter_prev:
1437 * @iter: a #GSequenceIter
1439 * Returns an iterator pointing to the previous position before @iter. If
1440 * @iter is the begin iterator, the begin iterator is returned.
1442 * Return value: a #GSequenceIter pointing to the previous position before
1448 g_sequence_iter_prev (GSequenceIter *iter)
1450 g_return_val_if_fail (iter != NULL, NULL);
1452 return node_get_prev (iter);
1456 * g_sequence_iter_move:
1457 * @iter: a #GSequenceIter
1458 * @delta: A positive or negative number indicating how many positions away
1459 * from @iter the returned #GSequenceIter will be.
1461 * Returns the #GSequenceIter which is @delta positions away from @iter.
1462 * If @iter is closer than -@delta positions to the beginning of the sequence,
1463 * the begin iterator is returned. If @iter is closer than @delta positions
1464 * to the end of the sequence, the end iterator is returned.
1466 * Return value: a #GSequenceIter which is @delta positions away from @iter.
1471 g_sequence_iter_move (GSequenceIter *iter,
1477 g_return_val_if_fail (iter != NULL, NULL);
1479 len = g_sequence_get_length (get_sequence (iter));
1481 new_pos = node_get_pos (iter) + delta;
1485 else if (new_pos > len)
1488 return node_get_by_pos (iter, new_pos);
1493 * @a: a #GSequenceIter
1494 * @b: a #GSequenceIter
1496 * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
1497 * to point into difference sequences.
1502 g_sequence_swap (GSequenceIter *a,
1505 GSequenceNode *leftmost, *rightmost, *rightmost_next;
1508 g_return_if_fail (!g_sequence_iter_is_end (a));
1509 g_return_if_fail (!g_sequence_iter_is_end (b));
1514 a_pos = g_sequence_iter_get_position (a);
1515 b_pos = g_sequence_iter_get_position (b);
1528 rightmost_next = node_get_next (rightmost);
1530 /* The situation is now like this:
1532 * ..., leftmost, ......., rightmost, rightmost_next, ...
1535 g_sequence_move (rightmost, leftmost);
1536 g_sequence_move (leftmost, rightmost_next);
1540 * Implementation of a treap
1545 get_priority (GSequenceNode *node)
1547 guint key = GPOINTER_TO_UINT (node);
1549 /* This hash function is based on one found on Thomas Wang's
1552 * http://www.concentric.net/~Ttwang/tech/inthash.htm
1555 key = (key << 15) - key - 1;
1556 key = key ^ (key >> 12);
1557 key = key + (key << 2);
1558 key = key ^ (key >> 4);
1559 key = key + (key << 3) + (key << 11);
1560 key = key ^ (key >> 16);
1562 /* We rely on 0 being less than all other priorities */
1563 return key? key : 1;
1566 static GSequenceNode *
1567 find_root (GSequenceNode *node)
1569 while (node->parent)
1570 node = node->parent;
1575 static GSequenceNode *
1576 node_new (gpointer data)
1578 GSequenceNode *node = g_slice_new0 (GSequenceNode);
1584 node->parent = NULL;
1589 static GSequenceNode *
1590 node_get_first (GSequenceNode *node)
1592 node = find_root (node);
1600 static GSequenceNode *
1601 node_get_last (GSequenceNode *node)
1603 node = find_root (node);
1611 #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1612 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1614 static GSequenceNode *
1615 node_get_next (GSequenceNode *node)
1617 GSequenceNode *n = node;
1627 while (NODE_RIGHT_CHILD (n))
1639 static GSequenceNode *
1640 node_get_prev (GSequenceNode *node)
1642 GSequenceNode *n = node;
1652 while (NODE_LEFT_CHILD (n))
1664 #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1667 node_get_pos (GSequenceNode *node)
1672 n_smaller = node->left->n_nodes;
1676 if (NODE_RIGHT_CHILD (node))
1677 n_smaller += N_NODES (node->parent->left) + 1;
1679 node = node->parent;
1685 static GSequenceNode *
1686 node_get_by_pos (GSequenceNode *node,
1691 node = find_root (node);
1693 while ((i = N_NODES (node->left)) != pos)
1709 static GSequenceNode *
1710 node_find (GSequenceNode *haystack,
1711 GSequenceNode *needle,
1713 GSequenceIterCompareFunc iter_cmp,
1718 haystack = find_root (haystack);
1722 /* iter_cmp can't be passed the end node, since the function may
1725 if (haystack == end)
1728 c = iter_cmp (haystack, needle, cmp_data);
1734 haystack = haystack->left;
1736 haystack = haystack->right;
1738 while (haystack != NULL);
1743 static GSequenceNode *
1744 node_find_closest (GSequenceNode *haystack,
1745 GSequenceNode *needle,
1747 GSequenceIterCompareFunc iter_cmp,
1750 GSequenceNode *best;
1753 haystack = find_root (haystack);
1759 /* iter_cmp can't be passed the end node, since the function may
1762 if (haystack == end)
1765 c = iter_cmp (haystack, needle, cmp_data);
1767 /* In the following we don't break even if c == 0. Instead we go on
1768 * searching along the 'bigger' nodes, so that we find the last one
1769 * that is equal to the needle.
1772 haystack = haystack->left;
1774 haystack = haystack->right;
1776 while (haystack != NULL);
1778 /* If the best node is smaller or equal to the data, then move one step
1779 * to the right to make sure the best one is strictly bigger than the data
1781 if (best != end && c <= 0)
1782 best = node_get_next (best);
1788 node_get_length (GSequenceNode *node)
1790 node = find_root (node);
1792 return node->n_nodes;
1796 real_node_free (GSequenceNode *node,
1801 real_node_free (node->left, seq);
1802 real_node_free (node->right, seq);
1804 if (seq && seq->data_destroy_notify && node != seq->end_node)
1805 seq->data_destroy_notify (node->data);
1807 g_slice_free (GSequenceNode, node);
1812 node_free (GSequenceNode *node,
1815 node = find_root (node);
1817 real_node_free (node, seq);
1821 node_update_fields (GSequenceNode *node)
1825 n_nodes += N_NODES (node->left);
1826 n_nodes += N_NODES (node->right);
1828 node->n_nodes = n_nodes;
1832 node_rotate (GSequenceNode *node)
1834 GSequenceNode *tmp, *old;
1836 g_assert (node->parent);
1837 g_assert (node->parent != node);
1839 if (NODE_LEFT_CHILD (node))
1844 node->right = node->parent;
1845 node->parent = node->parent->parent;
1848 if (node->parent->left == node->right)
1849 node->parent->left = node;
1851 node->parent->right = node;
1854 g_assert (node->right);
1856 node->right->parent = node;
1857 node->right->left = tmp;
1859 if (node->right->left)
1860 node->right->left->parent = node->right;
1869 node->left = node->parent;
1870 node->parent = node->parent->parent;
1873 if (node->parent->right == node->left)
1874 node->parent->right = node;
1876 node->parent->left = node;
1879 g_assert (node->left);
1881 node->left->parent = node;
1882 node->left->right = tmp;
1884 if (node->left->right)
1885 node->left->right->parent = node->left;
1890 node_update_fields (old);
1891 node_update_fields (node);
1895 node_update_fields_deep (GSequenceNode *node)
1899 node_update_fields (node);
1901 node_update_fields_deep (node->parent);
1906 rotate_down (GSequenceNode *node,
1911 left = node->left ? get_priority (node->left) : 0;
1912 right = node->right ? get_priority (node->right) : 0;
1914 while (priority < left || priority < right)
1917 node_rotate (node->left);
1919 node_rotate (node->right);
1921 left = node->left ? get_priority (node->left) : 0;
1922 right = node->right ? get_priority (node->right) : 0;
1927 node_cut (GSequenceNode *node)
1929 while (node->parent)
1933 node->left->parent = NULL;
1936 node_update_fields (node);
1938 rotate_down (node, get_priority (node));
1942 node_join (GSequenceNode *left,
1943 GSequenceNode *right)
1945 GSequenceNode *fake = node_new (NULL);
1947 fake->left = find_root (left);
1948 fake->right = find_root (right);
1949 fake->left->parent = fake;
1950 fake->right->parent = fake;
1952 node_update_fields (fake);
1956 node_free (fake, NULL);
1960 node_insert_before (GSequenceNode *node,
1963 new->left = node->left;
1965 new->left->parent = new;
1970 node_update_fields_deep (new);
1972 while (new->parent && get_priority (new) > get_priority (new->parent))
1975 rotate_down (new, get_priority (new));
1979 node_unlink (GSequenceNode *node)
1981 rotate_down (node, 0);
1983 if (NODE_RIGHT_CHILD (node))
1984 node->parent->right = NULL;
1985 else if (NODE_LEFT_CHILD (node))
1986 node->parent->left = NULL;
1989 node_update_fields_deep (node->parent);
1991 node->parent = NULL;
1995 node_insert_sorted (GSequenceNode *node,
1998 GSequenceIterCompareFunc iter_cmp,
2001 GSequenceNode *closest;
2003 closest = node_find_closest (node, new, end, iter_cmp, cmp_data);
2007 node_insert_before (closest, new);