X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=glib%2Fgsequence.c;h=76e24e73bd02b65901b4f4017d7e10c4a62e5127;hb=d0083f7e2dd621c6b78496bdb6ecf5d580c5e110;hp=ee00708ba49ca8657519fb4ebeb62ddc2a8b76e4;hpb=3a161ee8f34f8c5861075a4b0d52730f7ba5bec0;p=platform%2Fupstream%2Fglib.git diff --git a/glib/gsequence.c b/glib/gsequence.c index ee00708..76e24e7 100644 --- a/glib/gsequence.c +++ b/glib/gsequence.c @@ -13,35 +13,33 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the - * Free Software Foundation, Inc., 59 Temple Place - Suite 330, - * Boston, MA 02111-1307, USA. + * License along with this library; if not, see . */ #include "config.h" -#include "glib.h" -#include "galias.h" +#include "gsequence.h" +#include "gmem.h" +#include "gtestutils.h" +#include "gslice.h" /** - * SECTION: sequence + * SECTION:sequence * @title: Sequences * @short_description: scalable lists * * The #GSequence data structure has the API of a list, but is * implemented internally with a balanced binary tree. This means that - * it is possible to maintain a sorted list of n elements in time O(n - * log n). The data contained in each element can be either integer - * values, by using of the Type Conversion Macros, - * or simply pointers to any type of data. - * - * A #GSequence is accessed through iterators, - * represented by a #GSequenceIter. An iterator represents a position - * between two elements of the sequence. For example, the - * begin iterator represents the gap immediately - * before the first element of the sequence, and the - * end iterator represents the gap immediately + * it is possible to maintain a sorted list of n elements in time O(n log n). + * The data contained in each element can be either integer values, by using + * of the [Type Conversion Macros][glib-Type-Conversion-Macros], or simply + * pointers to any type of data. + * + * A #GSequence is accessed through "iterators", represented by a + * #GSequenceIter. An iterator represents a position between two + * elements of the sequence. For example, the "begin" iterator + * represents the gap immediately before the first element of the + * sequence, and the "end" iterator represents the gap immediately * after the last element. In an empty sequence, the begin and end * iterators are the same. * @@ -54,7 +52,7 @@ * * The function g_sequence_get() is used with an iterator to access the * element immediately following the gap that the iterator represents. - * The iterator is said to point to that element. + * The iterator is said to "point" to that element. * * Iterators are stable across most operations on a #GSequence. For * example an iterator pointing to some element of a sequence will @@ -63,28 +61,28 @@ * g_sequence_move_range() will not invalidate the iterators pointing * to it. The only operation that will invalidate an iterator is when * the element it points to is removed from any sequence. - **/ + */ /** * GSequenceIter: * * The #GSequenceIter struct is an opaque data type representing an * iterator pointing into a #GSequence. - **/ + */ /** * GSequenceIterCompareFunc: * @a: a #GSequenceIter * @b: a #GSequenceIter * @data: user data - * @Returns: zero if the iterators are equal, a negative value if @a - * comes before @b, and a positive value if @b comes before - * @a. * * A #GSequenceIterCompareFunc is a function used to compare iterators. * It must return zero if the iterators compare equal, a negative value * if @a comes before @b, and a positive value if @b comes before @a. - **/ + * + * Returns: zero if the iterators are equal, a negative value if @a + * comes before @b, and a positive value if @b comes before @a. + */ typedef struct _GSequenceNode GSequenceNode; @@ -92,8 +90,8 @@ typedef struct _GSequenceNode GSequenceNode; * GSequence: * * The #GSequence struct is an opaque data type representing a - * Sequence data type. - **/ + * [sequence][glib-Sequences] data type. + */ struct _GSequence { GSequenceNode * end_node; @@ -107,13 +105,13 @@ struct _GSequence * sort/sort_changed/search_iter() functions call out to the application * g_sequence_iter_get_sequence() will return the correct sequence. */ - GSequence * real_sequence; + GSequence * real_sequence; }; struct _GSequenceNode { gint n_nodes; - GSequenceNode * parent; + GSequenceNode * parent; GSequenceNode * left; GSequenceNode * right; gpointer data; /* For the end node, this field points @@ -132,6 +130,11 @@ static GSequenceNode *node_get_next (GSequenceNode *node); static gint node_get_pos (GSequenceNode *node); static GSequenceNode *node_get_by_pos (GSequenceNode *node, gint pos); +static GSequenceNode *node_find (GSequenceNode *haystack, + GSequenceNode *needle, + GSequenceNode *end, + GSequenceIterCompareFunc cmp, + gpointer user_data); static GSequenceNode *node_find_closest (GSequenceNode *haystack, GSequenceNode *needle, GSequenceNode *end, @@ -145,7 +148,7 @@ static void node_insert_before (GSequenceNode *node, GSequenceNode *new); static void node_unlink (GSequenceNode *node); static void node_join (GSequenceNode *left, - GSequenceNode *right); + GSequenceNode *right); static void node_insert_sorted (GSequenceNode *node, GSequenceNode *new, GSequenceNode *end, @@ -214,15 +217,15 @@ iter_compare (GSequenceIter *node1, { const SortInfo *info = data; gint retval; - + if (node1 == info->end_node) return 1; - + if (node2 == info->end_node) return -1; - + retval = info->cmp_func (node1->data, node2->data, info->cmp_data); - + return retval; } @@ -232,14 +235,14 @@ iter_compare (GSequenceIter *node1, /** * g_sequence_new: - * @data_destroy: a #GDestroyNotify function, or %NULL - * + * @data_destroy: (allow-none): a #GDestroyNotify function, or %NULL + * * Creates a new GSequence. The @data_destroy function, if non-%NULL will * be called on all items when the sequence is destroyed and on items that * are removed from the sequence. - * - * Return value: a new #GSequence - * + * + * Returns: a new #GSequence + * * Since: 2.14 **/ GSequence * @@ -247,35 +250,35 @@ g_sequence_new (GDestroyNotify data_destroy) { GSequence *seq = g_new (GSequence, 1); seq->data_destroy_notify = data_destroy; - + seq->end_node = node_new (seq); - + seq->access_prohibited = FALSE; seq->real_sequence = seq; - + return seq; } /** * g_sequence_free: * @seq: a #GSequence - * - * Frees the memory allocated for @seq. If @seq has a data destroy - * function associated with it, that function is called on all items in - * @seq. - * + * + * Frees the memory allocated for @seq. If @seq has a data destroy + * function associated with it, that function is called on all items + * in @seq. + * * Since: 2.14 - **/ + */ void g_sequence_free (GSequence *seq) { g_return_if_fail (seq != NULL); - + check_seq_access (seq); - + node_free (seq->end_node, seq); - + g_free (seq); } @@ -285,12 +288,12 @@ g_sequence_free (GSequence *seq) * @end: a #GSequenceIter * @func: a #GFunc * @user_data: user data passed to @func - * + * * Calls @func for each item in the range (@begin, @end) passing * @user_data to the function. - * + * * Since: 2.14 - **/ + */ void g_sequence_foreach_range (GSequenceIter *begin, GSequenceIter *end, @@ -299,25 +302,25 @@ g_sequence_foreach_range (GSequenceIter *begin, { GSequence *seq; GSequenceIter *iter; - + g_return_if_fail (func != NULL); g_return_if_fail (begin != NULL); g_return_if_fail (end != NULL); - + seq = get_sequence (begin); - + seq->access_prohibited = TRUE; - + iter = begin; while (iter != end) { GSequenceIter *next = node_get_next (iter); - + func (iter->data, user_data); - + iter = next; } - + seq->access_prohibited = FALSE; } @@ -326,24 +329,24 @@ g_sequence_foreach_range (GSequenceIter *begin, * @seq: a #GSequence * @func: the function to call for each item in @seq * @user_data: user data passed to @func - * + * * Calls @func for each item in the sequence passing @user_data * to the function. - * + * * Since: 2.14 - **/ + */ void g_sequence_foreach (GSequence *seq, GFunc func, gpointer user_data) { GSequenceIter *begin, *end; - + check_seq_access (seq); - + begin = g_sequence_get_begin_iter (seq); end = g_sequence_get_end_iter (seq); - + g_sequence_foreach_range (begin, end, func, user_data); } @@ -351,36 +354,36 @@ g_sequence_foreach (GSequence *seq, * g_sequence_range_get_midpoint: * @begin: a #GSequenceIter * @end: a #GSequenceIter - * + * * Finds an iterator somewhere in the range (@begin, @end). This * iterator will be close to the middle of the range, but is not - * guaranteed to be exactly in the middle. - * - * The @begin and @end iterators must both point to the same sequence and - * @begin must come before or be equal to @end in the sequence. - * - * Return value: A #GSequenceIter pointing somewhere in the - * (@begin, @end) range. - * + * guaranteed to be exactly in the middle. + * + * The @begin and @end iterators must both point to the same sequence + * and @begin must come before or be equal to @end in the sequence. + * + * Returns: a #GSequenceIter pointing somewhere in the + * (@begin, @end) range + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_range_get_midpoint (GSequenceIter *begin, GSequenceIter *end) { int begin_pos, end_pos, mid_pos; - + g_return_val_if_fail (begin != NULL, NULL); g_return_val_if_fail (end != NULL, NULL); g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL); - + begin_pos = node_get_pos (begin); end_pos = node_get_pos (end); - + g_return_val_if_fail (end_pos >= begin_pos, NULL); - + mid_pos = begin_pos + (end_pos - begin_pos) / 2; - + return node_get_by_pos (begin, mid_pos); } @@ -388,33 +391,33 @@ g_sequence_range_get_midpoint (GSequenceIter *begin, * g_sequence_iter_compare: * @a: a #GSequenceIter * @b: a #GSequenceIter - * + * * Returns a negative number if @a comes before @b, 0 if they are equal, * and a positive number if @a comes after @b. * * The @a and @b iterators must point into the same sequence. - * - * Return value: A negative number if @a comes before @b, 0 if they are - * equal, and a positive number if @a comes after @b. - * + * + * Returns: a negative number if @a comes before @b, 0 if they are + * equal, and a positive number if @a comes after @b + * * Since: 2.14 - **/ + */ gint g_sequence_iter_compare (GSequenceIter *a, GSequenceIter *b) { gint a_pos, b_pos; - + g_return_val_if_fail (a != NULL, 0); g_return_val_if_fail (b != NULL, 0); g_return_val_if_fail (get_sequence (a) == get_sequence (b), 0); - + check_iter_access (a); check_iter_access (b); - + a_pos = node_get_pos (a); b_pos = node_get_pos (b); - + if (a_pos == b_pos) return 0; else if (a_pos > b_pos) @@ -425,28 +428,28 @@ g_sequence_iter_compare (GSequenceIter *a, /** * g_sequence_append: - * @seq: a #GSequencePointer + * @seq: a #GSequence * @data: the data for the new item - * + * * Adds a new item to the end of @seq. - * - * Return value: an iterator pointing to the new item - * + * + * Returns: an iterator pointing to the new item + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_append (GSequence *seq, gpointer data) { GSequenceNode *node; - + g_return_val_if_fail (seq != NULL, NULL); - + check_seq_access (seq); - + node = node_new (data); node_insert_before (seq->end_node, node); - + return node; } @@ -454,28 +457,28 @@ g_sequence_append (GSequence *seq, * g_sequence_prepend: * @seq: a #GSequence * @data: the data for the new item - * + * * Adds a new item to the front of @seq - * - * Return value: an iterator pointing to the new item - * + * + * Returns: an iterator pointing to the new item + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_prepend (GSequence *seq, gpointer data) { GSequenceNode *node, *first; - + g_return_val_if_fail (seq != NULL, NULL); - + check_seq_access (seq); - + node = node_new (data); first = node_get_first (seq->end_node); - + node_insert_before (first, node); - + return node; } @@ -483,54 +486,54 @@ g_sequence_prepend (GSequence *seq, * g_sequence_insert_before: * @iter: a #GSequenceIter * @data: the data for the new item - * + * * Inserts a new item just before the item pointed to by @iter. - * - * Return value: an iterator pointing to the new item - * + * + * Returns: an iterator pointing to the new item + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_insert_before (GSequenceIter *iter, gpointer data) { GSequenceNode *node; - + g_return_val_if_fail (iter != NULL, NULL); - + check_iter_access (iter); - + node = node_new (data); - + node_insert_before (iter, node); - + return node; } /** * g_sequence_remove: * @iter: a #GSequenceIter - * + * * Removes the item pointed to by @iter. It is an error to pass the * end iterator to this function. * - * If the sequnce has a data destroy function associated with it, this + * If the sequence has a data destroy function associated with it, this * function is called on the data for the removed item. - * + * * Since: 2.14 - **/ + */ void g_sequence_remove (GSequenceIter *iter) { GSequence *seq; - + g_return_if_fail (iter != NULL); g_return_if_fail (!is_end (iter)); - + check_iter_access (iter); - - seq = get_sequence (iter); - + + seq = get_sequence (iter); + node_unlink (iter); node_free (iter, seq); } @@ -539,23 +542,23 @@ g_sequence_remove (GSequenceIter *iter) * g_sequence_remove_range: * @begin: a #GSequenceIter * @end: a #GSequenceIter - * + * * Removes all items in the (@begin, @end) range. * * If the sequence has a data destroy function associated with it, this * function is called on the data for the removed items. - * + * * Since: 2.14 - **/ + */ void g_sequence_remove_range (GSequenceIter *begin, GSequenceIter *end) { g_return_if_fail (get_sequence (begin) == get_sequence (end)); - + check_iter_access (begin); check_iter_access (end); - + g_sequence_move_range (NULL, begin, end); } @@ -564,18 +567,18 @@ g_sequence_remove_range (GSequenceIter *begin, * @dest: a #GSequenceIter * @begin: a #GSequenceIter * @end: a #GSequenceIter - * + * * Inserts the (@begin, @end) range at the destination pointed to by ptr. * The @begin and @end iters must point into the same sequence. It is * allowed for @dest to point to a different sequence than the one pointed * into by @begin and @end. - * + * * If @dest is NULL, the range indicated by @begin and @end is * removed from the sequence. If @dest iter points to a place within * the (@begin, @end) range, the range does not move. - * + * * Since: 2.14 - **/ + */ void g_sequence_move_range (GSequenceIter *dest, GSequenceIter *begin, @@ -583,27 +586,27 @@ g_sequence_move_range (GSequenceIter *dest, { GSequence *src_seq; GSequenceNode *first; - + g_return_if_fail (begin != NULL); g_return_if_fail (end != NULL); - + check_iter_access (begin); check_iter_access (end); if (dest) check_iter_access (dest); - + src_seq = get_sequence (begin); - + g_return_if_fail (src_seq == get_sequence (end)); - + /* Dest points to begin or end? */ if (dest == begin || dest == end) return; - + /* begin comes after end? */ if (g_sequence_iter_compare (begin, end) >= 0) return; - + /* dest points somewhere in the (begin, end) range? */ if (dest && get_sequence (dest) == src_seq && g_sequence_iter_compare (dest, begin) > 0 && @@ -611,28 +614,28 @@ g_sequence_move_range (GSequenceIter *dest, { return; } - + src_seq = get_sequence (begin); - + first = node_get_first (begin); - + node_cut (begin); - + node_cut (end); - + if (first != begin) node_join (first, end); - + if (dest) { first = node_get_first (dest); - + node_cut (dest); - + node_join (begin, dest); - + if (dest != first) - node_join (first, begin); + node_join (first, begin); } else { @@ -643,16 +646,18 @@ g_sequence_move_range (GSequenceIter *dest, /** * g_sequence_sort: * @seq: a #GSequence - * @cmp_func: the #GCompareDataFunc used to sort @seq. This function is - * passed two items of @seq and should return 0 if they are equal, - * a negative value if the first comes before the second, and a - * positive value if the second comes before the first. + * @cmp_func: the function used to sort the sequence * @cmp_data: user data passed to @cmp_func - * + * * Sorts @seq using @cmp_func. - * + * + * @cmp_func is passed two items of @seq and should + * return 0 if they are equal, a negative value if the + * first comes before the second, and a positive value + * if the second comes before the first. + * * Since: 2.14 - **/ + */ void g_sequence_sort (GSequence *seq, GCompareDataFunc cmp_func, @@ -663,9 +668,9 @@ g_sequence_sort (GSequence *seq, info.cmp_func = cmp_func; info.cmp_data = cmp_data; info.end_node = seq->end_node; - + check_seq_access (seq); - + g_sequence_sort_iter (seq, iter_compare, &info); } @@ -673,21 +678,22 @@ g_sequence_sort (GSequence *seq, * g_sequence_insert_sorted: * @seq: a #GSequence * @data: the data to insert - * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It - * is called with two items of the @seq and @user_data. It should - * return 0 if the items are equal, a negative value if the first - * item comes before the second, and a positive value if the second - * item comes before the first. + * @cmp_func: the function used to compare items in the sequence * @cmp_data: user data passed to @cmp_func. * - * Inserts @data into @sequence using @func to determine the new position. - * The sequence must already be sorted according to @cmp_func; otherwise the - * new position of @data is undefined. + * Inserts @data into @sequence using @func to determine the new + * position. The sequence must already be sorted according to @cmp_func; + * otherwise the new position of @data is undefined. + * + * @cmp_func is called with two items of the @seq and @user_data. + * It should return 0 if the items are equal, a negative value + * if the first item comes before the second, and a positive value + * if the second item comes before the first. + * + * Returns: a #GSequenceIter pointing to the new item. * - * Return value: a #GSequenceIter pointing to the new item. - * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_insert_sorted (GSequence *seq, gpointer data, @@ -698,32 +704,33 @@ g_sequence_insert_sorted (GSequence *seq, g_return_val_if_fail (seq != NULL, NULL); g_return_val_if_fail (cmp_func != NULL, NULL); - + info.cmp_func = cmp_func; info.cmp_data = cmp_data; info.end_node = seq->end_node; check_seq_access (seq); - + return g_sequence_insert_sorted_iter (seq, data, iter_compare, &info); } /** * g_sequence_sort_changed: * @iter: A #GSequenceIter - * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It - * is called with two items of the @seq and @user_data. It should - * return 0 if the items are equal, a negative value if the first - * item comes before the second, and a positive value if the second - * item comes before the first. + * @cmp_func: the function used to compare items in the sequence * @cmp_data: user data passed to @cmp_func. * * Moves the data pointed to a new position as indicated by @cmp_func. This * function should be called for items in a sequence already sorted according * to @cmp_func whenever some aspect of an item changes so that @cmp_func * may return different values for that item. - * + * + * @cmp_func is called with two items of the @seq and @user_data. + * It should return 0 if the items are equal, a negative value if + * the first item comes before the second, and a positive value if + * the second item comes before the first. + * * Since: 2.14 - **/ + */ void g_sequence_sort_changed (GSequenceIter *iter, GCompareDataFunc cmp_func, @@ -732,12 +739,12 @@ g_sequence_sort_changed (GSequenceIter *iter, SortInfo info; g_return_if_fail (!is_end (iter)); - + info.cmp_func = cmp_func; info.cmp_data = cmp_data; info.end_node = get_sequence (iter)->end_node; check_iter_access (iter); - + g_sequence_sort_changed_iter (iter, iter_compare, &info); } @@ -745,21 +752,31 @@ g_sequence_sort_changed (GSequenceIter *iter, * g_sequence_search: * @seq: a #GSequence * @data: data for the new item - * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It - * is called with two items of the @seq and @user_data. It should - * return 0 if the items are equal, a negative value if the first - * item comes before the second, and a positive value if the second - * item comes before the first. - * @cmp_data: user data passed to @cmp_func. - * + * @cmp_func: the function used to compare items in the sequence + * @cmp_data: user data passed to @cmp_func + * * Returns an iterator pointing to the position where @data would * be inserted according to @cmp_func and @cmp_data. - * - * Return value: an #GSequenceIter pointing to the position where @data - * would have been inserted according to @cmp_func and @cmp_data. - * + * + * @cmp_func is called with two items of the @seq and @user_data. + * It should return 0 if the items are equal, a negative value if + * the first item comes before the second, and a positive value if + * the second item comes before the first. + * + * If you are simply searching for an existing element of the sequence, + * consider using g_sequence_lookup(). + * + * This function will fail if the data contained in the sequence is + * unsorted. Use g_sequence_insert_sorted() or + * g_sequence_insert_sorted_iter() to add data to your sequence or, if + * you want to add a large amount of data, call g_sequence_sort() after + * doing unsorted insertions. + * + * Returns: an #GSequenceIter pointing to the position where @data + * would have been inserted according to @cmp_func and @cmp_data + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_search (GSequence *seq, gpointer data, @@ -769,30 +786,79 @@ g_sequence_search (GSequence *seq, SortInfo info; g_return_val_if_fail (seq != NULL, NULL); - + info.cmp_func = cmp_func; info.cmp_data = cmp_data; info.end_node = seq->end_node; check_seq_access (seq); - + return g_sequence_search_iter (seq, data, iter_compare, &info); } /** + * g_sequence_lookup: + * @seq: a #GSequence + * @data: data to lookup + * @cmp_func: the function used to compare items in the sequence + * @cmp_data: user data passed to @cmp_func + * + * Returns an iterator pointing to the position of the first item found + * equal to @data according to @cmp_func and @cmp_data. If more than one + * item is equal, it is not guaranteed that it is the first which is + * returned. In that case, you can use g_sequence_iter_next() and + * g_sequence_iter_prev() to get others. + * + * @cmp_func is called with two items of the @seq and @user_data. + * It should return 0 if the items are equal, a negative value if + * the first item comes before the second, and a positive value if + * the second item comes before the first. + * + * This function will fail if the data contained in the sequence is + * unsorted. Use g_sequence_insert_sorted() or + * g_sequence_insert_sorted_iter() to add data to your sequence or, if + * you want to add a large amount of data, call g_sequence_sort() after + * doing unsorted insertions. + * + * Returns: an #GSequenceIter pointing to the position of the + * first item found equal to @data according to @cmp_func and + * @cmp_data, or %NULL if no such item exists + * + * Since: 2.28 + */ +GSequenceIter * +g_sequence_lookup (GSequence *seq, + gpointer data, + GCompareDataFunc cmp_func, + gpointer cmp_data) +{ + SortInfo info; + + g_return_val_if_fail (seq != NULL, NULL); + + info.cmp_func = cmp_func; + info.cmp_data = cmp_data; + info.end_node = seq->end_node; + check_seq_access (seq); + + return g_sequence_lookup_iter (seq, data, iter_compare, &info); +} + +/** * g_sequence_sort_iter: * @seq: a #GSequence - * @cmp_func: the #GSequenceItercompare used to compare iterators in the - * sequence. It is called with two iterators pointing into @seq. It should - * return 0 if the iterators are equal, a negative value if the first - * iterator comes before the second, and a positive value if the second - * iterator comes before the first. + * @cmp_func: the function used to compare iterators in the sequence * @cmp_data: user data passed to @cmp_func * * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead * of a GCompareDataFunc as the compare function - * + * + * @cmp_func is called with two iterators pointing into @seq. It should + * return 0 if the iterators are equal, a negative value if the first + * iterator comes before the second, and a positive value if the second + * iterator comes before the first. + * * Since: 2.14 - **/ + */ void g_sequence_sort_iter (GSequence *seq, GSequenceIterCompareFunc cmp_func, @@ -800,53 +866,54 @@ g_sequence_sort_iter (GSequence *seq, { GSequence *tmp; GSequenceNode *begin, *end; - + g_return_if_fail (seq != NULL); g_return_if_fail (cmp_func != NULL); - + check_seq_access (seq); - + begin = g_sequence_get_begin_iter (seq); end = g_sequence_get_end_iter (seq); - + tmp = g_sequence_new (NULL); tmp->real_sequence = seq; - + g_sequence_move_range (g_sequence_get_begin_iter (tmp), begin, end); - + seq->access_prohibited = TRUE; tmp->access_prohibited = TRUE; - + while (g_sequence_get_length (tmp) > 0) { GSequenceNode *node = g_sequence_get_begin_iter (tmp); - + node_insert_sorted (seq->end_node, node, seq->end_node, - cmp_func, cmp_data); + cmp_func, cmp_data); } - + tmp->access_prohibited = FALSE; seq->access_prohibited = FALSE; - + g_sequence_free (tmp); } /** * g_sequence_sort_changed_iter: * @iter: a #GSequenceIter - * @iter_cmp: the #GSequenceItercompare used to compare iterators in the - * sequence. It is called with two iterators pointing into @seq. It should - * return 0 if the iterators are equal, a negative value if the first - * iterator comes before the second, and a positive value if the second - * iterator comes before the first. + * @iter_cmp: the function used to compare iterators in the sequence * @cmp_data: user data passed to @cmp_func * * Like g_sequence_sort_changed(), but uses * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as * the compare function. - * + * + * @iter_cmp is called with two iterators pointing into @seq. It should + * return 0 if the iterators are equal, a negative value if the first + * iterator comes before the second, and a positive value if the second + * iterator comes before the first. + * * Since: 2.14 - **/ + */ void g_sequence_sort_changed_iter (GSequenceIter *iter, GSequenceIterCompareFunc iter_cmp, @@ -859,36 +926,36 @@ g_sequence_sort_changed_iter (GSequenceIter *iter, g_return_if_fail (!is_end (iter)); g_return_if_fail (iter_cmp != NULL); check_iter_access (iter); - + /* If one of the neighbours is equal to iter, then * don't move it. This ensures that sort_changed() is * a stable operation. */ - + next = node_get_next (iter); prev = node_get_prev (iter); - + if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0) return; - + if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0) return; - + seq = get_sequence (iter); - + seq->access_prohibited = TRUE; tmp_seq = g_sequence_new (NULL); tmp_seq->real_sequence = seq; - + node_unlink (iter); node_insert_before (tmp_seq->end_node, iter); - + node_insert_sorted (seq->end_node, iter, seq->end_node, iter_cmp, cmp_data); g_sequence_free (tmp_seq); - + seq->access_prohibited = FALSE; } @@ -896,40 +963,46 @@ g_sequence_sort_changed_iter (GSequenceIter *iter, * g_sequence_insert_sorted_iter: * @seq: a #GSequence * @data: data for the new item - * @iter_cmp: the #GSequenceItercompare used to compare iterators in the - * sequence. It is called with two iterators pointing into @seq. It should - * return 0 if the iterators are equal, a negative value if the first - * iterator comes before the second, and a positive value if the second - * iterator comes before the first. + * @iter_cmp: the function used to compare iterators in the sequence * @cmp_data: user data passed to @cmp_func - * + * * Like g_sequence_insert_sorted(), but uses * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as * the compare function. - * - * Return value: a #GSequenceIter pointing to the new item - * + * + * @iter_cmp is called with two iterators pointing into @seq. + * It should return 0 if the iterators are equal, a negative + * value if the first iterator comes before the second, and a + * positive value if the second iterator comes before the first. + * + * It is called with two iterators pointing into @seq. It should + * return 0 if the iterators are equal, a negative value if the + * first iterator comes before the second, and a positive value + * if the second iterator comes before the first. + * + * Returns: a #GSequenceIter pointing to the new item + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_insert_sorted_iter (GSequence *seq, - gpointer data, - GSequenceIterCompareFunc iter_cmp, - gpointer cmp_data) + gpointer data, + GSequenceIterCompareFunc iter_cmp, + gpointer cmp_data) { GSequenceNode *new_node; GSequence *tmp_seq; g_return_val_if_fail (seq != NULL, NULL); g_return_val_if_fail (iter_cmp != NULL, NULL); - + check_seq_access (seq); seq->access_prohibited = TRUE; - + /* Create a new temporary sequence and put the new node into * that. The reason for this is that the user compare function - * will be called with the new node, and if it dereferences, + * will be called with the new node, and if it dereferences, * "is_end" will be called on it. But that will crash if the * node is not actually in a sequence. * @@ -941,16 +1014,16 @@ g_sequence_insert_sorted_iter (GSequence *seq, */ tmp_seq = g_sequence_new (NULL); tmp_seq->real_sequence = seq; - + new_node = g_sequence_append (tmp_seq, data); - + node_insert_sorted (seq->end_node, new_node, seq->end_node, iter_cmp, cmp_data); - + g_sequence_free (tmp_seq); seq->access_prohibited = FALSE; - + return new_node; } @@ -958,22 +1031,32 @@ g_sequence_insert_sorted_iter (GSequence *seq, * g_sequence_search_iter: * @seq: a #GSequence * @data: data for the new item - * @iter_cmp: the #GSequenceIterCompare function used to compare iterators - * in the sequence. It is called with two iterators pointing into @seq. - * It should return 0 if the iterators are equal, a negative value if the - * first iterator comes before the second, and a positive value if the - * second iterator comes before the first. + * @iter_cmp: the function used to compare iterators in the sequence * @cmp_data: user data passed to @iter_cmp * - * Like g_sequence_search(), but uses - * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as - * the compare function. - * - * Return value: a #GSequenceIter pointing to the position in @seq - * where @data would have been inserted according to @iter_cmp and @cmp_data. - * + * Like g_sequence_search(), but uses a #GSequenceIterCompareFunc + * instead of a #GCompareDataFunc as the compare function. + * + * @iter_cmp is called with two iterators pointing into @seq. + * It should return 0 if the iterators are equal, a negative value + * if the first iterator comes before the second, and a positive + * value if the second iterator comes before the first. + * + * If you are simply searching for an existing element of the sequence, + * consider using g_sequence_lookup_iter(). + * + * This function will fail if the data contained in the sequence is + * unsorted. Use g_sequence_insert_sorted() or + * g_sequence_insert_sorted_iter() to add data to your sequence or, if + * you want to add a large amount of data, call g_sequence_sort() after + * doing unsorted insertions. + * + * Returns: a #GSequenceIter pointing to the position in @seq + * where @data would have been inserted according to @iter_cmp + * and @cmp_data + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_search_iter (GSequence *seq, gpointer data, @@ -983,43 +1066,101 @@ g_sequence_search_iter (GSequence *seq, GSequenceNode *node; GSequenceNode *dummy; GSequence *tmp_seq; - + g_return_val_if_fail (seq != NULL, NULL); - + check_seq_access (seq); - + seq->access_prohibited = TRUE; tmp_seq = g_sequence_new (NULL); tmp_seq->real_sequence = seq; - + dummy = g_sequence_append (tmp_seq, data); - + node = node_find_closest (seq->end_node, dummy, seq->end_node, iter_cmp, cmp_data); g_sequence_free (tmp_seq); - + + seq->access_prohibited = FALSE; + + return node; +} + +/** + * g_sequence_lookup_iter: + * @seq: a #GSequence + * @data: data to lookup + * @iter_cmp: the function used to compare iterators in the sequence + * @cmp_data: user data passed to @iter_cmp + * + * Like g_sequence_lookup(), but uses a #GSequenceIterCompareFunc + * instead of a #GCompareDataFunc as the compare function. + * + * @iter_cmp is called with two iterators pointing into @seq. + * It should return 0 if the iterators are equal, a negative value + * if the first iterator comes before the second, and a positive + * value if the second iterator comes before the first. + * + * This function will fail if the data contained in the sequence is + * unsorted. Use g_sequence_insert_sorted() or + * g_sequence_insert_sorted_iter() to add data to your sequence or, if + * you want to add a large amount of data, call g_sequence_sort() after + * doing unsorted insertions. + * + * Returns: an #GSequenceIter pointing to the position of + * the first item found equal to @data according to @cmp_func + * and @cmp_data, or %NULL if no such item exists + * + * Since: 2.28 + */ +GSequenceIter * +g_sequence_lookup_iter (GSequence *seq, + gpointer data, + GSequenceIterCompareFunc iter_cmp, + gpointer cmp_data) +{ + GSequenceNode *node; + GSequenceNode *dummy; + GSequence *tmp_seq; + + g_return_val_if_fail (seq != NULL, NULL); + + check_seq_access (seq); + + seq->access_prohibited = TRUE; + + tmp_seq = g_sequence_new (NULL); + tmp_seq->real_sequence = seq; + + dummy = g_sequence_append (tmp_seq, data); + + node = node_find (seq->end_node, dummy, + seq->end_node, iter_cmp, cmp_data); + + g_sequence_free (tmp_seq); + seq->access_prohibited = FALSE; - + return node; } /** * g_sequence_iter_get_sequence: * @iter: a #GSequenceIter - * + * * Returns the #GSequence that @iter points into. - * - * Return value: the #GSequence that @iter points into. - * + * + * Returns: the #GSequence that @iter points into + * * Since: 2.14 - **/ + */ GSequence * g_sequence_iter_get_sequence (GSequenceIter *iter) { GSequence *seq; - + g_return_val_if_fail (iter != NULL, NULL); seq = get_sequence (iter); @@ -1033,19 +1174,19 @@ g_sequence_iter_get_sequence (GSequenceIter *iter) /** * g_sequence_get: * @iter: a #GSequenceIter - * + * * Returns the data that @iter points to. - * - * Return value: the data that @iter points to - * + * + * Returns: the data that @iter points to + * * Since: 2.14 - **/ + */ gpointer g_sequence_get (GSequenceIter *iter) { g_return_val_if_fail (iter != NULL, NULL); g_return_val_if_fail (!is_end (iter), NULL); - + return iter->data; } @@ -1053,24 +1194,24 @@ g_sequence_get (GSequenceIter *iter) * g_sequence_set: * @iter: a #GSequenceIter * @data: new data for the item - * + * * Changes the data for the item pointed to by @iter to be @data. If * the sequence has a data destroy function associated with it, that * function is called on the existing data that @iter pointed to. - * + * * Since: 2.14 - **/ + */ void g_sequence_set (GSequenceIter *iter, gpointer data) { GSequence *seq; - + g_return_if_fail (iter != NULL); g_return_if_fail (!is_end (iter)); - + seq = get_sequence (iter); - + /* If @data is identical to iter->data, it is destroyed * here. This will work right in case of ref-counted objects. Also * it is similar to what ghashtables do. @@ -1079,23 +1220,23 @@ g_sequence_set (GSequenceIter *iter, * code relying on self-setting not destroying would be * pretty dubious anyway ... */ - + if (seq->data_destroy_notify) seq->data_destroy_notify (iter->data); - + iter->data = data; } /** * g_sequence_get_length: * @seq: a #GSequence - * + * * Returns the length of @seq - * - * Return value: the length of @seq - * + * + * Returns: the length of @seq + * * Since: 2.14 - **/ + */ gint g_sequence_get_length (GSequence *seq) { @@ -1104,32 +1245,32 @@ g_sequence_get_length (GSequence *seq) /** * g_sequence_get_end_iter: - * @seq: a #GSequence - * + * @seq: a #GSequence + * * Returns the end iterator for @seg - * - * Return value: the end iterator for @seq - * + * + * Returns: the end iterator for @seq + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_get_end_iter (GSequence *seq) { g_return_val_if_fail (seq != NULL, NULL); - + return seq->end_node; } /** * g_sequence_get_begin_iter: * @seq: a #GSequence - * + * * Returns the begin iterator for @seq. - * - * Return value: the begin iterator for @seq. - * + * + * Returns: the begin iterator for @seq. + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_get_begin_iter (GSequence *seq) { @@ -1143,10 +1284,10 @@ clamp_position (GSequence *seq, int pos) { gint len = g_sequence_get_length (seq); - + if (pos > len || pos < 0) pos = len; - + return pos; } @@ -1156,23 +1297,23 @@ clamp_position (GSequence *seq, /** * g_sequence_get_iter_at_pos: * @seq: a #GSequence - * @pos: a position in @seq, or -1 for the end. - * + * @pos: a position in @seq, or -1 for the end + * * Returns the iterator at position @pos. If @pos is negative or larger * than the number of items in @seq, the end iterator is returned. - * - * Return value: The #GSequenceIter at position @pos - * + * + * Returns: The #GSequenceIter at position @pos + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_get_iter_at_pos (GSequence *seq, gint pos) { g_return_val_if_fail (seq != NULL, NULL); - + pos = clamp_position (seq, pos); - + return node_get_by_pos (seq->end_node, pos); } @@ -1180,13 +1321,13 @@ g_sequence_get_iter_at_pos (GSequence *seq, * g_sequence_move: * @src: a #GSequenceIter pointing to the item to move * @dest: a #GSequenceIter pointing to the position to which - * the item is moved. + * the item is moved * * Moves the item pointed to by @src to the position indicated by @dest. * After calling this function @dest will point to the position immediately * after @src. It is allowed for @src and @dest to point into different * sequences. - * + * * Since: 2.14 **/ void @@ -1196,10 +1337,10 @@ g_sequence_move (GSequenceIter *src, g_return_if_fail (src != NULL); g_return_if_fail (dest != NULL); g_return_if_fail (!is_end (src)); - + if (src == dest) return; - + node_unlink (src); node_insert_before (dest, src); } @@ -1209,93 +1350,93 @@ g_sequence_move (GSequenceIter *src, /** * g_sequence_iter_is_end: * @iter: a #GSequenceIter - * + * * Returns whether @iter is the end iterator - * - * Return value: Whether @iter is the end iterator. - * + * + * Returns: Whether @iter is the end iterator + * * Since: 2.14 - **/ + */ gboolean g_sequence_iter_is_end (GSequenceIter *iter) { g_return_val_if_fail (iter != NULL, FALSE); - + return is_end (iter); } /** * g_sequence_iter_is_begin: * @iter: a #GSequenceIter - * + * * Returns whether @iter is the begin iterator - * - * Return value: whether @iter is the begin iterator - * + * + * Returns: whether @iter is the begin iterator + * * Since: 2.14 - **/ + */ gboolean g_sequence_iter_is_begin (GSequenceIter *iter) { g_return_val_if_fail (iter != NULL, FALSE); - + return (node_get_prev (iter) == iter); } /** * g_sequence_iter_get_position: * @iter: a #GSequenceIter - * + * * Returns the position of @iter - * - * Return value: the position of @iter - * + * + * Returns: the position of @iter + * * Since: 2.14 - **/ + */ gint g_sequence_iter_get_position (GSequenceIter *iter) { g_return_val_if_fail (iter != NULL, -1); - + return node_get_pos (iter); } /** * g_sequence_iter_next: * @iter: a #GSequenceIter - * - * Returns an iterator pointing to the next position after @iter. If - * @iter is the end iterator, the end iterator is returned. - * - * Return value: a #GSequenceIter pointing to the next position after @iter. - * + * + * Returns an iterator pointing to the next position after @iter. + * If @iter is the end iterator, the end iterator is returned. + * + * Returns: a #GSequenceIter pointing to the next position after @iter + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_iter_next (GSequenceIter *iter) { g_return_val_if_fail (iter != NULL, NULL); - + return node_get_next (iter); } /** * g_sequence_iter_prev: * @iter: a #GSequenceIter - * - * Returns an iterator pointing to the previous position before @iter. If - * @iter is the begin iterator, the begin iterator is returned. - * - * Return value: a #GSequenceIter pointing to the previous position before - * @iter. - * + * + * Returns an iterator pointing to the previous position before @iter. + * If @iter is the begin iterator, the begin iterator is returned. + * + * Returns: a #GSequenceIter pointing to the previous position + * before @iter + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_iter_prev (GSequenceIter *iter) { g_return_val_if_fail (iter != NULL, NULL); - + return node_get_prev (iter); } @@ -1303,29 +1444,35 @@ g_sequence_iter_prev (GSequenceIter *iter) * g_sequence_iter_move: * @iter: a #GSequenceIter * @delta: A positive or negative number indicating how many positions away - * from @iter the returned #GSequenceIter will be. + * from @iter the returned #GSequenceIter will be * * Returns the #GSequenceIter which is @delta positions away from @iter. * If @iter is closer than -@delta positions to the beginning of the sequence, * the begin iterator is returned. If @iter is closer than @delta positions * to the end of the sequence, the end iterator is returned. * - * Return value: a #GSequenceIter which is @delta positions away from @iter. - * + * Returns: a #GSequenceIter which is @delta positions away from @iter + * * Since: 2.14 - **/ + */ GSequenceIter * g_sequence_iter_move (GSequenceIter *iter, gint delta) { gint new_pos; - + gint len; + g_return_val_if_fail (iter != NULL, NULL); - + + len = g_sequence_get_length (get_sequence (iter)); + new_pos = node_get_pos (iter) + delta; - - new_pos = clamp_position (get_sequence (iter), new_pos); - + + if (new_pos < 0) + new_pos = 0; + else if (new_pos > len) + new_pos = len; + return node_get_by_pos (iter, new_pos); } @@ -1333,28 +1480,28 @@ g_sequence_iter_move (GSequenceIter *iter, * g_sequence_swap: * @a: a #GSequenceIter * @b: a #GSequenceIter - * + * * Swaps the items pointed to by @a and @b. It is allowed for @a and @b * to point into difference sequences. - * + * * Since: 2.14 - **/ + */ void g_sequence_swap (GSequenceIter *a, GSequenceIter *b) { GSequenceNode *leftmost, *rightmost, *rightmost_next; int a_pos, b_pos; - + g_return_if_fail (!g_sequence_iter_is_end (a)); g_return_if_fail (!g_sequence_iter_is_end (b)); - + if (a == b) return; - + a_pos = g_sequence_iter_get_position (a); b_pos = g_sequence_iter_get_position (b); - + if (a_pos > b_pos) { leftmost = b; @@ -1365,9 +1512,9 @@ g_sequence_swap (GSequenceIter *a, leftmost = a; rightmost = b; } - + rightmost_next = node_get_next (rightmost); - + /* The situation is now like this: * * ..., leftmost, ......., rightmost, rightmost_next, ... @@ -1409,7 +1556,7 @@ find_root (GSequenceNode *node) { while (node->parent) node = node->parent; - + return node; } @@ -1417,13 +1564,13 @@ static GSequenceNode * node_new (gpointer data) { GSequenceNode *node = g_slice_new0 (GSequenceNode); - + node->n_nodes = 1; node->data = data; node->left = NULL; node->right = NULL; node->parent = NULL; - + return node; } @@ -1431,10 +1578,10 @@ static GSequenceNode * node_get_first (GSequenceNode *node) { node = find_root (node); - + while (node->left) node = node->left; - + return node; } @@ -1442,10 +1589,10 @@ static GSequenceNode * node_get_last (GSequenceNode *node) { node = find_root (node); - + while (node->right) node = node->right; - + return node; } @@ -1461,19 +1608,19 @@ node_get_next (GSequenceNode *node) { n = n->right; while (n->left) - n = n->left; + n = n->left; } else { while (NODE_RIGHT_CHILD (n)) - n = n->parent; - + n = n->parent; + if (n->parent) - n = n->parent; + n = n->parent; else - n = node; + n = node; } - + return n; } @@ -1481,24 +1628,24 @@ static GSequenceNode * node_get_prev (GSequenceNode *node) { GSequenceNode *n = node; - + if (n->left) { n = n->left; while (n->right) - n = n->right; + n = n->right; } else { while (NODE_LEFT_CHILD (n)) - n = n->parent; - + n = n->parent; + if (n->parent) - n = n->parent; + n = n->parent; else - n = node; + n = node; } - + return n; } @@ -1508,46 +1655,80 @@ static gint node_get_pos (GSequenceNode *node) { int n_smaller = 0; - + if (node->left) n_smaller = node->left->n_nodes; - + while (node) { if (NODE_RIGHT_CHILD (node)) - n_smaller += N_NODES (node->parent->left) + 1; - + n_smaller += N_NODES (node->parent->left) + 1; + node = node->parent; } - + return n_smaller; } static GSequenceNode * node_get_by_pos (GSequenceNode *node, - gint pos) + gint pos) { int i; - + node = find_root (node); - + while ((i = N_NODES (node->left)) != pos) { if (i < pos) { - node = node->right; - pos -= (i + 1); + node = node->right; + pos -= (i + 1); } else { - node = node->left; - } + node = node->left; + } } - + return node; } static GSequenceNode * +node_find (GSequenceNode *haystack, + GSequenceNode *needle, + GSequenceNode *end, + GSequenceIterCompareFunc iter_cmp, + gpointer cmp_data) +{ + gint c; + + haystack = find_root (haystack); + + do + { + /* iter_cmp can't be passed the end node, since the function may + * be user-supplied + */ + if (haystack == end) + c = 1; + else + c = iter_cmp (haystack, needle, cmp_data); + + if (c == 0) + break; + + if (c > 0) + haystack = haystack->left; + else + haystack = haystack->right; + } + while (haystack != NULL); + + return haystack; +} + +static GSequenceNode * node_find_closest (GSequenceNode *haystack, GSequenceNode *needle, GSequenceNode *end, @@ -1556,13 +1737,13 @@ node_find_closest (GSequenceNode *haystack, { GSequenceNode *best; gint c; - + haystack = find_root (haystack); - + do { best = haystack; - + /* iter_cmp can't be passed the end node, since the function may * be user-supplied */ @@ -1570,8 +1751,8 @@ node_find_closest (GSequenceNode *haystack, c = 1; else c = iter_cmp (haystack, needle, cmp_data); - - /* In the following we don't break even if c == 0. Instaed we go on + + /* In the following we don't break even if c == 0. Instead we go on * searching along the 'bigger' nodes, so that we find the last one * that is equal to the needle. */ @@ -1581,13 +1762,13 @@ node_find_closest (GSequenceNode *haystack, haystack = haystack->right; } while (haystack != NULL); - + /* If the best node is smaller or equal to the data, then move one step * to the right to make sure the best one is strictly bigger than the data */ if (best != end && c <= 0) best = node_get_next (best); - + return best; } @@ -1595,32 +1776,32 @@ static gint node_get_length (GSequenceNode *node) { node = find_root (node); - + return node->n_nodes; } static void real_node_free (GSequenceNode *node, - GSequence *seq) + GSequence *seq) { if (node) { real_node_free (node->left, seq); real_node_free (node->right, seq); - + if (seq && seq->data_destroy_notify && node != seq->end_node) - seq->data_destroy_notify (node->data); - + seq->data_destroy_notify (node->data); + g_slice_free (GSequenceNode, node); } } static void node_free (GSequenceNode *node, - GSequence *seq) + GSequence *seq) { node = find_root (node); - + real_node_free (node, seq); } @@ -1628,10 +1809,10 @@ static void node_update_fields (GSequenceNode *node) { int n_nodes = 1; - + n_nodes += N_NODES (node->left); n_nodes += N_NODES (node->right); - + node->n_nodes = n_nodes; } @@ -1639,15 +1820,15 @@ static void node_rotate (GSequenceNode *node) { GSequenceNode *tmp, *old; - + g_assert (node->parent); g_assert (node->parent != node); - + if (NODE_LEFT_CHILD (node)) { /* rotate right */ tmp = node->right; - + node->right = node->parent; node->parent = node->parent->parent; if (node->parent) @@ -1657,15 +1838,15 @@ node_rotate (GSequenceNode *node) else node->parent->right = node; } - + g_assert (node->right); - + node->right->parent = node; node->right->left = tmp; - + if (node->right->left) node->right->left->parent = node->right; - + old = node->right; } else @@ -1676,24 +1857,24 @@ node_rotate (GSequenceNode *node) node->left = node->parent; node->parent = node->parent->parent; if (node->parent) - { + { if (node->parent->right == node->left) node->parent->right = node; else node->parent->left = node; } - + g_assert (node->left); - + node->left->parent = node; node->left->right = tmp; - + if (node->left->right) node->left->right->parent = node->left; - + old = node->left; } - + node_update_fields (old); node_update_fields (node); } @@ -1704,27 +1885,27 @@ node_update_fields_deep (GSequenceNode *node) if (node) { node_update_fields (node); - + node_update_fields_deep (node->parent); } } static void rotate_down (GSequenceNode *node, - guint priority) + guint priority) { guint left, right; - + left = node->left ? get_priority (node->left) : 0; right = node->right ? get_priority (node->right) : 0; - + while (priority < left || priority < right) { if (left > right) - node_rotate (node->left); + node_rotate (node->left); else - node_rotate (node->right); - + node_rotate (node->right); + left = node->left ? get_priority (node->left) : 0; right = node->right ? get_priority (node->right) : 0; } @@ -1735,50 +1916,50 @@ node_cut (GSequenceNode *node) { while (node->parent) node_rotate (node); - + if (node->left) node->left->parent = NULL; - + node->left = NULL; node_update_fields (node); - + rotate_down (node, get_priority (node)); } static void node_join (GSequenceNode *left, - GSequenceNode *right) + GSequenceNode *right) { GSequenceNode *fake = node_new (NULL); - + fake->left = find_root (left); fake->right = find_root (right); fake->left->parent = fake; fake->right->parent = fake; - + node_update_fields (fake); - + node_unlink (fake); - + node_free (fake, NULL); } static void node_insert_before (GSequenceNode *node, - GSequenceNode *new) + GSequenceNode *new) { new->left = node->left; if (new->left) new->left->parent = new; - + new->parent = node; node->left = new; - + node_update_fields_deep (new); - + while (new->parent && get_priority (new) > get_priority (new->parent)) node_rotate (new); - + rotate_down (new, get_priority (new)); } @@ -1786,15 +1967,15 @@ static void node_unlink (GSequenceNode *node) { rotate_down (node, 0); - + if (NODE_RIGHT_CHILD (node)) node->parent->right = NULL; else if (NODE_LEFT_CHILD (node)) node->parent->left = NULL; - + if (node->parent) node_update_fields_deep (node->parent); - + node->parent = NULL; } @@ -1806,14 +1987,10 @@ node_insert_sorted (GSequenceNode *node, gpointer cmp_data) { GSequenceNode *closest; - + closest = node_find_closest (node, new, end, iter_cmp, cmp_data); - + node_unlink (new); - + node_insert_before (closest, new); } - - -#define __G_SEQUENCE_C__ -#include "galiasdef.c"