Про Glib в языке C от IBM

 

Про Glib в языке C от IBM

Оригинал: Manage C data using the GLib collections

Автор: Tom Copeland

 Published 27 июня 2005 г.

Перед началом работы

Об этом руководстве

В этом руководстве показано, как использовать коллекции GLib для эффективного и элегантного управления данными в ваших программах на C. Коллекции GLib являются результатом многолетнего усовершенствования и используются многочисленными программами с открытым исходным кодом. Эти коллекции предоставляют более сложные структуры данных/контейнеры (функции и переменные, необходимые для управления данными), которых не хватает в языке C.

Это руководство написано для программистов Linux или UNIX, чьи навыки и опыт находятся на уровне от начального до среднего.

Предварительные условия

Чтобы получить максимальную отдачу от этого руководства, вы должны быть знакомы с UNIX-подобной средой и знать, как использовать оболочку командной строки.

Вам также потребуются некоторые базовые инструменты программирования для компиляции примеров исходного кода, такие как компилятор, такой как GCC (см. раздел "Ресурсы" для загрузки GCC); все примеры кода в этом руководстве были скомпилированы с помощью GCC 3.4.2.

Вам также необходимо установить среду выполнения GLib и библиотеки разработки. Большинство современных дистрибутивов Linux поставляются с установленной средой выполнения GLib; например, установка Fedora Core 3 для «рабочей станции» поставляется с двумя пакетами RPM GLib: glib2-2.4.7-1 и glib2-devel-2.4.7-1.

Упорядочивание данных

Область действия GLib

Сначала давайте рассмотрим возможности GLib.

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

GLib также определяет ряд структур данных (и связанных с ними операций), в том числе:

• Фрагменты памяти
• Двусвязные списки
• Односвязные списки
• Хеш-таблицы
• Строки (которые могут динамически увеличиваться)
• Фрагменты строк (группы строк)
• Массивы (размер которых может увеличиваться по мере добавления элементов)
• Сбалансированные бинарные деревья
• N-арные деревья
• Кварки (двусторонняя ассоциация строки и уникального целочисленного идентификатора)
• Списки данных с ключами (списки элементов данных, доступных по строковому или целочисленному идентификатору)
• Отношения и кортежи (таблицы данных, которые можно индексировать по любому количеству полей)
• Кеши

Каждая программа должна управлять данными

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

Если вы пишете код на языке C, вы обнаружите, что в нем довольно мало сложных структур данных. Конечно, существует множество простых способов хранения данных:

• Примитивные типы -- int s, float, char и т. д.
• enum, который может содержать ряд символических имен для целых чисел.
• Массив — самая гибкая структура данных в C.

Массив может содержать примитивы или серии данных любого типа или указатели на данные любого типа.

Но массивы также имеют много ограничений. Их размер нельзя изменить, поэтому, если вы выделяете память для массива из десяти элементов и обнаруживаете, что вам нужно поместить в него одиннадцать элементов, вам нужно создать новый массив, скопировать в него старые элементы, а затем поместить новый элемент. . Если вы собираетесь перебирать каждый элемент в массиве, вам нужно либо отслеживать, сколько элементов находится в массиве, либо убедиться, что в конце массива есть какой-то маркер «конец массива», чтобы вы знали, когда остановиться.

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

Написание юнит-тестов может сильно помочь, но в целом переписывать одну и ту же структуру данных для каждой новой программы — дело неблагодарное.

В этом помогут встроенные структуры данных. Некоторые языки поставляются со встроенными контейнерами. C++ содержит стандартную библиотеку шаблонов (STL), в которой есть набор классов контейнеров, таких как списки, приоритетные очереди, наборы и карты. Эти контейнеры также являются типобезопасными, что означает, что вы можете поместить только один тип элемента в каждый создаваемый объект-контейнер. Это делает их более безопасными в использовании и устраняет утомительное приведение типов, которое требуется в C. Кроме того, STL содержит множество итераторов, утилит сортировки и т. д., упрощающих работу с контейнерами.

Язык программирования Java также поставляется с набором контейнерных классов. Пакет java.util содержит ArrayList, HashMap, TreeSet и различные другие стандартные структуры. Он также включает в себя утилиты для общей сортировки данных и создания неизменяемых коллекций, а также различные другие полезные функции.

Однако в C нет встроенной поддержки контейнеров; вам придется либо создавать свою собственную, либо использовать чужую библиотеку структур данных.

