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
82 * @Returns: zero if the iterators are equal, a negative value if @a
83 * comes before @b, and a positive value if @b comes before
86 * A #GSequenceIterCompareFunc is a function used to compare iterators.
87 * It must return zero if the iterators compare equal, a negative value
88 * if @a comes before @b, and a positive value if @b comes before @a.
91 typedef struct _GSequenceNode GSequenceNode
;
96 * The #GSequence struct is an opaque data type representing a
97 * <link linkend="glib-Sequences">Sequence</link> data type.
101 GSequenceNode
* end_node
;
102 GDestroyNotify data_destroy_notify
;
103 gboolean access_prohibited
;
105 /* The 'real_sequence' is used when temporary sequences are created
106 * to hold nodes that are being rearranged. The 'real_sequence' of such
107 * a temporary sequence points to the sequence that is actually being
108 * manipulated. The only reason we need this is so that when the
109 * sort/sort_changed/search_iter() functions call out to the application
110 * g_sequence_iter_get_sequence() will return the correct sequence.
112 GSequence
* real_sequence
;
115 struct _GSequenceNode
118 GSequenceNode
* parent
;
119 GSequenceNode
* left
;
120 GSequenceNode
* right
;
121 gpointer data
; /* For the end node, this field points
127 * Declaration of GSequenceNode methods
129 static GSequenceNode
*node_new (gpointer data
);
130 static GSequenceNode
*node_get_first (GSequenceNode
*node
);
131 static GSequenceNode
*node_get_last (GSequenceNode
*node
);
132 static GSequenceNode
*node_get_prev (GSequenceNode
*node
);
133 static GSequenceNode
*node_get_next (GSequenceNode
*node
);
134 static gint
node_get_pos (GSequenceNode
*node
);
135 static GSequenceNode
*node_get_by_pos (GSequenceNode
*node
,
137 static GSequenceNode
*node_find (GSequenceNode
*haystack
,
138 GSequenceNode
*needle
,
140 GSequenceIterCompareFunc cmp
,
142 static GSequenceNode
*node_find_closest (GSequenceNode
*haystack
,
143 GSequenceNode
*needle
,
145 GSequenceIterCompareFunc cmp
,
147 static gint
node_get_length (GSequenceNode
*node
);
148 static void node_free (GSequenceNode
*node
,
150 static void node_cut (GSequenceNode
*split
);
151 static void node_insert_before (GSequenceNode
*node
,
153 static void node_unlink (GSequenceNode
*node
);
154 static void node_join (GSequenceNode
*left
,
155 GSequenceNode
*right
);
156 static void node_insert_sorted (GSequenceNode
*node
,
159 GSequenceIterCompareFunc cmp_func
,
164 * Various helper functions
167 check_seq_access (GSequence
*seq
)
169 if (G_UNLIKELY (seq
->access_prohibited
))
171 g_warning ("Accessing a sequence while it is "
172 "being sorted or searched is not allowed");
177 get_sequence (GSequenceNode
*node
)
179 return (GSequence
*)node_get_last (node
)->data
;
183 check_iter_access (GSequenceIter
*iter
)
185 check_seq_access (get_sequence (iter
));
189 is_end (GSequenceIter
*iter
)
199 if (iter
->parent
->right
!= iter
)
202 seq
= get_sequence (iter
);
204 return seq
->end_node
== iter
;
209 GCompareDataFunc cmp_func
;
211 GSequenceNode
*end_node
;
214 /* This function compares two iters using a normal compare
215 * function and user_data passed in in a SortInfo struct
218 iter_compare (GSequenceIter
*node1
,
219 GSequenceIter
*node2
,
222 const SortInfo
*info
= data
;
225 if (node1
== info
->end_node
)
228 if (node2
== info
->end_node
)
231 retval
= info
->cmp_func (node1
->data
, node2
->data
, info
->cmp_data
);
242 * @data_destroy: (allow-none): a #GDestroyNotify function, or %NULL
244 * Creates a new GSequence. The @data_destroy function, if non-%NULL will
245 * be called on all items when the sequence is destroyed and on items that
246 * are removed from the sequence.
248 * Return value: a new #GSequence
253 g_sequence_new (GDestroyNotify data_destroy
)
255 GSequence
*seq
= g_new (GSequence
, 1);
256 seq
->data_destroy_notify
= data_destroy
;
258 seq
->end_node
= node_new (seq
);
260 seq
->access_prohibited
= FALSE
;
262 seq
->real_sequence
= seq
;
271 * Frees the memory allocated for @seq. If @seq has a data destroy
272 * function associated with it, that function is called on all items in
278 g_sequence_free (GSequence
*seq
)
280 g_return_if_fail (seq
!= NULL
);
282 check_seq_access (seq
);
284 node_free (seq
->end_node
, seq
);
290 * g_sequence_foreach_range:
291 * @begin: a #GSequenceIter
292 * @end: a #GSequenceIter
294 * @user_data: user data passed to @func
296 * Calls @func for each item in the range (@begin, @end) passing
297 * @user_data to the function.
302 g_sequence_foreach_range (GSequenceIter
*begin
,
310 g_return_if_fail (func
!= NULL
);
311 g_return_if_fail (begin
!= NULL
);
312 g_return_if_fail (end
!= NULL
);
314 seq
= get_sequence (begin
);
316 seq
->access_prohibited
= TRUE
;
321 GSequenceIter
*next
= node_get_next (iter
);
323 func (iter
->data
, user_data
);
328 seq
->access_prohibited
= FALSE
;
332 * g_sequence_foreach:
334 * @func: the function to call for each item in @seq
335 * @user_data: user data passed to @func
337 * Calls @func for each item in the sequence passing @user_data
343 g_sequence_foreach (GSequence
*seq
,
347 GSequenceIter
*begin
, *end
;
349 check_seq_access (seq
);
351 begin
= g_sequence_get_begin_iter (seq
);
352 end
= g_sequence_get_end_iter (seq
);
354 g_sequence_foreach_range (begin
, end
, func
, user_data
);
358 * g_sequence_range_get_midpoint:
359 * @begin: a #GSequenceIter
360 * @end: a #GSequenceIter
362 * Finds an iterator somewhere in the range (@begin, @end). This
363 * iterator will be close to the middle of the range, but is not
364 * guaranteed to be <emphasis>exactly</emphasis> in the middle.
366 * The @begin and @end iterators must both point to the same sequence and
367 * @begin must come before or be equal to @end in the sequence.
369 * Return value: A #GSequenceIter pointing somewhere in the
370 * (@begin, @end) range.
375 g_sequence_range_get_midpoint (GSequenceIter
*begin
,
378 int begin_pos
, end_pos
, mid_pos
;
380 g_return_val_if_fail (begin
!= NULL
, NULL
);
381 g_return_val_if_fail (end
!= NULL
, NULL
);
382 g_return_val_if_fail (get_sequence (begin
) == get_sequence (end
), NULL
);
384 begin_pos
= node_get_pos (begin
);
385 end_pos
= node_get_pos (end
);
387 g_return_val_if_fail (end_pos
>= begin_pos
, NULL
);
389 mid_pos
= begin_pos
+ (end_pos
- begin_pos
) / 2;
391 return node_get_by_pos (begin
, mid_pos
);
395 * g_sequence_iter_compare:
396 * @a: a #GSequenceIter
397 * @b: a #GSequenceIter
399 * Returns a negative number if @a comes before @b, 0 if they are equal,
400 * and a positive number if @a comes after @b.
402 * The @a and @b iterators must point into the same sequence.
404 * Return value: A negative number if @a comes before @b, 0 if they are
405 * equal, and a positive number if @a comes after @b.
410 g_sequence_iter_compare (GSequenceIter
*a
,
415 g_return_val_if_fail (a
!= NULL
, 0);
416 g_return_val_if_fail (b
!= NULL
, 0);
417 g_return_val_if_fail (get_sequence (a
) == get_sequence (b
), 0);
419 check_iter_access (a
);
420 check_iter_access (b
);
422 a_pos
= node_get_pos (a
);
423 b_pos
= node_get_pos (b
);
427 else if (a_pos
> b_pos
)
436 * @data: the data for the new item
438 * Adds a new item to the end of @seq.
440 * Return value: an iterator pointing to the new item
445 g_sequence_append (GSequence
*seq
,
450 g_return_val_if_fail (seq
!= NULL
, NULL
);
452 check_seq_access (seq
);
454 node
= node_new (data
);
455 node_insert_before (seq
->end_node
, node
);
461 * g_sequence_prepend:
463 * @data: the data for the new item
465 * Adds a new item to the front of @seq
467 * Return value: an iterator pointing to the new item
472 g_sequence_prepend (GSequence
*seq
,
475 GSequenceNode
*node
, *first
;
477 g_return_val_if_fail (seq
!= NULL
, NULL
);
479 check_seq_access (seq
);
481 node
= node_new (data
);
482 first
= node_get_first (seq
->end_node
);
484 node_insert_before (first
, node
);
490 * g_sequence_insert_before:
491 * @iter: a #GSequenceIter
492 * @data: the data for the new item
494 * Inserts a new item just before the item pointed to by @iter.
496 * Return value: an iterator pointing to the new item
501 g_sequence_insert_before (GSequenceIter
*iter
,
506 g_return_val_if_fail (iter
!= NULL
, NULL
);
508 check_iter_access (iter
);
510 node
= node_new (data
);
512 node_insert_before (iter
, node
);
519 * @iter: a #GSequenceIter
521 * Removes the item pointed to by @iter. It is an error to pass the
522 * end iterator to this function.
524 * If the sequence has a data destroy function associated with it, this
525 * function is called on the data for the removed item.
530 g_sequence_remove (GSequenceIter
*iter
)
534 g_return_if_fail (iter
!= NULL
);
535 g_return_if_fail (!is_end (iter
));
537 check_iter_access (iter
);
539 seq
= get_sequence (iter
);
542 node_free (iter
, seq
);
546 * g_sequence_remove_range:
547 * @begin: a #GSequenceIter
548 * @end: a #GSequenceIter
550 * Removes all items in the (@begin, @end) range.
552 * If the sequence has a data destroy function associated with it, this
553 * function is called on the data for the removed items.
558 g_sequence_remove_range (GSequenceIter
*begin
,
561 g_return_if_fail (get_sequence (begin
) == get_sequence (end
));
563 check_iter_access (begin
);
564 check_iter_access (end
);
566 g_sequence_move_range (NULL
, begin
, end
);
570 * g_sequence_move_range:
571 * @dest: a #GSequenceIter
572 * @begin: a #GSequenceIter
573 * @end: a #GSequenceIter
575 * Inserts the (@begin, @end) range at the destination pointed to by ptr.
576 * The @begin and @end iters must point into the same sequence. It is
577 * allowed for @dest to point to a different sequence than the one pointed
578 * into by @begin and @end.
580 * If @dest is NULL, the range indicated by @begin and @end is
581 * removed from the sequence. If @dest iter points to a place within
582 * the (@begin, @end) range, the range does not move.
587 g_sequence_move_range (GSequenceIter
*dest
,
588 GSequenceIter
*begin
,
592 GSequenceNode
*first
;
594 g_return_if_fail (begin
!= NULL
);
595 g_return_if_fail (end
!= NULL
);
597 check_iter_access (begin
);
598 check_iter_access (end
);
600 check_iter_access (dest
);
602 src_seq
= get_sequence (begin
);
604 g_return_if_fail (src_seq
== get_sequence (end
));
606 /* Dest points to begin or end? */
607 if (dest
== begin
|| dest
== end
)
610 /* begin comes after end? */
611 if (g_sequence_iter_compare (begin
, end
) >= 0)
614 /* dest points somewhere in the (begin, end) range? */
615 if (dest
&& get_sequence (dest
) == src_seq
&&
616 g_sequence_iter_compare (dest
, begin
) > 0 &&
617 g_sequence_iter_compare (dest
, end
) < 0)
622 src_seq
= get_sequence (begin
);
624 first
= node_get_first (begin
);
631 node_join (first
, end
);
635 first
= node_get_first (dest
);
639 node_join (begin
, dest
);
642 node_join (first
, begin
);
646 node_free (begin
, src_seq
);
653 * @cmp_func: the function used to sort the sequence
654 * @cmp_data: user data passed to @cmp_func
656 * Sorts @seq using @cmp_func.
658 * @cmp_func is passed two items of @seq and should
659 * return 0 if they are equal, a negative value if the
660 * first comes before the second, and a positive value
661 * if the second comes before the first.
666 g_sequence_sort (GSequence
*seq
,
667 GCompareDataFunc cmp_func
,
672 info
.cmp_func
= cmp_func
;
673 info
.cmp_data
= cmp_data
;
674 info
.end_node
= seq
->end_node
;
676 check_seq_access (seq
);
678 g_sequence_sort_iter (seq
, iter_compare
, &info
);
682 * g_sequence_insert_sorted:
684 * @data: the data to insert
685 * @cmp_func: the function used to compare items in the sequence
686 * @cmp_data: user data passed to @cmp_func.
688 * Inserts @data into @sequence using @func to determine the new
689 * position. The sequence must already be sorted according to @cmp_func;
690 * otherwise the new position of @data is undefined.
692 * @cmp_func is called with two items of the @seq and @user_data.
693 * It should return 0 if the items are equal, a negative value
694 * if the first item comes before the second, and a positive value
695 * if the second item comes before the first.
697 * Return value: a #GSequenceIter pointing to the new item.
702 g_sequence_insert_sorted (GSequence
*seq
,
704 GCompareDataFunc cmp_func
,
709 g_return_val_if_fail (seq
!= NULL
, NULL
);
710 g_return_val_if_fail (cmp_func
!= NULL
, NULL
);
712 info
.cmp_func
= cmp_func
;
713 info
.cmp_data
= cmp_data
;
714 info
.end_node
= seq
->end_node
;
715 check_seq_access (seq
);
717 return g_sequence_insert_sorted_iter (seq
, data
, iter_compare
, &info
);
721 * g_sequence_sort_changed:
722 * @iter: A #GSequenceIter
723 * @cmp_func: the function used to compare items in the sequence
724 * @cmp_data: user data passed to @cmp_func.
726 * Moves the data pointed to a new position as indicated by @cmp_func. This
727 * function should be called for items in a sequence already sorted according
728 * to @cmp_func whenever some aspect of an item changes so that @cmp_func
729 * may return different values for that item.
731 * @cmp_func is called with two items of the @seq and @user_data.
732 * It should return 0 if the items are equal, a negative value if
733 * the first item comes before the second, and a positive value if
734 * the second item comes before the first.
739 g_sequence_sort_changed (GSequenceIter
*iter
,
740 GCompareDataFunc cmp_func
,
745 g_return_if_fail (!is_end (iter
));
747 info
.cmp_func
= cmp_func
;
748 info
.cmp_data
= cmp_data
;
749 info
.end_node
= get_sequence (iter
)->end_node
;
750 check_iter_access (iter
);
752 g_sequence_sort_changed_iter (iter
, iter_compare
, &info
);
758 * @data: data for the new item
759 * @cmp_func: the function used to compare items in the sequence
760 * @cmp_data: user data passed to @cmp_func.
762 * Returns an iterator pointing to the position where @data would
763 * be inserted according to @cmp_func and @cmp_data.
765 * @cmp_func is called with two items of the @seq and @user_data.
766 * It should return 0 if the items are equal, a negative value if
767 * the first item comes before the second, and a positive value if
768 * the second item comes before the first.
770 * If you are simply searching for an existing element of the sequence,
771 * consider using g_sequence_lookup().
774 * This function will fail if the data contained in the sequence is
775 * unsorted. Use g_sequence_insert_sorted() or
776 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
777 * you want to add a large amount of data, call g_sequence_sort() after
778 * doing unsorted insertions.
781 * Return value: an #GSequenceIter pointing to the position where @data
782 * would have been inserted according to @cmp_func and @cmp_data.
787 g_sequence_search (GSequence
*seq
,
789 GCompareDataFunc cmp_func
,
794 g_return_val_if_fail (seq
!= NULL
, NULL
);
796 info
.cmp_func
= cmp_func
;
797 info
.cmp_data
= cmp_data
;
798 info
.end_node
= seq
->end_node
;
799 check_seq_access (seq
);
801 return g_sequence_search_iter (seq
, data
, iter_compare
, &info
);
807 * @data: data to lookup
808 * @cmp_func: the function used to compare items in the sequence
809 * @cmp_data: user data passed to @cmp_func.
811 * Returns an iterator pointing to the position of the first item found
812 * equal to @data according to @cmp_func and @cmp_data. If more than one
813 * item is equal, it is not guaranteed that it is the first which is
814 * returned. In that case, you can use g_sequence_iter_next() and
815 * g_sequence_iter_prev() to get others.
817 * @cmp_func is called with two items of the @seq and @user_data.
818 * It should return 0 if the items are equal, a negative value if
819 * the first item comes before the second, and a positive value if
820 * the second item comes before the first.
823 * This function will fail if the data contained in the sequence is
824 * unsorted. Use g_sequence_insert_sorted() or
825 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
826 * you want to add a large amount of data, call g_sequence_sort() after
827 * doing unsorted insertions.
830 * Return value: an #GSequenceIter pointing to the position of the
831 * first item found equal to @data according to @cmp_func and @cmp_data.
836 g_sequence_lookup (GSequence
*seq
,
838 GCompareDataFunc cmp_func
,
843 g_return_val_if_fail (seq
!= NULL
, NULL
);
845 info
.cmp_func
= cmp_func
;
846 info
.cmp_data
= cmp_data
;
847 info
.end_node
= seq
->end_node
;
848 check_seq_access (seq
);
850 return g_sequence_lookup_iter (seq
, data
, iter_compare
, &info
);
854 * g_sequence_sort_iter:
856 * @cmp_func: the function used to compare iterators in the sequence
857 * @cmp_data: user data passed to @cmp_func
859 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
860 * of a GCompareDataFunc as the compare function
862 * @cmp_func is called with two iterators pointing into @seq. It should
863 * return 0 if the iterators are equal, a negative value if the first
864 * iterator comes before the second, and a positive value if the second
865 * iterator comes before the first.
870 g_sequence_sort_iter (GSequence
*seq
,
871 GSequenceIterCompareFunc cmp_func
,
875 GSequenceNode
*begin
, *end
;
877 g_return_if_fail (seq
!= NULL
);
878 g_return_if_fail (cmp_func
!= NULL
);
880 check_seq_access (seq
);
882 begin
= g_sequence_get_begin_iter (seq
);
883 end
= g_sequence_get_end_iter (seq
);
885 tmp
= g_sequence_new (NULL
);
886 tmp
->real_sequence
= seq
;
888 g_sequence_move_range (g_sequence_get_begin_iter (tmp
), begin
, end
);
890 seq
->access_prohibited
= TRUE
;
891 tmp
->access_prohibited
= TRUE
;
893 while (g_sequence_get_length (tmp
) > 0)
895 GSequenceNode
*node
= g_sequence_get_begin_iter (tmp
);
897 node_insert_sorted (seq
->end_node
, node
, seq
->end_node
,
901 tmp
->access_prohibited
= FALSE
;
902 seq
->access_prohibited
= FALSE
;
904 g_sequence_free (tmp
);
908 * g_sequence_sort_changed_iter:
909 * @iter: a #GSequenceIter
910 * @iter_cmp: the function used to compare iterators in the sequence
911 * @cmp_data: user data passed to @cmp_func
913 * Like g_sequence_sort_changed(), but uses
914 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
915 * the compare function.
917 * @iter_cmp is called with two iterators pointing into @seq. It should
918 * return 0 if the iterators are equal, a negative value if the first
919 * iterator comes before the second, and a positive value if the second
920 * iterator comes before the first.
925 g_sequence_sort_changed_iter (GSequenceIter
*iter
,
926 GSequenceIterCompareFunc iter_cmp
,
929 GSequence
*seq
, *tmp_seq
;
930 GSequenceIter
*next
, *prev
;
932 g_return_if_fail (iter
!= NULL
);
933 g_return_if_fail (!is_end (iter
));
934 g_return_if_fail (iter_cmp
!= NULL
);
935 check_iter_access (iter
);
937 /* If one of the neighbours is equal to iter, then
938 * don't move it. This ensures that sort_changed() is
939 * a stable operation.
942 next
= node_get_next (iter
);
943 prev
= node_get_prev (iter
);
945 if (prev
!= iter
&& iter_cmp (prev
, iter
, cmp_data
) == 0)
948 if (!is_end (next
) && iter_cmp (next
, iter
, cmp_data
) == 0)
951 seq
= get_sequence (iter
);
953 seq
->access_prohibited
= TRUE
;
955 tmp_seq
= g_sequence_new (NULL
);
956 tmp_seq
->real_sequence
= seq
;
959 node_insert_before (tmp_seq
->end_node
, iter
);
961 node_insert_sorted (seq
->end_node
, iter
, seq
->end_node
,
964 g_sequence_free (tmp_seq
);
966 seq
->access_prohibited
= FALSE
;
970 * g_sequence_insert_sorted_iter:
972 * @data: data for the new item
973 * @iter_cmp: the function used to compare iterators in the sequence
974 * @cmp_data: user data passed to @cmp_func
976 * Like g_sequence_insert_sorted(), but uses
977 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
978 * the compare function.
980 * @iter_cmp is called with two iterators pointing into @seq.
981 * It should return 0 if the iterators are equal, a negative
982 * value if the first iterator comes before the second, and a
983 * positive value if the second iterator comes before the first.
985 * It is called with two iterators pointing into @seq. It should
986 * return 0 if the iterators are equal, a negative value if the
987 * first iterator comes before the second, and a positive value
988 * if the second iterator comes before the first.
990 * Return value: a #GSequenceIter pointing to the new item
995 g_sequence_insert_sorted_iter (GSequence
*seq
,
997 GSequenceIterCompareFunc iter_cmp
,
1000 GSequenceNode
*new_node
;
1003 g_return_val_if_fail (seq
!= NULL
, NULL
);
1004 g_return_val_if_fail (iter_cmp
!= NULL
, NULL
);
1006 check_seq_access (seq
);
1008 seq
->access_prohibited
= TRUE
;
1010 /* Create a new temporary sequence and put the new node into
1011 * that. The reason for this is that the user compare function
1012 * will be called with the new node, and if it dereferences,
1013 * "is_end" will be called on it. But that will crash if the
1014 * node is not actually in a sequence.
1016 * node_insert_sorted() makes sure the node is unlinked before
1019 * The reason we need the "iter" versions at all is that that
1020 * is the only kind of compare functions GtkTreeView can use.
1022 tmp_seq
= g_sequence_new (NULL
);
1023 tmp_seq
->real_sequence
= seq
;
1025 new_node
= g_sequence_append (tmp_seq
, data
);
1027 node_insert_sorted (seq
->end_node
, new_node
,
1028 seq
->end_node
, iter_cmp
, cmp_data
);
1030 g_sequence_free (tmp_seq
);
1032 seq
->access_prohibited
= FALSE
;
1038 * g_sequence_search_iter:
1039 * @seq: a #GSequence
1040 * @data: data for the new item
1041 * @iter_cmp: the function used to compare iterators in the sequence
1042 * @cmp_data: user data passed to @iter_cmp
1044 * Like g_sequence_search(), but uses a #GSequenceIterCompareFunc
1045 * instead of a #GCompareDataFunc as the compare function.
1047 * @iter_cmp is called with two iterators pointing into @seq.
1048 * It should return 0 if the iterators are equal, a negative value
1049 * if the first iterator comes before the second, and a positive
1050 * value if the second iterator comes before the first.
1052 * If you are simply searching for an existing element of the sequence,
1053 * consider using g_sequence_lookup_iter().
1056 * This function will fail if the data contained in the sequence is
1057 * unsorted. Use g_sequence_insert_sorted() or
1058 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
1059 * you want to add a large amount of data, call g_sequence_sort() after
1060 * doing unsorted insertions.
1063 * Return value: a #GSequenceIter pointing to the position in @seq
1064 * where @data would have been inserted according to @iter_cmp
1070 g_sequence_search_iter (GSequence
*seq
,
1072 GSequenceIterCompareFunc iter_cmp
,
1075 GSequenceNode
*node
;
1076 GSequenceNode
*dummy
;
1079 g_return_val_if_fail (seq
!= NULL
, NULL
);
1081 check_seq_access (seq
);
1083 seq
->access_prohibited
= TRUE
;
1085 tmp_seq
= g_sequence_new (NULL
);
1086 tmp_seq
->real_sequence
= seq
;
1088 dummy
= g_sequence_append (tmp_seq
, data
);
1090 node
= node_find_closest (seq
->end_node
, dummy
,
1091 seq
->end_node
, iter_cmp
, cmp_data
);
1093 g_sequence_free (tmp_seq
);
1095 seq
->access_prohibited
= FALSE
;
1101 * g_sequence_lookup_iter:
1102 * @seq: a #GSequence
1103 * @data: data to lookup
1104 * @iter_cmp: the function used to compare iterators in the sequence
1105 * @cmp_data: user data passed to @iter_cmp
1107 * Like g_sequence_lookup(), but uses a #GSequenceIterCompareFunc
1108 * instead of a #GCompareDataFunc as the compare function.
1110 * @iter_cmp is called with two iterators pointing into @seq.
1111 * It should return 0 if the iterators are equal, a negative value
1112 * if the first iterator comes before the second, and a positive
1113 * value if the second iterator comes before the first.
1116 * This function will fail if the data contained in the sequence is
1117 * unsorted. Use g_sequence_insert_sorted() or
1118 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
1119 * you want to add a large amount of data, call g_sequence_sort() after
1120 * doing unsorted insertions.
1123 * Return value: an #GSequenceIter pointing to the position of
1124 * the first item found equal to @data according to @cmp_func
1130 g_sequence_lookup_iter (GSequence
*seq
,
1132 GSequenceIterCompareFunc iter_cmp
,
1135 GSequenceNode
*node
;
1136 GSequenceNode
*dummy
;
1139 g_return_val_if_fail (seq
!= NULL
, NULL
);
1141 check_seq_access (seq
);
1143 seq
->access_prohibited
= TRUE
;
1145 tmp_seq
= g_sequence_new (NULL
);
1146 tmp_seq
->real_sequence
= seq
;
1148 dummy
= g_sequence_append (tmp_seq
, data
);
1150 node
= node_find (seq
->end_node
, dummy
,
1151 seq
->end_node
, iter_cmp
, cmp_data
);
1153 g_sequence_free (tmp_seq
);
1155 seq
->access_prohibited
= FALSE
;
1161 * g_sequence_iter_get_sequence:
1162 * @iter: a #GSequenceIter
1164 * Returns the #GSequence that @iter points into.
1166 * Return value: the #GSequence that @iter points into.
1171 g_sequence_iter_get_sequence (GSequenceIter
*iter
)
1175 g_return_val_if_fail (iter
!= NULL
, NULL
);
1177 seq
= get_sequence (iter
);
1179 /* For temporary sequences, this points to the sequence that
1180 * is actually being manipulated
1182 return seq
->real_sequence
;
1187 * @iter: a #GSequenceIter
1189 * Returns the data that @iter points to.
1191 * Return value: the data that @iter points to
1196 g_sequence_get (GSequenceIter
*iter
)
1198 g_return_val_if_fail (iter
!= NULL
, NULL
);
1199 g_return_val_if_fail (!is_end (iter
), NULL
);
1206 * @iter: a #GSequenceIter
1207 * @data: new data for the item
1209 * Changes the data for the item pointed to by @iter to be @data. If
1210 * the sequence has a data destroy function associated with it, that
1211 * function is called on the existing data that @iter pointed to.
1216 g_sequence_set (GSequenceIter
*iter
,
1221 g_return_if_fail (iter
!= NULL
);
1222 g_return_if_fail (!is_end (iter
));
1224 seq
= get_sequence (iter
);
1226 /* If @data is identical to iter->data, it is destroyed
1227 * here. This will work right in case of ref-counted objects. Also
1228 * it is similar to what ghashtables do.
1230 * For non-refcounted data it's a little less convenient, but
1231 * code relying on self-setting not destroying would be
1232 * pretty dubious anyway ...
1235 if (seq
->data_destroy_notify
)
1236 seq
->data_destroy_notify (iter
->data
);
1242 * g_sequence_get_length:
1243 * @seq: a #GSequence
1245 * Returns the length of @seq
1247 * Return value: the length of @seq
1252 g_sequence_get_length (GSequence
*seq
)
1254 return node_get_length (seq
->end_node
) - 1;
1258 * g_sequence_get_end_iter:
1259 * @seq: a #GSequence
1261 * Returns the end iterator for @seg
1263 * Return value: the end iterator for @seq
1268 g_sequence_get_end_iter (GSequence
*seq
)
1270 g_return_val_if_fail (seq
!= NULL
, NULL
);
1272 return seq
->end_node
;
1276 * g_sequence_get_begin_iter:
1277 * @seq: a #GSequence
1279 * Returns the begin iterator for @seq.
1281 * Return value: the begin iterator for @seq.
1286 g_sequence_get_begin_iter (GSequence
*seq
)
1288 g_return_val_if_fail (seq
!= NULL
, NULL
);
1290 return node_get_first (seq
->end_node
);
1294 clamp_position (GSequence
*seq
,
1297 gint len
= g_sequence_get_length (seq
);
1299 if (pos
> len
|| pos
< 0)
1306 * if pos > number of items or -1, will return end pointer
1309 * g_sequence_get_iter_at_pos:
1310 * @seq: a #GSequence
1311 * @pos: a position in @seq, or -1 for the end.
1313 * Returns the iterator at position @pos. If @pos is negative or larger
1314 * than the number of items in @seq, the end iterator is returned.
1316 * Return value: The #GSequenceIter at position @pos
1321 g_sequence_get_iter_at_pos (GSequence
*seq
,
1324 g_return_val_if_fail (seq
!= NULL
, NULL
);
1326 pos
= clamp_position (seq
, pos
);
1328 return node_get_by_pos (seq
->end_node
, pos
);
1333 * @src: a #GSequenceIter pointing to the item to move
1334 * @dest: a #GSequenceIter pointing to the position to which
1335 * the item is moved.
1337 * Moves the item pointed to by @src to the position indicated by @dest.
1338 * After calling this function @dest will point to the position immediately
1339 * after @src. It is allowed for @src and @dest to point into different
1345 g_sequence_move (GSequenceIter
*src
,
1346 GSequenceIter
*dest
)
1348 g_return_if_fail (src
!= NULL
);
1349 g_return_if_fail (dest
!= NULL
);
1350 g_return_if_fail (!is_end (src
));
1356 node_insert_before (dest
, src
);
1362 * g_sequence_iter_is_end:
1363 * @iter: a #GSequenceIter
1365 * Returns whether @iter is the end iterator
1367 * Return value: Whether @iter is the end iterator.
1372 g_sequence_iter_is_end (GSequenceIter
*iter
)
1374 g_return_val_if_fail (iter
!= NULL
, FALSE
);
1376 return is_end (iter
);
1380 * g_sequence_iter_is_begin:
1381 * @iter: a #GSequenceIter
1383 * Returns whether @iter is the begin iterator
1385 * Return value: whether @iter is the begin iterator
1390 g_sequence_iter_is_begin (GSequenceIter
*iter
)
1392 g_return_val_if_fail (iter
!= NULL
, FALSE
);
1394 return (node_get_prev (iter
) == iter
);
1398 * g_sequence_iter_get_position:
1399 * @iter: a #GSequenceIter
1401 * Returns the position of @iter
1403 * Return value: the position of @iter
1408 g_sequence_iter_get_position (GSequenceIter
*iter
)
1410 g_return_val_if_fail (iter
!= NULL
, -1);
1412 return node_get_pos (iter
);
1416 * g_sequence_iter_next:
1417 * @iter: a #GSequenceIter
1419 * Returns an iterator pointing to the next position after @iter. If
1420 * @iter is the end iterator, the end iterator is returned.
1422 * Return value: a #GSequenceIter pointing to the next position after @iter.
1427 g_sequence_iter_next (GSequenceIter
*iter
)
1429 g_return_val_if_fail (iter
!= NULL
, NULL
);
1431 return node_get_next (iter
);
1435 * g_sequence_iter_prev:
1436 * @iter: a #GSequenceIter
1438 * Returns an iterator pointing to the previous position before @iter. If
1439 * @iter is the begin iterator, the begin iterator is returned.
1441 * Return value: a #GSequenceIter pointing to the previous position before
1447 g_sequence_iter_prev (GSequenceIter
*iter
)
1449 g_return_val_if_fail (iter
!= NULL
, NULL
);
1451 return node_get_prev (iter
);
1455 * g_sequence_iter_move:
1456 * @iter: a #GSequenceIter
1457 * @delta: A positive or negative number indicating how many positions away
1458 * from @iter the returned #GSequenceIter will be.
1460 * Returns the #GSequenceIter which is @delta positions away from @iter.
1461 * If @iter is closer than -@delta positions to the beginning of the sequence,
1462 * the begin iterator is returned. If @iter is closer than @delta positions
1463 * to the end of the sequence, the end iterator is returned.
1465 * Return value: a #GSequenceIter which is @delta positions away from @iter.
1470 g_sequence_iter_move (GSequenceIter
*iter
,
1476 g_return_val_if_fail (iter
!= NULL
, NULL
);
1478 len
= g_sequence_get_length (get_sequence (iter
));
1480 new_pos
= node_get_pos (iter
) + delta
;
1484 else if (new_pos
> len
)
1487 return node_get_by_pos (iter
, new_pos
);
1492 * @a: a #GSequenceIter
1493 * @b: a #GSequenceIter
1495 * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
1496 * to point into difference sequences.
1501 g_sequence_swap (GSequenceIter
*a
,
1504 GSequenceNode
*leftmost
, *rightmost
, *rightmost_next
;
1507 g_return_if_fail (!g_sequence_iter_is_end (a
));
1508 g_return_if_fail (!g_sequence_iter_is_end (b
));
1513 a_pos
= g_sequence_iter_get_position (a
);
1514 b_pos
= g_sequence_iter_get_position (b
);
1527 rightmost_next
= node_get_next (rightmost
);
1529 /* The situation is now like this:
1531 * ..., leftmost, ......., rightmost, rightmost_next, ...
1534 g_sequence_move (rightmost
, leftmost
);
1535 g_sequence_move (leftmost
, rightmost_next
);
1539 * Implementation of a treap
1544 get_priority (GSequenceNode
*node
)
1546 guint key
= GPOINTER_TO_UINT (node
);
1548 /* This hash function is based on one found on Thomas Wang's
1551 * http://www.concentric.net/~Ttwang/tech/inthash.htm
1554 key
= (key
<< 15) - key
- 1;
1555 key
= key
^ (key
>> 12);
1556 key
= key
+ (key
<< 2);
1557 key
= key
^ (key
>> 4);
1558 key
= key
+ (key
<< 3) + (key
<< 11);
1559 key
= key
^ (key
>> 16);
1561 /* We rely on 0 being less than all other priorities */
1562 return key
? key
: 1;
1565 static GSequenceNode
*
1566 find_root (GSequenceNode
*node
)
1568 while (node
->parent
)
1569 node
= node
->parent
;
1574 static GSequenceNode
*
1575 node_new (gpointer data
)
1577 GSequenceNode
*node
= g_slice_new0 (GSequenceNode
);
1583 node
->parent
= NULL
;
1588 static GSequenceNode
*
1589 node_get_first (GSequenceNode
*node
)
1591 node
= find_root (node
);
1599 static GSequenceNode
*
1600 node_get_last (GSequenceNode
*node
)
1602 node
= find_root (node
);
1610 #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1611 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1613 static GSequenceNode
*
1614 node_get_next (GSequenceNode
*node
)
1616 GSequenceNode
*n
= node
;
1626 while (NODE_RIGHT_CHILD (n
))
1638 static GSequenceNode
*
1639 node_get_prev (GSequenceNode
*node
)
1641 GSequenceNode
*n
= node
;
1651 while (NODE_LEFT_CHILD (n
))
1663 #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1666 node_get_pos (GSequenceNode
*node
)
1671 n_smaller
= node
->left
->n_nodes
;
1675 if (NODE_RIGHT_CHILD (node
))
1676 n_smaller
+= N_NODES (node
->parent
->left
) + 1;
1678 node
= node
->parent
;
1684 static GSequenceNode
*
1685 node_get_by_pos (GSequenceNode
*node
,
1690 node
= find_root (node
);
1692 while ((i
= N_NODES (node
->left
)) != pos
)
1708 static GSequenceNode
*
1709 node_find (GSequenceNode
*haystack
,
1710 GSequenceNode
*needle
,
1712 GSequenceIterCompareFunc iter_cmp
,
1717 haystack
= find_root (haystack
);
1721 /* iter_cmp can't be passed the end node, since the function may
1724 if (haystack
== end
)
1727 c
= iter_cmp (haystack
, needle
, cmp_data
);
1733 haystack
= haystack
->left
;
1735 haystack
= haystack
->right
;
1737 while (haystack
!= NULL
);
1742 static GSequenceNode
*
1743 node_find_closest (GSequenceNode
*haystack
,
1744 GSequenceNode
*needle
,
1746 GSequenceIterCompareFunc iter_cmp
,
1749 GSequenceNode
*best
;
1752 haystack
= find_root (haystack
);
1758 /* iter_cmp can't be passed the end node, since the function may
1761 if (haystack
== end
)
1764 c
= iter_cmp (haystack
, needle
, cmp_data
);
1766 /* In the following we don't break even if c == 0. Instead we go on
1767 * searching along the 'bigger' nodes, so that we find the last one
1768 * that is equal to the needle.
1771 haystack
= haystack
->left
;
1773 haystack
= haystack
->right
;
1775 while (haystack
!= NULL
);
1777 /* If the best node is smaller or equal to the data, then move one step
1778 * to the right to make sure the best one is strictly bigger than the data
1780 if (best
!= end
&& c
<= 0)
1781 best
= node_get_next (best
);
1787 node_get_length (GSequenceNode
*node
)
1789 node
= find_root (node
);
1791 return node
->n_nodes
;
1795 real_node_free (GSequenceNode
*node
,
1800 real_node_free (node
->left
, seq
);
1801 real_node_free (node
->right
, seq
);
1803 if (seq
&& seq
->data_destroy_notify
&& node
!= seq
->end_node
)
1804 seq
->data_destroy_notify (node
->data
);
1806 g_slice_free (GSequenceNode
, node
);
1811 node_free (GSequenceNode
*node
,
1814 node
= find_root (node
);
1816 real_node_free (node
, seq
);
1820 node_update_fields (GSequenceNode
*node
)
1824 n_nodes
+= N_NODES (node
->left
);
1825 n_nodes
+= N_NODES (node
->right
);
1827 node
->n_nodes
= n_nodes
;
1831 node_rotate (GSequenceNode
*node
)
1833 GSequenceNode
*tmp
, *old
;
1835 g_assert (node
->parent
);
1836 g_assert (node
->parent
!= node
);
1838 if (NODE_LEFT_CHILD (node
))
1843 node
->right
= node
->parent
;
1844 node
->parent
= node
->parent
->parent
;
1847 if (node
->parent
->left
== node
->right
)
1848 node
->parent
->left
= node
;
1850 node
->parent
->right
= node
;
1853 g_assert (node
->right
);
1855 node
->right
->parent
= node
;
1856 node
->right
->left
= tmp
;
1858 if (node
->right
->left
)
1859 node
->right
->left
->parent
= node
->right
;
1868 node
->left
= node
->parent
;
1869 node
->parent
= node
->parent
->parent
;
1872 if (node
->parent
->right
== node
->left
)
1873 node
->parent
->right
= node
;
1875 node
->parent
->left
= node
;
1878 g_assert (node
->left
);
1880 node
->left
->parent
= node
;
1881 node
->left
->right
= tmp
;
1883 if (node
->left
->right
)
1884 node
->left
->right
->parent
= node
->left
;
1889 node_update_fields (old
);
1890 node_update_fields (node
);
1894 node_update_fields_deep (GSequenceNode
*node
)
1898 node_update_fields (node
);
1900 node_update_fields_deep (node
->parent
);
1905 rotate_down (GSequenceNode
*node
,
1910 left
= node
->left
? get_priority (node
->left
) : 0;
1911 right
= node
->right
? get_priority (node
->right
) : 0;
1913 while (priority
< left
|| priority
< right
)
1916 node_rotate (node
->left
);
1918 node_rotate (node
->right
);
1920 left
= node
->left
? get_priority (node
->left
) : 0;
1921 right
= node
->right
? get_priority (node
->right
) : 0;
1926 node_cut (GSequenceNode
*node
)
1928 while (node
->parent
)
1932 node
->left
->parent
= NULL
;
1935 node_update_fields (node
);
1937 rotate_down (node
, get_priority (node
));
1941 node_join (GSequenceNode
*left
,
1942 GSequenceNode
*right
)
1944 GSequenceNode
*fake
= node_new (NULL
);
1946 fake
->left
= find_root (left
);
1947 fake
->right
= find_root (right
);
1948 fake
->left
->parent
= fake
;
1949 fake
->right
->parent
= fake
;
1951 node_update_fields (fake
);
1955 node_free (fake
, NULL
);
1959 node_insert_before (GSequenceNode
*node
,
1962 new->left
= node
->left
;
1964 new->left
->parent
= new;
1969 node_update_fields_deep (new);
1971 while (new->parent
&& get_priority (new) > get_priority (new->parent
))
1974 rotate_down (new, get_priority (new));
1978 node_unlink (GSequenceNode
*node
)
1980 rotate_down (node
, 0);
1982 if (NODE_RIGHT_CHILD (node
))
1983 node
->parent
->right
= NULL
;
1984 else if (NODE_LEFT_CHILD (node
))
1985 node
->parent
->left
= NULL
;
1988 node_update_fields_deep (node
->parent
);
1990 node
->parent
= NULL
;
1994 node_insert_sorted (GSequenceNode
*node
,
1997 GSequenceIterCompareFunc iter_cmp
,
2000 GSequenceNode
*closest
;
2002 closest
= node_find_closest (node
, new, end
, iter_cmp
, cmp_data
);
2006 node_insert_before (closest
, new);