Singly-Linked Lists

Singly-Linked Lists — Связанные списки содержащие целочисленные значения или указатели на данные, с ограничением итерации только в одном направлении.

Краткое описание

#include <glib.h> GSList; GSList* g_slist_alloc (void); GSList* g_slist_append (GSList *list, gpointer data); GSList* g_slist_prepend (GSList *list, gpointer data); GSList* g_slist_insert (GSList *list, gpointer data, gint position); GSList* g_slist_insert_before (GSList *slist, GSList *sibling, gpointer data); GSList* g_slist_insert_sorted (GSList *list, gpointer data, GCompareFunc func); GSList* g_slist_remove (GSList *list, gconstpointer data); GSList* g_slist_remove_link (GSList *list, GSList *link_); GSList* g_slist_delete_link (GSList *list, GSList *link_); GSList* g_slist_remove_all (GSList *list, gconstpointer data); void g_slist_free (GSList *list); void g_slist_free_1 (GSList *list); #define g_slist_free1 guint g_slist_length (GSList *list); GSList* g_slist_copy (GSList *list); GSList* g_slist_reverse (GSList *list); GSList* g_slist_insert_sorted_with_data (GSList *list, gpointer data, GCompareDataFunc func, gpointer user_data); GSList* g_slist_sort (GSList *list, GCompareFunc compare_func); GSList* g_slist_sort_with_data (GSList *list, GCompareDataFunc compare_func, gpointer user_data); GSList* g_slist_concat (GSList *list1, GSList *list2); void g_slist_foreach (GSList *list, GFunc func, gpointer user_data); GSList* g_slist_last (GSList *list); #define g_slist_next (slist) GSList* g_slist_nth (GSList *list, guint n); gpointer g_slist_nth_data (GSList *list, guint n); GSList* g_slist_find (GSList *list, gconstpointer data); GSList* g_slist_find_custom (GSList *list, gconstpointer data, GCompareFunc func); gint g_slist_position (GSList *list, GSList *llink); gint g_slist_index (GSList *list, gconstpointer data); void g_slist_push_allocator (gpointer dummy); void g_slist_pop_allocator (void);

Описание

Структура GSList и связанные с ней функции обеспечивают стандартный односвязный список структур данных.

Каждый элемент в списке содержит часть данных, вместе с указателем который привязывает следующий элемент в списке. Используя этот указатель можно перемещаться по списку только в одном направлении (в отличие от двусвязных списков которые позволяют перемещение в двух направлениях).

Данные содержащиеся в каждом элементе могут быть либо целочисленными значениями, используя один из Type Conversion Macros, либо просто указателями на любой тип данных.

Список элементов распределяется slice allocator, что более эффективно чем индивидуальное распределение элементов.

Помните что функции GSList предполагают помещение указателя на первый элемент в списке. Функции которые вставляют элементы, возвращают новое начало списка, которое может иметь изменения.

Нет функции для создания GSList. NULL рассматривается как пустой список, поэтому вы можете установить GSList* в NULL.

Для добавления элементов, используйте g_slist_append(), g_slist_prepend(), g_slist_insert() и g_slist_insert_sorted().

Для удаления элементов, используйте g_slist_remove().

Для поиска элементов в списке используйте g_slist_last(), g_slist_next(), g_slist_nth(), g_slist_nth_data(), g_slist_find() и g_slist_find_custom().

Для поиска номера элемента используйте g_slist_position() и g_slist_index().

Для вызова функции для каждого элемента в списке используйте g_slist_foreach().

Для освобождения элементов списка, используйте g_slist_free().

Детали

GSList

typedef struct { gpointer data; GSList *next; } GSList;

Структура GSList используется для каждого элемента в односвязном списке.

gpointer data; содержит элементы данных, которые могут указывать на любой тип данных, или любое целочисленное значение используя Type Conversion Macros.
GSList *next; содержит ссылку на следующий элемент в списке.

g_slist_alloc ()

GSList* g_slist_alloc (void);

Распределяет свободное пространство для одного элемента GSList. Она вызывается с помощью g_slist_append(), g_slist_prepend(), g_slist_insert() и g_slist_insert_sorted() функций и очень редко используется самостоятельно.

Возвращает : указатель на вновь распределённый элемент GSList.

g_slist_append ()

GSList* g_slist_append (GSList *list, gpointer data);

Добавляет новый элемент в конец списка.

Примечание

Возвращает значение начала списка, которое может измениться, поэтому убедитесь что вы сохранили новое значение.

Примечание

Помните что g_slist_append() перебирает все элементы в списке для поиска конца, это не эффективно когда добавляется много элементов. Основная идиома избежать неэффективности в прикреплении элементов сначала перевернутого списка и последующее переворачивание обратно когда все элементы добавлены.