К счастью, GLib — отличная бесплатная библиотека с открытым исходным кодом, которая удовлетворяет эту потребность. Она содержит большинство стандартных структур данных и многие утилиты, необходимые для эффективного управления данными в ваших программах. Она существует с 1996 года, поэтому была тщательно протестирована с добавлением множества полезных функций.

Анализ алгоритма в 100 словах (или меньше)

Разные операции с контейнерами занимают разное время. Например, доступ к первому элементу в длинном списке выполняется намного быстрее, чем сортировка того же списка. Нотация, используемая для описания времени выполнения этих операций, называется O-нотация. Эта тема достойна изучения семестра компьютерных наук, но в двух словах, O-нотация — это наихудший анализ операции. Другими словами, это измерение наибольшего времени, которое потребуется для завершения операции. Это оказалось полезным способом измерения операций со структурой данных, поскольку часто встречаются операции в наихудшем случае (например, когда вы ищете в списке и не находите элемент, который искали).

Ниже продемонстрированы некоторые примеры использования O-нотации, в которых можно использовать набор игральных карт, выложенных в ряд на столе лицевой стороной вниз:

• O(1) -- Выбор первой карты. O(1) также известен как "постоянное время", потому что получение первой карты занимает одинаковое количество времени, независимо от того, сколько карт находится в списке.
• O(n) -- Переворачивание каждой карты. O(n) известен как "линейное время", потому что время, необходимое для этого, увеличивается линейно по мере увеличения количества карточек.
• O(n!) -- Создание списка всех возможных перестановок всех карточек. С каждой новой карточкой, добавляемой в список, количество перестановок увеличивается в несколько раз.

В этом руководстве вы встретите ссылки на O-нотацию операций с различными структурами данных. Знание затрат на конкретную операцию с определенной структурой данных может помочь вам разумно выбирать контейнеры и улучшить производительность вашего приложения.

Компиляция программ GLib

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

//ex‑compile.c
#include <glib.h>
int main(int argc, char∗∗ argv) {
 GList∗ list = NULL;
 list = g_list_append(list, "Hello world!");
 printf("The first item is '%s'\n", g_list_first(list)‑>data);
 return 0;
}

Вы можете компилировать эту программу вызывая GCC примерно так:

$ gcc ‑I/usr/include/glib‑2.0 ‑I/usr/lib/glib‑2.0/include  
   ‑lglib‑2.0 ‑o ex‑compile ex‑compile.c

А затем выполнить собранный экзешник:

$ ./ex‑compile
The first item is 'Hello world!'
$

Однако это довольно трудоемкий вызов GCC. Далее следует более простой способ указать GCC на библиотеки GLib.

Использование pkg-config

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

$ gcc 'pkg‑config ‑‑cflags ‑‑libs glib‑2.0' ‑o ex‑compile ex‑compile.c

ПРИМЕЧАНИЕ.Я попробовал выполнить эту команду в MSYS2 в Windows и получил ошибку. А вот эта команда выполнились:

gcc `pkg-config --cflags glib-2.0` -o glist glist.c `pkg-config --libs glib-2.0`

Обращаю внимание на использование обратных кавычек и раздельные вставки cflag в начале крманды и libs в конце!

Источник информации: https://discourse.gnome.org/t/fail-to-compile-gtk3-both-in-msys2-and-cmd/8470

И вывод такой же, как и раньше:

$ ./ex‑compile
The first item is 'Hello world!'
$

Обратите внимание, что теперь вам больше не нужно указывать пути к заголовочным файлам GLib; Об этом позаботится параметр pkgconfig --cflags. И то же самое касается библиотек, на которые указывает параметр --libs. Конечно, здесь нет никакой магии; pkgconfig просто считывает расположение библиотеки и заголовочного файла из файла конфигурации. В системе Fedora Core 3 файлы pkgconfig расположены в /usr/lib/pkgconfig, а файл glib-2.0.pc выглядит следующим образом:

$ cat /usr/lib/pkgconfig/glib‑2.0.pc
 prefix=/usr
 exec_prefix=/usr
 libdir=/usr/lib
 includedir=/usr/include

 glib_genmarshal=glib‑genmarshal
 gobject_query=gobject‑query
 glib_mkenums=glib‑mkenums

 Name: GLib
 Description: C Utility Library
 Version: 2.4.7
 Libs: ‑L${libdir} ‑lglib‑2.0
 Cflags: ‑I${includedir}/glib‑2.0 ‑I${libdir}/glib‑2.0/include

