From 3e2f1e38255d8157a2ecf244d6a5f6515b8c2d6b Mon Sep 17 00:00:00 2001 From: Matthias Clasen Date: Fri, 3 Sep 2010 20:27:45 -0400 Subject: [PATCH] Remove redundant header inclusions and some whitespace cleanup. --- glib/gsequence.c | 638 ++++++++++++++++++++++++++++--------------------------- 1 file changed, 320 insertions(+), 318 deletions(-) diff --git a/glib/gsequence.c b/glib/gsequence.c index c95c66e..8b28ce7 100644 --- a/glib/gsequence.c +++ b/glib/gsequence.c @@ -20,8 +20,10 @@ #include "config.h" -#include "glib.h" +#include "gsequence.h" +#include "gmem.h" +#include "gtestutils.h" /** * SECTION: sequence * @title: Sequences @@ -106,13 +108,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 @@ -144,7 +146,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, @@ -213,15 +215,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,13 +234,13 @@ iter_compare (GSequenceIter *node1, /** * g_sequence_new: * @data_destroy: 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 - * + * * Since: 2.14 **/ GSequence * @@ -246,35 +248,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 + * + * 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); } @@ -284,10 +286,10 @@ 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 @@ -298,25 +300,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; } @@ -325,10 +327,10 @@ 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 @@ -337,12 +339,12 @@ g_sequence_foreach (GSequence *seq, 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); } @@ -350,17 +352,17 @@ 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. - * + * * Since: 2.14 **/ GSequenceIter * @@ -368,18 +370,18 @@ 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); } @@ -387,15 +389,15 @@ 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. - * + * * Since: 2.14 **/ gint @@ -403,17 +405,17 @@ 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) @@ -426,11 +428,11 @@ g_sequence_iter_compare (GSequenceIter *a, * g_sequence_append: * @seq: a #GSequencePointer * @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 - * + * * Since: 2.14 **/ GSequenceIter * @@ -438,14 +440,14 @@ 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; } @@ -453,11 +455,11 @@ 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 - * + * * Since: 2.14 **/ GSequenceIter * @@ -465,16 +467,16 @@ 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; } @@ -482,11 +484,11 @@ 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 - * + * * Since: 2.14 **/ GSequenceIter * @@ -494,42 +496,42 @@ 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 * 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); } @@ -538,12 +540,12 @@ 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 @@ -551,10 +553,10 @@ 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); } @@ -563,16 +565,16 @@ 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 @@ -582,27 +584,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 && @@ -610,28 +612,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 { @@ -647,9 +649,9 @@ g_sequence_move_range (GSequenceIter *dest, * a negative value if the first comes before the second, and a * positive value if the second comes before the first. * @cmp_data: user data passed to @cmp_func - * + * * Sorts @seq using @cmp_func. - * + * * Since: 2.14 **/ void @@ -662,9 +664,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); } @@ -684,7 +686,7 @@ g_sequence_sort (GSequence *seq, * new position of @data is undefined. * * Return value: a #GSequenceIter pointing to the new item. - * + * * Since: 2.14 **/ GSequenceIter * @@ -697,12 +699,12 @@ 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); } @@ -720,7 +722,7 @@ g_sequence_insert_sorted (GSequence *seq, * 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. - * + * * Since: 2.14 **/ void @@ -731,12 +733,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); } @@ -750,13 +752,13 @@ g_sequence_sort_changed (GSequenceIter *iter, * 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. - * + * * 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. - * + * * Since: 2.14 **/ GSequenceIter * @@ -768,12 +770,12 @@ 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); } @@ -789,7 +791,7 @@ g_sequence_search (GSequence *seq, * * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead * of a GCompareDataFunc as the compare function - * + * * Since: 2.14 **/ void @@ -799,34 +801,34 @@ 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); } @@ -843,7 +845,7 @@ g_sequence_sort_iter (GSequence *seq, * Like g_sequence_sort_changed(), but uses * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as * the compare function. - * + * * Since: 2.14 **/ void @@ -858,36 +860,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; } @@ -901,34 +903,34 @@ g_sequence_sort_changed_iter (GSequenceIter *iter, * iterator comes before the second, and a positive value if the second * iterator comes before the first. * @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 - * + * * 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. * @@ -940,16 +942,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; } @@ -967,10 +969,10 @@ g_sequence_insert_sorted_iter (GSequence *seq, * 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. - * + * * Since: 2.14 **/ GSequenceIter * @@ -982,43 +984,43 @@ 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_iter_get_sequence: * @iter: a #GSequenceIter - * + * * Returns the #GSequence that @iter points into. - * + * * Return value: 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); @@ -1032,11 +1034,11 @@ 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 - * + * * Since: 2.14 **/ gpointer @@ -1044,7 +1046,7 @@ 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; } @@ -1052,11 +1054,11 @@ 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 @@ -1064,12 +1066,12 @@ 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. @@ -1078,21 +1080,21 @@ 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 - * + * * Since: 2.14 **/ gint @@ -1103,30 +1105,30 @@ 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 - * + * * 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. - * + * * Since: 2.14 **/ GSequenceIter * @@ -1142,10 +1144,10 @@ clamp_position (GSequence *seq, int pos) { gint len = g_sequence_get_length (seq); - + if (pos > len || pos < 0) pos = len; - + return pos; } @@ -1156,12 +1158,12 @@ clamp_position (GSequence *seq, * g_sequence_get_iter_at_pos: * @seq: a #GSequence * @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 - * + * * Since: 2.14 **/ GSequenceIter * @@ -1169,9 +1171,9 @@ 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); } @@ -1185,7 +1187,7 @@ g_sequence_get_iter_at_pos (GSequence *seq, * 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 @@ -1195,10 +1197,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); } @@ -1208,93 +1210,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. - * + * * 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 - * + * * 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 - * + * * 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. - * + * * 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. - * + * * Since: 2.14 **/ GSequenceIter * g_sequence_iter_prev (GSequenceIter *iter) { g_return_val_if_fail (iter != NULL, NULL); - + return node_get_prev (iter); } @@ -1310,7 +1312,7 @@ g_sequence_iter_prev (GSequenceIter *iter) * to the end of the sequence, the end iterator is returned. * * Return value: a #GSequenceIter which is @delta positions away from @iter. - * + * * Since: 2.14 **/ GSequenceIter * @@ -1318,13 +1320,13 @@ g_sequence_iter_move (GSequenceIter *iter, gint delta) { gint new_pos; - + g_return_val_if_fail (iter != NULL, NULL); - + new_pos = node_get_pos (iter) + delta; - + new_pos = clamp_position (get_sequence (iter), new_pos); - + return node_get_by_pos (iter, new_pos); } @@ -1332,10 +1334,10 @@ 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 @@ -1344,16 +1346,16 @@ g_sequence_swap (GSequenceIter *a, { 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; @@ -1364,9 +1366,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, ... @@ -1408,7 +1410,7 @@ find_root (GSequenceNode *node) { while (node->parent) node = node->parent; - + return node; } @@ -1416,13 +1418,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; } @@ -1430,10 +1432,10 @@ static GSequenceNode * node_get_first (GSequenceNode *node) { node = find_root (node); - + while (node->left) node = node->left; - + return node; } @@ -1441,10 +1443,10 @@ static GSequenceNode * node_get_last (GSequenceNode *node) { node = find_root (node); - + while (node->right) node = node->right; - + return node; } @@ -1460,19 +1462,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; } @@ -1480,24 +1482,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; } @@ -1507,42 +1509,42 @@ 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; } @@ -1555,13 +1557,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 */ @@ -1569,7 +1571,7 @@ 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 * searching along the 'bigger' nodes, so that we find the last one * that is equal to the needle. @@ -1580,13 +1582,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; } @@ -1594,32 +1596,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); } @@ -1627,10 +1629,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; } @@ -1638,15 +1640,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) @@ -1656,15 +1658,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 @@ -1675,24 +1677,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); } @@ -1703,27 +1705,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; } @@ -1734,50 +1736,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)); } @@ -1785,15 +1787,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; } @@ -1805,10 +1807,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); } -- 2.7.4