/* Помните что это инициализирует пустой список. */ GSList *list = NULL, *number_list = NULL; /* Это список строк. */ list = g_slist_append (list, "first"); list = g_slist_append (list, "second"); /* Это список целочисленных. */ number_list = g_slist_append (number_list, GINT_TO_POINTER (27)); number_list = g_slist_append (number_list, GINT_TO_POINTER (14));
list : GSList.
data : данные для нового элемента.
Возвращает : новое начало GSList.

g_slist_prepend ()

GSList* g_slist_prepend (GSList *list, gpointer data);

Добавляет новый элемент в начало списка.

Примечание

Возвращает значение нового начала списка, которое может меняться, поэтому убедитесь что вы сохранили новое значение.

/* Помните что это инициализирует пустой список. */ GSList *list = NULL; list = g_slist_prepend (list, "last"); list = g_slist_prepend (list, "first");
list : GSList.
data : данные для нового элемента
Возвращает : новое начало GSList.

g_slist_insert ()

GSList* g_slist_insert (GSList *list, gpointer data, gint position);

Вставляет новый элемент в данную позицию списка.

list : GSList.
data : данные для нового элемента.
position : позиция для вставляемого элемента. Если отрицательное, или больше чем число элементов в списке, новый элемент добавляется в конец списка.
Возвращает : новое начало GSList.

g_slist_insert_before ()

GSList* g_slist_insert_before (GSList *slist, GSList *sibling, gpointer data);

Вставляет узел перед sibling содержащим data. Возвращает новый первый элемент списка.

slist : GSList.
sibling : узел для вставки перед data.
data : данные помещаемые во вновь вставленный узел.
Возвращает : новый первый элемент списка.

g_slist_insert_sorted ()

GSList* g_slist_insert_sorted (GSList *list, gpointer data, GCompareFunc func);

Вставляет новый элемент в список, используя полученную функцию сравнения для определения его позиции.

list : GSList.
data : данные для нового элемента.
func : функция для сравнения элементов всписке. Она должна возвращать число > 0 если первый параметр располагается после второго параметра при сортировке.
Возвращает : новое начало GSList.

g_slist_remove ()

GSList* g_slist_remove (GSList *list, gconstpointer data);

Удаляет элемент из GSList. Если два элемента содержат одинаковые данные, удаляет только первый. Если нет элементов содержащих данные, GSList не изменяется.

list : GSList.
data : данные удаляемого элемента.
Возвращает : новое начало GSList.

g_slist_remove_link ()

GSList* g_slist_remove_link (GSList *list, GSList *link_);

Удаляет элемент из GSList, не освобождая элемент. Ссылка на следующий элемент у удаляемого устанавливается в NULL, так как он сам становится списком с единственным элементом.

list : GSList.
link_ : элемент в GSList.
Возвращает : новое начало GSList, без элемента.

g_slist_delete_link ()

GSList* g_slist_delete_link (GSList *list, GSList *link_);

Удаляет узел list. Возвращает новый первый элемент списка.

list : GSList.
link_ : узел для удаления.
Возвращает : новый первый элемент list.

g_slist_remove_all ()

GSList* g_slist_remove_all (GSList *list, gconstpointer data);

Удаляет все узлы списка с данными data. Возвращает новый первый элемент списка. В отличие от g_slist_remove() которая удаляет только первый узел соответствующий полученным данным.

list : GSList.
data : данные для удаления.
Возвращает : новый первый элемент list.

g_slist_free ()

void g_slist_free (GSList *list);

Освобождает всю память используемую GSList. Освобождает элементы возвращаемые распределителем слайсов.

list : GSList.

g_slist_free_1 ()

void g_slist_free_1 (GSList *list);

Освобождает один элемент GSList. Её полезно использовать после g_slist_remove_link().

list : элемент GSList.

g_slist_free1

#define g_slist_free1

Макрос который делает тоже самое что и g_slist_free_1().

Начиная с версии 2.10


g_slist_length ()

guint g_slist_length (GSList *list);

Определяет количество элементов в GSList.

list : GSList.
Возвращает : количество элементов в GSList.

g_slist_copy ()

GSList* g_slist_copy (GSList *list);

Копирует GSList.

Помните что это "пустая" копия. Если список элементов содержит указатели на данные, то указатели копируются, а фактические данные нет.

list : GSList.
Возвращает : копия list.

g_slist_reverse ()

GSList* g_slist_reverse (GSList *list);

Переворачивает GSList.

list : GSList.
Возвращает : начало перевернутой GSList.

g_slist_insert_sorted_with_data ()

GSList* g_slist_insert_sorted_with_data (GSList *list, gpointer data, GCompareDataFunc func, gpointer user_data);

Вставляет новый элемент в список, использует полученную функцию сравнения для определения позиции.

list : GSList.
data : данные для нового элемента.
func : функция сравнивающая элементы в списке. Она должна возвращать число > 0 если первый параметр располагается после второго параметра при сортировке.
user_data : данные помещаемые в функцию сравнения.
Возвращает : новое начало GSList. Начиная с версии 2.10