Таким образом, вся информация просто скрыта слоем косвенности. И если у вас есть дистрибутив Linux, который не поддерживает pkgconfig, вы всегда можете просто вернуться к указанию GCC непосредственно на заголовочные файлы и библиотеки.

 

Односвязные списки

Концепции односвязных списков

Возможно, самым простым контейнером в GLib является односвязный список; GSList. Как следует из названия, это ряд элементов данных, которые связаны друг с другом, так что вы можете переходить от одного элемента данных к другому. Он называется односвязным списком, потому что между элементами существует только одна ссылка. Таким образом, вы можете двигаться только «вперед» по списку, но вы не можете двигаться вперед, а затем назад.

Чтобы углубиться в детали, каждый раз, когда вы добавляете элемент в список, создается новая структура GSList. Эта структура GSList состоит из элемента данных и указателя. Затем предыдущий конец списка указывает на этот новый узел, что означает, что теперь новый узел находится в конце списка. Терминология может немного сбивать с толку, поскольку вся структура называется GSList, и каждый узел также является структурой GSList.

Концептуально список — это просто последовательность списков, каждый из которых состоит из одного элемента. Это как если бы это была очередь машин на светофоре; даже если бы на светофоре стояла только одна машина, это все равно считалось бы очередью машин.

Связывание списка элементов имеет некоторые последствия для использования. Определение длины списка — операция O(n); вы не сможете определить длину списка, если не посчитаете каждый элемент. Добавление в начало списка выполняется быстро (операция O(1)), поскольку список не имеет фиксированной длины и не требует перестроения после превышения порогового значения. Но поиск элемента — это операция O(n), поскольку вам нужно выполнить линейный поиск по всему списку, пока вы не найдете то, что ищете. Добавление элемента в конец списка также является операцией O(n), поскольку, чтобы добраться до конца, вам нужно начать с начала и повторять, пока не дойдете до конца списка.

GSList может содержать два основных типа данных: целые числа или указатели. Но на самом деле это означает, что в GSList можно поместить практически все что угодно. Например, если вам нужен GSList с типом данных "short", вы можете просто поместить указатели на шорты в GSList.

На данный момент достаточно теории; на самом деле использовать GSList!

Создание, добавление и удаление

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

//ex‑gslist‑1.c
#include <glib.h>
int main(int argc, char∗∗ argv) {
 GSList∗ list = NULL;
 printf("The list is now %d items long\n", g_slist_length(list));
 list = g_slist_append(list, "first");
 list = g_slist_append(list, "second");
 printf("The list is now %d items long\n", g_slist_length(list));
 g_slist_free(list);
 return 0;
}

∗∗∗∗∗ Output ∗∗∗∗∗

The list is now 0 items long
The list is now 2 items long

Несколько замечаний по приведенному выше коду:

• Большинство функций GLib имеют формат g_(имя контейнера)_(имя функции). Таким образом, чтобы получить длину GSList, вы должны вызвать g_slist_length.
• Нет функции для создания нового GSList; вместо этого просто объявите указатель на структуру GSList и присвойте ему значение NULL.
• g_slist_append возвращает новое начало списка, поэтому вам нужно придерживаться этого возвращаемого значения.
• g_slist_free не волнует, были ли какие-либо элементы помещены в список или нет; Быстрый взгляд на исходный код показывает, что g_slist_free сразу возвращается, если GSList имеет значение NULL. g_slist_length также работает с пустым списком; в этом случае он просто возвращает 0.

 Добавление и последующее удаление данных

Вы можете ввести данные; вам, вероятно, также нужно будет выбрать их. Вот пример:

//ex‑gslist‑2.c

#include <glib.h>

int main(int argc, char∗∗ argv) {

 GSList∗ list = NULL;

 list = g_slist_append(list, "second");

 list = g_slist_prepend(list, "first");

 printf("The list is now %d items long\n", g_slist_length(list));

 list = g_slist_remove(list, "first");

 printf("The list is now %d items long\n", g_slist_length(list));

 g_slist_free(list);

 return 0;

}

∗∗∗∗∗ Output ∗∗∗∗∗

The list is now 2 items long

The list is now 1 items long

Большая часть этого кода должна показаться вам знакомой, но следует учитывать некоторые моменты:

