X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=glib%2Fgsequence.c;h=76e24e73bd02b65901b4f4017d7e10c4a62e5127;hb=2a53b4d0e2c98a14aedf31e38f0ad1fb2e8fe26f;hp=e2e16720e4b03ea8d0a4c195df05cdae794b46ab;hpb=840d9bab2624105e8f18c08b41e8f4b86fc1345e;p=platform%2Fupstream%2Fglib.git diff --git a/glib/gsequence.c b/glib/gsequence.c index e2e1672..76e24e7 100644 --- a/glib/gsequence.c +++ b/glib/gsequence.c @@ -13,18 +13,85 @@ * 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 + * @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][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. + * + * Some methods on #GSequence operate on ranges of items. For example + * g_sequence_foreach_range() will call a user-specified function on + * each element with the given range. The range is delimited by the + * gaps represented by the passed-in iterators, so if you pass in the + * begin and end iterators, the range in question is the entire + * sequence. + * + * 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. + * + * Iterators are stable across most operations on a #GSequence. For + * example an iterator pointing to some element of a sequence will + * continue to point to that element even after the sequence is sorted. + * Even moving an element to another sequence using for example + * 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 + * + * 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; +/** + * GSequence: + * + * The #GSequence struct is an opaque data type representing a + * [sequence][glib-Sequences] data type. + */ struct _GSequence { GSequenceNode * end_node; @@ -32,19 +99,19 @@ struct _GSequence gboolean access_prohibited; /* The 'real_sequence' is used when temporary sequences are created - * to hold nodes that being rearranged. The 'real_sequence' of such + * to hold nodes that are being rearranged. The 'real_sequence' of such * a temporary sequence points to the sequence that is actually being * manipulated. The only reason we need this is so that when the * 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 @@ -63,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, @@ -72,17 +144,18 @@ static gint node_get_length (GSequenceNode *node); static void node_free (GSequenceNode *node, GSequence *seq); static void node_cut (GSequenceNode *split); -static void node_insert_after (GSequenceNode *node, - GSequenceNode *second); static void node_insert_before (GSequenceNode *node, GSequenceNode *new); static void node_unlink (GSequenceNode *node); +static void node_join (GSequenceNode *left, + GSequenceNode *right); static void node_insert_sorted (GSequenceNode *node, GSequenceNode *new, GSequenceNode *end, GSequenceIterCompareFunc cmp_func, gpointer cmp_data); + /* * Various helper functions */ @@ -111,8 +184,19 @@ check_iter_access (GSequenceIter *iter) static gboolean is_end (GSequenceIter *iter) { - GSequence *seq = get_sequence (iter); - + GSequence *seq; + + if (iter->right) + return FALSE; + + if (!iter->parent) + return TRUE; + + if (iter->parent->right != iter) + return FALSE; + + seq = get_sequence (iter); + return seq->end_node == iter; } @@ -133,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; } @@ -151,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 * @@ -166,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); } @@ -204,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, @@ -218,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; } @@ -245,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); } @@ -270,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); } @@ -307,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) @@ -344,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; } @@ -373,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; } @@ -402,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); } @@ -458,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); } @@ -483,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, @@ -502,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 && @@ -530,46 +614,63 @@ 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_insert_after (node_get_last (first), end); - + node_join (first, end); + if (dest) - node_insert_before (dest, begin); + { + first = node_get_first (dest); + + node_cut (dest); + + node_join (begin, dest); + + if (dest != first) + node_join (first, begin); + } else - node_free (begin, src_seq); + { + node_free (begin, src_seq); + } } /** * 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 fi 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, gpointer cmp_data) { - SortInfo info = { cmp_func, cmp_data, seq->end_node }; - + SortInfo info; + + 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); } @@ -577,67 +678,73 @@ 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, GCompareDataFunc cmp_func, gpointer cmp_data) { - SortInfo info = { cmp_func, cmp_data, NULL }; - + SortInfo info; + 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, gpointer cmp_data) { - SortInfo info = { cmp_func, cmp_data, NULL }; - + 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); } @@ -645,52 +752,113 @@ 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, GCompareDataFunc cmp_func, gpointer cmp_data) { - SortInfo info = { cmp_func, cmp_data, NULL }; - + 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, @@ -698,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, @@ -757,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; } @@ -794,61 +963,67 @@ 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. * * node_insert_sorted() makes sure the node is unlinked before - * is is inserted. + * it is inserted. * * The reason we need the "iter" versions at all is that that * is the only kind of compare functions GtkTreeView can use. */ 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; } @@ -856,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, @@ -881,55 +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; - /* Create a new temporary sequence and put the dummy node into - * that. The reason for this is that the user compare function - * 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. - * - * node_insert_sorted() makes sure the node is unlinked before - * is is inserted. - * - * The reason we need the "iter" versions at all is that that - * is the only kind of compare functions GtkTreeView can use. - */ 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); @@ -943,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; } @@ -963,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. @@ -989,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) { @@ -1014,38 +1245,37 @@ 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); - - g_assert (is_end (seq->end_node)); - + 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) { g_return_val_if_fail (seq != NULL, NULL); + return node_get_first (seq->end_node); } @@ -1054,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; } @@ -1067,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); } @@ -1091,12 +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. - * + * after @src. It is allowed for @src and @dest to point into different + * sequences. + * * Since: 2.14 **/ void @@ -1106,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); } @@ -1119,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); } @@ -1213,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); } @@ -1243,27 +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 - * + * + * 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; @@ -1274,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, ... @@ -1287,113 +1525,38 @@ g_sequence_swap (GSequenceIter *a, } /* - * Implementation of the splay tree. + * Implementation of a treap + * + * */ -static void -node_update_fields (GSequenceNode *node) +static guint +get_priority (GSequenceNode *node) { - g_assert (node != NULL); - - node->n_nodes = 1; - - if (node->left) - node->n_nodes += node->left->n_nodes; - - if (node->right) - node->n_nodes += node->right->n_nodes; -} + guint key = GPOINTER_TO_UINT (node); -#define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n)) -#define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n)) + /* This hash function is based on one found on Thomas Wang's + * web page at + * + * http://www.concentric.net/~Ttwang/tech/inthash.htm + * + */ + key = (key << 15) - key - 1; + key = key ^ (key >> 12); + key = key + (key << 2); + key = key ^ (key >> 4); + key = key + (key << 3) + (key << 11); + key = key ^ (key >> 16); -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) - { - if (node->parent->left == node->right) - node->parent->left = 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 - { - /* rotate left */ - tmp = node->left; - - 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); + /* We rely on 0 being less than all other priorities */ + return key? key : 1; } static GSequenceNode * -splay (GSequenceNode *node) +find_root (GSequenceNode *node) { while (node->parent) - { - if (!node->parent->parent) - { - /* zig */ - node_rotate (node); - } - else if ((NODE_LEFT_CHILD (node) && NODE_LEFT_CHILD (node->parent)) || - (NODE_RIGHT_CHILD (node) && NODE_RIGHT_CHILD (node->parent))) - { - /* zig-zig */ - node_rotate (node->parent); - node_rotate (node); - } - else - { - /* zig-zag */ - node_rotate (node); - node_rotate (node); - } - } - + node = node->parent; + return node; } @@ -1401,72 +1564,121 @@ static GSequenceNode * node_new (gpointer data) { GSequenceNode *node = g_slice_new0 (GSequenceNode); - - node->parent = NULL; - node->parent = NULL; + + node->n_nodes = 1; + node->data = data; node->left = NULL; node->right = NULL; - - node->data = data; - node->n_nodes = 1; - + node->parent = NULL; + return node; } static GSequenceNode * -find_min (GSequenceNode *node) +node_get_first (GSequenceNode *node) { - splay (node); - + node = find_root (node); + while (node->left) node = node->left; - + return node; } static GSequenceNode * -find_max (GSequenceNode *node) +node_get_last (GSequenceNode *node) { - splay (node); - + node = find_root (node); + while (node->right) node = node->right; - + return node; } +#define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n)) +#define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n)) + static GSequenceNode * -node_get_first (GSequenceNode *node) +node_get_next (GSequenceNode *node) { - return splay (find_min (node)); + GSequenceNode *n = node; + + if (n->right) + { + n = n->right; + while (n->left) + n = n->left; + } + else + { + while (NODE_RIGHT_CHILD (n)) + n = n->parent; + + if (n->parent) + n = n->parent; + else + n = node; + } + + return n; } static GSequenceNode * -node_get_last (GSequenceNode *node) +node_get_prev (GSequenceNode *node) { - return splay (find_max (node)); + GSequenceNode *n = node; + + if (n->left) + { + n = n->left; + while (n->right) + n = n->right; + } + else + { + while (NODE_LEFT_CHILD (n)) + n = n->parent; + + if (n->parent) + n = n->parent; + else + n = node; + } + + return n; } +#define N_NODES(n) ((n)? (n)->n_nodes : 0) + static gint -get_n_nodes (GSequenceNode *node) +node_get_pos (GSequenceNode *node) { - if (node) - return node->n_nodes; - else - return 0; + 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; + + node = node->parent; + } + + return n_smaller; } static GSequenceNode * node_get_by_pos (GSequenceNode *node, - gint pos) -{ - gint i; - - g_assert (node != NULL); - - splay (node); - - while ((i = get_n_nodes (node->left)) != pos) + gint pos) +{ + int i; + + node = find_root (node); + + while ((i = N_NODES (node->left)) != pos) { if (i < pos) { @@ -1476,55 +1688,46 @@ node_get_by_pos (GSequenceNode *node, else { node = node->left; - g_assert (node->parent != NULL); } } - - return splay (node); -} -static GSequenceNode * -node_get_prev (GSequenceNode *node) -{ - splay (node); - - if (node->left) - { - node = node->left; - while (node->right) - node = node->right; - } - - return splay (node); + return node; } static GSequenceNode * -node_get_next (GSequenceNode *node) +node_find (GSequenceNode *haystack, + GSequenceNode *needle, + GSequenceNode *end, + GSequenceIterCompareFunc iter_cmp, + gpointer cmp_data) { - splay (node); - - if (node->right) + gint c; + + haystack = find_root (haystack); + + do { - node = node->right; - while (node->left) - node = node->left; - } - - return splay (node); -} + /* 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); -static gint -node_get_pos (GSequenceNode *node) -{ - splay (node); - - return get_n_nodes (node->left); + if (c == 0) + break; + + if (c > 0) + haystack = haystack->left; + else + haystack = haystack->right; + } + while (haystack != NULL); + + return haystack; } -/* Return closest node _strictly_ bigger than @needle. This node - * always exists because the tree has an explicit end node). - * This end node of @haystack must be passed in @end. - */ static GSequenceNode * node_find_closest (GSequenceNode *haystack, GSequenceNode *needle, @@ -1534,15 +1737,13 @@ node_find_closest (GSequenceNode *haystack, { GSequenceNode *best; gint c; - - g_assert (haystack); - - haystack = splay (haystack); - + + haystack = find_root (haystack); + do { best = haystack; - + /* iter_cmp can't be passed the end node, since the function may * be user-supplied */ @@ -1550,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. */ @@ -1561,150 +1762,221 @@ 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; } +static gint +node_get_length (GSequenceNode *node) +{ + node = find_root (node); + + return node->n_nodes; +} + +static void +real_node_free (GSequenceNode *node, + 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); + + g_slice_free (GSequenceNode, node); + } +} + static void node_free (GSequenceNode *node, - GSequence *seq) + GSequence *seq) +{ + node = find_root (node); + + real_node_free (node, seq); +} + +static void +node_update_fields (GSequenceNode *node) { - GPtrArray *stack = g_ptr_array_new (); - - splay (node); + int n_nodes = 1; + + n_nodes += N_NODES (node->left); + n_nodes += N_NODES (node->right); + + node->n_nodes = n_nodes; +} + +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) + { + if (node->parent->left == node->right) + node->parent->left = node; + else + node->parent->right = node; + } + + g_assert (node->right); + + node->right->parent = node; + node->right->left = tmp; - g_ptr_array_add (stack, node); - - while (stack->len > 0) + if (node->right->left) + node->right->left->parent = node->right; + + old = node->right; + } + else { - node = g_ptr_array_remove_index (stack, stack->len - 1); - - if (node) + /* rotate left */ + tmp = node->left; + + node->left = node->parent; + node->parent = node->parent->parent; + if (node->parent) { - g_ptr_array_add (stack, node->right); - g_ptr_array_add (stack, node->left); - - if (seq && seq->data_destroy_notify && node != seq->end_node) - seq->data_destroy_notify (node->data); - - g_slice_free (GSequenceNode, node); + 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); +} + +static void +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 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); + else + node_rotate (node->right); + + left = node->left ? get_priority (node->left) : 0; + right = node->right ? get_priority (node->right) : 0; } - - g_ptr_array_free (stack, TRUE); } -/* Splits into two trees. @node will be part of the right tree - */ static void node_cut (GSequenceNode *node) { - splay (node); - - g_assert (node->parent == NULL); - + 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 *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) { - g_assert (node != NULL); - g_assert (new != NULL); - - splay (node); - - new = splay (find_min (new)); - g_assert (new->left == NULL); - - if (node->left) - node->left->parent = new; - new->left = node->left; + if (new->left) + new->left->parent = new; + new->parent = node; - node->left = new; - - node_update_fields (new); - node_update_fields (node); -} -static void -node_insert_after (GSequenceNode *node, - GSequenceNode *new) -{ - g_assert (node != NULL); - g_assert (new != NULL); - - splay (node); - - new = splay (find_max (new)); - g_assert (new->right == NULL); - g_assert (node->parent == NULL); - - if (node->right) - node->right->parent = new; - - new->right = node->right; - new->parent = node; - - node->right = new; - - node_update_fields (new); - node_update_fields (node); -} + node_update_fields_deep (new); -static gint -node_get_length (GSequenceNode *node) -{ - g_assert (node != NULL); - - splay (node); - return node->n_nodes; + while (new->parent && get_priority (new) > get_priority (new->parent)) + node_rotate (new); + + rotate_down (new, get_priority (new)); } static void node_unlink (GSequenceNode *node) { - GSequenceNode *right, *left; - - splay (node); - - left = node->left; - right = node->right; - - node->parent = node->left = node->right = NULL; - node_update_fields (node); - - if (right) - { - right->parent = NULL; - - right = node_get_first (right); - g_assert (right->left == NULL); - - right->left = left; - if (left) - { - left->parent = right; - node_update_fields (right); - } - } - else if (left) - { - left->parent = NULL; - } + 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; } static void @@ -1715,58 +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); -} -static gint -node_calc_height (GSequenceNode *node) -{ - gint left_height; - gint right_height; - - if (node) - { - left_height = 0; - right_height = 0; - - if (node->left) - left_height = node_calc_height (node->left); - - if (node->right) - right_height = node_calc_height (node->right); - - return MAX (left_height, right_height) + 1; - } - - return 0; -} + closest = node_find_closest (node, new, end, iter_cmp, cmp_data); -/* Self-test function */ -static void -check_node (GSequenceNode *node) -{ - if (node) - { - g_assert (node->parent != node); - g_assert (node->n_nodes == - 1 + get_n_nodes (node->left) + get_n_nodes (node->right)); - check_node (node->left); - check_node (node->right); - } -} + node_unlink (new); -void -g_sequence_self_test_internal_to_glib_dont_use (GSequence *seq) -{ - GSequenceNode *node = splay (seq->end_node); - - check_node (node); + node_insert_before (closest, new); } - -#define __G_SEQUENCE_C__ -#include "galiasdef.c"