g_slist_sort ()

GSList* g_slist_sort (GSList *list, GCompareFunc compare_func);

Сортирует GSList используя полученную функцию сравнения.

list : GSList.
compare_func : функция сравнения используемая для сортировки GSList. Эта функция принимает данные из 2 элементов GSList и должна вернуть 0 если они равны, отрицательное значение если первый элемент располагается перед вторым, или положительное значение если первый элемент располагается после второго.
Возвращает : начало отсортированной GSList.

g_slist_sort_with_data ()

GSList* g_slist_sort_with_data (GSList *list, GCompareDataFunc compare_func, gpointer user_data);

Подобна g_slist_sort(), но сравнивающая функция принимает аргумент пользовательских данных.

list : GSList
compare_func : сравнивающая функция.
user_data : данные помещаемые в функцию сравнения.
Возвращает : новый первый элемент списка.

g_slist_concat ()

GSList* g_slist_concat (GSList *list1, GSList *list2);

Добавляет второй GSList в конец первого GSList. Помните что элементы второго GSList не копируются. Они используются непосредственно.

list1 : GSList.
list2 : GSList для добавления в конец первого GSList.
Возвращает : начало нового GSList.

g_slist_foreach ()

void g_slist_foreach (GSList *list, GFunc func, gpointer user_data);

Вызывает функцию для каждого элемента GSList.

list : GSList.
func : функция вызываемая для каждого элемента данных.
user_data : пользовательские данные для помещения в функцию.

g_slist_last ()

GSList* g_slist_last (GSList *list);

Получает последний элемент в GSList.

list : GSList.
Возвращает : последний элемент в GSList, или NULL если GSList не имеет элементов.

g_slist_next()

#define g_slist_next(slist)

Удобный макрос для получения следующего элемента в GSList.

slist : элемент в GSList.
Возвращает : следующий элемент, или NULL если нет больше элементов.

g_slist_nth ()

GSList* g_slist_nth (GSList *list, guint n);

Определяет элемент в указанной позиции GSList.

list : GSList.
n : позиция элемента, подсчёт с 0.
Возвращает : элемент, или NULL если позиция выходит за пределы GSList.

g_slist_nth_data ()

gpointer g_slist_nth_data (GSList *list, guint n);

Определяет данные элемента в указанной позиции.

list : GSList.
n : позиция элемента.
Возвращает : данные элемента, или NULL если выходит за пределы GSList.

g_slist_find ()

GSList* g_slist_find (GSList *list, gconstpointer data);

Находит элемент в GSList который содержит указанные данные.

list : GSList.
data : данные элемента для поиска.
Возвращает : найденный элемент GSList, или NULL если он не найден.

g_slist_find_custom ()

GSList* g_slist_find_custom (GSList *list, gconstpointer data, GCompareFunc func);

Ищет элемент в GSList, используя полученную функцию для поиска желаемого элемента. Она перемещается по списку, вызов полученной функции должен вернуть 0 когда желаемый элемент найден. Функция принимает два gconstpointer аргумента, данные элемента GSList как первый аргумент и полученные пользовательские данные.

list : GSList.
data : пользовательские данные помещаемые в функцию.
func : функция вызываемая для каждого элемента. Она должна возвращать 0 когда желаемый элемент найден.
Возвращает : найденный элемент GSList, или NULL если он не найден.

g_slist_position ()

gint g_slist_position (GSList *list, GSList *llink);

Определяет позицию полученного элемента в GSList (начиная с 0).

list : GSList.
llink : элемент в GSList.
Возвращает : позиция элемента в GSList, или -1 если элемент не найден.

g_slist_index ()

gint g_slist_index (GSList *list, gconstpointer data);

Получает позицию элемента содержащего полученные данные (начиная с 0).

list : GSList.
data : данные для поиска.
Возвращает : номер элемента содержащего данные, или -1 если данные не найдены.

g_slist_push_allocator ()

void g_slist_push_allocator (gpointer dummy);

Внимание

g_slist_push_allocator устарела начиная с версии 2.10 и не должна использоваться во вновь создаваемом коде. Она ничего не делает, так как GSList конвертирован в slice allocator

Устанавливает распределитель используемый для распределения элементов GSList. Использует g_slist_pop_allocator() для восстановления предыдущих распределений.

Помните что эта функция не доступна если GLib скомпилирована с опцией --disable-mem-pools

dummy : GAllocator используемый для распределения элементов GSList.

g_slist_pop_allocator ()

void g_slist_pop_allocator (void);

Внимание

g_slist_pop_allocator устарела начиная с версии 2.10 и не должна использоваться во вновь создаваемом коде. Она ничего не делает, так как GSList конвертирован в slice allocator

Восстанавливает предыдущий GAllocator, используемый для распределения элементов GSList.

Помните что эта функция не доступна если GLib скомпилирована с опцией --disable-mem-pools