Если вы вызовете g_slist_remove и передадите элемент, которого нет в списке, список не изменится.

g_slist_remove также возвращает новое начало списка.

Вы можете видеть, что "first" добавляется с вызовом g_slist_prepend. Это более быстрый вызов, чем g_slist_append; это O (1), а не O (n), потому что, как упоминалось ранее, выполнение добавления требует полного обхода списка. Поэтому, если вообще удобно использовать g_slist_prepend, вам нужен именно он.

Удаление повторяющихся элементов

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

//ex‑gslist‑3.c

#include <glib.h>

int main(int argc, char∗∗ argv) {

 GSList∗ list = NULL;

 list = g_slist_append(list, "first");

 list = g_slist_append(list, "second");

 list = g_slist_append(list, "second");

 list = g_slist_append(list, "third");

 list = g_slist_append(list, "third");

 printf("The list is now %d items long\n", g_slist_length(list));

 list = g_slist_remove(list, "second");

 list = g_slist_remove_all(list, "third");

 printf("The list is now %d items long\n", g_slist_length(list));

 g_slist_free(list);

 return 0;

}

∗∗∗∗∗ Output ∗∗∗∗∗

The list is now 5 items long

The list is now 2 items long

Таким образом, если GSList дважды содержит один и тот же указатель и вы вызываете g_slist_remove, будет удален только первый указатель. Но вы можете удалить все вхождения элемента с помощью g_slist_remove_all.

Последние, n-е и n-е данные

После того, как несколько элементов появятся в GSList, вы можете выбирать их различными способами. Вот несколько примеров с пояснениями в прилагаемых операторах printf:

//ex‑gslist‑4.c

#include <glib.h>

int main(int argc, char∗∗ argv) {

 GSList∗ list = NULL;

 list = g_slist_append(list, "first");

 list = g_slist_append(list, "second");

 list = g_slist_append(list, "third");

 printf("The last item is '%s'\n", g_slist_last(list)‑>data);

 printf("The item at index '1' is '%s'\n", g_slist_nth(list, 1)‑>data);

 printf("Now the item at index '1' the easy way: '%s'\n", g_slist_nth_data(list, 1));

 printf("And the 'next' item after first item is '%s'\n", g_slist_next(list)‑>data);

 g_slist_free(list);

 return 0;

}

∗∗∗∗∗ Output ∗∗∗∗∗

The last item is 'third'

The item at index '1' is 'second'

Now the item at index '1' the easy way: 'second'

And the 'next' item after first item is 'second'

Обратите внимание, что в GSList есть несколько функций быстрого доступа; вы можете просто вызвать g_slist_nth_data вместо того, чтобы вызывать g_slist_nth и затем разыменовывать возвращенный указатель.

Последний оператор printf немного отличается. g_slist_next — это не вызов функции, а скорее макрос. Он расширяется до разыменования указателя ссылки на следующий элемент в GSList. В этом случае вы можете видеть, что мы передали первый элемент в GSList, поэтому макрос расширился, чтобы предоставить второй элемент. Это также быстрая операция, так как нет накладных расходов на вызовы функций.

Шаг назад: работа с пользовательским типом

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

//ex‑gslist‑5.c

#include <glib.h>

typedef struct {

 char∗ name;

 int shoe_size;

} Person;

int main(int argc, char∗∗ argv) {

 GSList∗ list = NULL;

 Person∗ tom = (Person∗)malloc(sizeof(Person));

 tom‑>name = "Tom";

 tom‑>shoe_size = 12;

 list = g_slist_append(list, tom);

 Person∗ fred = g_new(Person, 1); // allocate memory for one Person struct

 fred‑>name = "Fred";

 fred‑>shoe_size = 11;

 list = g_slist_append(list, fred);

 printf("Tom's shoe size is '%d'\n", ((Person∗)list‑>data)‑>shoe_size);

 printf("The last Person's name is '%s'\n", ((Person∗)g_slist_last(list)‑>data)‑>name);

 g_slist_free(list);

 free(tom);

 g_free(fred);

 return 0;

}

∗∗∗∗∗ Output ∗∗∗∗∗

Tom's shoe size is '12'

The last Person's name is 'Fred'

Несколько замечаний о работе с GLib и пользовательскими типами:

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

В этом примере используется другой макрос GLib — макрос g_new — для создания экземпляра Fred``Person. Этот макрос просто расширяется, чтобы использовать malloc для выделения правильного объема памяти для данного типа, но это немного чище, чем ввод вызова функции malloc вручную.

