Doubly-Linked Lists

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

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

#include <glib.h> GList; GList* g_list_append (GList *list, gpointer data); GList* g_list_prepend (GList *list, gpointer data); GList* g_list_insert (GList *list, gpointer data, gint position); GList* g_list_insert_before (GList *list, GList *sibling, gpointer data); GList* g_list_insert_sorted (GList *list, gpointer data, GCompareFunc func); GList* g_list_remove (GList *list, gconstpointer data); GList* g_list_remove_link (GList *list, GList *llink); GList* g_list_delete_link (GList *list, GList *link_); GList* g_list_remove_all (GList *list, gconstpointer data); void g_list_free (GList *list); GList* g_list_alloc (void); void g_list_free_1 (GList *list); #define g_list_free1 guint g_list_length (GList *list); GList* g_list_copy (GList *list); GList* g_list_reverse (GList *list); GList* g_list_sort (GList *list, GCompareFunc compare_func); gint (*GCompareFunc) (gconstpointer a, gconstpointer b); GList* g_list_insert_sorted_with_data (GList *list, gpointer data, GCompareDataFunc func, gpointer user_data); GList* g_list_sort_with_data (GList *list, GCompareDataFunc compare_func, gpointer user_data); gint (*GCompareDataFunc) (gconstpointer a, gconstpointer b, gpointer user_data); GList* g_list_concat (GList *list1, GList *list2); void g_list_foreach (GList *list, GFunc func, gpointer user_data); void (*GFunc) (gpointer data, gpointer user_data); GList* g_list_first (GList *list); GList* g_list_last (GList *list); #define g_list_previous (list) #define g_list_next (list) GList* g_list_nth (GList *list, guint n); gpointer g_list_nth_data (GList *list, guint n); GList* g_list_nth_prev (GList *list, guint n); GList* g_list_find (GList *list, gconstpointer data); GList* g_list_find_custom (GList *list, gconstpointer data, GCompareFunc func); gint g_list_position (GList *list, GList *llink); gint g_list_index (GList *list, gconstpointer data); void g_list_push_allocator (gpointer allocator); void g_list_pop_allocator (void);

Описание

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

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

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

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

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

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

Для добавления элементов используйте g_list_append(), g_list_prepend(), g_list_insert() и g_list_insert_sorted().

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

Для поиска элементов в списке используйте g_list_first(), g_list_last(), g_list_next(), g_list_previous(), g_list_nth(), g_list_nth_data(), g_list_find() и g_list_find_custom().

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

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

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

Детали

GList

typedef struct { gpointer data; GList *next; GList *prev; } GList;

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

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

g_list_append ()

GList* g_list_append (GList *list, gpointer data);

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

Примечание

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

Примечание

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

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

g_list_prepend ()

GList* g_list_prepend (GList *list, gpointer data);

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

Примечание

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

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

g_list_insert ()

GList* g_list_insert (GList *list, gpointer data, gint position);

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

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

g_list_insert_before ()

GList* g_list_insert_before (GList *list, GList *sibling, gpointer data);

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

list : указатель на GList.
sibling : номер элемента перед которым вставляется новый элемент,или NULL для вставки в конец списка.
data : данные для нового элемента.
Возвращает : новое начало GList.

g_list_insert_sorted ()

GList* g_list_insert_sorted (GList *list, gpointer data, GCompareFunc func);

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

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

g_list_remove ()

GList* g_list_remove (GList *list, gconstpointer data);

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

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

g_list_remove_link ()

GList* g_list_remove_link (GList *list, GList *llink);

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

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

g_list_delete_link ()

GList* g_list_delete_link (GList *list, GList *link_);

Удаляет узел link_ из list.

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

g_list_remove_all ()

GList* g_list_remove_all (GList *list, gconstpointer data);

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

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

g_list_free ()

void g_list_free (GList *list);

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

Примечание

Если первый элемент содержит динамически-распределённую память, он должен быть освобождён первым.

