1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
3 * Soeren Sandmann (sandmann@daimi.au.dk)
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the
17 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 * Boston, MA 02111-1307, USA.
23 #include "gsequence.h"
26 #include "gtestutils.h"
30 * @short_description: scalable lists
32 * The #GSequence data structure has the API of a list, but is
33 * implemented internally with a balanced binary tree. This means that
34 * it is possible to maintain a sorted list of n elements in time O(n
35 * log n). The data contained in each element can be either integer
36 * values, by using of the <link
37 * linkend="glib-Type-Conversion-Macros">Type Conversion Macros</link>,
38 * or simply pointers to any type of data.
40 * A #GSequence is accessed through <firstterm>iterators</firstterm>,
41 * represented by a #GSequenceIter. An iterator represents a position
42 * between two elements of the sequence. For example, the
43 * <firstterm>begin</firstterm> iterator represents the gap immediately
44 * before the first element of the sequence, and the
45 * <firstterm>end</firstterm> iterator represents the gap immediately
46 * after the last element. In an empty sequence, the begin and end
47 * iterators are the same.
49 * Some methods on #GSequence operate on ranges of items. For example
50 * g_sequence_foreach_range() will call a user-specified function on
51 * each element with the given range. The range is delimited by the
52 * gaps represented by the passed-in iterators, so if you pass in the
53 * begin and end iterators, the range in question is the entire
56 * The function g_sequence_get() is used with an iterator to access the
57 * element immediately following the gap that the iterator represents.
58 * The iterator is said to <firstterm>point</firstterm> to that element.
60 * Iterators are stable across most operations on a #GSequence. For
61 * example an iterator pointing to some element of a sequence will
62 * continue to point to that element even after the sequence is sorted.
63 * Even moving an element to another sequence using for example
64 * g_sequence_move_range() will not invalidate the iterators pointing
65 * to it. The only operation that will invalidate an iterator is when
66 * the element it points to is removed from any sequence.
72 * The #GSequenceIter struct is an opaque data type representing an
73 * iterator pointing into a #GSequence.
77 * GSequenceIterCompareFunc:
78 * @a: a #GSequenceIter
79 * @b: a #GSequenceIter
81 * @Returns: zero if the iterators are equal, a negative value if @a
82 * comes before @b, and a positive value if @b comes before
85 * A #GSequenceIterCompareFunc is a function used to compare iterators.
86 * It must return zero if the iterators compare equal, a negative value
87 * if @a comes before @b, and a positive value if @b comes before @a.
90 typedef struct _GSequenceNode GSequenceNode
;
95 * The #GSequence struct is an opaque data type representing a
96 * <link linkend="glib-Sequences">Sequence</link> data type.
100 GSequenceNode
* end_node
;
101 GDestroyNotify data_destroy_notify
;
102 gboolean access_prohibited
;
104 /* The 'real_sequence' is used when temporary sequences are created
105 * to hold nodes that are being rearranged. The 'real_sequence' of such
106 * a temporary sequence points to the sequence that is actually being
107 * manipulated. The only reason we need this is so that when the
108 * sort/sort_changed/search_iter() functions call out to the application
109 * g_sequence_iter_get_sequence() will return the correct sequence.
111 GSequence
* real_sequence
;
114 struct _GSequenceNode
117 GSequenceNode
* parent
;
118 GSequenceNode
* left
;
119 GSequenceNode
* right
;
120 gpointer data
; /* For the end node, this field points
126 * Declaration of GSequenceNode methods
128 static GSequenceNode
*node_new (gpointer data
);
129 static GSequenceNode
*node_get_first (GSequenceNode
*node
);
130 static GSequenceNode
*node_get_last (GSequenceNode
*node
);
131 static GSequenceNode
*node_get_prev (GSequenceNode
*node
);
132 static GSequenceNode
*node_get_next (GSequenceNode
*node
);
133 static gint
node_get_pos (GSequenceNode
*node
);
134 static GSequenceNode
*node_get_by_pos (GSequenceNode
*node
,
136 static GSequenceNode
*node_find (GSequenceNode
*haystack
,
137 GSequenceNode
*needle
,
139 GSequenceIterCompareFunc cmp
,
141 static GSequenceNode
*node_find_closest (GSequenceNode
*haystack
,
142 GSequenceNode
*needle
,
144 GSequenceIterCompareFunc cmp
,
146 static gint
node_get_length (GSequenceNode
*node
);
147 static void node_free (GSequenceNode
*node
,
149 static void node_cut (GSequenceNode
*split
);
150 static void node_insert_before (GSequenceNode
*node
,
152 static void node_unlink (GSequenceNode
*node
);
153 static void node_join (GSequenceNode
*left
,
154 GSequenceNode
*right
);
155 static void node_insert_sorted (GSequenceNode
*node
,
158 GSequenceIterCompareFunc cmp_func
,
163 * Various helper functions
166 check_seq_access (GSequence
*seq
)
168 if (G_UNLIKELY (seq
->access_prohibited
))
170 g_warning ("Accessing a sequence while it is "
171 "being sorted or searched is not allowed");
176 get_sequence (GSequenceNode
*node
)
178 return (GSequence
*)node_get_last (node
)->data
;
182 check_iter_access (GSequenceIter
*iter
)
184 check_seq_access (get_sequence (iter
));
188 is_end (GSequenceIter
*iter
)
198 if (iter
->parent
->right
!= iter
)
201 seq
= get_sequence (iter
);
203 return seq
->end_node
== iter
;
208 GCompareDataFunc cmp_func
;
210 GSequenceNode
*end_node
;
213 /* This function compares two iters using a normal compare
214 * function and user_data passed in in a SortInfo struct
217 iter_compare (GSequenceIter
*node1
,
218 GSequenceIter
*node2
,
221 const SortInfo
*info
= data
;
224 if (node1
== info
->end_node
)
227 if (node2
== info
->end_node
)
230 retval
= info
->cmp_func (node1
->data
, node2
->data
, info
->cmp_data
);
241 * @data_destroy: a #GDestroyNotify function, or %NULL
243 * Creates a new GSequence. The @data_destroy function, if non-%NULL will
244 * be called on all items when the sequence is destroyed and on items that
245 * are removed from the sequence.
247 * Return value: a new #GSequence
252 g_sequence_new (GDestroyNotify data_destroy
)
254 GSequence
*seq
= g_new (GSequence
, 1);
255 seq
->data_destroy_notify
= data_destroy
;
257 seq
->end_node
= node_new (seq
);
259 seq
->access_prohibited
= FALSE
;
261 seq
->real_sequence
= seq
;
270 * Frees the memory allocated for @seq. If @seq has a data destroy
271 * function associated with it, that function is called on all items in
277 g_sequence_free (GSequence
*seq
)
279 g_return_if_fail (seq
!= NULL
);
281 check_seq_access (seq
);
283 node_free (seq
->end_node
, seq
);
289 * g_sequence_foreach_range:
290 * @begin: a #GSequenceIter
291 * @end: a #GSequenceIter
293 * @user_data: user data passed to @func
295 * Calls @func for each item in the range (@begin, @end) passing
296 * @user_data to the function.
301 g_sequence_foreach_range (GSequenceIter
*begin
,
309 g_return_if_fail (func
!= NULL
);
310 g_return_if_fail (begin
!= NULL
);
311 g_return_if_fail (end
!= NULL
);
313 seq
= get_sequence (begin
);
315 seq
->access_prohibited
= TRUE
;
320 GSequenceIter
*next
= node_get_next (iter
);
322 func (iter
->data
, user_data
);
327 seq
->access_prohibited
= FALSE
;
331 * g_sequence_foreach:
333 * @func: the function to call for each item in @seq
334 * @user_data: user data passed to @func
336 * Calls @func for each item in the sequence passing @user_data
342 g_sequence_foreach (GSequence
*seq
,
346 GSequenceIter
*begin
, *end
;
348 check_seq_access (seq
);
350 begin
= g_sequence_get_begin_iter (seq
);
351 end
= g_sequence_get_end_iter (seq
);
353 g_sequence_foreach_range (begin
, end
, func
, user_data
);
357 * g_sequence_range_get_midpoint:
358 * @begin: a #GSequenceIter
359 * @end: a #GSequenceIter
361 * Finds an iterator somewhere in the range (@begin, @end). This
362 * iterator will be close to the middle of the range, but is not
363 * guaranteed to be <emphasis>exactly</emphasis> in the middle.
365 * The @begin and @end iterators must both point to the same sequence and
366 * @begin must come before or be equal to @end in the sequence.
368 * Return value: A #GSequenceIter pointing somewhere in the
369 * (@begin, @end) range.
374 g_sequence_range_get_midpoint (GSequenceIter
*begin
,
377 int begin_pos
, end_pos
, mid_pos
;
379 g_return_val_if_fail (begin
!= NULL
, NULL
);
380 g_return_val_if_fail (end
!= NULL
, NULL
);
381 g_return_val_if_fail (get_sequence (begin
) == get_sequence (end
), NULL
);
383 begin_pos
= node_get_pos (begin
);
384 end_pos
= node_get_pos (end
);
386 g_return_val_if_fail (end_pos
>= begin_pos
, NULL
);
388 mid_pos
= begin_pos
+ (end_pos
- begin_pos
) / 2;
390 return node_get_by_pos (begin
, mid_pos
);
394 * g_sequence_iter_compare:
395 * @a: a #GSequenceIter
396 * @b: a #GSequenceIter
398 * Returns a negative number if @a comes before @b, 0 if they are equal,
399 * and a positive number if @a comes after @b.
401 * The @a and @b iterators must point into the same sequence.
403 * Return value: A negative number if @a comes before @b, 0 if they are
404 * equal, and a positive number if @a comes after @b.
409 g_sequence_iter_compare (GSequenceIter
*a
,
414 g_return_val_if_fail (a
!= NULL
, 0);
415 g_return_val_if_fail (b
!= NULL
, 0);
416 g_return_val_if_fail (get_sequence (a
) == get_sequence (b
), 0);
418 check_iter_access (a
);
419 check_iter_access (b
);
421 a_pos
= node_get_pos (a
);
422 b_pos
= node_get_pos (b
);
426 else if (a_pos
> b_pos
)
434 * @seq: a #GSequencePointer
435 * @data: the data for the new item
437 * Adds a new item to the end of @seq.
439 * Return value: an iterator pointing to the new item
444 g_sequence_append (GSequence
*seq
,
449 g_return_val_if_fail (seq
!= NULL
, NULL
);
451 check_seq_access (seq
);
453 node
= node_new (data
);
454 node_insert_before (seq
->end_node
, node
);
460 * g_sequence_prepend:
462 * @data: the data for the new item
464 * Adds a new item to the front of @seq
466 * Return value: an iterator pointing to the new item
471 g_sequence_prepend (GSequence
*seq
,
474 GSequenceNode
*node
, *first
;
476 g_return_val_if_fail (seq
!= NULL
, NULL
);
478 check_seq_access (seq
);
480 node
= node_new (data
);
481 first
= node_get_first (seq
->end_node
);
483 node_insert_before (first
, node
);
489 * g_sequence_insert_before:
490 * @iter: a #GSequenceIter
491 * @data: the data for the new item
493 * Inserts a new item just before the item pointed to by @iter.
495 * Return value: an iterator pointing to the new item
500 g_sequence_insert_before (GSequenceIter
*iter
,
505 g_return_val_if_fail (iter
!= NULL
, NULL
);
507 check_iter_access (iter
);
509 node
= node_new (data
);
511 node_insert_before (iter
, node
);
518 * @iter: a #GSequenceIter
520 * Removes the item pointed to by @iter. It is an error to pass the
521 * end iterator to this function.
523 * If the sequnce has a data destroy function associated with it, this
524 * function is called on the data for the removed item.
529 g_sequence_remove (GSequenceIter
*iter
)
533 g_return_if_fail (iter
!= NULL
);
534 g_return_if_fail (!is_end (iter
));
536 check_iter_access (iter
);
538 seq
= get_sequence (iter
);
541 node_free (iter
, seq
);
545 * g_sequence_remove_range:
546 * @begin: a #GSequenceIter
547 * @end: a #GSequenceIter
549 * Removes all items in the (@begin, @end) range.
551 * If the sequence has a data destroy function associated with it, this
552 * function is called on the data for the removed items.
557 g_sequence_remove_range (GSequenceIter
*begin
,
560 g_return_if_fail (get_sequence (begin
) == get_sequence (end
));
562 check_iter_access (begin
);
563 check_iter_access (end
);
565 g_sequence_move_range (NULL
, begin
, end
);
569 * g_sequence_move_range:
570 * @dest: a #GSequenceIter
571 * @begin: a #GSequenceIter
572 * @end: a #GSequenceIter
574 * Inserts the (@begin, @end) range at the destination pointed to by ptr.
575 * The @begin and @end iters must point into the same sequence. It is
576 * allowed for @dest to point to a different sequence than the one pointed
577 * into by @begin and @end.
579 * If @dest is NULL, the range indicated by @begin and @end is
580 * removed from the sequence. If @dest iter points to a place within
581 * the (@begin, @end) range, the range does not move.
586 g_sequence_move_range (GSequenceIter
*dest
,
587 GSequenceIter
*begin
,
591 GSequenceNode
*first
;
593 g_return_if_fail (begin
!= NULL
);
594 g_return_if_fail (end
!= NULL
);
596 check_iter_access (begin
);
597 check_iter_access (end
);
599 check_iter_access (dest
);
601 src_seq
= get_sequence (begin
);
603 g_return_if_fail (src_seq
== get_sequence (end
));
605 /* Dest points to begin or end? */
606 if (dest
== begin
|| dest
== end
)
609 /* begin comes after end? */
610 if (g_sequence_iter_compare (begin
, end
) >= 0)
613 /* dest points somewhere in the (begin, end) range? */
614 if (dest
&& get_sequence (dest
) == src_seq
&&
615 g_sequence_iter_compare (dest
, begin
) > 0 &&
616 g_sequence_iter_compare (dest
, end
) < 0)
621 src_seq
= get_sequence (begin
);
623 first
= node_get_first (begin
);
630 node_join (first
, end
);
634 first
= node_get_first (dest
);
638 node_join (begin
, dest
);
641 node_join (first
, begin
);
645 node_free (begin
, src_seq
);
652 * @cmp_func: the #GCompareDataFunc used to sort @seq. This function is
653 * passed two items of @seq and should return 0 if they are equal,
654 * a negative value if the first comes before the second, and a
655 * positive value if the second comes before the first.
656 * @cmp_data: user data passed to @cmp_func
658 * Sorts @seq using @cmp_func.
663 g_sequence_sort (GSequence
*seq
,
664 GCompareDataFunc cmp_func
,
669 info
.cmp_func
= cmp_func
;
670 info
.cmp_data
= cmp_data
;
671 info
.end_node
= seq
->end_node
;
673 check_seq_access (seq
);
675 g_sequence_sort_iter (seq
, iter_compare
, &info
);
679 * g_sequence_insert_sorted:
681 * @data: the data to insert
682 * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
683 * is called with two items of the @seq and @user_data. It should
684 * return 0 if the items are equal, a negative value if the first
685 * item comes before the second, and a positive value if the second
686 * item comes before the first.
687 * @cmp_data: user data passed to @cmp_func.
689 * Inserts @data into @sequence using @func to determine the new position.
690 * The sequence must already be sorted according to @cmp_func; otherwise the
691 * new position of @data is undefined.
693 * Return value: 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 #GCompareDataFunc used to compare items in the sequence. It
720 * is called with two items of the @seq and @user_data. It should
721 * return 0 if the items are equal, a negative value if the first
722 * item comes before the second, and a positive value if the second
723 * item comes before the first.
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.
734 g_sequence_sort_changed (GSequenceIter
*iter
,
735 GCompareDataFunc cmp_func
,
740 g_return_if_fail (!is_end (iter
));
742 info
.cmp_func
= cmp_func
;
743 info
.cmp_data
= cmp_data
;
744 info
.end_node
= get_sequence (iter
)->end_node
;
745 check_iter_access (iter
);
747 g_sequence_sort_changed_iter (iter
, iter_compare
, &info
);
753 * @data: data for the new item
754 * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
755 * is called with two items of the @seq and @user_data. It should
756 * return 0 if the items are equal, a negative value if the first
757 * item comes before the second, and a positive value if the second
758 * item comes before the first.
759 * @cmp_data: user data passed to @cmp_func.
761 * Returns an iterator pointing to the position where @data would
762 * be inserted according to @cmp_func and @cmp_data.
764 * If you are simply searching for an existing element of the sequence,
765 * consider using g_sequence_lookup().
767 * Return value: an #GSequenceIter pointing to the position where @data
768 * would have been inserted according to @cmp_func and @cmp_data.
773 g_sequence_search (GSequence
*seq
,
775 GCompareDataFunc cmp_func
,
780 g_return_val_if_fail (seq
!= NULL
, NULL
);
782 info
.cmp_func
= cmp_func
;
783 info
.cmp_data
= cmp_data
;
784 info
.end_node
= seq
->end_node
;
785 check_seq_access (seq
);
787 return g_sequence_search_iter (seq
, data
, iter_compare
, &info
);
793 * @data: data to lookup
794 * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
795 * is called with two items of the @seq and @user_data. It should
796 * return 0 if the items are equal, a negative value if the first
797 * item comes before the second, and a positive value if the second
798 * item comes before the first.
799 * @cmp_data: user data passed to @cmp_func.
801 * Returns an iterator pointing to the position of the first item found
802 * equal to @data according to @cmp_func and @cmp_data. If more than one item
803 * is equal, it is not guaranteed that it is the first which is returned.
804 * In that case, you can use g_sequence_iter_next() and g_sequence_iter_prev()
807 * Return value: an #GSequenceIter pointing to the position of the first item
808 * found equal to @data according to @cmp_func and @cmp_data.
813 g_sequence_lookup (GSequence
*seq
,
815 GCompareDataFunc cmp_func
,
820 g_return_val_if_fail (seq
!= NULL
, NULL
);
822 info
.cmp_func
= cmp_func
;
823 info
.cmp_data
= cmp_data
;
824 info
.end_node
= seq
->end_node
;
825 check_seq_access (seq
);
827 return g_sequence_lookup_iter (seq
, data
, iter_compare
, &info
);
831 * g_sequence_sort_iter:
833 * @cmp_func: the #GSequenceItercompare used to compare iterators in the
834 * sequence. It is called with two iterators pointing into @seq. It should
835 * return 0 if the iterators are equal, a negative value if the first
836 * iterator comes before the second, and a positive value if the second
837 * iterator comes before the first.
838 * @cmp_data: user data passed to @cmp_func
840 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
841 * of a GCompareDataFunc as the compare function
846 g_sequence_sort_iter (GSequence
*seq
,
847 GSequenceIterCompareFunc cmp_func
,
851 GSequenceNode
*begin
, *end
;
853 g_return_if_fail (seq
!= NULL
);
854 g_return_if_fail (cmp_func
!= NULL
);
856 check_seq_access (seq
);
858 begin
= g_sequence_get_begin_iter (seq
);
859 end
= g_sequence_get_end_iter (seq
);
861 tmp
= g_sequence_new (NULL
);
862 tmp
->real_sequence
= seq
;
864 g_sequence_move_range (g_sequence_get_begin_iter (tmp
), begin
, end
);
866 seq
->access_prohibited
= TRUE
;
867 tmp
->access_prohibited
= TRUE
;
869 while (g_sequence_get_length (tmp
) > 0)
871 GSequenceNode
*node
= g_sequence_get_begin_iter (tmp
);
873 node_insert_sorted (seq
->end_node
, node
, seq
->end_node
,
877 tmp
->access_prohibited
= FALSE
;
878 seq
->access_prohibited
= FALSE
;
880 g_sequence_free (tmp
);
884 * g_sequence_sort_changed_iter:
885 * @iter: a #GSequenceIter
886 * @iter_cmp: the #GSequenceItercompare used to compare iterators in the
887 * sequence. It is called with two iterators pointing into @seq. It should
888 * return 0 if the iterators are equal, a negative value if the first
889 * iterator comes before the second, and a positive value if the second
890 * iterator comes before the first.
891 * @cmp_data: user data passed to @cmp_func
893 * Like g_sequence_sort_changed(), but uses
894 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
895 * the compare function.
900 g_sequence_sort_changed_iter (GSequenceIter
*iter
,
901 GSequenceIterCompareFunc iter_cmp
,
904 GSequence
*seq
, *tmp_seq
;
905 GSequenceIter
*next
, *prev
;
907 g_return_if_fail (iter
!= NULL
);
908 g_return_if_fail (!is_end (iter
));
909 g_return_if_fail (iter_cmp
!= NULL
);
910 check_iter_access (iter
);
912 /* If one of the neighbours is equal to iter, then
913 * don't move it. This ensures that sort_changed() is
914 * a stable operation.
917 next
= node_get_next (iter
);
918 prev
= node_get_prev (iter
);
920 if (prev
!= iter
&& iter_cmp (prev
, iter
, cmp_data
) == 0)
923 if (!is_end (next
) && iter_cmp (next
, iter
, cmp_data
) == 0)
926 seq
= get_sequence (iter
);
928 seq
->access_prohibited
= TRUE
;
930 tmp_seq
= g_sequence_new (NULL
);
931 tmp_seq
->real_sequence
= seq
;
934 node_insert_before (tmp_seq
->end_node
, iter
);
936 node_insert_sorted (seq
->end_node
, iter
, seq
->end_node
,
939 g_sequence_free (tmp_seq
);
941 seq
->access_prohibited
= FALSE
;
945 * g_sequence_insert_sorted_iter:
947 * @data: data for the new item
948 * @iter_cmp: the #GSequenceItercompare used to compare iterators in the
949 * sequence. It is called with two iterators pointing into @seq. It should
950 * return 0 if the iterators are equal, a negative value if the first
951 * iterator comes before the second, and a positive value if the second
952 * iterator comes before the first.
953 * @cmp_data: user data passed to @cmp_func
955 * Like g_sequence_insert_sorted(), but uses
956 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
957 * the compare function.
959 * Return value: a #GSequenceIter pointing to the new item
964 g_sequence_insert_sorted_iter (GSequence
*seq
,
966 GSequenceIterCompareFunc iter_cmp
,
969 GSequenceNode
*new_node
;
972 g_return_val_if_fail (seq
!= NULL
, NULL
);
973 g_return_val_if_fail (iter_cmp
!= NULL
, NULL
);
975 check_seq_access (seq
);
977 seq
->access_prohibited
= TRUE
;
979 /* Create a new temporary sequence and put the new node into
980 * that. The reason for this is that the user compare function
981 * will be called with the new node, and if it dereferences,
982 * "is_end" will be called on it. But that will crash if the
983 * node is not actually in a sequence.
985 * node_insert_sorted() makes sure the node is unlinked before
988 * The reason we need the "iter" versions at all is that that
989 * is the only kind of compare functions GtkTreeView can use.
991 tmp_seq
= g_sequence_new (NULL
);
992 tmp_seq
->real_sequence
= seq
;
994 new_node
= g_sequence_append (tmp_seq
, data
);
996 node_insert_sorted (seq
->end_node
, new_node
,
997 seq
->end_node
, iter_cmp
, cmp_data
);
999 g_sequence_free (tmp_seq
);
1001 seq
->access_prohibited
= FALSE
;
1007 * g_sequence_search_iter:
1008 * @seq: a #GSequence
1009 * @data: data for the new item
1010 * @iter_cmp: the #GSequenceIterCompare function used to compare iterators
1011 * in the sequence. It is called with two iterators pointing into @seq.
1012 * It should return 0 if the iterators are equal, a negative value if the
1013 * first iterator comes before the second, and a positive value if the
1014 * second iterator comes before the first.
1015 * @cmp_data: user data passed to @iter_cmp
1017 * Like g_sequence_search(), but uses
1018 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
1019 * the compare function.
1021 * If you are simply searching for an existing element of the sequence,
1022 * consider using g_sequence_lookup_iter().
1024 * Return value: a #GSequenceIter pointing to the position in @seq
1025 * where @data would have been inserted according to @iter_cmp and @cmp_data.
1030 g_sequence_search_iter (GSequence
*seq
,
1032 GSequenceIterCompareFunc iter_cmp
,
1035 GSequenceNode
*node
;
1036 GSequenceNode
*dummy
;
1039 g_return_val_if_fail (seq
!= NULL
, NULL
);
1041 check_seq_access (seq
);
1043 seq
->access_prohibited
= TRUE
;
1045 tmp_seq
= g_sequence_new (NULL
);
1046 tmp_seq
->real_sequence
= seq
;
1048 dummy
= g_sequence_append (tmp_seq
, data
);
1050 node
= node_find_closest (seq
->end_node
, dummy
,
1051 seq
->end_node
, iter_cmp
, cmp_data
);
1053 g_sequence_free (tmp_seq
);
1055 seq
->access_prohibited
= FALSE
;
1061 * g_sequence_lookup_iter:
1062 * @seq: a #GSequence
1063 * @data: data to lookup
1064 * @iter_cmp: the #GSequenceIterCompare function used to compare iterators
1065 * in the sequence. It is called with two iterators pointing into @seq.
1066 * It should return 0 if the iterators are equal, a negative value if the
1067 * first iterator comes before the second, and a positive value if the
1068 * second iterator comes before the first.
1069 * @cmp_data: user data passed to @iter_cmp
1071 * Like g_sequence_lookup(), but uses
1072 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
1073 * the compare function.
1075 * Return value: an #GSequenceIter pointing to the position of the first item
1076 * found equal to @data according to @cmp_func and @cmp_data.
1081 g_sequence_lookup_iter (GSequence
*seq
,
1083 GSequenceIterCompareFunc iter_cmp
,
1086 GSequenceNode
*node
;
1087 GSequenceNode
*dummy
;
1090 g_return_val_if_fail (seq
!= NULL
, NULL
);
1092 check_seq_access (seq
);
1094 seq
->access_prohibited
= TRUE
;
1096 tmp_seq
= g_sequence_new (NULL
);
1097 tmp_seq
->real_sequence
= seq
;
1099 dummy
= g_sequence_append (tmp_seq
, data
);
1101 node
= node_find (seq
->end_node
, dummy
,
1102 seq
->end_node
, iter_cmp
, cmp_data
);
1104 g_sequence_free (tmp_seq
);
1106 seq
->access_prohibited
= FALSE
;
1112 * g_sequence_iter_get_sequence:
1113 * @iter: a #GSequenceIter
1115 * Returns the #GSequence that @iter points into.
1117 * Return value: the #GSequence that @iter points into.
1122 g_sequence_iter_get_sequence (GSequenceIter
*iter
)
1126 g_return_val_if_fail (iter
!= NULL
, NULL
);
1128 seq
= get_sequence (iter
);
1130 /* For temporary sequences, this points to the sequence that
1131 * is actually being manipulated
1133 return seq
->real_sequence
;
1138 * @iter: a #GSequenceIter
1140 * Returns the data that @iter points to.
1142 * Return value: the data that @iter points to
1147 g_sequence_get (GSequenceIter
*iter
)
1149 g_return_val_if_fail (iter
!= NULL
, NULL
);
1150 g_return_val_if_fail (!is_end (iter
), NULL
);
1157 * @iter: a #GSequenceIter
1158 * @data: new data for the item
1160 * Changes the data for the item pointed to by @iter to be @data. If
1161 * the sequence has a data destroy function associated with it, that
1162 * function is called on the existing data that @iter pointed to.
1167 g_sequence_set (GSequenceIter
*iter
,
1172 g_return_if_fail (iter
!= NULL
);
1173 g_return_if_fail (!is_end (iter
));
1175 seq
= get_sequence (iter
);
1177 /* If @data is identical to iter->data, it is destroyed
1178 * here. This will work right in case of ref-counted objects. Also
1179 * it is similar to what ghashtables do.
1181 * For non-refcounted data it's a little less convenient, but
1182 * code relying on self-setting not destroying would be
1183 * pretty dubious anyway ...
1186 if (seq
->data_destroy_notify
)
1187 seq
->data_destroy_notify (iter
->data
);
1193 * g_sequence_get_length:
1194 * @seq: a #GSequence
1196 * Returns the length of @seq
1198 * Return value: the length of @seq
1203 g_sequence_get_length (GSequence
*seq
)
1205 return node_get_length (seq
->end_node
) - 1;
1209 * g_sequence_get_end_iter:
1210 * @seq: a #GSequence
1212 * Returns the end iterator for @seg
1214 * Return value: the end iterator for @seq
1219 g_sequence_get_end_iter (GSequence
*seq
)
1221 g_return_val_if_fail (seq
!= NULL
, NULL
);
1223 return seq
->end_node
;
1227 * g_sequence_get_begin_iter:
1228 * @seq: a #GSequence
1230 * Returns the begin iterator for @seq.
1232 * Return value: the begin iterator for @seq.
1237 g_sequence_get_begin_iter (GSequence
*seq
)
1239 g_return_val_if_fail (seq
!= NULL
, NULL
);
1241 return node_get_first (seq
->end_node
);
1245 clamp_position (GSequence
*seq
,
1248 gint len
= g_sequence_get_length (seq
);
1250 if (pos
> len
|| pos
< 0)
1257 * if pos > number of items or -1, will return end pointer
1260 * g_sequence_get_iter_at_pos:
1261 * @seq: a #GSequence
1262 * @pos: a position in @seq, or -1 for the end.
1264 * Returns the iterator at position @pos. If @pos is negative or larger
1265 * than the number of items in @seq, the end iterator is returned.
1267 * Return value: The #GSequenceIter at position @pos
1272 g_sequence_get_iter_at_pos (GSequence
*seq
,
1275 g_return_val_if_fail (seq
!= NULL
, NULL
);
1277 pos
= clamp_position (seq
, pos
);
1279 return node_get_by_pos (seq
->end_node
, pos
);
1284 * @src: a #GSequenceIter pointing to the item to move
1285 * @dest: a #GSequenceIter pointing to the position to which
1286 * the item is moved.
1288 * Moves the item pointed to by @src to the position indicated by @dest.
1289 * After calling this function @dest will point to the position immediately
1290 * after @src. It is allowed for @src and @dest to point into different
1296 g_sequence_move (GSequenceIter
*src
,
1297 GSequenceIter
*dest
)
1299 g_return_if_fail (src
!= NULL
);
1300 g_return_if_fail (dest
!= NULL
);
1301 g_return_if_fail (!is_end (src
));
1307 node_insert_before (dest
, src
);
1313 * g_sequence_iter_is_end:
1314 * @iter: a #GSequenceIter
1316 * Returns whether @iter is the end iterator
1318 * Return value: Whether @iter is the end iterator.
1323 g_sequence_iter_is_end (GSequenceIter
*iter
)
1325 g_return_val_if_fail (iter
!= NULL
, FALSE
);
1327 return is_end (iter
);
1331 * g_sequence_iter_is_begin:
1332 * @iter: a #GSequenceIter
1334 * Returns whether @iter is the begin iterator
1336 * Return value: whether @iter is the begin iterator
1341 g_sequence_iter_is_begin (GSequenceIter
*iter
)
1343 g_return_val_if_fail (iter
!= NULL
, FALSE
);
1345 return (node_get_prev (iter
) == iter
);
1349 * g_sequence_iter_get_position:
1350 * @iter: a #GSequenceIter
1352 * Returns the position of @iter
1354 * Return value: the position of @iter
1359 g_sequence_iter_get_position (GSequenceIter
*iter
)
1361 g_return_val_if_fail (iter
!= NULL
, -1);
1363 return node_get_pos (iter
);
1367 * g_sequence_iter_next:
1368 * @iter: a #GSequenceIter
1370 * Returns an iterator pointing to the next position after @iter. If
1371 * @iter is the end iterator, the end iterator is returned.
1373 * Return value: a #GSequenceIter pointing to the next position after @iter.
1378 g_sequence_iter_next (GSequenceIter
*iter
)
1380 g_return_val_if_fail (iter
!= NULL
, NULL
);
1382 return node_get_next (iter
);
1386 * g_sequence_iter_prev:
1387 * @iter: a #GSequenceIter
1389 * Returns an iterator pointing to the previous position before @iter. If
1390 * @iter is the begin iterator, the begin iterator is returned.
1392 * Return value: a #GSequenceIter pointing to the previous position before
1398 g_sequence_iter_prev (GSequenceIter
*iter
)
1400 g_return_val_if_fail (iter
!= NULL
, NULL
);
1402 return node_get_prev (iter
);
1406 * g_sequence_iter_move:
1407 * @iter: a #GSequenceIter
1408 * @delta: A positive or negative number indicating how many positions away
1409 * from @iter the returned #GSequenceIter will be.
1411 * Returns the #GSequenceIter which is @delta positions away from @iter.
1412 * If @iter is closer than -@delta positions to the beginning of the sequence,
1413 * the begin iterator is returned. If @iter is closer than @delta positions
1414 * to the end of the sequence, the end iterator is returned.
1416 * Return value: a #GSequenceIter which is @delta positions away from @iter.
1421 g_sequence_iter_move (GSequenceIter
*iter
,
1426 g_return_val_if_fail (iter
!= NULL
, NULL
);
1428 new_pos
= node_get_pos (iter
) + delta
;
1430 new_pos
= clamp_position (get_sequence (iter
), new_pos
);
1432 return node_get_by_pos (iter
, new_pos
);
1437 * @a: a #GSequenceIter
1438 * @b: a #GSequenceIter
1440 * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
1441 * to point into difference sequences.
1446 g_sequence_swap (GSequenceIter
*a
,
1449 GSequenceNode
*leftmost
, *rightmost
, *rightmost_next
;
1452 g_return_if_fail (!g_sequence_iter_is_end (a
));
1453 g_return_if_fail (!g_sequence_iter_is_end (b
));
1458 a_pos
= g_sequence_iter_get_position (a
);
1459 b_pos
= g_sequence_iter_get_position (b
);
1472 rightmost_next
= node_get_next (rightmost
);
1474 /* The situation is now like this:
1476 * ..., leftmost, ......., rightmost, rightmost_next, ...
1479 g_sequence_move (rightmost
, leftmost
);
1480 g_sequence_move (leftmost
, rightmost_next
);
1484 * Implementation of a treap
1489 get_priority (GSequenceNode
*node
)
1491 guint key
= GPOINTER_TO_UINT (node
);
1493 /* This hash function is based on one found on Thomas Wang's
1496 * http://www.concentric.net/~Ttwang/tech/inthash.htm
1499 key
= (key
<< 15) - key
- 1;
1500 key
= key
^ (key
>> 12);
1501 key
= key
+ (key
<< 2);
1502 key
= key
^ (key
>> 4);
1503 key
= key
+ (key
<< 3) + (key
<< 11);
1504 key
= key
^ (key
>> 16);
1506 /* We rely on 0 being less than all other priorities */
1507 return key
? key
: 1;
1510 static GSequenceNode
*
1511 find_root (GSequenceNode
*node
)
1513 while (node
->parent
)
1514 node
= node
->parent
;
1519 static GSequenceNode
*
1520 node_new (gpointer data
)
1522 GSequenceNode
*node
= g_slice_new0 (GSequenceNode
);
1528 node
->parent
= NULL
;
1533 static GSequenceNode
*
1534 node_get_first (GSequenceNode
*node
)
1536 node
= find_root (node
);
1544 static GSequenceNode
*
1545 node_get_last (GSequenceNode
*node
)
1547 node
= find_root (node
);
1555 #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1556 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1558 static GSequenceNode
*
1559 node_get_next (GSequenceNode
*node
)
1561 GSequenceNode
*n
= node
;
1571 while (NODE_RIGHT_CHILD (n
))
1583 static GSequenceNode
*
1584 node_get_prev (GSequenceNode
*node
)
1586 GSequenceNode
*n
= node
;
1596 while (NODE_LEFT_CHILD (n
))
1608 #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1611 node_get_pos (GSequenceNode
*node
)
1616 n_smaller
= node
->left
->n_nodes
;
1620 if (NODE_RIGHT_CHILD (node
))
1621 n_smaller
+= N_NODES (node
->parent
->left
) + 1;
1623 node
= node
->parent
;
1629 static GSequenceNode
*
1630 node_get_by_pos (GSequenceNode
*node
,
1635 node
= find_root (node
);
1637 while ((i
= N_NODES (node
->left
)) != pos
)
1653 static GSequenceNode
*
1654 node_find (GSequenceNode
*haystack
,
1655 GSequenceNode
*needle
,
1657 GSequenceIterCompareFunc iter_cmp
,
1662 haystack
= find_root (haystack
);
1666 /* iter_cmp can't be passed the end node, since the function may
1669 if (haystack
== end
)
1672 c
= iter_cmp (haystack
, needle
, cmp_data
);
1678 haystack
= haystack
->left
;
1680 haystack
= haystack
->right
;
1682 while (haystack
!= NULL
);
1687 static GSequenceNode
*
1688 node_find_closest (GSequenceNode
*haystack
,
1689 GSequenceNode
*needle
,
1691 GSequenceIterCompareFunc iter_cmp
,
1694 GSequenceNode
*best
;
1697 haystack
= find_root (haystack
);
1703 /* iter_cmp can't be passed the end node, since the function may
1706 if (haystack
== end
)
1709 c
= iter_cmp (haystack
, needle
, cmp_data
);
1711 /* In the following we don't break even if c == 0. Instead we go on
1712 * searching along the 'bigger' nodes, so that we find the last one
1713 * that is equal to the needle.
1716 haystack
= haystack
->left
;
1718 haystack
= haystack
->right
;
1720 while (haystack
!= NULL
);
1722 /* If the best node is smaller or equal to the data, then move one step
1723 * to the right to make sure the best one is strictly bigger than the data
1725 if (best
!= end
&& c
<= 0)
1726 best
= node_get_next (best
);
1732 node_get_length (GSequenceNode
*node
)
1734 node
= find_root (node
);
1736 return node
->n_nodes
;
1740 real_node_free (GSequenceNode
*node
,
1745 real_node_free (node
->left
, seq
);
1746 real_node_free (node
->right
, seq
);
1748 if (seq
&& seq
->data_destroy_notify
&& node
!= seq
->end_node
)
1749 seq
->data_destroy_notify (node
->data
);
1751 g_slice_free (GSequenceNode
, node
);
1756 node_free (GSequenceNode
*node
,
1759 node
= find_root (node
);
1761 real_node_free (node
, seq
);
1765 node_update_fields (GSequenceNode
*node
)
1769 n_nodes
+= N_NODES (node
->left
);
1770 n_nodes
+= N_NODES (node
->right
);
1772 node
->n_nodes
= n_nodes
;
1776 node_rotate (GSequenceNode
*node
)
1778 GSequenceNode
*tmp
, *old
;
1780 g_assert (node
->parent
);
1781 g_assert (node
->parent
!= node
);
1783 if (NODE_LEFT_CHILD (node
))
1788 node
->right
= node
->parent
;
1789 node
->parent
= node
->parent
->parent
;
1792 if (node
->parent
->left
== node
->right
)
1793 node
->parent
->left
= node
;
1795 node
->parent
->right
= node
;
1798 g_assert (node
->right
);
1800 node
->right
->parent
= node
;
1801 node
->right
->left
= tmp
;
1803 if (node
->right
->left
)
1804 node
->right
->left
->parent
= node
->right
;
1813 node
->left
= node
->parent
;
1814 node
->parent
= node
->parent
->parent
;
1817 if (node
->parent
->right
== node
->left
)
1818 node
->parent
->right
= node
;
1820 node
->parent
->left
= node
;
1823 g_assert (node
->left
);
1825 node
->left
->parent
= node
;
1826 node
->left
->right
= tmp
;
1828 if (node
->left
->right
)
1829 node
->left
->right
->parent
= node
->left
;
1834 node_update_fields (old
);
1835 node_update_fields (node
);
1839 node_update_fields_deep (GSequenceNode
*node
)
1843 node_update_fields (node
);
1845 node_update_fields_deep (node
->parent
);
1850 rotate_down (GSequenceNode
*node
,
1855 left
= node
->left
? get_priority (node
->left
) : 0;
1856 right
= node
->right
? get_priority (node
->right
) : 0;
1858 while (priority
< left
|| priority
< right
)
1861 node_rotate (node
->left
);
1863 node_rotate (node
->right
);
1865 left
= node
->left
? get_priority (node
->left
) : 0;
1866 right
= node
->right
? get_priority (node
->right
) : 0;
1871 node_cut (GSequenceNode
*node
)
1873 while (node
->parent
)
1877 node
->left
->parent
= NULL
;
1880 node_update_fields (node
);
1882 rotate_down (node
, get_priority (node
));
1886 node_join (GSequenceNode
*left
,
1887 GSequenceNode
*right
)
1889 GSequenceNode
*fake
= node_new (NULL
);
1891 fake
->left
= find_root (left
);
1892 fake
->right
= find_root (right
);
1893 fake
->left
->parent
= fake
;
1894 fake
->right
->parent
= fake
;
1896 node_update_fields (fake
);
1900 node_free (fake
, NULL
);
1904 node_insert_before (GSequenceNode
*node
,
1907 new->left
= node
->left
;
1909 new->left
->parent
= new;
1914 node_update_fields_deep (new);
1916 while (new->parent
&& get_priority (new) > get_priority (new->parent
))
1919 rotate_down (new, get_priority (new));
1923 node_unlink (GSequenceNode
*node
)
1925 rotate_down (node
, 0);
1927 if (NODE_RIGHT_CHILD (node
))
1928 node
->parent
->right
= NULL
;
1929 else if (NODE_LEFT_CHILD (node
))
1930 node
->parent
->left
= NULL
;
1933 node_update_fields_deep (node
->parent
);
1935 node
->parent
= NULL
;
1939 node_insert_sorted (GSequenceNode
*node
,
1942 GSequenceIterCompareFunc iter_cmp
,
1945 GSequenceNode
*closest
;
1947 closest
= node_find_closest (node
, new, end
, iter_cmp
, cmp_data
);
1951 node_insert_before (closest
, new);