Наконец, если вы собираетесь выделить память, вам нужно ее освободить. Вы можете видеть, как приведенный выше пример кода использует функцию GLib g_free, чтобы сделать именно это для экземпляра Fred``Person (поскольку он был выделен с помощью g_new). В большинстве случаев g_free просто обертывает обычную функцию free, но GLib также имеет функцию объединения памяти, которую могут использовать g_free и другие функции управления памятью.

Комбинирование, реверсирование и все такое

GSList поставляется с некоторыми удобными вспомогательными функциями, которые могут объединять и реверсировать списки. Вот как они работают:

//ex‑gslist‑6.c

#include <glib.h>

int main(int argc, char∗∗ argv) {

 GSList∗ list1 = NULL;

 list1 = g_slist_append(list1, "first");

 list1 = g_slist_append(list1, "second");

 GSList∗ list2 = NULL;

 list2 = g_slist_append(list2, "third");

 list2 = g_slist_append(list2, "fourth");

 GSList∗ both = g_slist_concat(list1, list2);

 printf("The third item in the concatenated list is '%s'\n", g_slist_nth_data(both, 2));

 GSList∗ reversed = g_slist_reverse(both);

 printf("The first item in the reversed list is '%s'\n", reversed‑>data);

 g_slist_free(reversed);

 return 0;

}

∗∗∗∗∗ Output ∗∗∗∗∗

The third item in the concatenated list is 'third'

The first item in the reversed list is 'fourth'

Как и ожидалось, два списка были объединены "голова к хвосту", так что первый элемент списка list2 стал третьим элементом нового списка. Обратите внимание, что элементы не копируются; они просто зацеплены, так что память нужно освобождать только один раз.

Кроме того, вы можете видеть, что вы можете распечатать первый элемент в перевернутом списке, используя только разыменование указателя (reversed->data). Поскольку каждый элемент в GSList является указателем на структуру GSList, вам не нужно вызывать функцию, чтобы получить первый элемент.

Простая итерация

Вот простой способ перебора содержимого GSList:

//ex‑gslist‑7.c

#include <glib.h>

int main(int argc, char∗∗ argv) {

 GSList∗ list = NULL, ∗iterator = NULL;

 list = g_slist_append(list, "first");

 list = g_slist_append(list, "second");

 list = g_slist_append(list, "third");

 for (iterator = list; iterator; iterator = iterator‑>next) {

  printf("Current item is '%s'\n", iterator‑>data);

 }

 g_slist_free(list);

 return 0;

}

∗∗∗∗∗ Output ∗∗∗∗∗

Current item is 'first'

Current item is 'second'

Current item is 'third'

Объект итератора — это просто переменная, объявленная как указатель на структуру GSList. Это кажется странным, но это то, что вы ожидаете. Поскольку односвязный список представляет собой набор структур GSList, итератор и список должны быть одного типа.

Обратите внимание, что в этом коде используется общая идиома использования GLib; он объявляет переменную итератора одновременно с объявлением самого GSList.

Наконец, выражение выхода из цикла for проверяет, равен ли итератор NULL. Это работает, поскольку NULL будет только после того, как цикл пройдет последний элемент в списке.

Расширенная итерация с функциями

Еще один способ выполнить итерацию по GSList — использовать функцию g_slist_foreach и указать функцию, которая будет вызываться для каждого элемента в списке.

//ex‑gslist‑8.c

#include <glib.h>

void print_iterator(gpointer item, gpointer prefix) {

 printf("%s %s\n", prefix, item);

}

void print_iterator_short(gpointer item) {

 printf("%s\n", item);

}

int main(int argc, char∗∗ argv) {

 GSList∗ list = g_slist_append(NULL, g_strdup("first"));

 list = g_slist_append(list, g_strdup("second"));

 list = g_slist_append(list, g_strdup("third"));

 printf("Iterating with a function:\n");

 g_slist_foreach(list, print_iterator, "‑‑>");

 printf("Iterating with a shorter function:\n");

 g_slist_foreach(list, (GFunc)print_iterator_short, NULL);

 printf("Now freeing each item\n");

 g_slist_foreach(list, (GFunc)g_free, NULL);

 g_slist_free(list);

 return 0;

}

∗∗∗∗∗ Output ∗∗∗∗∗