list : GList.

g_list_alloc ()

GList* g_list_alloc (void);

Распределяет пространство для одного элемента GList. Она вызывается с помощью g_list_append(), g_list_prepend(), g_list_insert() и g_list_insert_sorted() и очень редко используется самостоятельно.

Возвращает : указатель для вновь распределённого элемента GList.

g_list_free_1 ()

void g_list_free_1 (GList *list);

Освобождает один элемент GList. Она в основном используется после g_list_remove_link().

list : элемент GList.

g_list_free1

#define g_list_free1

Другое имя для g_list_free_1().


g_list_length ()

guint g_list_length (GList *list);

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

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

g_list_copy ()

GList* g_list_copy (GList *list);

Копирует GList.

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

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

g_list_reverse ()

GList* g_list_reverse (GList *list);

Переворачивает GList. Она просто переключает предыдущие и следующие указатели в каждом элементе.

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

g_list_sort ()

GList* g_list_sort (GList *list, GCompareFunc compare_func);

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

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

GCompareFunc ()

gint (*GCompareFunc) (gconstpointer a, gconstpointer b);

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

a : первое значение.
b : значение для сравнения.
Возвращает : отрицательное значение если a < b; ноль если a = b; положительное значение если a > b.

g_list_insert_sorted_with_data ()

GList* g_list_insert_sorted_with_data (GList *list, gpointer data, GCompareDataFunc func, gpointer user_data);

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

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

g_list_sort_with_data ()

GList* g_list_sort_with_data (GList *list, GCompareDataFunc compare_func, gpointer user_data);

Похожа на g_list_sort(), но функция сравнения принимает параметр пользовательских данных.

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

GCompareDataFunc ()

gint (*GCompareDataFunc) (gconstpointer a, gconstpointer b, gpointer user_data);

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

a : первое значение.
b : значение для сравнения.
user_data : данные помещаемые в функцию сравнения.
Возвращает : отрицательное значение если a < b; ноль если a = b; положительное значение если a > b.

g_list_concat ()

GList* g_list_concat (GList *list1, GList *list2);

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

list1 : GList.
list2 : GList добавляемый в конец первого GList.
Возвращает : начало нового GList.

g_list_foreach ()

void g_list_foreach (GList *list, GFunc func, gpointer user_data);

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

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

GFunc ()

void (*GFunc) (gpointer data, gpointer user_data);

Определяет тип функции помещаемой в g_list_foreach() и g_slist_foreach().

data : элементы данных.
user_data : данные помещаемые в g_list_foreach() или g_slist_foreach().

g_list_first ()

GList* g_list_first (GList *list);

Выдаёт первый элемент в GList.

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

g_list_last ()

GList* g_list_last (GList *list);

Выдаёт последний элемент в GList.

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

g_list_previous()

#define g_list_previous(list)

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

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

g_list_next()

#define g_list_next(list)

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

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

g_list_nth ()

GList* g_list_nth (GList *list, guint n);

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

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

g_list_nth_data ()

gpointer g_list_nth_data (GList *list, guint n);

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

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

g_list_nth_prev ()

GList* g_list_nth_prev (GList *list, guint n);

Определяет элемент n помещаемый перед list.

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

g_list_find ()

GList* g_list_find (GList *list, gconstpointer data);

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

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

g_list_find_custom ()

GList* g_list_find_custom (GList *list, gconstpointer data, GCompareFunc func);

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

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

g_list_position ()

gint g_list_position (GList *list, GList *llink);

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

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

g_list_index ()

gint g_list_index (GList *list, gconstpointer data);

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

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

g_list_push_allocator ()

void g_list_push_allocator (gpointer allocator);

Внимание

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

Заставляет использовать распределитель для распределения элементов GList. Использует g_list_pop_allocator() для восстановления предыдущего распределения.

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

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

g_list_pop_allocator ()

void g_list_pop_allocator (void);

Внимание

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

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

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