Sequences

Sequences — scalable lists

Functions

Types and Values

Includes

#include <gmodule.h>

Description

The GSequence data structure has the API of a list, but is implemented internally with a balanced binary tree. This means that most of the operations (access, search, insertion, deletion, ...) on GSequence are O(log(n)) in average and O(n) in worst case for time complexity. But, note that maintaining a balanced sorted list of n elements is done 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 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.

To sort the data, either use g_sequence_insert_sorted() or g_sequence_insert_sorted_iter() to add data to the GSequence or, if you want to add a large amount of data, it is more efficient to call g_sequence_sort() or g_sequence_sort_iter() after doing unsorted insertions.

Functions

GSequenceIterCompareFunc ()

gint
(*GSequenceIterCompareFunc) (GSequenceIter *a,
                             GSequenceIter *b,
                             gpointer 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 .

Parameters

a

a GSequenceIter

 

b

a GSequenceIter

 

user_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 .


g_sequence_new ()

GSequence *
g_sequence_new (GDestroyNotify data_destroy);

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.

Parameters

data_destroy

a GDestroyNotify function, or NULL.

[nullable]

Returns

a new GSequence.

[transfer full]

Since: 2.14


g_sequence_free ()

void
g_sequence_free (GSequence *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 .

Parameters

seq

a GSequence

 

Since: 2.14


g_sequence_get_length ()

gint
g_sequence_get_length (GSequence *seq);

Returns the positive length (>= 0) of seq . Note that this method is O(h) where `h' is the height of the tree. It is thus more efficient to use g_sequence_is_empty() when comparing the length to zero.

Parameters

seq

a GSequence

 

Returns

the length of seq

Since: 2.14


g_sequence_is_empty ()

gboolean
g_sequence_is_empty (GSequence *seq);

Returns TRUE if the sequence contains zero items.

This function is functionally identical to checking the result of g_sequence_get_length() being equal to zero. However this function is implemented in O(1) running time.

Parameters

seq

a GSequence

 

Returns

TRUE if the sequence is empty, otherwise FALSE.

Since: 2.48


g_sequence_foreach ()

void
g_sequence_foreach (GSequence *seq,
                    GFunc func,
                    gpointer user_data);

Calls func for each item in the sequence passing user_data to the function. func must not modify the sequence itself.

Parameters

seq

a GSequence

 

func

the function to call for each item in seq

 

user_data

user data passed to func

 

Since: 2.14


g_sequence_foreach_range ()

void
g_sequence_foreach_range (GSequenceIter *begin,
                          GSequenceIter *end,
                          GFunc func,
                          gpointer user_data);

Calls func for each item in the range (begin , end ) passing user_data to the function. func must not modify the sequence itself.

Parameters

begin

a GSequenceIter

 

end

a GSequenceIter

 

func

a GFunc

 

user_data

user data passed to func

 

Since: 2.14


g_sequence_sort ()

void
g_sequence_sort (GSequence *seq,
                 GCompareDataFunc cmp_func,
                 gpointer cmp_data);

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.

Parameters

seq

a GSequence

 

cmp_func

the function used to sort the sequence

 

cmp_data

user data passed to cmp_func

 

Since: 2.14


g_sequence_sort_iter ()

void
g_sequence_sort_iter (GSequence *seq,
                      GSequenceIterCompareFunc cmp_func,
                      gpointer cmp_data);

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.

Parameters

seq

a GSequence

 

cmp_func

the function used to compare iterators in the sequence

 

cmp_data

user data passed to cmp_func

 

Since: 2.14


g_sequence_get_begin_iter ()

GSequenceIter *
g_sequence_get_begin_iter (GSequence *seq);

Returns the begin iterator for seq .

Parameters

seq

a GSequence

 

Returns

the begin iterator for seq .

[transfer none]

Since: 2.14


g_sequence_get_end_iter ()

GSequenceIter *
g_sequence_get_end_iter (GSequence *seq);

Returns the end iterator for seg

Parameters

seq

a GSequence

 

Returns

the end iterator for seq .

[transfer none]

Since: 2.14


g_sequence_get_iter_at_pos ()

GSequenceIter *
g_sequence_get_iter_at_pos (GSequence *seq,
                            gint pos);

Returns the iterator at position pos . If pos is negative or larger than the number of items in seq , the end iterator is returned.

Parameters

seq

a GSequence

 

pos

a position in seq , or -1 for the end

 

Returns

The GSequenceIter at position pos .

[transfer none]

Since: 2.14


g_sequence_append ()

GSequenceIter *
g_sequence_append (GSequence *seq,
                   gpointer data);

Adds a new item to the end of seq .

Parameters

seq

a GSequence

 

data

the data for the new item

 

Returns

an iterator pointing to the new item.

[transfer none]

Since: 2.14


g_sequence_prepend ()

GSequenceIter *
g_sequence_prepend (GSequence *seq,
                    gpointer data);

Adds a new item to the front of seq

Parameters

seq

a GSequence

 

data

the data for the new item

 

Returns

an iterator pointing to the new item.

[transfer none]

Since: 2.14


g_sequence_insert_before ()

GSequenceIter *
g_sequence_insert_before (GSequenceIter *iter,
                          gpointer data);

Inserts a new item just before the item pointed to by iter .

Parameters

iter

a GSequenceIter

 

data

the data for the new item

 

Returns

an iterator pointing to the new item.

[transfer none]

Since: 2.14


g_sequence_move ()

void
g_sequence_move (GSequenceIter *src,
                 GSequenceIter *dest);

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.

Parameters

src

a GSequenceIter pointing to the item to move

 

dest

a GSequenceIter pointing to the position to which the item is moved

 

Since: 2.14


g_sequence_swap ()

void
g_sequence_swap (GSequenceIter *a,
                 GSequenceIter *b);

Swaps the items pointed to by a and b . It is allowed for a and b to point into difference sequences.

Parameters

Since: 2.14


g_sequence_insert_sorted ()

GSequenceIter *
g_sequence_insert_sorted (GSequence *seq,
                          gpointer data,
                          GCompareDataFunc cmp_func,
                          gpointer cmp_data);

Inserts data into seq using cmp_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 cmp_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.

Note that when adding a large amount of data to a GSequence, it is more efficient to do unsorted insertions and then call g_sequence_sort() or g_sequence_sort_iter().

Parameters

seq

a GSequence

 

data

the data to insert

 

cmp_func

the function used to compare items in the sequence

 

cmp_data

user data passed to cmp_func .

 

Returns

a GSequenceIter pointing to the new item.

[transfer none]

Since: 2.14


g_sequence_insert_sorted_iter ()

GSequenceIter *
g_sequence_insert_sorted_iter (GSequence *seq,
                               gpointer data,
                               GSequenceIterCompareFunc iter_cmp,
                               gpointer cmp_data);

Like g_sequence_insert_sorted(), 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.

Note that when adding a large amount of data to a GSequence, it is more efficient to do unsorted insertions and then call g_sequence_sort() or g_sequence_sort_iter().

Parameters

seq

a GSequence

 

data

data for the new item

 

iter_cmp

the function used to compare iterators in the sequence

 

cmp_data

user data passed to iter_cmp

 

Returns

a GSequenceIter pointing to the new item.

[transfer none]

Since: 2.14


g_sequence_sort_changed ()

void
g_sequence_sort_changed (GSequenceIter *iter,
                         GCompareDataFunc cmp_func,
                         gpointer cmp_data);

Moves the data pointed to by iter 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 cmp_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.

Parameters

iter

A GSequenceIter

 

cmp_func

the function used to compare items in the sequence

 

cmp_data

user data passed to cmp_func .

 

Since: 2.14


g_sequence_sort_changed_iter ()

void
g_sequence_sort_changed_iter (GSequenceIter *iter,
                              GSequenceIterCompareFunc iter_cmp,
                              gpointer cmp_data);

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 the GSequence that iter points into. 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.

Parameters

iter

a GSequenceIter

 

iter_cmp

the function used to compare iterators in the sequence

 

cmp_data

user data passed to cmp_func

 

Since: 2.14


g_sequence_remove ()

void
g_sequence_remove (GSequenceIter *iter);

Removes the item pointed to by iter . It is an error to pass the end iterator to this function.

If the sequence has a data destroy function associated with it, this function is called on the data for the removed item.

Parameters

iter

a GSequenceIter

 

Since: 2.14


g_sequence_remove_range ()

void
g_sequence_remove_range (GSequenceIter *begin,
                         GSequenceIter *end);

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.

Parameters

begin

a GSequenceIter

 

end

a GSequenceIter

 

Since: 2.14


g_sequence_move_range ()

void
g_sequence_move_range (GSequenceIter *dest,
                       GSequenceIter *begin,
                       GSequenceIter *end);

Inserts the (begin , end ) range at the destination pointed to by dest . 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 points to a place within the (begin , end ) range, the range does not move.

Parameters

dest

a GSequenceIter

 

begin

a GSequenceIter

 

end

a GSequenceIter

 

Since: 2.14


g_sequence_search ()

GSequenceIter *
g_sequence_search (GSequence *seq,
                   gpointer data,
                   GCompareDataFunc cmp_func,
                   gpointer cmp_data);

Returns an iterator pointing to the position where data would be inserted according to cmp_func and cmp_data .

cmp_func is called with two items of the seq , and cmp_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.

Parameters

seq

a GSequence

 

data

data for the new item

 

cmp_func

the function used to compare items in the sequence

 

cmp_data

user data passed to cmp_func

 

Returns

an GSequenceIter pointing to the position where data would have been inserted according to cmp_func and cmp_data .

[transfer none]

Since: 2.14


g_sequence_search_iter ()

GSequenceIter *
g_sequence_search_iter (GSequence *seq,
                        gpointer data,
                        GSequenceIterCompareFunc iter_cmp,
                        gpointer 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.

Parameters

seq

a GSequence

 

data

data for the new item

 

iter_cmp

the function used to compare iterators in the sequence

 

cmp_data

user data passed to iter_cmp

 

Returns

a GSequenceIter pointing to the position in seq where data would have been inserted according to iter_cmp and cmp_data .

[transfer none]

Since: 2.14


g_sequence_lookup ()

GSequenceIter *
g_sequence_lookup (GSequence *seq,
                   gpointer data,
                   GCompareDataFunc cmp_func,
                   gpointer cmp_data);

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 cmp_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.

Parameters

seq

a GSequence

 

data

data to look up

 

cmp_func

the function used to compare items in the sequence

 

cmp_data

user data passed to cmp_func

 

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.

[transfer none][nullable]

Since: 2.28


g_sequence_lookup_iter ()

GSequenceIter *
g_sequence_lookup_iter (GSequence *seq,
                        gpointer data,
                        GSequenceIterCompareFunc iter_cmp,
                        gpointer cmp_data);

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.

Parameters

seq

a GSequence

 

data

data to look up

 

iter_cmp

the function used to compare iterators in the sequence

 

cmp_data

user data passed to iter_cmp

 

Returns

an GSequenceIter pointing to the position of the first item found equal to data according to iter_cmp and cmp_data , or NULL if no such item exists.

[transfer none][nullable]

Since: 2.28


g_sequence_get ()

gpointer
g_sequence_get (GSequenceIter *iter);

Returns the data that iter points to.

Parameters

iter

a GSequenceIter

 

Returns

the data that iter points to.

[transfer none]

Since: 2.14


g_sequence_set ()

void
g_sequence_set (GSequenceIter *iter,
                gpointer data);

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.

Parameters

iter

a GSequenceIter

 

data

new data for the item

 

Since: 2.14


g_sequence_iter_is_begin ()

gboolean
g_sequence_iter_is_begin (GSequenceIter *iter);

Returns whether iter is the begin iterator

Parameters

iter

a GSequenceIter

 

Returns

whether iter is the begin iterator

Since: 2.14


g_sequence_iter_is_end ()

gboolean
g_sequence_iter_is_end (GSequenceIter *iter);

Returns whether iter is the end iterator

Parameters

iter

a GSequenceIter

 

Returns

Whether iter is the end iterator

Since: 2.14


g_sequence_iter_next ()

GSequenceIter *
g_sequence_iter_next (GSequenceIter *iter);

Returns an iterator pointing to the next position after iter . If iter is the end iterator, the end iterator is returned.

Parameters

iter

a GSequenceIter

 

Returns

a GSequenceIter pointing to the next position after iter .

[transfer none]

Since: 2.14


g_sequence_iter_prev ()

GSequenceIter *
g_sequence_iter_prev (GSequenceIter *iter);

Returns an iterator pointing to the previous position before iter . If iter is the begin iterator, the begin iterator is returned.

Parameters

iter

a GSequenceIter

 

Returns

a GSequenceIter pointing to the previous position before iter .

[transfer none]

Since: 2.14


g_sequence_iter_get_position ()

gint
g_sequence_iter_get_position (GSequenceIter *iter);

Returns the position of iter

Parameters

iter

a GSequenceIter

 

Returns

the position of iter

Since: 2.14


g_sequence_iter_move ()

GSequenceIter *
g_sequence_iter_move (GSequenceIter *iter,
                      gint delta);

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.

Parameters

iter

a GSequenceIter

 

delta

A positive or negative number indicating how many positions away from iter the returned GSequenceIter will be

 

Returns

a GSequenceIter which is delta positions away from iter .

[transfer none]

Since: 2.14


g_sequence_iter_get_sequence ()

GSequence *
g_sequence_iter_get_sequence (GSequenceIter *iter);

Returns the GSequence that iter points into.

Parameters

iter

a GSequenceIter

 

Returns

the GSequence that iter points into.

[transfer none]

Since: 2.14


g_sequence_iter_compare ()

gint
g_sequence_iter_compare (GSequenceIter *a,
                         GSequenceIter *b);

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.

Parameters

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


g_sequence_range_get_midpoint ()

GSequenceIter *
g_sequence_range_get_midpoint (GSequenceIter *begin,
                               GSequenceIter *end);

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.

Parameters

begin

a GSequenceIter

 

end

a GSequenceIter

 

Returns

a GSequenceIter pointing somewhere in the (begin , end ) range.

[transfer none]

Since: 2.14

Types and Values

GSequence

typedef struct _GSequence GSequence;

The GSequence struct is an opaque data type representing a sequence data type.


GSequenceIter

typedef struct _GSequenceNode  GSequenceIter;

The GSequenceIter struct is an opaque data type representing an iterator pointing into a GSequence.