Iterating with a function:

‑‑> first

‑‑> second

‑‑> third

Iterating with a shorter function:

first

second

third

Now freeing each item

В этом примере много хорошего:

Слово GSList x = g_slist_append(NULL, [независимо]) позволяет объявить, инициализировать и добавить первый элемент в список одним махом.

Функция g_strdup удобна для дублирования строки; просто не забудьте освободить его, когда закончите с ним.

g_slist_foreach позволяет вам передать указатель, поэтому вы можете эффективно передать ему любой аргумент вместе с каждым элементом в списке. Например, вы можете передать аккумулятор и собрать информацию о каждом элементе списка. Единственное ограничение на итерирующую функцию заключается в том, что она принимает в качестве аргумента хотя бы один gpointer; вы можете увидеть, как работает print_interator_short, даже если он принимает только один аргумент.

Обратите внимание, что код освобождает все строки, используя встроенную функцию GLib в качестве аргумента для g_slist_foreach. Все, что вам нужно было сделать в этом случае, это преобразовать функцию g_free в GFunc, чтобы это работало. Обратите внимание, что вам все равно придется освобождать сам GSList с помощью отдельного вызова g_slist_free.

Сортировка с помощью GCompareFunc

Вы можете отсортировать GSList, предоставив функцию, которая знает, как сравнивать элементы в этом списке. В следующем примере показан один из способов сортировки списка строк:

//ex‑gslist‑9.c

#include <glib.h>

gint my_comparator(gconstpointer item1, gconstpointer item2) {

 return g_ascii_strcasecmp(item1, item2);

}

int main(int argc, char∗∗ argv) {

 GSList∗ list = g_slist_append(NULL, "Chicago");

 list = g_slist_append(list, "Boston");

 list = g_slist_append(list, "Albany");

 list = g_slist_sort(list, (GCompareFunc)my_comparator);

 printf("The first item is now '%s'\n", list‑>data);

 printf("The last item is now '%s'\n", g_slist_last(list)‑>data);

 g_slist_free(list);

 return 0;

}

∗∗∗∗∗ Output ∗∗∗∗∗

The first item is now 'Albany'

The last item is now 'Chicago'

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

Кроме того, поскольку многие другие функции GLib следуют этому шаблону, их можно легко делегировать. Фактически, в приведенном выше примере вы можете так же легко заменить вызов my_comparator чем-то вроде g_slist_sort(list, (GCompareFunc)g_ascii_strcasecmp), и вы получите те же результаты.

Поиск элемента

Есть несколько способов найти элемент в GSList. Вы уже видели, как можно просто перебирать содержимое списка, сравнивая каждый элемент, пока не найдете целевой элемент. Вы можете использовать g_slist_find, если у вас уже есть данные, которые вы ищете, и вы просто хотите добраться до нужного места в списке. Наконец, вы можете использовать g_slist_find_custom, который позволяет использовать функцию для проверки каждого элемента в списке. g_slist_find и g_slist_find_custom показаны ниже:

//ex‑gslist‑10.c

#include <glib.h>

gint my_finder(gconstpointer item) {

 return g_ascii_strcasecmp(item, "second");

}

int main(int argc, char∗∗ argv) {

 GSList∗ list = g_slist_append(NULL, "first");

 list = g_slist_append(list, "second");

 list = g_slist_append(list, "third");

 GSList∗ item = g_slist_find(list, "second");

 printf("This should be the 'second' item: '%s'\n", item‑>data);

 item = g_slist_find_custom(list, NULL, (GCompareFunc)my_finder);

 printf("Again, this should be the 'second' item: '%s'\n", item‑>data);

 item = g_slist_find(list, "delta");

 printf("'delta' is not in the list, so we get: '%s'\n", item ? item‑>data : "(null)");

 g_slist_free(list);

 return 0;

}

∗∗∗∗∗ Output ∗∗∗∗∗

This should be the 'second' item: 'second'

Again, this should be the 'second' item: 'second'

'delta' is not in the list, so we get: '(null)'

Обратите внимание, что g_slist_find_custom также принимает указатель на что-либо в качестве второго аргумента, поэтому при необходимости вы можете что-то передать чтобы помочь функции поиска. Кроме того, функция GCompare является последним аргументом, а не вторым аргументом, поскольку она находится в g_slist_sort. Наконец, неудачный поиск возвращает NULL.

Расширенное добавление со вставкой

