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"
30 * @short_description: scalable lists
32 * The #GSequence data structure has the API of a list, but is
33 * implemented internally with a balanced binary tree. This means that
34 * it is possible to maintain a sorted list of n elements in time O(n
35 * log n). The data contained in each element can be either integer
36 * values, by using of the <link
37 * linkend="glib-Type-Conversion-Macros">Type Conversion Macros</link>,
38 * or simply pointers to any type of data.
40 * A #GSequence is accessed through <firstterm>iterators</firstterm>,
41 * represented by a #GSequenceIter. An iterator represents a position
42 * between two elements of the sequence. For example, the
43 * <firstterm>begin</firstterm> iterator represents the gap immediately
44 * before the first element of the sequence, and the
45 * <firstterm>end</firstterm> iterator represents the gap immediately
46 * after the last element. In an empty sequence, the begin and end
47 * iterators are the same.
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
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 <firstterm>point</firstterm> to that element.
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.
72 * The #GSequenceIter struct is an opaque data type representing an
73 * iterator pointing into a #GSequence.
77 * GSequenceIterCompareFunc:
78 * @a: a #GSequenceIter
79 * @b: a #GSequenceIter
81 * @Returns: zero if the iterators are equal, a negative value if @a
82 * comes before @b, and a positive value if @b comes before
85 * A #GSequenceIterCompareFunc is a function used to compare iterators.
86 * It must return zero if the iterators compare equal, a negative value
87 * if @a comes before @b, and a positive value if @b comes before @a.
90 typedef struct _GSequenceNode GSequenceNode;
95 * The #GSequence struct is an opaque data type representing a
96 * <link linkend="glib-Sequences">Sequence</link> data type.
100 GSequenceNode * end_node;
101 GDestroyNotify data_destroy_notify;
102 gboolean access_prohibited;
104 /* The 'real_sequence' is used when temporary sequences are created
105 * to hold nodes that are being rearranged. The 'real_sequence' of such
106 * a temporary sequence points to the sequence that is actually being
107 * manipulated. The only reason we need this is so that when the
108 * sort/sort_changed/search_iter() functions call out to the application
109 * g_sequence_iter_get_sequence() will return the correct sequence.
111 GSequence * real_sequence;
114 struct _GSequenceNode
117 GSequenceNode * parent;
118 GSequenceNode * left;
119 GSequenceNode * right;
120 gpointer data; /* For the end node, this field points
126 * Declaration of GSequenceNode methods
128 static GSequenceNode *node_new (gpointer data);
129 static GSequenceNode *node_get_first (GSequenceNode *node);
130 static GSequenceNode *node_get_last (GSequenceNode *node);
131 static GSequenceNode *node_get_prev (GSequenceNode *node);
132 static GSequenceNode *node_get_next (GSequenceNode *node);
133 static gint node_get_pos (GSequenceNode *node);
134 static GSequenceNode *node_get_by_pos (GSequenceNode *node,
136 static GSequenceNode *node_find (GSequenceNode *haystack,
137 GSequenceNode *needle,
139 GSequenceIterCompareFunc cmp,
141 static GSequenceNode *node_find_closest (GSequenceNode *haystack,
142 GSequenceNode *needle,
144 GSequenceIterCompareFunc cmp,
146 static gint node_get_length (GSequenceNode *node);
147 static void node_free (GSequenceNode *node,
149 static void node_cut (GSequenceNode *split);
150 static void node_insert_before (GSequenceNode *node,
152 static void node_unlink (GSequenceNode *node);
153 static void node_join (GSequenceNode *left,
154 GSequenceNode *right);
155 static void node_insert_sorted (GSequenceNode *node,
158 GSequenceIterCompareFunc cmp_func,
163 * Various helper functions
166 check_seq_access (GSequence *seq)
168 if (G_UNLIKELY (seq->access_prohibited))
170 g_warning ("Accessing a sequence while it is "
171 "being sorted or searched is not allowed");
176 get_sequence (GSequenceNode *node)
178 return (GSequence *)node_get_last (node)->data;
182 check_iter_access (GSequenceIter *iter)
184 check_seq_access (get_sequence (iter));
188 is_end (GSequenceIter *iter)
198 if (iter->parent->right != iter)
201 seq = get_sequence (iter);
203 return seq->end_node == iter;
208 GCompareDataFunc cmp_func;
210 GSequenceNode *end_node;
213 /* This function compares two iters using a normal compare
214 * function and user_data passed in in a SortInfo struct
217 iter_compare (GSequenceIter *node1,
218 GSequenceIter *node2,
221 const SortInfo *info = data;
224 if (node1 == info->end_node)
227 if (node2 == info->end_node)
230 retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
241 * @data_destroy: a #GDestroyNotify function, or %NULL
243 * Creates a new GSequence. The @data_destroy function, if non-%NULL will
244 * be called on all items when the sequence is destroyed and on items that
245 * are removed from the sequence.
247 * Return value: a new #GSequence
252 g_sequence_new (GDestroyNotify data_destroy)
254 GSequence *seq = g_new (GSequence, 1);
255 seq->data_destroy_notify = data_destroy;
257 seq->end_node = node_new (seq);
259 seq->access_prohibited = FALSE;
261 seq->real_sequence = seq;
270 * Frees the memory allocated for @seq. If @seq has a data destroy
271 * function associated with it, that function is called on all items in
277 g_sequence_free (GSequence *seq)
279 g_return_if_fail (seq != NULL);
281 check_seq_access (seq);
283 node_free (seq->end_node, seq);
289 * g_sequence_foreach_range:
290 * @begin: a #GSequenceIter
291 * @end: a #GSequenceIter
293 * @user_data: user data passed to @func
295 * Calls @func for each item in the range (@begin, @end) passing
296 * @user_data to the function.
301 g_sequence_foreach_range (GSequenceIter *begin,
309 g_return_if_fail (func != NULL);
310 g_return_if_fail (begin != NULL);
311 g_return_if_fail (end != NULL);
313 seq = get_sequence (begin);
315 seq->access_prohibited = TRUE;
320 GSequenceIter *next = node_get_next (iter);
322 func (iter->data, user_data);
327 seq->access_prohibited = FALSE;
331 * g_sequence_foreach:
333 * @func: the function to call for each item in @seq
334 * @user_data: user data passed to @func
336 * Calls @func for each item in the sequence passing @user_data
342 g_sequence_foreach (GSequence *seq,
346 GSequenceIter *begin, *end;
348 check_seq_access (seq);
350 begin = g_sequence_get_begin_iter (seq);
351 end = g_sequence_get_end_iter (seq);
353 g_sequence_foreach_range (begin, end, func, user_data);
357 * g_sequence_range_get_midpoint:
358 * @begin: a #GSequenceIter
359 * @end: a #GSequenceIter
361 * Finds an iterator somewhere in the range (@begin, @end). This
362 * iterator will be close to the middle of the range, but is not
363 * guaranteed to be <emphasis>exactly</emphasis> in the middle.
365 * The @begin and @end iterators must both point to the same sequence and
366 * @begin must come before or be equal to @end in the sequence.
368 * Return value: A #GSequenceIter pointing somewhere in the
369 * (@begin, @end) range.
374 g_sequence_range_get_midpoint (GSequenceIter *begin,
377 int begin_pos, end_pos, mid_pos;
379 g_return_val_if_fail (begin != NULL, NULL);
380 g_return_val_if_fail (end != NULL, NULL);
381 g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
383 begin_pos = node_get_pos (begin);
384 end_pos = node_get_pos (end);
386 g_return_val_if_fail (end_pos >= begin_pos, NULL);
388 mid_pos = begin_pos + (end_pos - begin_pos) / 2;
390 return node_get_by_pos (begin, mid_pos);
394 * g_sequence_iter_compare:
395 * @a: a #GSequenceIter
396 * @b: a #GSequenceIter
398 * Returns a negative number if @a comes before @b, 0 if they are equal,
399 * and a positive number if @a comes after @b.
401 * The @a and @b iterators must point into the same sequence.
403 * Return value: A negative number if @a comes before @b, 0 if they are
404 * equal, and a positive number if @a comes after @b.
409 g_sequence_iter_compare (GSequenceIter *a,
414 g_return_val_if_fail (a != NULL, 0);
415 g_return_val_if_fail (b != NULL, 0);
416 g_return_val_if_fail (get_sequence (a) == get_sequence (b), 0);
418 check_iter_access (a);
419 check_iter_access (b);
421 a_pos = node_get_pos (a);
422 b_pos = node_get_pos (b);
426 else if (a_pos > b_pos)
435 * @data: the data for the new item
437 * Adds a new item to the end of @seq.
439 * Return value: an iterator pointing to the new item
444 g_sequence_append (GSequence *seq,
449 g_return_val_if_fail (seq != NULL, NULL);
451 check_seq_access (seq);
453 node = node_new (data);
454 node_insert_before (seq->end_node, node);
460 * g_sequence_prepend:
462 * @data: the data for the new item
464 * Adds a new item to the front of @seq
466 * Return value: an iterator pointing to the new item
471 g_sequence_prepend (GSequence *seq,
474 GSequenceNode *node, *first;
476 g_return_val_if_fail (seq != NULL, NULL);
478 check_seq_access (seq);
480 node = node_new (data);
481 first = node_get_first (seq->end_node);
483 node_insert_before (first, node);
489 * g_sequence_insert_before:
490 * @iter: a #GSequenceIter
491 * @data: the data for the new item
493 * Inserts a new item just before the item pointed to by @iter.
495 * Return value: an iterator pointing to the new item
500 g_sequence_insert_before (GSequenceIter *iter,
505 g_return_val_if_fail (iter != NULL, NULL);
507 check_iter_access (iter);
509 node = node_new (data);
511 node_insert_before (iter, node);
518 * @iter: a #GSequenceIter
520 * Removes the item pointed to by @iter. It is an error to pass the
521 * end iterator to this function.
523 * If the sequnce has a data destroy function associated with it, this
524 * function is called on the data for the removed item.
529 g_sequence_remove (GSequenceIter *iter)
533 g_return_if_fail (iter != NULL);
534 g_return_if_fail (!is_end (iter));
536 check_iter_access (iter);
538 seq = get_sequence (iter);
541 node_free (iter, seq);
545 * g_sequence_remove_range:
546 * @begin: a #GSequenceIter
547 * @end: a #GSequenceIter
549 * Removes all items in the (@begin, @end) range.
551 * If the sequence has a data destroy function associated with it, this
552 * function is called on the data for the removed items.
557 g_sequence_remove_range (GSequenceIter *begin,
560 g_return_if_fail (get_sequence (begin) == get_sequence (end));
562 check_iter_access (begin);
563 check_iter_access (end);
565 g_sequence_move_range (NULL, begin, end);
569 * g_sequence_move_range:
570 * @dest: a #GSequenceIter
571 * @begin: a #GSequenceIter
572 * @end: a #GSequenceIter
574 * Inserts the (@begin, @end) range at the destination pointed to by ptr.
575 * The @begin and @end iters must point into the same sequence. It is
576 * allowed for @dest to point to a different sequence than the one pointed
577 * into by @begin and @end.
579 * If @dest is NULL, the range indicated by @begin and @end is
580 * removed from the sequence. If @dest iter points to a place within
581 * the (@begin, @end) range, the range does not move.
586 g_sequence_move_range (GSequenceIter *dest,
587 GSequenceIter *begin,
591 GSequenceNode *first;
593 g_return_if_fail (begin != NULL);
594 g_return_if_fail (end != NULL);
596 check_iter_access (begin);
597 check_iter_access (end);
599 check_iter_access (dest);
601 src_seq = get_sequence (begin);
603 g_return_if_fail (src_seq == get_sequence (end));
605 /* Dest points to begin or end? */
606 if (dest == begin || dest == end)
609 /* begin comes after end? */
610 if (g_sequence_iter_compare (begin, end) >= 0)
613 /* dest points somewhere in the (begin, end) range? */
614 if (dest && get_sequence (dest) == src_seq &&
615 g_sequence_iter_compare (dest, begin) > 0 &&
616 g_sequence_iter_compare (dest, end) < 0)
621 src_seq = get_sequence (begin);
623 first = node_get_first (begin);
630 node_join (first, end);
634 first = node_get_first (dest);
638 node_join (begin, dest);
641 node_join (first, begin);
645 node_free (begin, src_seq);
652 * @cmp_func: the function used to sort the sequence
653 * @cmp_data: user data passed to @cmp_func
655 * Sorts @seq using @cmp_func.
657 * @cmp_func is passed two items of @seq and should
658 * return 0 if they are equal, a negative value if the
659 * first comes before the second, and a positive value
660 * if the second comes before the first.
665 g_sequence_sort (GSequence *seq,
666 GCompareDataFunc cmp_func,
671 info.cmp_func = cmp_func;
672 info.cmp_data = cmp_data;
673 info.end_node = seq->end_node;
675 check_seq_access (seq);
677 g_sequence_sort_iter (seq, iter_compare, &info);
681 * g_sequence_insert_sorted:
683 * @data: the data to insert
684 * @cmp_func: the function used to compare items in the sequence
685 * @cmp_data: user data passed to @cmp_func.
687 * Inserts @data into @sequence using @func to determine the new
688 * position. The sequence must already be sorted according to @cmp_func;
689 * otherwise the new position of @data is undefined.
691 * @cmp_func is called with two items of the @seq and @user_data.
692 * It should return 0 if the items are equal, a negative value
693 * if the first item comes before the second, and a positive value
694 * if the second item comes before the first.
696 * Return value: a #GSequenceIter pointing to the new item.
701 g_sequence_insert_sorted (GSequence *seq,
703 GCompareDataFunc cmp_func,
708 g_return_val_if_fail (seq != NULL, NULL);
709 g_return_val_if_fail (cmp_func != NULL, NULL);
711 info.cmp_func = cmp_func;
712 info.cmp_data = cmp_data;
713 info.end_node = seq->end_node;
714 check_seq_access (seq);
716 return g_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
720 * g_sequence_sort_changed:
721 * @iter: A #GSequenceIter
722 * @cmp_func: the function used to compare items in the sequence
723 * @cmp_data: user data passed to @cmp_func.
725 * Moves the data pointed to a new position as indicated by @cmp_func. This
726 * function should be called for items in a sequence already sorted according
727 * to @cmp_func whenever some aspect of an item changes so that @cmp_func
728 * may return different values for that item.
730 * @cmp_func is called with two items of the @seq and @user_data.
731 * It should return 0 if the items are equal, a negative value if
732 * the first item comes before the second, and a positive value if
733 * the second item comes before the first.
738 g_sequence_sort_changed (GSequenceIter *iter,
739 GCompareDataFunc cmp_func,
744 g_return_if_fail (!is_end (iter));
746 info.cmp_func = cmp_func;
747 info.cmp_data = cmp_data;
748 info.end_node = get_sequence (iter)->end_node;
749 check_iter_access (iter);
751 g_sequence_sort_changed_iter (iter, iter_compare, &info);
757 * @data: data for the new item
758 * @cmp_func: the function used to compare items in the sequence
759 * @cmp_data: user data passed to @cmp_func.
761 * Returns an iterator pointing to the position where @data would
762 * be inserted according to @cmp_func and @cmp_data.
764 * @cmp_func is called with two items of the @seq and @user_data.
765 * It should return 0 if the items are equal, a negative value if
766 * the first item comes before the second, and a positive value if
767 * the second item comes before the first.
769 * If you are simply searching for an existing element of the sequence,
770 * consider using g_sequence_lookup().
772 * Return value: an #GSequenceIter pointing to the position where @data
773 * would have been inserted according to @cmp_func and @cmp_data.
778 g_sequence_search (GSequence *seq,
780 GCompareDataFunc cmp_func,
785 g_return_val_if_fail (seq != NULL, NULL);
787 info.cmp_func = cmp_func;
788 info.cmp_data = cmp_data;
789 info.end_node = seq->end_node;
790 check_seq_access (seq);
792 return g_sequence_search_iter (seq, data, iter_compare, &info);
798 * @data: data to lookup
799 * @cmp_func: the function used to compare items in the sequence
800 * @cmp_data: user data passed to @cmp_func.
802 * Returns an iterator pointing to the position of the first item found
803 * equal to @data according to @cmp_func and @cmp_data. If more than one
804 * item is equal, it is not guaranteed that it is the first which is
805 * returned. In that case, you can use g_sequence_iter_next() and
806 * g_sequence_iter_prev() to get others.
808 * @cmp_func is called with two items of the @seq and @user_data.
809 * It should return 0 if the items are equal, a negative value if
810 * the first item comes before the second, and a positive value if
811 * the second item comes before the first.
813 * Return value: an #GSequenceIter pointing to the position of the
814 * first item found equal to @data according to @cmp_func and @cmp_data.
819 g_sequence_lookup (GSequence *seq,
821 GCompareDataFunc cmp_func,
826 g_return_val_if_fail (seq != NULL, NULL);
828 info.cmp_func = cmp_func;
829 info.cmp_data = cmp_data;
830 info.end_node = seq->end_node;
831 check_seq_access (seq);
833 return g_sequence_lookup_iter (seq, data, iter_compare, &info);
837 * g_sequence_sort_iter:
839 * @cmp_func: the function used to compare iterators in the sequence
840 * @cmp_data: user data passed to @cmp_func
842 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
843 * of a GCompareDataFunc as the compare function
845 * @cmp_func is called with two iterators pointing into @seq. It should
846 * return 0 if the iterators are equal, a negative value if the first
847 * iterator comes before the second, and a positive value if the second
848 * iterator comes before the first.
853 g_sequence_sort_iter (GSequence *seq,
854 GSequenceIterCompareFunc cmp_func,
858 GSequenceNode *begin, *end;
860 g_return_if_fail (seq != NULL);
861 g_return_if_fail (cmp_func != NULL);
863 check_seq_access (seq);
865 begin = g_sequence_get_begin_iter (seq);
866 end = g_sequence_get_end_iter (seq);
868 tmp = g_sequence_new (NULL);
869 tmp->real_sequence = seq;
871 g_sequence_move_range (g_sequence_get_begin_iter (tmp), begin, end);
873 seq->access_prohibited = TRUE;
874 tmp->access_prohibited = TRUE;
876 while (g_sequence_get_length (tmp) > 0)
878 GSequenceNode *node = g_sequence_get_begin_iter (tmp);
880 node_insert_sorted (seq->end_node, node, seq->end_node,
884 tmp->access_prohibited = FALSE;
885 seq->access_prohibited = FALSE;
887 g_sequence_free (tmp);
891 * g_sequence_sort_changed_iter:
892 * @iter: a #GSequenceIter
893 * @iter_cmp: the function used to compare iterators in the sequence
894 * @cmp_data: user data passed to @cmp_func
896 * Like g_sequence_sort_changed(), but uses
897 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
898 * the compare function.
900 * @iter_cmp is called with two iterators pointing into @seq. It should
901 * return 0 if the iterators are equal, a negative value if the first
902 * iterator comes before the second, and a positive value if the second
903 * iterator comes before the first.
908 g_sequence_sort_changed_iter (GSequenceIter *iter,
909 GSequenceIterCompareFunc iter_cmp,
912 GSequence *seq, *tmp_seq;
913 GSequenceIter *next, *prev;
915 g_return_if_fail (iter != NULL);
916 g_return_if_fail (!is_end (iter));
917 g_return_if_fail (iter_cmp != NULL);
918 check_iter_access (iter);
920 /* If one of the neighbours is equal to iter, then
921 * don't move it. This ensures that sort_changed() is
922 * a stable operation.
925 next = node_get_next (iter);
926 prev = node_get_prev (iter);
928 if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
931 if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
934 seq = get_sequence (iter);
936 seq->access_prohibited = TRUE;
938 tmp_seq = g_sequence_new (NULL);
939 tmp_seq->real_sequence = seq;
942 node_insert_before (tmp_seq->end_node, iter);
944 node_insert_sorted (seq->end_node, iter, seq->end_node,
947 g_sequence_free (tmp_seq);
949 seq->access_prohibited = FALSE;
953 * g_sequence_insert_sorted_iter:
955 * @data: data for the new item
956 * @iter_cmp: the function used to compare iterators in the sequence
957 * @cmp_data: user data passed to @cmp_func
959 * Like g_sequence_insert_sorted(), but uses
960 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
961 * the compare function.
963 * @iter_cmp is called with two iterators pointing into @seq.
964 * It should return 0 if the iterators are equal, a negative
965 * value if the first iterator comes before the second, and a
966 * positive value if the second iterator comes before the first.
968 * It is called with two iterators pointing into @seq. It should
969 * return 0 if the iterators are equal, a negative value if the
970 * first iterator comes before the second, and a positive value
971 * if the second iterator comes before the first.
973 * Return value: a #GSequenceIter pointing to the new item
978 g_sequence_insert_sorted_iter (GSequence *seq,
980 GSequenceIterCompareFunc iter_cmp,
983 GSequenceNode *new_node;
986 g_return_val_if_fail (seq != NULL, NULL);
987 g_return_val_if_fail (iter_cmp != NULL, NULL);
989 check_seq_access (seq);
991 seq->access_prohibited = TRUE;
993 /* Create a new temporary sequence and put the new node into
994 * that. The reason for this is that the user compare function
995 * will be called with the new node, and if it dereferences,
996 * "is_end" will be called on it. But that will crash if the
997 * node is not actually in a sequence.
999 * node_insert_sorted() makes sure the node is unlinked before
1002 * The reason we need the "iter" versions at all is that that
1003 * is the only kind of compare functions GtkTreeView can use.
1005 tmp_seq = g_sequence_new (NULL);
1006 tmp_seq->real_sequence = seq;
1008 new_node = g_sequence_append (tmp_seq, data);
1010 node_insert_sorted (seq->end_node, new_node,
1011 seq->end_node, iter_cmp, cmp_data);
1013 g_sequence_free (tmp_seq);
1015 seq->access_prohibited = FALSE;
1021 * g_sequence_search_iter:
1022 * @seq: a #GSequence
1023 * @data: data for the new item
1024 * @iter_cmp: the function used to compare iterators in the sequence
1025 * @cmp_data: user data passed to @iter_cmp
1027 * Like g_sequence_search(), but uses a #GSequenceIterCompareFunc
1028 * instead of a #GCompareDataFunc as the compare function.
1030 * @iter_cmp is called with two iterators pointing into @seq.
1031 * It should return 0 if the iterators are equal, a negative value
1032 * if the first iterator comes before the second, and a positive
1033 * value if the second iterator comes before the first.
1035 * If you are simply searching for an existing element of the sequence,
1036 * consider using g_sequence_lookup_iter().
1038 * Return value: a #GSequenceIter pointing to the position in @seq
1039 * where @data would have been inserted according to @iter_cmp
1045 g_sequence_search_iter (GSequence *seq,
1047 GSequenceIterCompareFunc iter_cmp,
1050 GSequenceNode *node;
1051 GSequenceNode *dummy;
1054 g_return_val_if_fail (seq != NULL, NULL);
1056 check_seq_access (seq);
1058 seq->access_prohibited = TRUE;
1060 tmp_seq = g_sequence_new (NULL);
1061 tmp_seq->real_sequence = seq;
1063 dummy = g_sequence_append (tmp_seq, data);
1065 node = node_find_closest (seq->end_node, dummy,
1066 seq->end_node, iter_cmp, cmp_data);
1068 g_sequence_free (tmp_seq);
1070 seq->access_prohibited = FALSE;
1076 * g_sequence_lookup_iter:
1077 * @seq: a #GSequence
1078 * @data: data to lookup
1079 * @iter_cmp: the function used to compare iterators in the sequence
1080 * @cmp_data: user data passed to @iter_cmp
1082 * Like g_sequence_lookup(), but uses a #GSequenceIterCompareFunc
1083 * instead of a #GCompareDataFunc as the compare function.
1085 * @iter_cmp is called with two iterators pointing into @seq.
1086 * It should return 0 if the iterators are equal, a negative value
1087 * if the first iterator comes before the second, and a positive
1088 * value if the second iterator comes before the first.
1090 * Return value: an #GSequenceIter pointing to the position of
1091 * the first item found equal to @data according to @cmp_func
1097 g_sequence_lookup_iter (GSequence *seq,
1099 GSequenceIterCompareFunc iter_cmp,
1102 GSequenceNode *node;
1103 GSequenceNode *dummy;
1106 g_return_val_if_fail (seq != NULL, NULL);
1108 check_seq_access (seq);
1110 seq->access_prohibited = TRUE;
1112 tmp_seq = g_sequence_new (NULL);
1113 tmp_seq->real_sequence = seq;
1115 dummy = g_sequence_append (tmp_seq, data);
1117 node = node_find (seq->end_node, dummy,
1118 seq->end_node, iter_cmp, cmp_data);
1120 g_sequence_free (tmp_seq);
1122 seq->access_prohibited = FALSE;
1128 * g_sequence_iter_get_sequence:
1129 * @iter: a #GSequenceIter
1131 * Returns the #GSequence that @iter points into.
1133 * Return value: the #GSequence that @iter points into.
1138 g_sequence_iter_get_sequence (GSequenceIter *iter)
1142 g_return_val_if_fail (iter != NULL, NULL);
1144 seq = get_sequence (iter);
1146 /* For temporary sequences, this points to the sequence that
1147 * is actually being manipulated
1149 return seq->real_sequence;
1154 * @iter: a #GSequenceIter
1156 * Returns the data that @iter points to.
1158 * Return value: the data that @iter points to
1163 g_sequence_get (GSequenceIter *iter)
1165 g_return_val_if_fail (iter != NULL, NULL);
1166 g_return_val_if_fail (!is_end (iter), NULL);
1173 * @iter: a #GSequenceIter
1174 * @data: new data for the item
1176 * Changes the data for the item pointed to by @iter to be @data. If
1177 * the sequence has a data destroy function associated with it, that
1178 * function is called on the existing data that @iter pointed to.
1183 g_sequence_set (GSequenceIter *iter,
1188 g_return_if_fail (iter != NULL);
1189 g_return_if_fail (!is_end (iter));
1191 seq = get_sequence (iter);
1193 /* If @data is identical to iter->data, it is destroyed
1194 * here. This will work right in case of ref-counted objects. Also
1195 * it is similar to what ghashtables do.
1197 * For non-refcounted data it's a little less convenient, but
1198 * code relying on self-setting not destroying would be
1199 * pretty dubious anyway ...
1202 if (seq->data_destroy_notify)
1203 seq->data_destroy_notify (iter->data);
1209 * g_sequence_get_length:
1210 * @seq: a #GSequence
1212 * Returns the length of @seq
1214 * Return value: the length of @seq
1219 g_sequence_get_length (GSequence *seq)
1221 return node_get_length (seq->end_node) - 1;
1225 * g_sequence_get_end_iter:
1226 * @seq: a #GSequence
1228 * Returns the end iterator for @seg
1230 * Return value: the end iterator for @seq
1235 g_sequence_get_end_iter (GSequence *seq)
1237 g_return_val_if_fail (seq != NULL, NULL);
1239 return seq->end_node;
1243 * g_sequence_get_begin_iter:
1244 * @seq: a #GSequence
1246 * Returns the begin iterator for @seq.
1248 * Return value: the begin iterator for @seq.
1253 g_sequence_get_begin_iter (GSequence *seq)
1255 g_return_val_if_fail (seq != NULL, NULL);
1257 return node_get_first (seq->end_node);
1261 clamp_position (GSequence *seq,
1264 gint len = g_sequence_get_length (seq);
1266 if (pos > len || pos < 0)
1273 * if pos > number of items or -1, will return end pointer
1276 * g_sequence_get_iter_at_pos:
1277 * @seq: a #GSequence
1278 * @pos: a position in @seq, or -1 for the end.
1280 * Returns the iterator at position @pos. If @pos is negative or larger
1281 * than the number of items in @seq, the end iterator is returned.
1283 * Return value: The #GSequenceIter at position @pos
1288 g_sequence_get_iter_at_pos (GSequence *seq,
1291 g_return_val_if_fail (seq != NULL, NULL);
1293 pos = clamp_position (seq, pos);
1295 return node_get_by_pos (seq->end_node, pos);
1300 * @src: a #GSequenceIter pointing to the item to move
1301 * @dest: a #GSequenceIter pointing to the position to which
1302 * the item is moved.
1304 * Moves the item pointed to by @src to the position indicated by @dest.
1305 * After calling this function @dest will point to the position immediately
1306 * after @src. It is allowed for @src and @dest to point into different
1312 g_sequence_move (GSequenceIter *src,
1313 GSequenceIter *dest)
1315 g_return_if_fail (src != NULL);
1316 g_return_if_fail (dest != NULL);
1317 g_return_if_fail (!is_end (src));
1323 node_insert_before (dest, src);
1329 * g_sequence_iter_is_end:
1330 * @iter: a #GSequenceIter
1332 * Returns whether @iter is the end iterator
1334 * Return value: Whether @iter is the end iterator.
1339 g_sequence_iter_is_end (GSequenceIter *iter)
1341 g_return_val_if_fail (iter != NULL, FALSE);
1343 return is_end (iter);
1347 * g_sequence_iter_is_begin:
1348 * @iter: a #GSequenceIter
1350 * Returns whether @iter is the begin iterator
1352 * Return value: whether @iter is the begin iterator
1357 g_sequence_iter_is_begin (GSequenceIter *iter)
1359 g_return_val_if_fail (iter != NULL, FALSE);
1361 return (node_get_prev (iter) == iter);
1365 * g_sequence_iter_get_position:
1366 * @iter: a #GSequenceIter
1368 * Returns the position of @iter
1370 * Return value: the position of @iter
1375 g_sequence_iter_get_position (GSequenceIter *iter)
1377 g_return_val_if_fail (iter != NULL, -1);
1379 return node_get_pos (iter);
1383 * g_sequence_iter_next:
1384 * @iter: a #GSequenceIter
1386 * Returns an iterator pointing to the next position after @iter. If
1387 * @iter is the end iterator, the end iterator is returned.
1389 * Return value: a #GSequenceIter pointing to the next position after @iter.
1394 g_sequence_iter_next (GSequenceIter *iter)
1396 g_return_val_if_fail (iter != NULL, NULL);
1398 return node_get_next (iter);
1402 * g_sequence_iter_prev:
1403 * @iter: a #GSequenceIter
1405 * Returns an iterator pointing to the previous position before @iter. If
1406 * @iter is the begin iterator, the begin iterator is returned.
1408 * Return value: a #GSequenceIter pointing to the previous position before
1414 g_sequence_iter_prev (GSequenceIter *iter)
1416 g_return_val_if_fail (iter != NULL, NULL);
1418 return node_get_prev (iter);
1422 * g_sequence_iter_move:
1423 * @iter: a #GSequenceIter
1424 * @delta: A positive or negative number indicating how many positions away
1425 * from @iter the returned #GSequenceIter will be.
1427 * Returns the #GSequenceIter which is @delta positions away from @iter.
1428 * If @iter is closer than -@delta positions to the beginning of the sequence,
1429 * the begin iterator is returned. If @iter is closer than @delta positions
1430 * to the end of the sequence, the end iterator is returned.
1432 * Return value: a #GSequenceIter which is @delta positions away from @iter.
1437 g_sequence_iter_move (GSequenceIter *iter,
1443 g_return_val_if_fail (iter != NULL, NULL);
1445 len = g_sequence_get_length (get_sequence (iter));
1447 new_pos = node_get_pos (iter) + delta;
1451 else if (new_pos > len)
1454 return node_get_by_pos (iter, new_pos);
1459 * @a: a #GSequenceIter
1460 * @b: a #GSequenceIter
1462 * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
1463 * to point into difference sequences.
1468 g_sequence_swap (GSequenceIter *a,
1471 GSequenceNode *leftmost, *rightmost, *rightmost_next;
1474 g_return_if_fail (!g_sequence_iter_is_end (a));
1475 g_return_if_fail (!g_sequence_iter_is_end (b));
1480 a_pos = g_sequence_iter_get_position (a);
1481 b_pos = g_sequence_iter_get_position (b);
1494 rightmost_next = node_get_next (rightmost);
1496 /* The situation is now like this:
1498 * ..., leftmost, ......., rightmost, rightmost_next, ...
1501 g_sequence_move (rightmost, leftmost);
1502 g_sequence_move (leftmost, rightmost_next);
1506 * Implementation of a treap
1511 get_priority (GSequenceNode *node)
1513 guint key = GPOINTER_TO_UINT (node);
1515 /* This hash function is based on one found on Thomas Wang's
1518 * http://www.concentric.net/~Ttwang/tech/inthash.htm
1521 key = (key << 15) - key - 1;
1522 key = key ^ (key >> 12);
1523 key = key + (key << 2);
1524 key = key ^ (key >> 4);
1525 key = key + (key << 3) + (key << 11);
1526 key = key ^ (key >> 16);
1528 /* We rely on 0 being less than all other priorities */
1529 return key? key : 1;
1532 static GSequenceNode *
1533 find_root (GSequenceNode *node)
1535 while (node->parent)
1536 node = node->parent;
1541 static GSequenceNode *
1542 node_new (gpointer data)
1544 GSequenceNode *node = g_slice_new0 (GSequenceNode);
1550 node->parent = NULL;
1555 static GSequenceNode *
1556 node_get_first (GSequenceNode *node)
1558 node = find_root (node);
1566 static GSequenceNode *
1567 node_get_last (GSequenceNode *node)
1569 node = find_root (node);
1577 #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1578 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1580 static GSequenceNode *
1581 node_get_next (GSequenceNode *node)
1583 GSequenceNode *n = node;
1593 while (NODE_RIGHT_CHILD (n))
1605 static GSequenceNode *
1606 node_get_prev (GSequenceNode *node)
1608 GSequenceNode *n = node;
1618 while (NODE_LEFT_CHILD (n))
1630 #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1633 node_get_pos (GSequenceNode *node)
1638 n_smaller = node->left->n_nodes;
1642 if (NODE_RIGHT_CHILD (node))
1643 n_smaller += N_NODES (node->parent->left) + 1;
1645 node = node->parent;
1651 static GSequenceNode *
1652 node_get_by_pos (GSequenceNode *node,
1657 node = find_root (node);
1659 while ((i = N_NODES (node->left)) != pos)
1675 static GSequenceNode *
1676 node_find (GSequenceNode *haystack,
1677 GSequenceNode *needle,
1679 GSequenceIterCompareFunc iter_cmp,
1684 haystack = find_root (haystack);
1688 /* iter_cmp can't be passed the end node, since the function may
1691 if (haystack == end)
1694 c = iter_cmp (haystack, needle, cmp_data);
1700 haystack = haystack->left;
1702 haystack = haystack->right;
1704 while (haystack != NULL);
1709 static GSequenceNode *
1710 node_find_closest (GSequenceNode *haystack,
1711 GSequenceNode *needle,
1713 GSequenceIterCompareFunc iter_cmp,
1716 GSequenceNode *best;
1719 haystack = find_root (haystack);
1725 /* iter_cmp can't be passed the end node, since the function may
1728 if (haystack == end)
1731 c = iter_cmp (haystack, needle, cmp_data);
1733 /* In the following we don't break even if c == 0. Instead we go on
1734 * searching along the 'bigger' nodes, so that we find the last one
1735 * that is equal to the needle.
1738 haystack = haystack->left;
1740 haystack = haystack->right;
1742 while (haystack != NULL);
1744 /* If the best node is smaller or equal to the data, then move one step
1745 * to the right to make sure the best one is strictly bigger than the data
1747 if (best != end && c <= 0)
1748 best = node_get_next (best);
1754 node_get_length (GSequenceNode *node)
1756 node = find_root (node);
1758 return node->n_nodes;
1762 real_node_free (GSequenceNode *node,
1767 real_node_free (node->left, seq);
1768 real_node_free (node->right, seq);
1770 if (seq && seq->data_destroy_notify && node != seq->end_node)
1771 seq->data_destroy_notify (node->data);
1773 g_slice_free (GSequenceNode, node);
1778 node_free (GSequenceNode *node,
1781 node = find_root (node);
1783 real_node_free (node, seq);
1787 node_update_fields (GSequenceNode *node)
1791 n_nodes += N_NODES (node->left);
1792 n_nodes += N_NODES (node->right);
1794 node->n_nodes = n_nodes;
1798 node_rotate (GSequenceNode *node)
1800 GSequenceNode *tmp, *old;
1802 g_assert (node->parent);
1803 g_assert (node->parent != node);
1805 if (NODE_LEFT_CHILD (node))
1810 node->right = node->parent;
1811 node->parent = node->parent->parent;
1814 if (node->parent->left == node->right)
1815 node->parent->left = node;
1817 node->parent->right = node;
1820 g_assert (node->right);
1822 node->right->parent = node;
1823 node->right->left = tmp;
1825 if (node->right->left)
1826 node->right->left->parent = node->right;
1835 node->left = node->parent;
1836 node->parent = node->parent->parent;
1839 if (node->parent->right == node->left)
1840 node->parent->right = node;
1842 node->parent->left = node;
1845 g_assert (node->left);
1847 node->left->parent = node;
1848 node->left->right = tmp;
1850 if (node->left->right)
1851 node->left->right->parent = node->left;
1856 node_update_fields (old);
1857 node_update_fields (node);
1861 node_update_fields_deep (GSequenceNode *node)
1865 node_update_fields (node);
1867 node_update_fields_deep (node->parent);
1872 rotate_down (GSequenceNode *node,
1877 left = node->left ? get_priority (node->left) : 0;
1878 right = node->right ? get_priority (node->right) : 0;
1880 while (priority < left || priority < right)
1883 node_rotate (node->left);
1885 node_rotate (node->right);
1887 left = node->left ? get_priority (node->left) : 0;
1888 right = node->right ? get_priority (node->right) : 0;
1893 node_cut (GSequenceNode *node)
1895 while (node->parent)
1899 node->left->parent = NULL;
1902 node_update_fields (node);
1904 rotate_down (node, get_priority (node));
1908 node_join (GSequenceNode *left,
1909 GSequenceNode *right)
1911 GSequenceNode *fake = node_new (NULL);
1913 fake->left = find_root (left);
1914 fake->right = find_root (right);
1915 fake->left->parent = fake;
1916 fake->right->parent = fake;
1918 node_update_fields (fake);
1922 node_free (fake, NULL);
1926 node_insert_before (GSequenceNode *node,
1929 new->left = node->left;
1931 new->left->parent = new;
1936 node_update_fields_deep (new);
1938 while (new->parent && get_priority (new) > get_priority (new->parent))
1941 rotate_down (new, get_priority (new));
1945 node_unlink (GSequenceNode *node)
1947 rotate_down (node, 0);
1949 if (NODE_RIGHT_CHILD (node))
1950 node->parent->right = NULL;
1951 else if (NODE_LEFT_CHILD (node))
1952 node->parent->left = NULL;
1955 node_update_fields_deep (node->parent);
1957 node->parent = NULL;
1961 node_insert_sorted (GSequenceNode *node,
1964 GSequenceIterCompareFunc iter_cmp,
1967 GSequenceNode *closest;
1969 closest = node_find_closest (node, new, end, iter_cmp, cmp_data);
1973 node_insert_before (closest, new);