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.
26 typedef struct _GSequenceNode GSequenceNode;
30 GSequenceNode * end_node;
31 GDestroyNotify data_destroy_notify;
32 gboolean access_prohibited;
34 /* The 'real_sequence' is used when temporary sequences are created
35 * to hold nodes that are being rearranged. The 'real_sequence' of such
36 * a temporary sequence points to the sequence that is actually being
37 * manipulated. The only reason we need this is so that when the
38 * sort/sort_changed/search_iter() functions call out to the application
39 * g_sequence_iter_get_sequence() will return the correct sequence.
41 GSequence * real_sequence;
47 GSequenceNode * parent;
49 GSequenceNode * right;
50 gpointer data; /* For the end node, this field points
56 * Declaration of GSequenceNode methods
58 static GSequenceNode *node_new (gpointer data);
59 static GSequenceNode *node_get_first (GSequenceNode *node);
60 static GSequenceNode *node_get_last (GSequenceNode *node);
61 static GSequenceNode *node_get_prev (GSequenceNode *node);
62 static GSequenceNode *node_get_next (GSequenceNode *node);
63 static gint node_get_pos (GSequenceNode *node);
64 static GSequenceNode *node_get_by_pos (GSequenceNode *node,
66 static GSequenceNode *node_find_closest (GSequenceNode *haystack,
67 GSequenceNode *needle,
69 GSequenceIterCompareFunc cmp,
71 static gint node_get_length (GSequenceNode *node);
72 static void node_free (GSequenceNode *node,
74 static void node_cut (GSequenceNode *split);
75 static void node_insert_before (GSequenceNode *node,
77 static void node_unlink (GSequenceNode *node);
78 static void node_join (GSequenceNode *left,
79 GSequenceNode *right);
80 static void node_insert_sorted (GSequenceNode *node,
83 GSequenceIterCompareFunc cmp_func,
88 * Various helper functions
91 check_seq_access (GSequence *seq)
93 if (G_UNLIKELY (seq->access_prohibited))
95 g_warning ("Accessing a sequence while it is "
96 "being sorted or searched is not allowed");
101 get_sequence (GSequenceNode *node)
103 return (GSequence *)node_get_last (node)->data;
107 check_iter_access (GSequenceIter *iter)
109 check_seq_access (get_sequence (iter));
113 is_end (GSequenceIter *iter)
123 if (iter->parent->right != iter)
126 seq = get_sequence (iter);
128 return seq->end_node == iter;
133 GCompareDataFunc cmp_func;
135 GSequenceNode *end_node;
138 /* This function compares two iters using a normal compare
139 * function and user_data passed in in a SortInfo struct
142 iter_compare (GSequenceIter *node1,
143 GSequenceIter *node2,
146 const SortInfo *info = data;
149 if (node1 == info->end_node)
152 if (node2 == info->end_node)
155 retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
166 * @data_destroy: a #GDestroyNotify function, or %NULL
168 * Creates a new GSequence. The @data_destroy function, if non-%NULL will
169 * be called on all items when the sequence is destroyed and on items that
170 * are removed from the sequence.
172 * Return value: a new #GSequence
177 g_sequence_new (GDestroyNotify data_destroy)
179 GSequence *seq = g_new (GSequence, 1);
180 seq->data_destroy_notify = data_destroy;
182 seq->end_node = node_new (seq);
184 seq->access_prohibited = FALSE;
186 seq->real_sequence = seq;
195 * Frees the memory allocated for @seq. If @seq has a data destroy
196 * function associated with it, that function is called on all items in
202 g_sequence_free (GSequence *seq)
204 g_return_if_fail (seq != NULL);
206 check_seq_access (seq);
208 node_free (seq->end_node, seq);
214 * g_sequence_foreach_range:
215 * @begin: a #GSequenceIter
216 * @end: a #GSequenceIter
218 * @user_data: user data passed to @func
220 * Calls @func for each item in the range (@begin, @end) passing
221 * @user_data to the function.
226 g_sequence_foreach_range (GSequenceIter *begin,
234 g_return_if_fail (func != NULL);
235 g_return_if_fail (begin != NULL);
236 g_return_if_fail (end != NULL);
238 seq = get_sequence (begin);
240 seq->access_prohibited = TRUE;
245 GSequenceIter *next = node_get_next (iter);
247 func (iter->data, user_data);
252 seq->access_prohibited = FALSE;
256 * g_sequence_foreach:
258 * @func: the function to call for each item in @seq
259 * @user_data: user data passed to @func
261 * Calls @func for each item in the sequence passing @user_data
267 g_sequence_foreach (GSequence *seq,
271 GSequenceIter *begin, *end;
273 check_seq_access (seq);
275 begin = g_sequence_get_begin_iter (seq);
276 end = g_sequence_get_end_iter (seq);
278 g_sequence_foreach_range (begin, end, func, user_data);
282 * g_sequence_range_get_midpoint:
283 * @begin: a #GSequenceIter
284 * @end: a #GSequenceIter
286 * Finds an iterator somewhere in the range (@begin, @end). This
287 * iterator will be close to the middle of the range, but is not
288 * guaranteed to be <emphasis>exactly</emphasis> in the middle.
290 * The @begin and @end iterators must both point to the same sequence and
291 * @begin must come before or be equal to @end in the sequence.
293 * Return value: A #GSequenceIter pointing somewhere in the
294 * (@begin, @end) range.
299 g_sequence_range_get_midpoint (GSequenceIter *begin,
302 int begin_pos, end_pos, mid_pos;
304 g_return_val_if_fail (begin != NULL, NULL);
305 g_return_val_if_fail (end != NULL, NULL);
306 g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
308 begin_pos = node_get_pos (begin);
309 end_pos = node_get_pos (end);
311 g_return_val_if_fail (end_pos >= begin_pos, NULL);
313 mid_pos = begin_pos + (end_pos - begin_pos) / 2;
315 return node_get_by_pos (begin, mid_pos);
319 * g_sequence_iter_compare:
320 * @a: a #GSequenceIter
321 * @b: a #GSequenceIter
323 * Returns a negative number if @a comes before @b, 0 if they are equal,
324 * and a positive number if @a comes after @b.
326 * The @a and @b iterators must point into the same sequence.
328 * Return value: A negative number if @a comes before @b, 0 if they are
329 * equal, and a positive number if @a comes after @b.
334 g_sequence_iter_compare (GSequenceIter *a,
339 g_return_val_if_fail (a != NULL, 0);
340 g_return_val_if_fail (b != NULL, 0);
341 g_return_val_if_fail (get_sequence (a) == get_sequence (b), 0);
343 check_iter_access (a);
344 check_iter_access (b);
346 a_pos = node_get_pos (a);
347 b_pos = node_get_pos (b);
351 else if (a_pos > b_pos)
359 * @seq: a #GSequencePointer
360 * @data: the data for the new item
362 * Adds a new item to the end of @seq.
364 * Return value: an iterator pointing to the new item
369 g_sequence_append (GSequence *seq,
374 g_return_val_if_fail (seq != NULL, NULL);
376 check_seq_access (seq);
378 node = node_new (data);
379 node_insert_before (seq->end_node, node);
385 * g_sequence_prepend:
387 * @data: the data for the new item
389 * Adds a new item to the front of @seq
391 * Return value: an iterator pointing to the new item
396 g_sequence_prepend (GSequence *seq,
399 GSequenceNode *node, *first;
401 g_return_val_if_fail (seq != NULL, NULL);
403 check_seq_access (seq);
405 node = node_new (data);
406 first = node_get_first (seq->end_node);
408 node_insert_before (first, node);
414 * g_sequence_insert_before:
415 * @iter: a #GSequenceIter
416 * @data: the data for the new item
418 * Inserts a new item just before the item pointed to by @iter.
420 * Return value: an iterator pointing to the new item
425 g_sequence_insert_before (GSequenceIter *iter,
430 g_return_val_if_fail (iter != NULL, NULL);
432 check_iter_access (iter);
434 node = node_new (data);
436 node_insert_before (iter, node);
443 * @iter: a #GSequenceIter
445 * Removes the item pointed to by @iter. It is an error to pass the
446 * end iterator to this function.
448 * If the sequnce has a data destroy function associated with it, this
449 * function is called on the data for the removed item.
454 g_sequence_remove (GSequenceIter *iter)
458 g_return_if_fail (iter != NULL);
459 g_return_if_fail (!is_end (iter));
461 check_iter_access (iter);
463 seq = get_sequence (iter);
466 node_free (iter, seq);
470 * g_sequence_remove_range:
471 * @begin: a #GSequenceIter
472 * @end: a #GSequenceIter
474 * Removes all items in the (@begin, @end) range.
476 * If the sequence has a data destroy function associated with it, this
477 * function is called on the data for the removed items.
482 g_sequence_remove_range (GSequenceIter *begin,
485 g_return_if_fail (get_sequence (begin) == get_sequence (end));
487 check_iter_access (begin);
488 check_iter_access (end);
490 g_sequence_move_range (NULL, begin, end);
494 * g_sequence_move_range:
495 * @dest: a #GSequenceIter
496 * @begin: a #GSequenceIter
497 * @end: a #GSequenceIter
499 * Inserts the (@begin, @end) range at the destination pointed to by ptr.
500 * The @begin and @end iters must point into the same sequence. It is
501 * allowed for @dest to point to a different sequence than the one pointed
502 * into by @begin and @end.
504 * If @dest is NULL, the range indicated by @begin and @end is
505 * removed from the sequence. If @dest iter points to a place within
506 * the (@begin, @end) range, the range does not move.
511 g_sequence_move_range (GSequenceIter *dest,
512 GSequenceIter *begin,
516 GSequenceNode *first;
518 g_return_if_fail (begin != NULL);
519 g_return_if_fail (end != NULL);
521 check_iter_access (begin);
522 check_iter_access (end);
524 check_iter_access (dest);
526 src_seq = get_sequence (begin);
528 g_return_if_fail (src_seq == get_sequence (end));
530 /* Dest points to begin or end? */
531 if (dest == begin || dest == end)
534 /* begin comes after end? */
535 if (g_sequence_iter_compare (begin, end) >= 0)
538 /* dest points somewhere in the (begin, end) range? */
539 if (dest && get_sequence (dest) == src_seq &&
540 g_sequence_iter_compare (dest, begin) > 0 &&
541 g_sequence_iter_compare (dest, end) < 0)
546 src_seq = get_sequence (begin);
548 first = node_get_first (begin);
555 node_join (first, end);
559 first = node_get_first (dest);
563 node_join (begin, dest);
566 node_join (first, begin);
570 node_free (begin, src_seq);
577 * @cmp_func: the #GCompareDataFunc used to sort @seq. This function is
578 * passed two items of @seq and should return 0 if they are equal,
579 * a negative value fi the first comes before the second, and a
580 * positive value if the second comes before the first.
581 * @cmp_data: user data passed to @cmp_func
583 * Sorts @seq using @cmp_func.
588 g_sequence_sort (GSequence *seq,
589 GCompareDataFunc cmp_func,
592 SortInfo info = { cmp_func, cmp_data, seq->end_node };
594 check_seq_access (seq);
596 g_sequence_sort_iter (seq, iter_compare, &info);
600 * g_sequence_insert_sorted:
602 * @data: the data to insert
603 * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
604 * is called with two items of the @seq and @user_data. It should
605 * return 0 if the items are equal, a negative value if the first
606 * item comes before the second, and a positive value if the second
607 * item comes before the first.
608 * @cmp_data: user data passed to @cmp_func.
610 * Inserts @data into @sequence using @func to determine the new position.
611 * The sequence must already be sorted according to @cmp_func; otherwise the
612 * new position of @data is undefined.
614 * Return value: a #GSequenceIter pointing to the new item.
619 g_sequence_insert_sorted (GSequence *seq,
621 GCompareDataFunc cmp_func,
624 SortInfo info = { cmp_func, cmp_data, NULL };
626 g_return_val_if_fail (seq != NULL, NULL);
627 g_return_val_if_fail (cmp_func != NULL, NULL);
629 info.end_node = seq->end_node;
630 check_seq_access (seq);
632 return g_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
636 * g_sequence_sort_changed:
637 * @iter: A #GSequenceIter
638 * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
639 * is called with two items of the @seq and @user_data. It should
640 * return 0 if the items are equal, a negative value if the first
641 * item comes before the second, and a positive value if the second
642 * item comes before the first.
643 * @cmp_data: user data passed to @cmp_func.
645 * Moves the data pointed to a new position as indicated by @cmp_func. This
646 * function should be called for items in a sequence already sorted according
647 * to @cmp_func whenever some aspect of an item changes so that @cmp_func
648 * may return different values for that item.
653 g_sequence_sort_changed (GSequenceIter *iter,
654 GCompareDataFunc cmp_func,
657 SortInfo info = { cmp_func, cmp_data, NULL };
659 g_return_if_fail (!is_end (iter));
661 info.end_node = get_sequence (iter)->end_node;
662 check_iter_access (iter);
664 g_sequence_sort_changed_iter (iter, iter_compare, &info);
670 * @data: data for the new item
671 * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
672 * is called with two items of the @seq and @user_data. It should
673 * return 0 if the items are equal, a negative value if the first
674 * item comes before the second, and a positive value if the second
675 * item comes before the first.
676 * @cmp_data: user data passed to @cmp_func.
678 * Returns an iterator pointing to the position where @data would
679 * be inserted according to @cmp_func and @cmp_data.
681 * Return value: an #GSequenceIter pointing to the position where @data
682 * would have been inserted according to @cmp_func and @cmp_data.
687 g_sequence_search (GSequence *seq,
689 GCompareDataFunc cmp_func,
692 SortInfo info = { cmp_func, cmp_data, NULL };
694 g_return_val_if_fail (seq != NULL, NULL);
696 info.end_node = seq->end_node;
697 check_seq_access (seq);
699 return g_sequence_search_iter (seq, data, iter_compare, &info);
703 * g_sequence_sort_iter:
705 * @cmp_func: the #GSequenceItercompare used to compare iterators in the
706 * sequence. It is called with two iterators pointing into @seq. It should
707 * return 0 if the iterators are equal, a negative value if the first
708 * iterator comes before the second, and a positive value if the second
709 * iterator comes before the first.
710 * @cmp_data: user data passed to @cmp_func
712 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
713 * of a GCompareDataFunc as the compare function
718 g_sequence_sort_iter (GSequence *seq,
719 GSequenceIterCompareFunc cmp_func,
723 GSequenceNode *begin, *end;
725 g_return_if_fail (seq != NULL);
726 g_return_if_fail (cmp_func != NULL);
728 check_seq_access (seq);
730 begin = g_sequence_get_begin_iter (seq);
731 end = g_sequence_get_end_iter (seq);
733 tmp = g_sequence_new (NULL);
734 tmp->real_sequence = seq;
736 g_sequence_move_range (g_sequence_get_begin_iter (tmp), begin, end);
738 seq->access_prohibited = TRUE;
739 tmp->access_prohibited = TRUE;
741 while (g_sequence_get_length (tmp) > 0)
743 GSequenceNode *node = g_sequence_get_begin_iter (tmp);
745 node_insert_sorted (seq->end_node, node, seq->end_node,
749 tmp->access_prohibited = FALSE;
750 seq->access_prohibited = FALSE;
752 g_sequence_free (tmp);
756 * g_sequence_sort_changed_iter:
757 * @iter: a #GSequenceIter
758 * @iter_cmp: the #GSequenceItercompare used to compare iterators in the
759 * sequence. It is called with two iterators pointing into @seq. It should
760 * return 0 if the iterators are equal, a negative value if the first
761 * iterator comes before the second, and a positive value if the second
762 * iterator comes before the first.
763 * @cmp_data: user data passed to @cmp_func
765 * Like g_sequence_sort_changed(), but uses
766 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
767 * the compare function.
772 g_sequence_sort_changed_iter (GSequenceIter *iter,
773 GSequenceIterCompareFunc iter_cmp,
776 GSequence *seq, *tmp_seq;
777 GSequenceIter *next, *prev;
779 g_return_if_fail (iter != NULL);
780 g_return_if_fail (!is_end (iter));
781 g_return_if_fail (iter_cmp != NULL);
782 check_iter_access (iter);
784 /* If one of the neighbours is equal to iter, then
785 * don't move it. This ensures that sort_changed() is
786 * a stable operation.
789 next = node_get_next (iter);
790 prev = node_get_prev (iter);
792 if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
795 if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
798 seq = get_sequence (iter);
800 seq->access_prohibited = TRUE;
802 tmp_seq = g_sequence_new (NULL);
803 tmp_seq->real_sequence = seq;
806 node_insert_before (tmp_seq->end_node, iter);
808 node_insert_sorted (seq->end_node, iter, seq->end_node,
811 g_sequence_free (tmp_seq);
813 seq->access_prohibited = FALSE;
817 * g_sequence_insert_sorted_iter:
819 * @data: data for the new item
820 * @iter_cmp: the #GSequenceItercompare used to compare iterators in the
821 * sequence. It is called with two iterators pointing into @seq. It should
822 * return 0 if the iterators are equal, a negative value if the first
823 * iterator comes before the second, and a positive value if the second
824 * iterator comes before the first.
825 * @cmp_data: user data passed to @cmp_func
827 * Like g_sequence_insert_sorted(), but uses
828 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
829 * the compare function.
831 * Return value: a #GSequenceIter pointing to the new item
836 g_sequence_insert_sorted_iter (GSequence *seq,
838 GSequenceIterCompareFunc iter_cmp,
841 GSequenceNode *new_node;
844 g_return_val_if_fail (seq != NULL, NULL);
845 g_return_val_if_fail (iter_cmp != NULL, NULL);
847 check_seq_access (seq);
849 seq->access_prohibited = TRUE;
851 /* Create a new temporary sequence and put the new node into
852 * that. The reason for this is that the user compare function
853 * will be called with the new node, and if it dereferences,
854 * "is_end" will be called on it. But that will crash if the
855 * node is not actually in a sequence.
857 * node_insert_sorted() makes sure the node is unlinked before
860 * The reason we need the "iter" versions at all is that that
861 * is the only kind of compare functions GtkTreeView can use.
863 tmp_seq = g_sequence_new (NULL);
864 tmp_seq->real_sequence = seq;
866 new_node = g_sequence_append (tmp_seq, data);
868 node_insert_sorted (seq->end_node, new_node,
869 seq->end_node, iter_cmp, cmp_data);
871 g_sequence_free (tmp_seq);
873 seq->access_prohibited = FALSE;
879 * g_sequence_search_iter:
881 * @data: data for the new item
882 * @iter_cmp: the #GSequenceIterCompare function used to compare iterators
883 * in the sequence. It is called with two iterators pointing into @seq.
884 * It should return 0 if the iterators are equal, a negative value if the
885 * first iterator comes before the second, and a positive value if the
886 * second iterator comes before the first.
887 * @cmp_data: user data passed to @iter_cmp
889 * Like g_sequence_search(), but uses
890 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
891 * the compare function.
893 * Return value: a #GSequenceIter pointing to the position in @seq
894 * where @data would have been inserted according to @iter_cmp and @cmp_data.
899 g_sequence_search_iter (GSequence *seq,
901 GSequenceIterCompareFunc iter_cmp,
905 GSequenceNode *dummy;
908 g_return_val_if_fail (seq != NULL, NULL);
910 check_seq_access (seq);
912 seq->access_prohibited = TRUE;
914 tmp_seq = g_sequence_new (NULL);
915 tmp_seq->real_sequence = seq;
917 dummy = g_sequence_append (tmp_seq, data);
919 node = node_find_closest (seq->end_node, dummy,
920 seq->end_node, iter_cmp, cmp_data);
922 g_sequence_free (tmp_seq);
924 seq->access_prohibited = FALSE;
930 * g_sequence_iter_get_sequence:
931 * @iter: a #GSequenceIter
933 * Returns the #GSequence that @iter points into.
935 * Return value: the #GSequence that @iter points into.
940 g_sequence_iter_get_sequence (GSequenceIter *iter)
944 g_return_val_if_fail (iter != NULL, NULL);
946 seq = get_sequence (iter);
948 /* For temporary sequences, this points to the sequence that
949 * is actually being manipulated
951 return seq->real_sequence;
956 * @iter: a #GSequenceIter
958 * Returns the data that @iter points to.
960 * Return value: the data that @iter points to
965 g_sequence_get (GSequenceIter *iter)
967 g_return_val_if_fail (iter != NULL, NULL);
968 g_return_val_if_fail (!is_end (iter), NULL);
975 * @iter: a #GSequenceIter
976 * @data: new data for the item
978 * Changes the data for the item pointed to by @iter to be @data. If
979 * the sequence has a data destroy function associated with it, that
980 * function is called on the existing data that @iter pointed to.
985 g_sequence_set (GSequenceIter *iter,
990 g_return_if_fail (iter != NULL);
991 g_return_if_fail (!is_end (iter));
993 seq = get_sequence (iter);
995 /* If @data is identical to iter->data, it is destroyed
996 * here. This will work right in case of ref-counted objects. Also
997 * it is similar to what ghashtables do.
999 * For non-refcounted data it's a little less convenient, but
1000 * code relying on self-setting not destroying would be
1001 * pretty dubious anyway ...
1004 if (seq->data_destroy_notify)
1005 seq->data_destroy_notify (iter->data);
1011 * g_sequence_get_length:
1012 * @seq: a #GSequence
1014 * Returns the length of @seq
1016 * Return value: the length of @seq
1021 g_sequence_get_length (GSequence *seq)
1023 return node_get_length (seq->end_node) - 1;
1027 * g_sequence_get_end_iter:
1028 * @seq: a #GSequence
1030 * Returns the end iterator for @seg
1032 * Return value: the end iterator for @seq
1037 g_sequence_get_end_iter (GSequence *seq)
1039 g_return_val_if_fail (seq != NULL, NULL);
1041 return seq->end_node;
1045 * g_sequence_get_begin_iter:
1046 * @seq: a #GSequence
1048 * Returns the begin iterator for @seq.
1050 * Return value: the begin iterator for @seq.
1055 g_sequence_get_begin_iter (GSequence *seq)
1057 g_return_val_if_fail (seq != NULL, NULL);
1059 return node_get_first (seq->end_node);
1063 clamp_position (GSequence *seq,
1066 gint len = g_sequence_get_length (seq);
1068 if (pos > len || pos < 0)
1075 * if pos > number of items or -1, will return end pointer
1078 * g_sequence_get_iter_at_pos:
1079 * @seq: a #GSequence
1080 * @pos: a position in @seq, or -1 for the end.
1082 * Returns the iterator at position @pos. If @pos is negative or larger
1083 * than the number of items in @seq, the end iterator is returned.
1085 * Return value: The #GSequenceIter at position @pos
1090 g_sequence_get_iter_at_pos (GSequence *seq,
1093 g_return_val_if_fail (seq != NULL, NULL);
1095 pos = clamp_position (seq, pos);
1097 return node_get_by_pos (seq->end_node, pos);
1102 * @src: a #GSequenceIter pointing to the item to move
1103 * @dest: a #GSequenceIter pointing to the position to which
1104 * the item is moved.
1106 * Moves the item pointed to by @src to the position indicated by @dest.
1107 * After calling this function @dest will point to the position immediately
1108 * after @src. It is allowed for @src and @dest to point into different
1114 g_sequence_move (GSequenceIter *src,
1115 GSequenceIter *dest)
1117 g_return_if_fail (src != NULL);
1118 g_return_if_fail (dest != NULL);
1119 g_return_if_fail (!is_end (src));
1125 node_insert_before (dest, src);
1131 * g_sequence_iter_is_end:
1132 * @iter: a #GSequenceIter
1134 * Returns whether @iter is the end iterator
1136 * Return value: Whether @iter is the end iterator.
1141 g_sequence_iter_is_end (GSequenceIter *iter)
1143 g_return_val_if_fail (iter != NULL, FALSE);
1145 return is_end (iter);
1149 * g_sequence_iter_is_begin:
1150 * @iter: a #GSequenceIter
1152 * Returns whether @iter is the begin iterator
1154 * Return value: whether @iter is the begin iterator
1159 g_sequence_iter_is_begin (GSequenceIter *iter)
1161 g_return_val_if_fail (iter != NULL, FALSE);
1163 return (node_get_prev (iter) == iter);
1167 * g_sequence_iter_get_position:
1168 * @iter: a #GSequenceIter
1170 * Returns the position of @iter
1172 * Return value: the position of @iter
1177 g_sequence_iter_get_position (GSequenceIter *iter)
1179 g_return_val_if_fail (iter != NULL, -1);
1181 return node_get_pos (iter);
1185 * g_sequence_iter_next:
1186 * @iter: a #GSequenceIter
1188 * Returns an iterator pointing to the next position after @iter. If
1189 * @iter is the end iterator, the end iterator is returned.
1191 * Return value: a #GSequenceIter pointing to the next position after @iter.
1196 g_sequence_iter_next (GSequenceIter *iter)
1198 g_return_val_if_fail (iter != NULL, NULL);
1200 return node_get_next (iter);
1204 * g_sequence_iter_prev:
1205 * @iter: a #GSequenceIter
1207 * Returns an iterator pointing to the previous position before @iter. If
1208 * @iter is the begin iterator, the begin iterator is returned.
1210 * Return value: a #GSequenceIter pointing to the previous position before
1216 g_sequence_iter_prev (GSequenceIter *iter)
1218 g_return_val_if_fail (iter != NULL, NULL);
1220 return node_get_prev (iter);
1224 * g_sequence_iter_move:
1225 * @iter: a #GSequenceIter
1226 * @delta: A positive or negative number indicating how many positions away
1227 * from @iter the returned #GSequenceIter will be.
1229 * Returns the #GSequenceIter which is @delta positions away from @iter.
1230 * If @iter is closer than -@delta positions to the beginning of the sequence,
1231 * the begin iterator is returned. If @iter is closer than @delta positions
1232 * to the end of the sequence, the end iterator is returned.
1234 * Return value: a #GSequenceIter which is @delta positions away from @iter.
1239 g_sequence_iter_move (GSequenceIter *iter,
1244 g_return_val_if_fail (iter != NULL, NULL);
1246 new_pos = node_get_pos (iter) + delta;
1248 new_pos = clamp_position (get_sequence (iter), new_pos);
1250 return node_get_by_pos (iter, new_pos);
1255 * @a: a #GSequenceIter
1256 * @b: a #GSequenceIter
1258 * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
1259 * to point into difference sequences.
1264 g_sequence_swap (GSequenceIter *a,
1267 GSequenceNode *leftmost, *rightmost, *rightmost_next;
1270 g_return_if_fail (!g_sequence_iter_is_end (a));
1271 g_return_if_fail (!g_sequence_iter_is_end (b));
1276 a_pos = g_sequence_iter_get_position (a);
1277 b_pos = g_sequence_iter_get_position (b);
1290 rightmost_next = node_get_next (rightmost);
1292 /* The situation is now like this:
1294 * ..., leftmost, ......., rightmost, rightmost_next, ...
1297 g_sequence_move (rightmost, leftmost);
1298 g_sequence_move (leftmost, rightmost_next);
1302 * Implementation of a treap
1307 get_priority (GSequenceNode *node)
1309 guint key = GPOINTER_TO_UINT (node);
1311 /* This hash function is based on one found on Thomas Wang's
1314 * http://www.concentric.net/~Ttwang/tech/inthash.htm
1317 key = (key << 15) - key - 1;
1318 key = key ^ (key >> 12);
1319 key = key + (key << 2);
1320 key = key ^ (key >> 4);
1321 key = key + (key << 3) + (key << 11);
1322 key = key ^ (key >> 16);
1324 /* We rely on 0 being less than all other priorities */
1325 return key? key : 1;
1328 static GSequenceNode *
1329 find_root (GSequenceNode *node)
1331 while (node->parent)
1332 node = node->parent;
1337 static GSequenceNode *
1338 node_new (gpointer data)
1340 GSequenceNode *node = g_slice_new0 (GSequenceNode);
1346 node->parent = NULL;
1351 static GSequenceNode *
1352 node_get_first (GSequenceNode *node)
1354 node = find_root (node);
1362 static GSequenceNode *
1363 node_get_last (GSequenceNode *node)
1365 node = find_root (node);
1373 #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1374 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1376 static GSequenceNode *
1377 node_get_next (GSequenceNode *node)
1379 GSequenceNode *n = node;
1389 while (NODE_RIGHT_CHILD (n))
1401 static GSequenceNode *
1402 node_get_prev (GSequenceNode *node)
1404 GSequenceNode *n = node;
1414 while (NODE_LEFT_CHILD (n))
1426 #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1429 node_get_pos (GSequenceNode *node)
1434 n_smaller = node->left->n_nodes;
1438 if (NODE_RIGHT_CHILD (node))
1439 n_smaller += N_NODES (node->parent->left) + 1;
1441 node = node->parent;
1447 static GSequenceNode *
1448 node_get_by_pos (GSequenceNode *node,
1453 node = find_root (node);
1455 while ((i = N_NODES (node->left)) != pos)
1471 static GSequenceNode *
1472 node_find_closest (GSequenceNode *haystack,
1473 GSequenceNode *needle,
1475 GSequenceIterCompareFunc iter_cmp,
1478 GSequenceNode *best;
1481 haystack = find_root (haystack);
1487 /* iter_cmp can't be passed the end node, since the function may
1490 if (haystack == end)
1493 c = iter_cmp (haystack, needle, cmp_data);
1495 /* In the following we don't break even if c == 0. Instaed we go on
1496 * searching along the 'bigger' nodes, so that we find the last one
1497 * that is equal to the needle.
1500 haystack = haystack->left;
1502 haystack = haystack->right;
1504 while (haystack != NULL);
1506 /* If the best node is smaller or equal to the data, then move one step
1507 * to the right to make sure the best one is strictly bigger than the data
1509 if (best != end && c <= 0)
1510 best = node_get_next (best);
1516 node_get_length (GSequenceNode *node)
1518 node = find_root (node);
1520 return node->n_nodes;
1524 real_node_free (GSequenceNode *node,
1529 real_node_free (node->left, seq);
1530 real_node_free (node->right, seq);
1532 if (seq && seq->data_destroy_notify && node != seq->end_node)
1533 seq->data_destroy_notify (node->data);
1535 g_slice_free (GSequenceNode, node);
1540 node_free (GSequenceNode *node,
1543 node = find_root (node);
1545 real_node_free (node, seq);
1549 node_update_fields (GSequenceNode *node)
1553 n_nodes += N_NODES (node->left);
1554 n_nodes += N_NODES (node->right);
1556 node->n_nodes = n_nodes;
1560 node_rotate (GSequenceNode *node)
1562 GSequenceNode *tmp, *old;
1564 g_assert (node->parent);
1565 g_assert (node->parent != node);
1567 if (NODE_LEFT_CHILD (node))
1572 node->right = node->parent;
1573 node->parent = node->parent->parent;
1576 if (node->parent->left == node->right)
1577 node->parent->left = node;
1579 node->parent->right = node;
1582 g_assert (node->right);
1584 node->right->parent = node;
1585 node->right->left = tmp;
1587 if (node->right->left)
1588 node->right->left->parent = node->right;
1597 node->left = node->parent;
1598 node->parent = node->parent->parent;
1601 if (node->parent->right == node->left)
1602 node->parent->right = node;
1604 node->parent->left = node;
1607 g_assert (node->left);
1609 node->left->parent = node;
1610 node->left->right = tmp;
1612 if (node->left->right)
1613 node->left->right->parent = node->left;
1618 node_update_fields (old);
1619 node_update_fields (node);
1623 node_update_fields_deep (GSequenceNode *node)
1627 node_update_fields (node);
1629 node_update_fields_deep (node->parent);
1634 rotate_down (GSequenceNode *node,
1639 left = node->left ? get_priority (node->left) : 0;
1640 right = node->right ? get_priority (node->right) : 0;
1642 while (priority < left || priority < right)
1645 node_rotate (node->left);
1647 node_rotate (node->right);
1649 left = node->left ? get_priority (node->left) : 0;
1650 right = node->right ? get_priority (node->right) : 0;
1655 node_cut (GSequenceNode *node)
1657 while (node->parent)
1661 node->left->parent = NULL;
1664 node_update_fields (node);
1666 rotate_down (node, get_priority (node));
1670 node_join (GSequenceNode *left,
1671 GSequenceNode *right)
1673 GSequenceNode *fake = node_new (NULL);
1675 fake->left = find_root (left);
1676 fake->right = find_root (right);
1677 fake->left->parent = fake;
1678 fake->right->parent = fake;
1680 node_update_fields (fake);
1684 node_free (fake, NULL);
1688 node_insert_before (GSequenceNode *node,
1691 new->left = node->left;
1693 new->left->parent = new;
1698 node_update_fields_deep (new);
1700 while (new->parent && get_priority (new) > get_priority (new->parent))
1703 rotate_down (new, get_priority (new));
1707 node_unlink (GSequenceNode *node)
1709 rotate_down (node, 0);
1711 if (NODE_RIGHT_CHILD (node))
1712 node->parent->right = NULL;
1713 else if (NODE_LEFT_CHILD (node))
1714 node->parent->left = NULL;
1717 node_update_fields_deep (node->parent);
1719 node->parent = NULL;
1723 node_insert_sorted (GSequenceNode *node,
1726 GSequenceIterCompareFunc iter_cmp,
1729 GSequenceNode *closest;
1731 closest = node_find_closest (node, new, end, iter_cmp, cmp_data);
1735 node_insert_before (closest, new);
1739 #define __G_SEQUENCE_C__
1740 #include "galiasdef.c"