Теперь, когда вы видели GCompareFunc несколько раз, некоторые из наиболее интересных операций вставки станут более понятными. Элементы можно вставлять в заданную позицию с помощью g_slist_insert, перед указанным элементом с помощью g_slist_insert_before и в отсортированном порядке с помощью g_slist_insert_sorted. Вот как это выглядит:

//ex‑gslist‑11.c

#include <glib.h>

int main(int argc, char∗∗ argv) {

 GSList∗ list = g_slist_append(NULL, "Anaheim "), ∗iterator = NULL;

 list = g_slist_append(list, "Elkton ");

 printf("Before inserting 'Boston', second item is: '%s'\n", g_slist_nth(list, 1)‑>data);

 g_slist_insert(list, "Boston ", 1);

 printf("After insertion, second item is: '%s'\n", g_slist_nth(list, 1)‑>data);

 list = g_slist_insert_before(list, g_slist_nth(list, 2), "Chicago ");

 printf("After an insert_before, third item is: '%s'\n", g_slist_nth(list, 2)‑>data);

 list = g_slist_insert_sorted(list, "Denver ", (GCompareFunc)g_ascii_strcasecmp);

 printf("After inserting 'Denver', here's the final list:\n");

 g_slist_foreach(list, (GFunc)printf, NULL);

 g_slist_free(list);

 return 0;

}

∗∗∗∗∗ Output ∗∗∗∗∗

Before inserting 'Boston', second item is: 'Elkton '

After insertion, second item is: 'Boston '

After an insert_before, third item is: 'Chicago '

After inserting 'Denver', here's the final list:

Anaheim Boston Chicago Denver Elkton

Поскольку g_slist_insert_sorted принимает GCompareFunc, встроенную функцию GLib легко использовать повторно. g_ascii_strcasecmp. И теперь вы можете понять, почему в конце каждого элемента есть дополнительный пробел; это сделано для того, чтобы другой пример g_slist_foreach мог прокрасться туда в конце примера кода, на этот раз с printf в качестве GFunc.

Реальное использование односвязных списков

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

Gaim использует GSLlists для хранения текущих разговоров и для различных целей в большинстве плагинов:

gaim-1.2.1/src/away.c использует отсортированный GSList для хранения "сообщений об отсутствии" (сообщений, полученных, когда клиент находится в автономном режиме). Он использует пользовательский GCompareFunc, sort_awaymsg_list, чтобы сортировать эти сообщения по имени отправителя.

gaim-1.2.1/src/protocols/gg/gg.c использует GSList для хранения списка разрешенных учетных записей; затем он использует пользовательский поиск, чтобы убедиться, что учетная запись находится в этом списке. Пользовательский поиск просто делегирует g_ascii_strcasecmp, так что вполне возможно, что его можно полностью исключить и передать g_ascii_strcasecmp напрямую в g_slist_find_custom.

Evolution также использует множество GSLlist:

evolution-data-server-1.0.2/calendar/libecal/e-cal-component.c использует GSList для хранения участников собрания. В одном случае он создает GSList, повторно вызывая g_slist_prepend и заканчивая g_slist_reverse, чтобы получить элементы в нужном порядке. Как упоминалось ранее, это быстрее, чем добавление элементов с помощью g_slist_append.

evolution-2.0.2/addressbook/gui/contact-editor/e-contact-editor.c использует g_slist_find в своего рода защитном предложении; он использует его в обработчике сигнала, чтобы гарантировать, что EContactEditor, полученный в обратном вызове сигнала, все еще существует, прежде чем передать его в качестве аргумента функции.

GIMP использует GSList и в некоторых приятных случаях:

gimp-2.2.4/plug-ins/maze/algorithms.c использует GSList для отслеживания ячеек в алгоритме генерации лабиринта.

gimp-2.2.4/app/widgets/gimpclipboard.c использует GSList для хранения форматов пиксельного буфера буфера обмена (таких как PNG и JPEG); он передает пользовательскую функцию GCompareFunc в g_slist_sort.

gimp-2.2.4/app/core/gimppreviewcache.c использует GSList как своего рода очередь на основе размера; он содержит предварительные просмотры изображений в GSList и использует g_slist_insert_sorted для вставки меньших изображений в первую очередь. Другая функция в том же файле очищает кеш, перебирая тот же GSList и сравнивая каждый элемент по площади поверхности, чтобы найти наименьший элемент для удаления.