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

			Справочное описание GLib
Начало \| Описание