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
833 * @cmp_data, or %NULL if no such item exists.
838 g_sequence_lookup (GSequence
*seq
,
840 GCompareDataFunc cmp_func
,
845 g_return_val_if_fail (seq
!= NULL
, NULL
);
847 info
.cmp_func
= cmp_func
;
848 info
.cmp_data
= cmp_data
;
849 info
.end_node
= seq
->end_node
;
850 check_seq_access (seq
);
852 return g_sequence_lookup_iter (seq
, data
, iter_compare
, &info
);
856 * g_sequence_sort_iter:
858 * @cmp_func: the function used to compare iterators in the sequence
859 * @cmp_data: user data passed to @cmp_func
861 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
862 * of a GCompareDataFunc as the compare function
864 * @cmp_func is called with two iterators pointing into @seq. It should
865 * return 0 if the iterators are equal, a negative value if the first
866 * iterator comes before the second, and a positive value if the second
867 * iterator comes before the first.
872 g_sequence_sort_iter (GSequence
*seq
,
873 GSequenceIterCompareFunc cmp_func
,
877 GSequenceNode
*begin
, *end
;
879 g_return_if_fail (seq
!= NULL
);
880 g_return_if_fail (cmp_func
!= NULL
);
882 check_seq_access (seq
);
884 begin
= g_sequence_get_begin_iter (seq
);
885 end
= g_sequence_get_end_iter (seq
);
887 tmp
= g_sequence_new (NULL
);
888 tmp
->real_sequence
= seq
;
890 g_sequence_move_range (g_sequence_get_begin_iter (tmp
), begin
, end
);
892 seq
->access_prohibited
= TRUE
;
893 tmp
->access_prohibited
= TRUE
;
895 while (g_sequence_get_length (tmp
) > 0)
897 GSequenceNode
*node
= g_sequence_get_begin_iter (tmp
);
899 node_insert_sorted (seq
->end_node
, node
, seq
->end_node
,
903 tmp
->access_prohibited
= FALSE
;
904 seq
->access_prohibited
= FALSE
;
906 g_sequence_free (tmp
);
910 * g_sequence_sort_changed_iter:
911 * @iter: a #GSequenceIter
912 * @iter_cmp: the function used to compare iterators in the sequence
913 * @cmp_data: user data passed to @cmp_func
915 * Like g_sequence_sort_changed(), but uses
916 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
917 * the compare function.
919 * @iter_cmp is called with two iterators pointing into @seq. It should
920 * return 0 if the iterators are equal, a negative value if the first
921 * iterator comes before the second, and a positive value if the second
922 * iterator comes before the first.
927 g_sequence_sort_changed_iter (GSequenceIter
*iter
,
928 GSequenceIterCompareFunc iter_cmp
,
931 GSequence
*seq
, *tmp_seq
;
932 GSequenceIter
*next
, *prev
;
934 g_return_if_fail (iter
!= NULL
);
935 g_return_if_fail (!is_end (iter
));
936 g_return_if_fail (iter_cmp
!= NULL
);
937 check_iter_access (iter
);
939 /* If one of the neighbours is equal to iter, then
940 * don't move it. This ensures that sort_changed() is
941 * a stable operation.
944 next
= node_get_next (iter
);
945 prev
= node_get_prev (iter
);
947 if (prev
!= iter
&& iter_cmp (prev
, iter
, cmp_data
) == 0)
950 if (!is_end (next
) && iter_cmp (next
, iter
, cmp_data
) == 0)
953 seq
= get_sequence (iter
);
955 seq
->access_prohibited
= TRUE
;
957 tmp_seq
= g_sequence_new (NULL
);
958 tmp_seq
->real_sequence
= seq
;
961 node_insert_before (tmp_seq
->end_node
, iter
);
963 node_insert_sorted (seq
->end_node
, iter
, seq
->end_node
,
966 g_sequence_free (tmp_seq
);
968 seq
->access_prohibited
= FALSE
;
972 * g_sequence_insert_sorted_iter:
974 * @data: data for the new item
975 * @iter_cmp: the function used to compare iterators in the sequence
976 * @cmp_data: user data passed to @cmp_func
978 * Like g_sequence_insert_sorted(), but uses
979 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
980 * the compare function.
982 * @iter_cmp is called with two iterators pointing into @seq.
983 * It should return 0 if the iterators are equal, a negative
984 * value if the first iterator comes before the second, and a
985 * positive value if the second iterator comes before the first.
987 * It is called with two iterators pointing into @seq. It should
988 * return 0 if the iterators are equal, a negative value if the
989 * first iterator comes before the second, and a positive value
990 * if the second iterator comes before the first.
992 * Return value: a #GSequenceIter pointing to the new item
997 g_sequence_insert_sorted_iter (GSequence
*seq
,
999 GSequenceIterCompareFunc iter_cmp
,
1002 GSequenceNode
*new_node
;
1005 g_return_val_if_fail (seq
!= NULL
, NULL
);
1006 g_return_val_if_fail (iter_cmp
!= NULL
, NULL
);
1008 check_seq_access (seq
);
1010 seq
->access_prohibited
= TRUE
;
1012 /* Create a new temporary sequence and put the new node into
1013 * that. The reason for this is that the user compare function
1014 * will be called with the new node, and if it dereferences,
1015 * "is_end" will be called on it. But that will crash if the
1016 * node is not actually in a sequence.
1018 * node_insert_sorted() makes sure the node is unlinked before
1021 * The reason we need the "iter" versions at all is that that
1022 * is the only kind of compare functions GtkTreeView can use.
1024 tmp_seq
= g_sequence_new (NULL
);
1025 tmp_seq
->real_sequence
= seq
;
1027 new_node
= g_sequence_append (tmp_seq
, data
);
1029 node_insert_sorted (seq
->end_node
, new_node
,
1030 seq
->end_node
, iter_cmp
, cmp_data
);
1032 g_sequence_free (tmp_seq
);
1034 seq
->access_prohibited
= FALSE
;
1040 * g_sequence_search_iter:
1041 * @seq: a #GSequence
1042 * @data: data for the new item
1043 * @iter_cmp: the function used to compare iterators in the sequence
1044 * @cmp_data: user data passed to @iter_cmp
1046 * Like g_sequence_search(), but uses a #GSequenceIterCompareFunc
1047 * instead of a #GCompareDataFunc as the compare function.
1049 * @iter_cmp is called with two iterators pointing into @seq.
1050 * It should return 0 if the iterators are equal, a negative value
1051 * if the first iterator comes before the second, and a positive
1052 * value if the second iterator comes before the first.
1054 * If you are simply searching for an existing element of the sequence,
1055 * consider using g_sequence_lookup_iter().
1058 * This function will fail if the data contained in the sequence is
1059 * unsorted. Use g_sequence_insert_sorted() or
1060 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
1061 * you want to add a large amount of data, call g_sequence_sort() after
1062 * doing unsorted insertions.
1065 * Return value: a #GSequenceIter pointing to the position in @seq
1066 * where @data would have been inserted according to @iter_cmp
1072 g_sequence_search_iter (GSequence
*seq
,
1074 GSequenceIterCompareFunc iter_cmp
,
1077 GSequenceNode
*node
;
1078 GSequenceNode
*dummy
;
1081 g_return_val_if_fail (seq
!= NULL
, NULL
);
1083 check_seq_access (seq
);
1085 seq
->access_prohibited
= TRUE
;
1087 tmp_seq
= g_sequence_new (NULL
);
1088 tmp_seq
->real_sequence
= seq
;
1090 dummy
= g_sequence_append (tmp_seq
, data
);
1092 node
= node_find_closest (seq
->end_node
, dummy
,
1093 seq
->end_node
, iter_cmp
, cmp_data
);
1095 g_sequence_free (tmp_seq
);
1097 seq
->access_prohibited
= FALSE
;
1103 * g_sequence_lookup_iter:
1104 * @seq: a #GSequence
1105 * @data: data to lookup
1106 * @iter_cmp: the function used to compare iterators in the sequence
1107 * @cmp_data: user data passed to @iter_cmp
1109 * Like g_sequence_lookup(), but uses a #GSequenceIterCompareFunc
1110 * instead of a #GCompareDataFunc as the compare function.
1112 * @iter_cmp is called with two iterators pointing into @seq.
1113 * It should return 0 if the iterators are equal, a negative value
1114 * if the first iterator comes before the second, and a positive
1115 * value if the second iterator comes before the first.
1118 * This function will fail if the data contained in the sequence is
1119 * unsorted. Use g_sequence_insert_sorted() or
1120 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
1121 * you want to add a large amount of data, call g_sequence_sort() after
1122 * doing unsorted insertions.
1125 * Return value: an #GSequenceIter pointing to the position of
1126 * the first item found equal to @data according to @cmp_func
1127 * and @cmp_data, or %NULL if no such item exists.
1132 g_sequence_lookup_iter (GSequence
*seq
,
1134 GSequenceIterCompareFunc iter_cmp
,
1137 GSequenceNode
*node
;
1138 GSequenceNode
*dummy
;
1141 g_return_val_if_fail (seq
!= NULL
, NULL
);
1143 check_seq_access (seq
);
1145 seq
->access_prohibited
= TRUE
;
1147 tmp_seq
= g_sequence_new (NULL
);
1148 tmp_seq
->real_sequence
= seq
;
1150 dummy
= g_sequence_append (tmp_seq
, data
);
1152 node
= node_find (seq
->end_node
, dummy
,
1153 seq
->end_node
, iter_cmp
, cmp_data
);
1155 g_sequence_free (tmp_seq
);
1157 seq
->access_prohibited
= FALSE
;
1163 * g_sequence_iter_get_sequence:
1164 * @iter: a #GSequenceIter
1166 * Returns the #GSequence that @iter points into.
1168 * Return value: the #GSequence that @iter points into.
1173 g_sequence_iter_get_sequence (GSequenceIter
*iter
)
1177 g_return_val_if_fail (iter
!= NULL
, NULL
);
1179 seq
= get_sequence (iter
);
1181 /* For temporary sequences, this points to the sequence that
1182 * is actually being manipulated
1184 return seq
->real_sequence
;
1189 * @iter: a #GSequenceIter
1191 * Returns the data that @iter points to.
1193 * Return value: the data that @iter points to
1198 g_sequence_get (GSequenceIter
*iter
)
1200 g_return_val_if_fail (iter
!= NULL
, NULL
);
1201 g_return_val_if_fail (!is_end (iter
), NULL
);
1208 * @iter: a #GSequenceIter
1209 * @data: new data for the item
1211 * Changes the data for the item pointed to by @iter to be @data. If
1212 * the sequence has a data destroy function associated with it, that
1213 * function is called on the existing data that @iter pointed to.
1218 g_sequence_set (GSequenceIter
*iter
,
1223 g_return_if_fail (iter
!= NULL
);
1224 g_return_if_fail (!is_end (iter
));
1226 seq
= get_sequence (iter
);
1228 /* If @data is identical to iter->data, it is destroyed
1229 * here. This will work right in case of ref-counted objects. Also
1230 * it is similar to what ghashtables do.
1232 * For non-refcounted data it's a little less convenient, but
1233 * code relying on self-setting not destroying would be
1234 * pretty dubious anyway ...
1237 if (seq
->data_destroy_notify
)
1238 seq
->data_destroy_notify (iter
->data
);
1244 * g_sequence_get_length:
1245 * @seq: a #GSequence
1247 * Returns the length of @seq
1249 * Return value: the length of @seq
1254 g_sequence_get_length (GSequence
*seq
)
1256 return node_get_length (seq
->end_node
) - 1;
1260 * g_sequence_get_end_iter:
1261 * @seq: a #GSequence
1263 * Returns the end iterator for @seg
1265 * Return value: the end iterator for @seq
1270 g_sequence_get_end_iter (GSequence
*seq
)
1272 g_return_val_if_fail (seq
!= NULL
, NULL
);
1274 return seq
->end_node
;
1278 * g_sequence_get_begin_iter:
1279 * @seq: a #GSequence
1281 * Returns the begin iterator for @seq.
1283 * Return value: the begin iterator for @seq.
1288 g_sequence_get_begin_iter (GSequence
*seq
)
1290 g_return_val_if_fail (seq
!= NULL
, NULL
);
1292 return node_get_first (seq
->end_node
);
1296 clamp_position (GSequence
*seq
,
1299 gint len
= g_sequence_get_length (seq
);
1301 if (pos
> len
|| pos
< 0)
1308 * if pos > number of items or -1, will return end pointer
1311 * g_sequence_get_iter_at_pos:
1312 * @seq: a #GSequence
1313 * @pos: a position in @seq, or -1 for the end.
1315 * Returns the iterator at position @pos. If @pos is negative or larger
1316 * than the number of items in @seq, the end iterator is returned.
1318 * Return value: The #GSequenceIter at position @pos
1323 g_sequence_get_iter_at_pos (GSequence
*seq
,
1326 g_return_val_if_fail (seq
!= NULL
, NULL
);
1328 pos
= clamp_position (seq
, pos
);
1330 return node_get_by_pos (seq
->end_node
, pos
);
1335 * @src: a #GSequenceIter pointing to the item to move
1336 * @dest: a #GSequenceIter pointing to the position to which
1337 * the item is moved.
1339 * Moves the item pointed to by @src to the position indicated by @dest.
1340 * After calling this function @dest will point to the position immediately
1341 * after @src. It is allowed for @src and @dest to point into different
1347 g_sequence_move (GSequenceIter
*src
,
1348 GSequenceIter
*dest
)
1350 g_return_if_fail (src
!= NULL
);
1351 g_return_if_fail (dest
!= NULL
);
1352 g_return_if_fail (!is_end (src
));
1358 node_insert_before (dest
, src
);
1364 * g_sequence_iter_is_end:
1365 * @iter: a #GSequenceIter
1367 * Returns whether @iter is the end iterator
1369 * Return value: Whether @iter is the end iterator.
1374 g_sequence_iter_is_end (GSequenceIter
*iter
)
1376 g_return_val_if_fail (iter
!= NULL
, FALSE
);
1378 return is_end (iter
);
1382 * g_sequence_iter_is_begin:
1383 * @iter: a #GSequenceIter
1385 * Returns whether @iter is the begin iterator
1387 * Return value: whether @iter is the begin iterator
1392 g_sequence_iter_is_begin (GSequenceIter
*iter
)
1394 g_return_val_if_fail (iter
!= NULL
, FALSE
);
1396 return (node_get_prev (iter
) == iter
);
1400 * g_sequence_iter_get_position:
1401 * @iter: a #GSequenceIter
1403 * Returns the position of @iter
1405 * Return value: the position of @iter
1410 g_sequence_iter_get_position (GSequenceIter
*iter
)
1412 g_return_val_if_fail (iter
!= NULL
, -1);
1414 return node_get_pos (iter
);
1418 * g_sequence_iter_next:
1419 * @iter: a #GSequenceIter
1421 * Returns an iterator pointing to the next position after @iter. If
1422 * @iter is the end iterator, the end iterator is returned.
1424 * Return value: a #GSequenceIter pointing to the next position after @iter.
1429 g_sequence_iter_next (GSequenceIter
*iter
)
1431 g_return_val_if_fail (iter
!= NULL
, NULL
);
1433 return node_get_next (iter
);
1437 * g_sequence_iter_prev:
1438 * @iter: a #GSequenceIter
1440 * Returns an iterator pointing to the previous position before @iter. If
1441 * @iter is the begin iterator, the begin iterator is returned.
1443 * Return value: a #GSequenceIter pointing to the previous position before
1449 g_sequence_iter_prev (GSequenceIter
*iter
)
1451 g_return_val_if_fail (iter
!= NULL
, NULL
);
1453 return node_get_prev (iter
);
1457 * g_sequence_iter_move:
1458 * @iter: a #GSequenceIter
1459 * @delta: A positive or negative number indicating how many positions away
1460 * from @iter the returned #GSequenceIter will be.
1462 * Returns the #GSequenceIter which is @delta positions away from @iter.
1463 * If @iter is closer than -@delta positions to the beginning of the sequence,
1464 * the begin iterator is returned. If @iter is closer than @delta positions
1465 * to the end of the sequence, the end iterator is returned.
1467 * Return value: a #GSequenceIter which is @delta positions away from @iter.
1472 g_sequence_iter_move (GSequenceIter
*iter
,
1478 g_return_val_if_fail (iter
!= NULL
, NULL
);
1480 len
= g_sequence_get_length (get_sequence (iter
));
1482 new_pos
= node_get_pos (iter
) + delta
;
1486 else if (new_pos
> len
)
1489 return node_get_by_pos (iter
, new_pos
);
1494 * @a: a #GSequenceIter
1495 * @b: a #GSequenceIter
1497 * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
1498 * to point into difference sequences.
1503 g_sequence_swap (GSequenceIter
*a
,
1506 GSequenceNode
*leftmost
, *rightmost
, *rightmost_next
;
1509 g_return_if_fail (!g_sequence_iter_is_end (a
));
1510 g_return_if_fail (!g_sequence_iter_is_end (b
));
1515 a_pos
= g_sequence_iter_get_position (a
);
1516 b_pos
= g_sequence_iter_get_position (b
);
1529 rightmost_next
= node_get_next (rightmost
);
1531 /* The situation is now like this:
1533 * ..., leftmost, ......., rightmost, rightmost_next, ...
1536 g_sequence_move (rightmost
, leftmost
);
1537 g_sequence_move (leftmost
, rightmost_next
);
1541 * Implementation of a treap
1546 get_priority (GSequenceNode
*node
)
1548 guint key
= GPOINTER_TO_UINT (node
);
1550 /* This hash function is based on one found on Thomas Wang's
1553 * http://www.concentric.net/~Ttwang/tech/inthash.htm
1556 key
= (key
<< 15) - key
- 1;
1557 key
= key
^ (key
>> 12);
1558 key
= key
+ (key
<< 2);
1559 key
= key
^ (key
>> 4);
1560 key
= key
+ (key
<< 3) + (key
<< 11);
1561 key
= key
^ (key
>> 16);
1563 /* We rely on 0 being less than all other priorities */
1564 return key
? key
: 1;
1567 static GSequenceNode
*
1568 find_root (GSequenceNode
*node
)
1570 while (node
->parent
)
1571 node
= node
->parent
;
1576 static GSequenceNode
*
1577 node_new (gpointer data
)
1579 GSequenceNode
*node
= g_slice_new0 (GSequenceNode
);
1585 node
->parent
= NULL
;
1590 static GSequenceNode
*
1591 node_get_first (GSequenceNode
*node
)
1593 node
= find_root (node
);
1601 static GSequenceNode
*
1602 node_get_last (GSequenceNode
*node
)
1604 node
= find_root (node
);
1612 #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1613 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1615 static GSequenceNode
*
1616 node_get_next (GSequenceNode
*node
)
1618 GSequenceNode
*n
= node
;
1628 while (NODE_RIGHT_CHILD (n
))
1640 static GSequenceNode
*
1641 node_get_prev (GSequenceNode
*node
)
1643 GSequenceNode
*n
= node
;
1653 while (NODE_LEFT_CHILD (n
))
1665 #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1668 node_get_pos (GSequenceNode
*node
)
1673 n_smaller
= node
->left
->n_nodes
;
1677 if (NODE_RIGHT_CHILD (node
))
1678 n_smaller
+= N_NODES (node
->parent
->left
) + 1;
1680 node
= node
->parent
;
1686 static GSequenceNode
*
1687 node_get_by_pos (GSequenceNode
*node
,
1692 node
= find_root (node
);
1694 while ((i
= N_NODES (node
->left
)) != pos
)
1710 static GSequenceNode
*
1711 node_find (GSequenceNode
*haystack
,
1712 GSequenceNode
*needle
,
1714 GSequenceIterCompareFunc iter_cmp
,
1719 haystack
= find_root (haystack
);
1723 /* iter_cmp can't be passed the end node, since the function may
1726 if (haystack
== end
)
1729 c
= iter_cmp (haystack
, needle
, cmp_data
);
1735 haystack
= haystack
->left
;
1737 haystack
= haystack
->right
;
1739 while (haystack
!= NULL
);
1744 static GSequenceNode
*
1745 node_find_closest (GSequenceNode
*haystack
,
1746 GSequenceNode
*needle
,
1748 GSequenceIterCompareFunc iter_cmp
,
1751 GSequenceNode
*best
;
1754 haystack
= find_root (haystack
);
1760 /* iter_cmp can't be passed the end node, since the function may
1763 if (haystack
== end
)
1766 c
= iter_cmp (haystack
, needle
, cmp_data
);
1768 /* In the following we don't break even if c == 0. Instead we go on
1769 * searching along the 'bigger' nodes, so that we find the last one
1770 * that is equal to the needle.
1773 haystack
= haystack
->left
;
1775 haystack
= haystack
->right
;
1777 while (haystack
!= NULL
);
1779 /* If the best node is smaller or equal to the data, then move one step
1780 * to the right to make sure the best one is strictly bigger than the data
1782 if (best
!= end
&& c
<= 0)
1783 best
= node_get_next (best
);
1789 node_get_length (GSequenceNode
*node
)
1791 node
= find_root (node
);
1793 return node
->n_nodes
;
1797 real_node_free (GSequenceNode
*node
,
1802 real_node_free (node
->left
, seq
);
1803 real_node_free (node
->right
, seq
);
1805 if (seq
&& seq
->data_destroy_notify
&& node
!= seq
->end_node
)
1806 seq
->data_destroy_notify (node
->data
);
1808 g_slice_free (GSequenceNode
, node
);
1813 node_free (GSequenceNode
*node
,
1816 node
= find_root (node
);
1818 real_node_free (node
, seq
);
1822 node_update_fields (GSequenceNode
*node
)
1826 n_nodes
+= N_NODES (node
->left
);
1827 n_nodes
+= N_NODES (node
->right
);
1829 node
->n_nodes
= n_nodes
;
1833 node_rotate (GSequenceNode
*node
)
1835 GSequenceNode
*tmp
, *old
;
1837 g_assert (node
->parent
);
1838 g_assert (node
->parent
!= node
);
1840 if (NODE_LEFT_CHILD (node
))
1845 node
->right
= node
->parent
;
1846 node
->parent
= node
->parent
->parent
;
1849 if (node
->parent
->left
== node
->right
)
1850 node
->parent
->left
= node
;
1852 node
->parent
->right
= node
;
1855 g_assert (node
->right
);
1857 node
->right
->parent
= node
;
1858 node
->right
->left
= tmp
;
1860 if (node
->right
->left
)
1861 node
->right
->left
->parent
= node
->right
;
1870 node
->left
= node
->parent
;
1871 node
->parent
= node
->parent
->parent
;
1874 if (node
->parent
->right
== node
->left
)
1875 node
->parent
->right
= node
;
1877 node
->parent
->left
= node
;
1880 g_assert (node
->left
);
1882 node
->left
->parent
= node
;
1883 node
->left
->right
= tmp
;
1885 if (node
->left
->right
)
1886 node
->left
->right
->parent
= node
->left
;
1891 node_update_fields (old
);
1892 node_update_fields (node
);
1896 node_update_fields_deep (GSequenceNode
*node
)
1900 node_update_fields (node
);
1902 node_update_fields_deep (node
->parent
);
1907 rotate_down (GSequenceNode
*node
,
1912 left
= node
->left
? get_priority (node
->left
) : 0;
1913 right
= node
->right
? get_priority (node
->right
) : 0;
1915 while (priority
< left
|| priority
< right
)
1918 node_rotate (node
->left
);
1920 node_rotate (node
->right
);
1922 left
= node
->left
? get_priority (node
->left
) : 0;
1923 right
= node
->right
? get_priority (node
->right
) : 0;
1928 node_cut (GSequenceNode
*node
)
1930 while (node
->parent
)
1934 node
->left
->parent
= NULL
;
1937 node_update_fields (node
);
1939 rotate_down (node
, get_priority (node
));
1943 node_join (GSequenceNode
*left
,
1944 GSequenceNode
*right
)
1946 GSequenceNode
*fake
= node_new (NULL
);
1948 fake
->left
= find_root (left
);
1949 fake
->right
= find_root (right
);
1950 fake
->left
->parent
= fake
;
1951 fake
->right
->parent
= fake
;
1953 node_update_fields (fake
);
1957 node_free (fake
, NULL
);
1961 node_insert_before (GSequenceNode
*node
,
1964 new->left
= node
->left
;
1966 new->left
->parent
= new;
1971 node_update_fields_deep (new);
1973 while (new->parent
&& get_priority (new) > get_priority (new->parent
))
1976 rotate_down (new, get_priority (new));
1980 node_unlink (GSequenceNode
*node
)
1982 rotate_down (node
, 0);
1984 if (NODE_RIGHT_CHILD (node
))
1985 node
->parent
->right
= NULL
;
1986 else if (NODE_LEFT_CHILD (node
))
1987 node
->parent
->left
= NULL
;
1990 node_update_fields_deep (node
->parent
);
1992 node
->parent
= NULL
;
1996 node_insert_sorted (GSequenceNode
*node
,
1999 GSequenceIterCompareFunc iter_cmp
,
2002 GSequenceNode
*closest
;
2004 closest
= node_find_closest (node
, new, end
, iter_cmp
, cmp_data
);
2008 node_insert_before (closest
, new);