1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
3 * Soeren Sandmann (sandmann@daimi.au.dk)
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
21 #include "gsequence.h"
24 #include "gtestutils.h"
29 * @short_description: scalable lists
31 * The #GSequence data structure has the API of a list, but is
32 * implemented internally with a balanced binary tree. This means that
33 * it is possible to maintain a sorted list of n elements in time O(n log n).
34 * The data contained in each element can be either integer values, by using
35 * of the [Type Conversion Macros][glib-Type-Conversion-Macros], or simply
36 * pointers to any type of data.
38 * A #GSequence is accessed through "iterators", represented by a
39 * #GSequenceIter. An iterator represents a position between two
40 * elements of the sequence. For example, the "begin" iterator
41 * represents the gap immediately before the first element of the
42 * sequence, and the "end" iterator represents the gap immediately
43 * after the last element. In an empty sequence, the begin and end
44 * iterators are the same.
46 * Some methods on #GSequence operate on ranges of items. For example
47 * g_sequence_foreach_range() will call a user-specified function on
48 * each element with the given range. The range is delimited by the
49 * gaps represented by the passed-in iterators, so if you pass in the
50 * begin and end iterators, the range in question is the entire
53 * The function g_sequence_get() is used with an iterator to access the
54 * element immediately following the gap that the iterator represents.
55 * The iterator is said to "point" to that element.
57 * Iterators are stable across most operations on a #GSequence. For
58 * example an iterator pointing to some element of a sequence will
59 * continue to point to that element even after the sequence is sorted.
60 * Even moving an element to another sequence using for example
61 * g_sequence_move_range() will not invalidate the iterators pointing
62 * to it. The only operation that will invalidate an iterator is when
63 * the element it points to is removed from any sequence.
69 * The #GSequenceIter struct is an opaque data type representing an
70 * iterator pointing into a #GSequence.
74 * GSequenceIterCompareFunc:
75 * @a: a #GSequenceIter
76 * @b: a #GSequenceIter
79 * A #GSequenceIterCompareFunc is a function used to compare iterators.
80 * It must return zero if the iterators compare equal, a negative value
81 * if @a comes before @b, and a positive value if @b comes before @a.
83 * Returns: zero if the iterators are equal, a negative value if @a
84 * comes before @b, and a positive value if @b comes before @a.
87 typedef struct _GSequenceNode GSequenceNode
;
92 * The #GSequence struct is an opaque data type representing a
93 * [sequence][glib-Sequences] data type.
97 GSequenceNode
* end_node
;
98 GDestroyNotify data_destroy_notify
;
99 gboolean access_prohibited
;
101 /* The 'real_sequence' is used when temporary sequences are created
102 * to hold nodes that are being rearranged. The 'real_sequence' of such
103 * a temporary sequence points to the sequence that is actually being
104 * manipulated. The only reason we need this is so that when the
105 * sort/sort_changed/search_iter() functions call out to the application
106 * g_sequence_iter_get_sequence() will return the correct sequence.
108 GSequence
* real_sequence
;
111 struct _GSequenceNode
114 GSequenceNode
* parent
;
115 GSequenceNode
* left
;
116 GSequenceNode
* right
;
117 gpointer data
; /* For the end node, this field points
123 * Declaration of GSequenceNode methods
125 static GSequenceNode
*node_new (gpointer data
);
126 static GSequenceNode
*node_get_first (GSequenceNode
*node
);
127 static GSequenceNode
*node_get_last (GSequenceNode
*node
);
128 static GSequenceNode
*node_get_prev (GSequenceNode
*node
);
129 static GSequenceNode
*node_get_next (GSequenceNode
*node
);
130 static gint
node_get_pos (GSequenceNode
*node
);
131 static GSequenceNode
*node_get_by_pos (GSequenceNode
*node
,
133 static GSequenceNode
*node_find (GSequenceNode
*haystack
,
134 GSequenceNode
*needle
,
136 GSequenceIterCompareFunc cmp
,
138 static GSequenceNode
*node_find_closest (GSequenceNode
*haystack
,
139 GSequenceNode
*needle
,
141 GSequenceIterCompareFunc cmp
,
143 static gint
node_get_length (GSequenceNode
*node
);
144 static void node_free (GSequenceNode
*node
,
146 static void node_cut (GSequenceNode
*split
);
147 static void node_insert_before (GSequenceNode
*node
,
149 static void node_unlink (GSequenceNode
*node
);
150 static void node_join (GSequenceNode
*left
,
151 GSequenceNode
*right
);
152 static void node_insert_sorted (GSequenceNode
*node
,
155 GSequenceIterCompareFunc cmp_func
,
160 * Various helper functions
163 check_seq_access (GSequence
*seq
)
165 if (G_UNLIKELY (seq
->access_prohibited
))
167 g_warning ("Accessing a sequence while it is "
168 "being sorted or searched is not allowed");
173 get_sequence (GSequenceNode
*node
)
175 return (GSequence
*)node_get_last (node
)->data
;
179 check_iter_access (GSequenceIter
*iter
)
181 check_seq_access (get_sequence (iter
));
185 is_end (GSequenceIter
*iter
)
195 if (iter
->parent
->right
!= iter
)
198 seq
= get_sequence (iter
);
200 return seq
->end_node
== iter
;
205 GCompareDataFunc cmp_func
;
207 GSequenceNode
*end_node
;
210 /* This function compares two iters using a normal compare
211 * function and user_data passed in in a SortInfo struct
214 iter_compare (GSequenceIter
*node1
,
215 GSequenceIter
*node2
,
218 const SortInfo
*info
= data
;
221 if (node1
== info
->end_node
)
224 if (node2
== info
->end_node
)
227 retval
= info
->cmp_func (node1
->data
, node2
->data
, info
->cmp_data
);
238 * @data_destroy: (allow-none): a #GDestroyNotify function, or %NULL
240 * Creates a new GSequence. The @data_destroy function, if non-%NULL will
241 * be called on all items when the sequence is destroyed and on items that
242 * are removed from the sequence.
244 * Returns: a new #GSequence
249 g_sequence_new (GDestroyNotify data_destroy
)
251 GSequence
*seq
= g_new (GSequence
, 1);
252 seq
->data_destroy_notify
= data_destroy
;
254 seq
->end_node
= node_new (seq
);
256 seq
->access_prohibited
= FALSE
;
258 seq
->real_sequence
= seq
;
267 * Frees the memory allocated for @seq. If @seq has a data destroy
268 * function associated with it, that function is called on all items
274 g_sequence_free (GSequence
*seq
)
276 g_return_if_fail (seq
!= NULL
);
278 check_seq_access (seq
);
280 node_free (seq
->end_node
, seq
);
286 * g_sequence_foreach_range:
287 * @begin: a #GSequenceIter
288 * @end: a #GSequenceIter
290 * @user_data: user data passed to @func
292 * Calls @func for each item in the range (@begin, @end) passing
293 * @user_data to the function.
298 g_sequence_foreach_range (GSequenceIter
*begin
,
306 g_return_if_fail (func
!= NULL
);
307 g_return_if_fail (begin
!= NULL
);
308 g_return_if_fail (end
!= NULL
);
310 seq
= get_sequence (begin
);
312 seq
->access_prohibited
= TRUE
;
317 GSequenceIter
*next
= node_get_next (iter
);
319 func (iter
->data
, user_data
);
324 seq
->access_prohibited
= FALSE
;
328 * g_sequence_foreach:
330 * @func: the function to call for each item in @seq
331 * @user_data: user data passed to @func
333 * Calls @func for each item in the sequence passing @user_data
339 g_sequence_foreach (GSequence
*seq
,
343 GSequenceIter
*begin
, *end
;
345 check_seq_access (seq
);
347 begin
= g_sequence_get_begin_iter (seq
);
348 end
= g_sequence_get_end_iter (seq
);
350 g_sequence_foreach_range (begin
, end
, func
, user_data
);
354 * g_sequence_range_get_midpoint:
355 * @begin: a #GSequenceIter
356 * @end: a #GSequenceIter
358 * Finds an iterator somewhere in the range (@begin, @end). This
359 * iterator will be close to the middle of the range, but is not
360 * guaranteed to be exactly in the middle.
362 * The @begin and @end iterators must both point to the same sequence
363 * and @begin must come before or be equal to @end in the sequence.
365 * Returns: a #GSequenceIter pointing somewhere in the
366 * (@begin, @end) range
371 g_sequence_range_get_midpoint (GSequenceIter
*begin
,
374 int begin_pos
, end_pos
, mid_pos
;
376 g_return_val_if_fail (begin
!= NULL
, NULL
);
377 g_return_val_if_fail (end
!= NULL
, NULL
);
378 g_return_val_if_fail (get_sequence (begin
) == get_sequence (end
), NULL
);
380 begin_pos
= node_get_pos (begin
);
381 end_pos
= node_get_pos (end
);
383 g_return_val_if_fail (end_pos
>= begin_pos
, NULL
);
385 mid_pos
= begin_pos
+ (end_pos
- begin_pos
) / 2;
387 return node_get_by_pos (begin
, mid_pos
);
391 * g_sequence_iter_compare:
392 * @a: a #GSequenceIter
393 * @b: a #GSequenceIter
395 * Returns a negative number if @a comes before @b, 0 if they are equal,
396 * and a positive number if @a comes after @b.
398 * The @a and @b iterators must point into the same sequence.
400 * Returns: a negative number if @a comes before @b, 0 if they are
401 * equal, and a positive number if @a comes after @b
406 g_sequence_iter_compare (GSequenceIter
*a
,
411 g_return_val_if_fail (a
!= NULL
, 0);
412 g_return_val_if_fail (b
!= NULL
, 0);
413 g_return_val_if_fail (get_sequence (a
) == get_sequence (b
), 0);
415 check_iter_access (a
);
416 check_iter_access (b
);
418 a_pos
= node_get_pos (a
);
419 b_pos
= node_get_pos (b
);
423 else if (a_pos
> b_pos
)
432 * @data: the data for the new item
434 * Adds a new item to the end of @seq.
436 * Returns: an iterator pointing to the new item
441 g_sequence_append (GSequence
*seq
,
446 g_return_val_if_fail (seq
!= NULL
, NULL
);
448 check_seq_access (seq
);
450 node
= node_new (data
);
451 node_insert_before (seq
->end_node
, node
);
457 * g_sequence_prepend:
459 * @data: the data for the new item
461 * Adds a new item to the front of @seq
463 * Returns: an iterator pointing to the new item
468 g_sequence_prepend (GSequence
*seq
,
471 GSequenceNode
*node
, *first
;
473 g_return_val_if_fail (seq
!= NULL
, NULL
);
475 check_seq_access (seq
);
477 node
= node_new (data
);
478 first
= node_get_first (seq
->end_node
);
480 node_insert_before (first
, node
);
486 * g_sequence_insert_before:
487 * @iter: a #GSequenceIter
488 * @data: the data for the new item
490 * Inserts a new item just before the item pointed to by @iter.
492 * Returns: an iterator pointing to the new item
497 g_sequence_insert_before (GSequenceIter
*iter
,
502 g_return_val_if_fail (iter
!= NULL
, NULL
);
504 check_iter_access (iter
);
506 node
= node_new (data
);
508 node_insert_before (iter
, node
);
515 * @iter: a #GSequenceIter
517 * Removes the item pointed to by @iter. It is an error to pass the
518 * end iterator to this function.
520 * If the sequence has a data destroy function associated with it, this
521 * function is called on the data for the removed item.
526 g_sequence_remove (GSequenceIter
*iter
)
530 g_return_if_fail (iter
!= NULL
);
531 g_return_if_fail (!is_end (iter
));
533 check_iter_access (iter
);
535 seq
= get_sequence (iter
);
538 node_free (iter
, seq
);
542 * g_sequence_remove_range:
543 * @begin: a #GSequenceIter
544 * @end: a #GSequenceIter
546 * Removes all items in the (@begin, @end) range.
548 * If the sequence has a data destroy function associated with it, this
549 * function is called on the data for the removed items.
554 g_sequence_remove_range (GSequenceIter
*begin
,
557 g_return_if_fail (get_sequence (begin
) == get_sequence (end
));
559 check_iter_access (begin
);
560 check_iter_access (end
);
562 g_sequence_move_range (NULL
, begin
, end
);
566 * g_sequence_move_range:
567 * @dest: a #GSequenceIter
568 * @begin: a #GSequenceIter
569 * @end: a #GSequenceIter
571 * Inserts the (@begin, @end) range at the destination pointed to by ptr.
572 * The @begin and @end iters must point into the same sequence. It is
573 * allowed for @dest to point to a different sequence than the one pointed
574 * into by @begin and @end.
576 * If @dest is NULL, the range indicated by @begin and @end is
577 * removed from the sequence. If @dest iter points to a place within
578 * the (@begin, @end) range, the range does not move.
583 g_sequence_move_range (GSequenceIter
*dest
,
584 GSequenceIter
*begin
,
588 GSequenceNode
*first
;
590 g_return_if_fail (begin
!= NULL
);
591 g_return_if_fail (end
!= NULL
);
593 check_iter_access (begin
);
594 check_iter_access (end
);
596 check_iter_access (dest
);
598 src_seq
= get_sequence (begin
);
600 g_return_if_fail (src_seq
== get_sequence (end
));
602 /* Dest points to begin or end? */
603 if (dest
== begin
|| dest
== end
)
606 /* begin comes after end? */
607 if (g_sequence_iter_compare (begin
, end
) >= 0)
610 /* dest points somewhere in the (begin, end) range? */
611 if (dest
&& get_sequence (dest
) == src_seq
&&
612 g_sequence_iter_compare (dest
, begin
) > 0 &&
613 g_sequence_iter_compare (dest
, end
) < 0)
618 src_seq
= get_sequence (begin
);
620 first
= node_get_first (begin
);
627 node_join (first
, end
);
631 first
= node_get_first (dest
);
635 node_join (begin
, dest
);
638 node_join (first
, begin
);
642 node_free (begin
, src_seq
);
649 * @cmp_func: the function used to sort the sequence
650 * @cmp_data: user data passed to @cmp_func
652 * Sorts @seq using @cmp_func.
654 * @cmp_func is passed two items of @seq and should
655 * return 0 if they are equal, a negative value if the
656 * first comes before the second, and a positive value
657 * if the second comes before the first.
662 g_sequence_sort (GSequence
*seq
,
663 GCompareDataFunc cmp_func
,
668 info
.cmp_func
= cmp_func
;
669 info
.cmp_data
= cmp_data
;
670 info
.end_node
= seq
->end_node
;
672 check_seq_access (seq
);
674 g_sequence_sort_iter (seq
, iter_compare
, &info
);
678 * g_sequence_insert_sorted:
680 * @data: the data to insert
681 * @cmp_func: the function used to compare items in the sequence
682 * @cmp_data: user data passed to @cmp_func.
684 * Inserts @data into @sequence using @func to determine the new
685 * position. The sequence must already be sorted according to @cmp_func;
686 * otherwise the new position of @data is undefined.
688 * @cmp_func is called with two items of the @seq and @user_data.
689 * It should return 0 if the items are equal, a negative value
690 * if the first item comes before the second, and a positive value
691 * if the second item comes before the first.
693 * Returns: a #GSequenceIter pointing to the new item.
698 g_sequence_insert_sorted (GSequence
*seq
,
700 GCompareDataFunc cmp_func
,
705 g_return_val_if_fail (seq
!= NULL
, NULL
);
706 g_return_val_if_fail (cmp_func
!= NULL
, NULL
);
708 info
.cmp_func
= cmp_func
;
709 info
.cmp_data
= cmp_data
;
710 info
.end_node
= seq
->end_node
;
711 check_seq_access (seq
);
713 return g_sequence_insert_sorted_iter (seq
, data
, iter_compare
, &info
);
717 * g_sequence_sort_changed:
718 * @iter: A #GSequenceIter
719 * @cmp_func: the function used to compare items in the sequence
720 * @cmp_data: user data passed to @cmp_func.
722 * Moves the data pointed to a new position as indicated by @cmp_func. This
723 * function should be called for items in a sequence already sorted according
724 * to @cmp_func whenever some aspect of an item changes so that @cmp_func
725 * may return different values for that item.
727 * @cmp_func is called with two items of the @seq and @user_data.
728 * It should return 0 if the items are equal, a negative value if
729 * the first item comes before the second, and a positive value if
730 * the second item comes before the first.
735 g_sequence_sort_changed (GSequenceIter
*iter
,
736 GCompareDataFunc cmp_func
,
741 g_return_if_fail (!is_end (iter
));
743 info
.cmp_func
= cmp_func
;
744 info
.cmp_data
= cmp_data
;
745 info
.end_node
= get_sequence (iter
)->end_node
;
746 check_iter_access (iter
);
748 g_sequence_sort_changed_iter (iter
, iter_compare
, &info
);
754 * @data: data for the new item
755 * @cmp_func: the function used to compare items in the sequence
756 * @cmp_data: user data passed to @cmp_func
758 * Returns an iterator pointing to the position where @data would
759 * be inserted according to @cmp_func and @cmp_data.
761 * @cmp_func is called with two items of the @seq and @user_data.
762 * It should return 0 if the items are equal, a negative value if
763 * the first item comes before the second, and a positive value if
764 * the second item comes before the first.
766 * If you are simply searching for an existing element of the sequence,
767 * consider using g_sequence_lookup().
769 * This function will fail if the data contained in the sequence is
770 * unsorted. Use g_sequence_insert_sorted() or
771 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
772 * you want to add a large amount of data, call g_sequence_sort() after
773 * doing unsorted insertions.
775 * Returns: an #GSequenceIter pointing to the position where @data
776 * would have been inserted according to @cmp_func and @cmp_data
781 g_sequence_search (GSequence
*seq
,
783 GCompareDataFunc cmp_func
,
788 g_return_val_if_fail (seq
!= NULL
, NULL
);
790 info
.cmp_func
= cmp_func
;
791 info
.cmp_data
= cmp_data
;
792 info
.end_node
= seq
->end_node
;
793 check_seq_access (seq
);
795 return g_sequence_search_iter (seq
, data
, iter_compare
, &info
);
801 * @data: data to lookup
802 * @cmp_func: the function used to compare items in the sequence
803 * @cmp_data: user data passed to @cmp_func
805 * Returns an iterator pointing to the position of the first item found
806 * equal to @data according to @cmp_func and @cmp_data. If more than one
807 * item is equal, it is not guaranteed that it is the first which is
808 * returned. In that case, you can use g_sequence_iter_next() and
809 * g_sequence_iter_prev() to get others.
811 * @cmp_func is called with two items of the @seq and @user_data.
812 * It should return 0 if the items are equal, a negative value if
813 * the first item comes before the second, and a positive value if
814 * the second item comes before the first.
816 * This function will fail if the data contained in the sequence is
817 * unsorted. Use g_sequence_insert_sorted() or
818 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
819 * you want to add a large amount of data, call g_sequence_sort() after
820 * doing unsorted insertions.
822 * Returns: an #GSequenceIter pointing to the position of the
823 * first item found equal to @data according to @cmp_func and
824 * @cmp_data, or %NULL if no such item exists
829 g_sequence_lookup (GSequence
*seq
,
831 GCompareDataFunc cmp_func
,
836 g_return_val_if_fail (seq
!= NULL
, NULL
);
838 info
.cmp_func
= cmp_func
;
839 info
.cmp_data
= cmp_data
;
840 info
.end_node
= seq
->end_node
;
841 check_seq_access (seq
);
843 return g_sequence_lookup_iter (seq
, data
, iter_compare
, &info
);
847 * g_sequence_sort_iter:
849 * @cmp_func: the function used to compare iterators in the sequence
850 * @cmp_data: user data passed to @cmp_func
852 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
853 * of a GCompareDataFunc as the compare function
855 * @cmp_func is called with two iterators pointing into @seq. It should
856 * return 0 if the iterators are equal, a negative value if the first
857 * iterator comes before the second, and a positive value if the second
858 * iterator comes before the first.
863 g_sequence_sort_iter (GSequence
*seq
,
864 GSequenceIterCompareFunc cmp_func
,
868 GSequenceNode
*begin
, *end
;
870 g_return_if_fail (seq
!= NULL
);
871 g_return_if_fail (cmp_func
!= NULL
);
873 check_seq_access (seq
);
875 begin
= g_sequence_get_begin_iter (seq
);
876 end
= g_sequence_get_end_iter (seq
);
878 tmp
= g_sequence_new (NULL
);
879 tmp
->real_sequence
= seq
;
881 g_sequence_move_range (g_sequence_get_begin_iter (tmp
), begin
, end
);
883 seq
->access_prohibited
= TRUE
;
884 tmp
->access_prohibited
= TRUE
;
886 while (!g_sequence_is_empty (tmp
))
888 GSequenceNode
*node
= g_sequence_get_begin_iter (tmp
);
890 node_insert_sorted (seq
->end_node
, node
, seq
->end_node
,
894 tmp
->access_prohibited
= FALSE
;
895 seq
->access_prohibited
= FALSE
;
897 g_sequence_free (tmp
);
901 * g_sequence_sort_changed_iter:
902 * @iter: a #GSequenceIter
903 * @iter_cmp: the function used to compare iterators in the sequence
904 * @cmp_data: user data passed to @cmp_func
906 * Like g_sequence_sort_changed(), but uses
907 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
908 * the compare function.
910 * @iter_cmp is called with two iterators pointing into @seq. It should
911 * return 0 if the iterators are equal, a negative value if the first
912 * iterator comes before the second, and a positive value if the second
913 * iterator comes before the first.
918 g_sequence_sort_changed_iter (GSequenceIter
*iter
,
919 GSequenceIterCompareFunc iter_cmp
,
922 GSequence
*seq
, *tmp_seq
;
923 GSequenceIter
*next
, *prev
;
925 g_return_if_fail (iter
!= NULL
);
926 g_return_if_fail (!is_end (iter
));
927 g_return_if_fail (iter_cmp
!= NULL
);
928 check_iter_access (iter
);
930 /* If one of the neighbours is equal to iter, then
931 * don't move it. This ensures that sort_changed() is
932 * a stable operation.
935 next
= node_get_next (iter
);
936 prev
= node_get_prev (iter
);
938 if (prev
!= iter
&& iter_cmp (prev
, iter
, cmp_data
) == 0)
941 if (!is_end (next
) && iter_cmp (next
, iter
, cmp_data
) == 0)
944 seq
= get_sequence (iter
);
946 seq
->access_prohibited
= TRUE
;
948 tmp_seq
= g_sequence_new (NULL
);
949 tmp_seq
->real_sequence
= seq
;
952 node_insert_before (tmp_seq
->end_node
, iter
);
954 node_insert_sorted (seq
->end_node
, iter
, seq
->end_node
,
957 g_sequence_free (tmp_seq
);
959 seq
->access_prohibited
= FALSE
;
963 * g_sequence_insert_sorted_iter:
965 * @data: data for the new item
966 * @iter_cmp: the function used to compare iterators in the sequence
967 * @cmp_data: user data passed to @cmp_func
969 * Like g_sequence_insert_sorted(), but uses
970 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
971 * the compare function.
973 * @iter_cmp is called with two iterators pointing into @seq.
974 * It should return 0 if the iterators are equal, a negative
975 * value if the first iterator comes before the second, and a
976 * positive value if the second iterator comes before the first.
978 * It is called with two iterators pointing into @seq. It should
979 * return 0 if the iterators are equal, a negative value if the
980 * first iterator comes before the second, and a positive value
981 * if the second iterator comes before the first.
983 * Returns: a #GSequenceIter pointing to the new item
988 g_sequence_insert_sorted_iter (GSequence
*seq
,
990 GSequenceIterCompareFunc iter_cmp
,
993 GSequenceNode
*new_node
;
996 g_return_val_if_fail (seq
!= NULL
, NULL
);
997 g_return_val_if_fail (iter_cmp
!= NULL
, NULL
);
999 check_seq_access (seq
);
1001 seq
->access_prohibited
= TRUE
;
1003 /* Create a new temporary sequence and put the new node into
1004 * that. The reason for this is that the user compare function
1005 * will be called with the new node, and if it dereferences,
1006 * "is_end" will be called on it. But that will crash if the
1007 * node is not actually in a sequence.
1009 * node_insert_sorted() makes sure the node is unlinked before
1012 * The reason we need the "iter" versions at all is that that
1013 * is the only kind of compare functions GtkTreeView can use.
1015 tmp_seq
= g_sequence_new (NULL
);
1016 tmp_seq
->real_sequence
= seq
;
1018 new_node
= g_sequence_append (tmp_seq
, data
);
1020 node_insert_sorted (seq
->end_node
, new_node
,
1021 seq
->end_node
, iter_cmp
, cmp_data
);
1023 g_sequence_free (tmp_seq
);
1025 seq
->access_prohibited
= FALSE
;
1031 * g_sequence_search_iter:
1032 * @seq: a #GSequence
1033 * @data: data for the new item
1034 * @iter_cmp: the function used to compare iterators in the sequence
1035 * @cmp_data: user data passed to @iter_cmp
1037 * Like g_sequence_search(), but uses a #GSequenceIterCompareFunc
1038 * instead of a #GCompareDataFunc as the compare function.
1040 * @iter_cmp is called with two iterators pointing into @seq.
1041 * It should return 0 if the iterators are equal, a negative value
1042 * if the first iterator comes before the second, and a positive
1043 * value if the second iterator comes before the first.
1045 * If you are simply searching for an existing element of the sequence,
1046 * consider using g_sequence_lookup_iter().
1048 * This function will fail if the data contained in the sequence is
1049 * unsorted. Use g_sequence_insert_sorted() or
1050 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
1051 * you want to add a large amount of data, call g_sequence_sort() after
1052 * doing unsorted insertions.
1054 * Returns: a #GSequenceIter pointing to the position in @seq
1055 * where @data would have been inserted according to @iter_cmp
1061 g_sequence_search_iter (GSequence
*seq
,
1063 GSequenceIterCompareFunc iter_cmp
,
1066 GSequenceNode
*node
;
1067 GSequenceNode
*dummy
;
1070 g_return_val_if_fail (seq
!= NULL
, NULL
);
1072 check_seq_access (seq
);
1074 seq
->access_prohibited
= TRUE
;
1076 tmp_seq
= g_sequence_new (NULL
);
1077 tmp_seq
->real_sequence
= seq
;
1079 dummy
= g_sequence_append (tmp_seq
, data
);
1081 node
= node_find_closest (seq
->end_node
, dummy
,
1082 seq
->end_node
, iter_cmp
, cmp_data
);
1084 g_sequence_free (tmp_seq
);
1086 seq
->access_prohibited
= FALSE
;
1092 * g_sequence_lookup_iter:
1093 * @seq: a #GSequence
1094 * @data: data to lookup
1095 * @iter_cmp: the function used to compare iterators in the sequence
1096 * @cmp_data: user data passed to @iter_cmp
1098 * Like g_sequence_lookup(), but uses a #GSequenceIterCompareFunc
1099 * instead of a #GCompareDataFunc as the compare function.
1101 * @iter_cmp is called with two iterators pointing into @seq.
1102 * It should return 0 if the iterators are equal, a negative value
1103 * if the first iterator comes before the second, and a positive
1104 * value if the second iterator comes before the first.
1106 * This function will fail if the data contained in the sequence is
1107 * unsorted. Use g_sequence_insert_sorted() or
1108 * g_sequence_insert_sorted_iter() to add data to your sequence or, if
1109 * you want to add a large amount of data, call g_sequence_sort() after
1110 * doing unsorted insertions.
1112 * Returns: an #GSequenceIter pointing to the position of
1113 * the first item found equal to @data according to @cmp_func
1114 * and @cmp_data, or %NULL if no such item exists
1119 g_sequence_lookup_iter (GSequence
*seq
,
1121 GSequenceIterCompareFunc iter_cmp
,
1124 GSequenceNode
*node
;
1125 GSequenceNode
*dummy
;
1128 g_return_val_if_fail (seq
!= NULL
, NULL
);
1130 check_seq_access (seq
);
1132 seq
->access_prohibited
= TRUE
;
1134 tmp_seq
= g_sequence_new (NULL
);
1135 tmp_seq
->real_sequence
= seq
;
1137 dummy
= g_sequence_append (tmp_seq
, data
);
1139 node
= node_find (seq
->end_node
, dummy
,
1140 seq
->end_node
, iter_cmp
, cmp_data
);
1142 g_sequence_free (tmp_seq
);
1144 seq
->access_prohibited
= FALSE
;
1150 * g_sequence_iter_get_sequence:
1151 * @iter: a #GSequenceIter
1153 * Returns the #GSequence that @iter points into.
1155 * Returns: the #GSequence that @iter points into
1160 g_sequence_iter_get_sequence (GSequenceIter
*iter
)
1164 g_return_val_if_fail (iter
!= NULL
, NULL
);
1166 seq
= get_sequence (iter
);
1168 /* For temporary sequences, this points to the sequence that
1169 * is actually being manipulated
1171 return seq
->real_sequence
;
1176 * @iter: a #GSequenceIter
1178 * Returns the data that @iter points to.
1180 * Returns: the data that @iter points to
1185 g_sequence_get (GSequenceIter
*iter
)
1187 g_return_val_if_fail (iter
!= NULL
, NULL
);
1188 g_return_val_if_fail (!is_end (iter
), NULL
);
1195 * @iter: a #GSequenceIter
1196 * @data: new data for the item
1198 * Changes the data for the item pointed to by @iter to be @data. If
1199 * the sequence has a data destroy function associated with it, that
1200 * function is called on the existing data that @iter pointed to.
1205 g_sequence_set (GSequenceIter
*iter
,
1210 g_return_if_fail (iter
!= NULL
);
1211 g_return_if_fail (!is_end (iter
));
1213 seq
= get_sequence (iter
);
1215 /* If @data is identical to iter->data, it is destroyed
1216 * here. This will work right in case of ref-counted objects. Also
1217 * it is similar to what ghashtables do.
1219 * For non-refcounted data it's a little less convenient, but
1220 * code relying on self-setting not destroying would be
1221 * pretty dubious anyway ...
1224 if (seq
->data_destroy_notify
)
1225 seq
->data_destroy_notify (iter
->data
);
1231 * g_sequence_get_length:
1232 * @seq: a #GSequence
1234 * Returns the length of @seq. Note that this method is O(h) where `h' is the
1235 * height of the tree. It is thus more efficient to use g_sequence_is_empty()
1236 * when comparing the length to zero.
1238 * Returns: the length of @seq
1243 g_sequence_get_length (GSequence
*seq
)
1245 return node_get_length (seq
->end_node
) - 1;
1249 * g_sequence_is_empty:
1250 * @seq: a #GSequence
1252 * Returns %TRUE if the sequence contains zero items.
1254 * This function is functionally identical to checking the result of
1255 * g_sequence_get_length() being equal to zero. However this function is
1256 * implemented in O(1) running time.
1258 * Returns: %TRUE if the sequence is empty, otherwise %FALSE.
1263 g_sequence_is_empty (GSequence
*seq
)
1265 return (seq
->end_node
->parent
== NULL
) && (seq
->end_node
->left
== NULL
);
1269 * g_sequence_get_end_iter:
1270 * @seq: a #GSequence
1272 * Returns the end iterator for @seg
1274 * Returns: the end iterator for @seq
1279 g_sequence_get_end_iter (GSequence
*seq
)
1281 g_return_val_if_fail (seq
!= NULL
, NULL
);
1283 return seq
->end_node
;
1287 * g_sequence_get_begin_iter:
1288 * @seq: a #GSequence
1290 * Returns the begin iterator for @seq.
1292 * Returns: the begin iterator for @seq.
1297 g_sequence_get_begin_iter (GSequence
*seq
)
1299 g_return_val_if_fail (seq
!= NULL
, NULL
);
1301 return node_get_first (seq
->end_node
);
1305 clamp_position (GSequence
*seq
,
1308 gint len
= g_sequence_get_length (seq
);
1310 if (pos
> len
|| pos
< 0)
1317 * if pos > number of items or -1, will return end pointer
1320 * g_sequence_get_iter_at_pos:
1321 * @seq: a #GSequence
1322 * @pos: a position in @seq, or -1 for the end
1324 * Returns the iterator at position @pos. If @pos is negative or larger
1325 * than the number of items in @seq, the end iterator is returned.
1327 * Returns: The #GSequenceIter at position @pos
1332 g_sequence_get_iter_at_pos (GSequence
*seq
,
1335 g_return_val_if_fail (seq
!= NULL
, NULL
);
1337 pos
= clamp_position (seq
, pos
);
1339 return node_get_by_pos (seq
->end_node
, pos
);
1344 * @src: a #GSequenceIter pointing to the item to move
1345 * @dest: a #GSequenceIter pointing to the position to which
1348 * Moves the item pointed to by @src to the position indicated by @dest.
1349 * After calling this function @dest will point to the position immediately
1350 * after @src. It is allowed for @src and @dest to point into different
1356 g_sequence_move (GSequenceIter
*src
,
1357 GSequenceIter
*dest
)
1359 g_return_if_fail (src
!= NULL
);
1360 g_return_if_fail (dest
!= NULL
);
1361 g_return_if_fail (!is_end (src
));
1367 node_insert_before (dest
, src
);
1373 * g_sequence_iter_is_end:
1374 * @iter: a #GSequenceIter
1376 * Returns whether @iter is the end iterator
1378 * Returns: Whether @iter is the end iterator
1383 g_sequence_iter_is_end (GSequenceIter
*iter
)
1385 g_return_val_if_fail (iter
!= NULL
, FALSE
);
1387 return is_end (iter
);
1391 * g_sequence_iter_is_begin:
1392 * @iter: a #GSequenceIter
1394 * Returns whether @iter is the begin iterator
1396 * Returns: whether @iter is the begin iterator
1401 g_sequence_iter_is_begin (GSequenceIter
*iter
)
1403 g_return_val_if_fail (iter
!= NULL
, FALSE
);
1405 return (node_get_prev (iter
) == iter
);
1409 * g_sequence_iter_get_position:
1410 * @iter: a #GSequenceIter
1412 * Returns the position of @iter
1414 * Returns: the position of @iter
1419 g_sequence_iter_get_position (GSequenceIter
*iter
)
1421 g_return_val_if_fail (iter
!= NULL
, -1);
1423 return node_get_pos (iter
);
1427 * g_sequence_iter_next:
1428 * @iter: a #GSequenceIter
1430 * Returns an iterator pointing to the next position after @iter.
1431 * If @iter is the end iterator, the end iterator is returned.
1433 * Returns: a #GSequenceIter pointing to the next position after @iter
1438 g_sequence_iter_next (GSequenceIter
*iter
)
1440 g_return_val_if_fail (iter
!= NULL
, NULL
);
1442 return node_get_next (iter
);
1446 * g_sequence_iter_prev:
1447 * @iter: a #GSequenceIter
1449 * Returns an iterator pointing to the previous position before @iter.
1450 * If @iter is the begin iterator, the begin iterator is returned.
1452 * Returns: a #GSequenceIter pointing to the previous position
1458 g_sequence_iter_prev (GSequenceIter
*iter
)
1460 g_return_val_if_fail (iter
!= NULL
, NULL
);
1462 return node_get_prev (iter
);
1466 * g_sequence_iter_move:
1467 * @iter: a #GSequenceIter
1468 * @delta: A positive or negative number indicating how many positions away
1469 * from @iter the returned #GSequenceIter will be
1471 * Returns the #GSequenceIter which is @delta positions away from @iter.
1472 * If @iter is closer than -@delta positions to the beginning of the sequence,
1473 * the begin iterator is returned. If @iter is closer than @delta positions
1474 * to the end of the sequence, the end iterator is returned.
1476 * Returns: a #GSequenceIter which is @delta positions away from @iter
1481 g_sequence_iter_move (GSequenceIter
*iter
,
1487 g_return_val_if_fail (iter
!= NULL
, NULL
);
1489 len
= g_sequence_get_length (get_sequence (iter
));
1491 new_pos
= node_get_pos (iter
) + delta
;
1495 else if (new_pos
> len
)
1498 return node_get_by_pos (iter
, new_pos
);
1503 * @a: a #GSequenceIter
1504 * @b: a #GSequenceIter
1506 * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
1507 * to point into difference sequences.
1512 g_sequence_swap (GSequenceIter
*a
,
1515 GSequenceNode
*leftmost
, *rightmost
, *rightmost_next
;
1518 g_return_if_fail (!g_sequence_iter_is_end (a
));
1519 g_return_if_fail (!g_sequence_iter_is_end (b
));
1524 a_pos
= g_sequence_iter_get_position (a
);
1525 b_pos
= g_sequence_iter_get_position (b
);
1538 rightmost_next
= node_get_next (rightmost
);
1540 /* The situation is now like this:
1542 * ..., leftmost, ......., rightmost, rightmost_next, ...
1545 g_sequence_move (rightmost
, leftmost
);
1546 g_sequence_move (leftmost
, rightmost_next
);
1550 * Implementation of a treap
1555 get_priority (GSequenceNode
*node
)
1557 guint key
= GPOINTER_TO_UINT (node
);
1559 /* This hash function is based on one found on Thomas Wang's
1562 * http://www.concentric.net/~Ttwang/tech/inthash.htm
1565 key
= (key
<< 15) - key
- 1;
1566 key
= key
^ (key
>> 12);
1567 key
= key
+ (key
<< 2);
1568 key
= key
^ (key
>> 4);
1569 key
= key
+ (key
<< 3) + (key
<< 11);
1570 key
= key
^ (key
>> 16);
1572 /* We rely on 0 being less than all other priorities */
1573 return key
? key
: 1;
1576 static GSequenceNode
*
1577 find_root (GSequenceNode
*node
)
1579 while (node
->parent
)
1580 node
= node
->parent
;
1585 static GSequenceNode
*
1586 node_new (gpointer data
)
1588 GSequenceNode
*node
= g_slice_new0 (GSequenceNode
);
1594 node
->parent
= NULL
;
1599 static GSequenceNode
*
1600 node_get_first (GSequenceNode
*node
)
1602 node
= find_root (node
);
1610 static GSequenceNode
*
1611 node_get_last (GSequenceNode
*node
)
1613 node
= find_root (node
);
1621 #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1622 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1624 static GSequenceNode
*
1625 node_get_next (GSequenceNode
*node
)
1627 GSequenceNode
*n
= node
;
1637 while (NODE_RIGHT_CHILD (n
))
1649 static GSequenceNode
*
1650 node_get_prev (GSequenceNode
*node
)
1652 GSequenceNode
*n
= node
;
1662 while (NODE_LEFT_CHILD (n
))
1674 #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1677 node_get_pos (GSequenceNode
*node
)
1682 n_smaller
= node
->left
->n_nodes
;
1686 if (NODE_RIGHT_CHILD (node
))
1687 n_smaller
+= N_NODES (node
->parent
->left
) + 1;
1689 node
= node
->parent
;
1695 static GSequenceNode
*
1696 node_get_by_pos (GSequenceNode
*node
,
1701 node
= find_root (node
);
1703 while ((i
= N_NODES (node
->left
)) != pos
)
1719 static GSequenceNode
*
1720 node_find (GSequenceNode
*haystack
,
1721 GSequenceNode
*needle
,
1723 GSequenceIterCompareFunc iter_cmp
,
1728 haystack
= find_root (haystack
);
1732 /* iter_cmp can't be passed the end node, since the function may
1735 if (haystack
== end
)
1738 c
= iter_cmp (haystack
, needle
, cmp_data
);
1744 haystack
= haystack
->left
;
1746 haystack
= haystack
->right
;
1748 while (haystack
!= NULL
);
1753 static GSequenceNode
*
1754 node_find_closest (GSequenceNode
*haystack
,
1755 GSequenceNode
*needle
,
1757 GSequenceIterCompareFunc iter_cmp
,
1760 GSequenceNode
*best
;
1763 haystack
= find_root (haystack
);
1769 /* iter_cmp can't be passed the end node, since the function may
1772 if (haystack
== end
)
1775 c
= iter_cmp (haystack
, needle
, cmp_data
);
1777 /* In the following we don't break even if c == 0. Instead we go on
1778 * searching along the 'bigger' nodes, so that we find the last one
1779 * that is equal to the needle.
1782 haystack
= haystack
->left
;
1784 haystack
= haystack
->right
;
1786 while (haystack
!= NULL
);
1788 /* If the best node is smaller or equal to the data, then move one step
1789 * to the right to make sure the best one is strictly bigger than the data
1791 if (best
!= end
&& c
<= 0)
1792 best
= node_get_next (best
);
1798 node_get_length (GSequenceNode
*node
)
1800 node
= find_root (node
);
1802 return node
->n_nodes
;
1806 real_node_free (GSequenceNode
*node
,
1811 real_node_free (node
->left
, seq
);
1812 real_node_free (node
->right
, seq
);
1814 if (seq
&& seq
->data_destroy_notify
&& node
!= seq
->end_node
)
1815 seq
->data_destroy_notify (node
->data
);
1817 g_slice_free (GSequenceNode
, node
);
1822 node_free (GSequenceNode
*node
,
1825 node
= find_root (node
);
1827 real_node_free (node
, seq
);
1831 node_update_fields (GSequenceNode
*node
)
1835 n_nodes
+= N_NODES (node
->left
);
1836 n_nodes
+= N_NODES (node
->right
);
1838 node
->n_nodes
= n_nodes
;
1842 node_rotate (GSequenceNode
*node
)
1844 GSequenceNode
*tmp
, *old
;
1846 g_assert (node
->parent
);
1847 g_assert (node
->parent
!= node
);
1849 if (NODE_LEFT_CHILD (node
))
1854 node
->right
= node
->parent
;
1855 node
->parent
= node
->parent
->parent
;
1858 if (node
->parent
->left
== node
->right
)
1859 node
->parent
->left
= node
;
1861 node
->parent
->right
= node
;
1864 g_assert (node
->right
);
1866 node
->right
->parent
= node
;
1867 node
->right
->left
= tmp
;
1869 if (node
->right
->left
)
1870 node
->right
->left
->parent
= node
->right
;
1879 node
->left
= node
->parent
;
1880 node
->parent
= node
->parent
->parent
;
1883 if (node
->parent
->right
== node
->left
)
1884 node
->parent
->right
= node
;
1886 node
->parent
->left
= node
;
1889 g_assert (node
->left
);
1891 node
->left
->parent
= node
;
1892 node
->left
->right
= tmp
;
1894 if (node
->left
->right
)
1895 node
->left
->right
->parent
= node
->left
;
1900 node_update_fields (old
);
1901 node_update_fields (node
);
1905 node_update_fields_deep (GSequenceNode
*node
)
1909 node_update_fields (node
);
1911 node_update_fields_deep (node
->parent
);
1916 rotate_down (GSequenceNode
*node
,
1921 left
= node
->left
? get_priority (node
->left
) : 0;
1922 right
= node
->right
? get_priority (node
->right
) : 0;
1924 while (priority
< left
|| priority
< right
)
1927 node_rotate (node
->left
);
1929 node_rotate (node
->right
);
1931 left
= node
->left
? get_priority (node
->left
) : 0;
1932 right
= node
->right
? get_priority (node
->right
) : 0;
1937 node_cut (GSequenceNode
*node
)
1939 while (node
->parent
)
1943 node
->left
->parent
= NULL
;
1946 node_update_fields (node
);
1948 rotate_down (node
, get_priority (node
));
1952 node_join (GSequenceNode
*left
,
1953 GSequenceNode
*right
)
1955 GSequenceNode
*fake
= node_new (NULL
);
1957 fake
->left
= find_root (left
);
1958 fake
->right
= find_root (right
);
1959 fake
->left
->parent
= fake
;
1960 fake
->right
->parent
= fake
;
1962 node_update_fields (fake
);
1966 node_free (fake
, NULL
);
1970 node_insert_before (GSequenceNode
*node
,
1973 new->left
= node
->left
;
1975 new->left
->parent
= new;
1980 node_update_fields_deep (new);
1982 while (new->parent
&& get_priority (new) > get_priority (new->parent
))
1985 rotate_down (new, get_priority (new));
1989 node_unlink (GSequenceNode
*node
)
1991 rotate_down (node
, 0);
1993 if (NODE_RIGHT_CHILD (node
))
1994 node
->parent
->right
= NULL
;
1995 else if (NODE_LEFT_CHILD (node
))
1996 node
->parent
->left
= NULL
;
1999 node_update_fields_deep (node
->parent
);
2001 node
->parent
= NULL
;
2005 node_insert_sorted (GSequenceNode
*node
,
2008 GSequenceIterCompareFunc iter_cmp
,
2011 GSequenceNode
*closest
;
2013 closest
= node_find_closest (node
, new, end
, iter_cmp
, cmp_data
);
2017 node_insert_before (closest
, new);