Использование коллекций GLib

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

Оригинал статьи: https://www.ibm.com/developerworks/linux/tutorials/l-glib/

Содержание:

Предпосылки

Чтобы получить максимальную отдачу от этого руководства, вы должны быть знакомы с 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 также определяет ряд структур данных (и связанных с ними операций), в том числе:

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

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

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

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

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

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

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

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

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

Встроенные структуры данных

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

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

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

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

Алгоритмическая сложность (кратко)

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

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

  • 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/incl \
    -lglib-2.0  ex-compile.c \
    -o ex-compile

И запустите его, чтобы увидеть ожидаемый результат:

$ ./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

Обратите внимание, что теперь вам больше не нужно указывать пути к заголовочным файлам GLib; Об этом --cflags опция --cflags в --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/includ

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

Реальное использование GLib

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

  • Gaim - это популярный клиент для обмена мгновенными сообщениями, который загружается из SourceForge более четверти миллиона раз в месяц.
  • GIMP (программа для работы с графическими изображениями) послужила отправной точкой для самого GLib; Это широко используемая программа обработки изображений, которая находится в стадии разработки с 1996 года.
  • Evolution - отличный менеджер персональной информации (PIM), который отслеживает электронную почту, контакты, задачи и встречи.

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

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

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

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

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

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

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

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

GSList может содержать два типа данных: целые числа или указатели. Но это действительно означает, что вы можете поместить практически все в GSList. Например, если вы хотите GSList «короткого» типа данных, вы можете просто поместить указатели на шорты в 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;
}

Вывод программы:

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

Пара замечаний по приведенному выше коду:

  • Большинство функций GLib имеют формат g_(container name)_(function name) . Таким образом, чтобы получить длину 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;
}

Вывод программы:

The list is now 2 items long
The list is now 1 items lon

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

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

Удаление дубликатов

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

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;
}

Вывод программы:

The list is now 5 items long
The list is now 2 items lon

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

Выборка элементов

Когда в 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;
}

Вывод программы:

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;
}

Вывод программы:

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;
}

Вывод программы:

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;
}

Вывод программы:

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;
}

Вывод программы:

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, [whatever]) позволяет вам объявить, инициализировать и добавить первый элемент в список одним махом.
  • Функция g_strdup удобна для дублирования строки; просто не забудьте освободить его, как только вы закончите с этим.
  • g_slist_foreach позволяет передавать указатель, поэтому вы можете эффективно 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;
}

Вывод программы:

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;
}

Вывод программы:

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;
}

Вывод программы:

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 пример g_slist_foreach может проникнуть туда в конце примера кода, на этот раз с printf в качестве GFunc .

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

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

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

  • gaim-1.2.1 /src/away.c использует отсортированный список GSList для хранения «отсутствующих сообщений» (сообщений, полученных, когда клиент находится в автономном режиме). Он использует собственный GCompareFunc , sort_awaymsg_list чтобы хранить эти сообщения отсортированными по имени отправителя.
  • gaim-1.2.1 /src/protocol/gg/gg.c использует GSList для хранения списка разрешенных учетных записей; Затем он использует пользовательский поиск, чтобы убедиться, что учетная запись находится в этом списке. Пользовательский искатель просто делегирует g_ascii_strcasecmp , так что вполне возможно, что он может быть полностью исключен и g_ascii_strcasecmp передан непосредственно в g_slist_find_custom .

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

  • 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 полученный им при EContactEditor сигнала, все еще присутствует, прежде чем передать его в качестве аргумента функции.

GIMP также использует GSList:

  • gimp-2.2.4 / plug-ins / maze /gorithms.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 для g_slist_insert_sorted вставки меньших изображений. Другая функция в том же файле обрезает кэш, перебирая тот же GSList и сравнивая каждый элемент по площади, чтобы найти наименьший из них для удаления.

Двусвязанные списки

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

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

GLib содержит реализацию двусвязного списка, которая называется GList . Большинство операций в GList аналогичны операциям в GSList. Мы рассмотрим несколько примеров базового использования, а затем добавим операции, которые допускает GList.

Основные операции двусвязных списков

Вот некоторые из общих операций, которые вы можете делать с GList:

//ex-glist-1.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GList* list = NULL;
    list = g_list_append(list, "Austin ");
    printf("The first item is '%s'\n", list->data);

    list = g_list_insert(list, "Baltimore ", 1);
    printf("The second item is '%s'\n", g_list_next(list)->data);

    list = g_list_remove(list, "Baltimore ");
    printf("After removal of 'Baltimore', the list length is %d\n", g_list_length(list));

    GList* other_list = g_list_append(NULL, "Baltimore ");
    list = g_list_concat(list, other_list);
    printf("After concatenation: ");

    g_list_foreach(list, (GFunc)printf, NULL);
    list = g_list_reverse(list);
    printf("\nAfter reversal: ");

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

    g_list_free(list);

    return 0;
}

Вывод программы:

The first item is 'Austin '
The second item is 'Baltimore '
After removal of 'Baltimore', the list length is 1
After concatenation: Austin Baltimore
After reversal: Baltimore Austin

Приведенный выше код, вероятно, выглядит довольно знакомым! Все вышеперечисленные операции также присутствуют в GSList; единственное отличие GList состоит в том, что имена функций начинаются с g_list а не с g_slist . И, конечно же, все они принимают указатель на структуру GList, а не указатель на структуру GSList.

Лучшая навигация

Теперь, когда вы увидели некоторые базовые операции GList, вот некоторые операции, которые возможны только потому, что каждый узел в GList имеет ссылку на предыдущий узел:

//ex-glist-2.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GList* list = g_list_append(NULL, "Austin ");
    list = g_list_append(list, "Bowie ");
    list = g_list_append(list, "Charleston ");

    printf("Here's the list: ");
    g_list_foreach(list, (GFunc)printf, NULL);

    GList* last = g_list_last(list);
    printf("\nThe first item (using g_list_first) is '%s'\n", g_list_first(last)->data);
    printf("The next-to-last item is '%s'\n", g_list_previous(last)->data);
    printf("The next-to-last item is '%s'\n", g_list_nth_prev(last, 1)->data);

    g_list_free(list);

    return 0;
}

Вывод программы:

Here's the list: Austin Bowie Charleston
The first item (using g_list_first) is 'Austin '
The next-to-last item is 'Bowie '
The next-to-last item is 'Bowie '

Ничего удивительного, но несколько замечаний:

  • Второй аргумент g_list_nth_prev - это целое число, указывающее, как далеко назад вы хотите пройти. Если вы передадите значение, выходящее за пределы GList, подготовьтесь к сбою.
  • g_list_first - g_list_first O (n); он начинается в указанном узле и ищет в обратном направлении, пока не найдет начало GList. Приведенный выше пример является наихудшим сценарием, потому что обход начинается в конце списка. g_list_last - это O (n) по той же причине.

Удаление узлов с помощью ссылок

Вы уже видели, как можно удалить узел из списка, если у вас есть указатель на данные, которые он содержит; g_list_remove делает это красиво. Если у вас есть указатель на сам узел, вы можете удалить этот узел непосредственно в быстрой операции O (1):

//ex-glist-3.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GList* list = g_list_append(NULL, "Austin ");
    list = g_list_append(list, "Bowie ");
    list = g_list_append(list, "Chicago ");

    printf("Here's the list: ");    
    g_list_foreach(list, (GFunc)printf, NULL);

    GList* bowie = g_list_nth(list, 1);
    list = g_list_remove_link(list, bowie); 
    g_list_free_1(bowie);

    printf("\nHere's the list after the remove_link call: ");
    g_list_foreach(list, (GFunc)printf, NULL);

    list = g_list_delete_link(list, g_list_nth(list, 1));

    printf("\nHere's the list after the delete_link call: ");   
    g_list_foreach(list, (GFunc)printf, NULL);

    g_list_free(list);

    return 0;
}

Вывод программы:

Here's the list: Austin Bowie Chicago
Here's the list after the remove_link call: Austin Chicago
Here's the list after the delete_link call: Austin

Поэтому, если у вас есть указатель на узел, а не на данные узла, вы можете удалить этот узел, используя g_list_remove_link.

После удаления вам нужно явно освободить его, используя g_list_free_1, что делает то, что подразумевает его имя: он освобождает один узел. Как обычно, вам нужно держаться за возвращаемое значение, g_list_remove_linkпоскольку это новое начало списка.

Наконец, если все, что вы хотите сделать, это удалить узел и освободить его, вы можете сделать это за один шаг с помощью вызова g_list_delete_link.

Те же функции существуют и для GSList; просто замените g_listна g_slistи примените всю вышеуказанную информацию.

Индексы и позиции

Если вы просто хотите найти позицию элемента в GList, у вас есть два варианта. Вы можете использовать g_list_index, который ищет элемент, используя данные в нем, или вы можете использовать g_list_position, который использует указатель на узел. Этот пример иллюстрирует оба:

//ex-glist-4.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GList* list = g_list_append(NULL, "Austin ");
    list = g_list_append(list, "Bowie ");
    list = g_list_append(list, "Bowie ");
    list = g_list_append(list, "Cheyenne ");

    printf("Here's the list: ");

    g_list_foreach(list, (GFunc)printf, NULL);
    printf("\nItem 'Bowie' is located at index %d\n", g_list_index(list, "Bowie "));
    printf("Item 'Dallas' is located at index %d\n", g_list_index(list, "Dallas"));

    GList* last = g_list_last(list);
    printf("Item 'Cheyenne' is located at index %d\n", g_list_position(list, last));

    g_list_free(list);

    return 0;
}

Вывод программы:

Here's the list: Austin Bowie Bowie Cheyenne
Item 'Bowie' is located at index 1
Item 'Dallas' is located at index -1
Item 'Cheyenne' is located at index 3

Обратите внимание, что g_list_indexвозвращает значение, -1если он не может найти данные. И если есть два узла с одинаковым значением данных, g_list_indexвозвращает индекс первого вхождения. g_list_positionтакже возвращает, -1если не может найти указанный узел.

Опять же, эти методы также присутствуют в GSList под разными именами.

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

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

Gaim использует много GLists:

  • gaim-1.2.1 / plugins / gevolution / add_buddy_dialog.c использует вызов для g_list_foreachосвобождения ссылок на каждый контакт при закрытии диалогового окна «добавить собеседника».
  • gaim-1.2.1 / src / account.c использует GList для хранения всех учетных записей; он использует, g_list_findчтобы убедиться, что учетная запись еще не существует, прежде чем добавить его с g_list_append.

Использование Evolution GList:

  • evolution-2.0.2 / filter / filter-rule.c использует GList для хранения частей (таких как строка темы для проверки) правила фильтрации почты; filter_rule_finaliseиспользует g_list_foreachдля выпуска ссылок на эти части.
  • evolution-2.0.2 / calendar / gui / alarm-notify / alarm.c использует GList для хранения сигналов тревоги; queue_alarmиспользуется g_list_insert_sortedдля вставки новых сигналов тревоги в правильное место, используя пользовательский GCompareFunc.

Использование GIMP:

  • gimp-2.2.4 / app / file / gimprecentlist.c использует GList для хранения недавно использованных файлов; gimp_recent_list_readчитает имена файлов из дескриптора файла XML и вызывает g_list_reverseперед возвратом GList.
  • gimp-2.2.4 / app / vectors / gimpbezierstroke.c использует GLists для хранения якорей инсульта; gimp_bezier_stroke_connect_strokeиспользуется, g_list_concatчтобы помочь соединить один штрих к другому.

Хеш-таблицы

Концепции хеш-таблиц

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

Так же, как словарь языка связывает слово с определением, хеш-таблицы используют ключ для однозначной идентификации значения . Хеш-таблицы могут очень быстро выполнять операции вставки, поиска и удаления ключа; на самом деле, при правильном использовании, все они могут быть с постоянным временем, то есть O (1) - операциями. Это гораздо лучше, чем поиск или удаление элемента из упорядоченного списка, операция O (n).

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

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

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

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

Некоторые основные операции с хеш-таблицами

Вот несколько примеров, чтобы поставить некоторые колеса на предыдущей теории:

//ex-ghashtable-1.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal);
    g_hash_table_insert(hash, "Virginia", "Richmond");
    g_hash_table_insert(hash, "Texas", "Austin");
    g_hash_table_insert(hash, "Ohio", "Columbus");

    printf("There are %d keys in the hash\n", g_hash_table_size(hash));
    printf("The capital of Texas is %s\n", g_hash_table_lookup(hash, "Texas"));

    gboolean found = g_hash_table_remove(hash, "Virginia");

    printf("The value 'Virginia' was %sfound and removed\n", found ? "" : "not ");
    g_hash_table_destroy(hash);

    return 0;
}

Вывод программы:

There are 3 keys in the hash
The capital of Texas is Austin
The value 'Virginia' was found and removed

Там много нового, поэтому некоторые заметки:

  • Вызов g_hash_table_newуказывает, что эта хеш-таблица будет использовать строки в качестве ключей. Функции g_str_hashи g_str_equalвстроены в GLib, так как это общий случай использования. Другие встроенные функции хеширования / равенства: g_int_hash/ g_int_equalдля использования целых чисел в качестве ключей и g_direct_hash/ g_direct_equalдля использования указателей в качестве ключей.
  • GLists и GSLists имеют g_[container]_freeфункцию для их очистки; GHashTable может быть очищен с g_hash_table_destroy.
  • Когда вы пытаетесь удалить пару ключ / значение g_hash_table_remove, вы получаете gbooleanвозвращаемое значение, указывающее, был ли ключ найден и удален. gbooleanПростой кросс-платформенная реализация GLib истинного / ложного значения.
  • g_hash_table_size возвращает количество ключей в хеш-таблице.

Вставка и замена значений

Когда вы вставляете ключ с помощью g_hash_table_insert, GHashTable сначала проверит, существует ли этот ключ. Если это так, значение будет заменено, но не ключ. Если вы хотите заменить и ключ, и значение, вам нужно использовать g_hash_table_replace. Это небольшая разница, поэтому оба проиллюстрированы ниже:

//ex-ghashtable-2.c
#include <glib.h>

static char* texas_1, *texas_2;

void key_destroyed(gpointer data) {
    printf("Got a key destroy call for %s\n", data == texas_1 ? "texas_1" : "texas_2");
}

int main(int argc, char** argv) 
{
    GHashTable* hash = g_hash_table_new_full(
        g_str_hash, g_str_equal, 
        (GDestroyNotify)key_destroyed, NULL);

    texas_1 = g_strdup("Texas");
    texas_2 = g_strdup("Texas");

    g_hash_table_insert(hash, texas_1, "Austin");
    printf("Calling insert with the texas_2 key\n");

    g_hash_table_insert(hash, texas_2, "Houston");
    printf("Calling replace with the texas_2 key\n");

    g_hash_table_replace(hash, texas_2, "Houston");
    printf("Destroying hash, so goodbye texas_2\n");

    g_hash_table_destroy(hash);
    g_free(texas_1);
    g_free(texas_2);

    return 0;
}

Вывод программы:

Calling insert with the texas_2 key
Got a key destroy call for texas_2
Calling replace with the texas_2 key
Got a key destroy call for texas_1
Destroying hash, so goodbye texas_2
Got a key destroy call for texas_2

Из результатов видно, что при g_hash_table_insertпопытке вставить ту же строку ( Texas), что и существующий ключ, GHashTable просто освобождает переданный ключ ( texas_2) и оставляет текущий ключ ( texas_1) на месте. Но когда g_hash_table_replaceсделали то же самое, texas_1ключ был уничтожен, и texas_2ключ был использован вместо него. Еще несколько заметок:

  • Когда вы создаете новый GHashTable, вы можете использовать g_hash_table_fullдля предоставления GDestroyNotifyреализации, которая будет вызываться при уничтожении ключа. Это позволяет вам выполнять любые очистки ресурса для этого ключа или, в этом случае, видеть, что действительно происходит с изменением ключа.
  • Вы видели g_strdupв разделе GSList; здесь он используется для выделения двух копий строки Texas. Вы можете видеть, что GHashTable функционирует g_str_hashи g_str_equalправильно обнаруживает, что фактические строки были эквивалентны, даже если переменные были указателями на различные области памяти. И вы должны были освободить texas_1и texas_2в конце функции, чтобы избежать утечки памяти. Конечно, в этом случае это не имело бы значения с момента выхода из программы, но в любом случае лучше прибраться.

Итерация пар ключ / значение

Иногда вам нужно перебрать все пары ключ / значение. Вот как это сделать, используя g_hash_table_foreach:

//ex-ghashtable-3.c
#include <glib.h>

void iterator(gpointer key, gpointer value, gpointer user_data) {
    printf(user_data, *(gint*)key, value);
}

int main(int argc, char** argv) 
{
    GHashTable* hash = g_hash_table_new(g_int_hash, g_int_equal);

    gint *k_one = g_new(gint, 1), 
        *k_two = g_new(gint, 1), 
        *k_three = g_new(gint, 1);

    *k_one = 1, 
    *k_two = 2, 
    *k_three = 3;

    g_hash_table_insert(hash, k_one, "one");
    g_hash_table_insert(hash, k_two, "four");
    g_hash_table_insert(hash, k_three, "nine");

    g_hash_table_foreach(hash, (GHFunc)iterator, "The square of %d is %s\n");
    g_hash_table_destroy(hash);

    return 0;
}

Вывод программы:

The square of 1 is one
The square of 2 is four
The square of 3 is nine

В этом примере есть несколько маленьких поворотов:

  • Вы можете видеть это, используя предоставляемые GLib хеш-функции g_int_hashи g_int_equalпозволяя вам использовать указатели на целые числа в качестве ключей. И этот пример использует GLib кросс-платформенную абстракцию для целых числа: gint.
  • g_hash_table_foreachочень похоже на функции g_slist_foreachи g_list_foreachвы уже видели. Разница лишь в том, что GHFuncпереданный g_hash_table_foreachпринимает три аргумента, а не два. В этом случае вы передали строку, которая будет использоваться для форматирования печати ключа и значения в качестве третьего аргумента. Кроме того, хотя ключи оказались в том порядке, в котором они были вставлены в этом примере, нет гарантии, что порядок вставки ключей будет сохранен.

Нахождение Элемента

Чтобы найти конкретное значение, используйте g_hash_table_findфункцию. Эта функция позволяет вам просматривать каждую пару ключ / значение, пока не найдете нужную. Вот пример:

//ex-ghashtable-4.c
#include <glib.h>

void value_destroyed(gpointer data) {
    printf("Got a value destroy call for %d\n", GPOINTER_TO_INT(data));
}

gboolean finder(gpointer key, gpointer value, gpointer user_data) {
    return (GPOINTER_TO_INT(key) + GPOINTER_TO_INT(value)) == 42;
}

int main(int argc, char** argv) 
{
    GHashTable* hash = g_hash_table_new_full(
        g_direct_hash, g_direct_equal, NULL, 
        (GDestroyNotify)value_destroyed);

    g_hash_table_insert(hash, GINT_TO_POINTER(6), GINT_TO_POINTER(36));
    g_hash_table_insert(hash, GINT_TO_POINTER(10), GINT_TO_POINTER(12));
    g_hash_table_insert(hash, GINT_TO_POINTER(20), GINT_TO_POINTER(22));

    gpointer item_ptr = g_hash_table_find(hash, (GHRFunc)finder, NULL);
    gint item = GPOINTER_TO_INT(item_ptr);

    printf("%d + %d == 42\n", item, 42-item);

    g_hash_table_destroy(hash);

    return 0;
}

Вывод программы:

36 + 6 == 42
Got a value destroy call for 36
Got a value destroy call for 22
Got a value destroy call for 12

Как обычно, этот пример представляет g_hash_table_findи несколько других вещей:

  • g_hash_table_findвозвращает первое значение, для которого GHRFuncвозвращает TRUE. Если GHRFuncне возвращает TRUE для какого-либо элемента (например, не найдено подходящего элемента), возвращается NULL.
  • Этот пример демонстрирует другой набор встроенных функций хеширования GLib: g_direct_hashи g_direct_equal. Этот набор функций позволяет использовать указатели в качестве ключей, но не пытается интерпретировать данные, стоящие за указателями. А поскольку вы помещаете указатели в таблицу GHashTable, вам нужно использовать некоторые удобные макросы GLib ( GINT_TO_POINTERи GPOINTER_TO_INT) для преобразования целых чисел в указатели и из них.
  • Наконец, этот пример создает GHashTable и предоставляет ему функцию GDestroyNotifyобратного вызова, чтобы вы могли видеть, когда элементы уничтожены. Большую часть времени вы захотите освободить часть памяти в такой функции, но, например, эта реализация просто выводит сообщение.

Хитрый бизнес: воровство со стола

Иногда вам может понадобиться удалить элемент из GHashTable без обратного вызова каких-либо GDestroyNotifyфункций, которые были предоставлены GHashTable. Вы можете сделать это либо с использованием определенного ключа, g_hash_table_stealлибо для всех ключей, которые соответствуют критерию g_hash_table_foreach_steal.

//ex-ghashtable-5.c
#include <glib.h>

gboolean wide_open(gpointer key, gpointer value, gpointer user_data) {
    return TRUE;
}

void key_destroyed(gpointer data) {
    printf("Got a GDestroyNotify callback\n");
}

int main(int argc, char** argv) 
{
    GHashTable* hash = g_hash_table_new_full(
        g_str_hash, g_str_equal,
        (GDestroyNotify)key_destroyed,
        (GDestroyNotify)key_destroyed);

    g_hash_table_insert(hash, "Texas", "Austin");
    g_hash_table_insert(hash, "Virginia", "Richmond");
    g_hash_table_insert(hash, "Ohio", "Columbus");
    g_hash_table_insert(hash, "Oregon", "Salem");
    g_hash_table_insert(hash, "New York", "Albany");

    printf("Removing New York, you should see two callbacks\n");
    g_hash_table_remove(hash, "New York");

    if (g_hash_table_steal(hash, "Texas")) {
        printf("Texas has been stolen, %d items remaining\n", g_hash_table_size(hash));
    }

    printf("Stealing remaining items\n");
    g_hash_table_foreach_steal(hash, (GHRFunc)wide_open, NULL);

    printf("Destroying the GHashTable, but it's empty, so no callbacks\n");
    g_hash_table_destroy(hash);

    return 0;
}

Вывод программы:

Removing New York, you should see two callbacks
Got a GDestroyNotify callback
Got a GDestroyNotify callback
Texas has been stolen, 3 items remaining
Stealing remaining items
Destroying the GHashTable, but it's empty, so no callbacks

Расширенный поиск: поиск ключа и значения

GHashTable предоставляет g_hash_table_lookup_extendedфункцию для тех случаев, когда вам нужно извлечь ключ и его значение из таблицы. Это очень похоже g_hash_table_lookup, но принимает еще два аргумента. Это аргументы "вне"; то есть они являются двояко-косвенными указателями, которые будут указывать на данные, когда они находятся. Вот как они работают:

//ex-ghashtable-6.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal);

    g_hash_table_insert(hash, "Texas", "Austin");
    g_hash_table_insert(hash, "Virginia", "Richmond");
    g_hash_table_insert(hash, "Ohio", "Columbus");

    char* state = NULL;
    char* capital = NULL;
    char** key_ptr = &state;
    char** value_ptr = &capital;

    gboolean result = g_hash_table_lookup_extended(
        hash, "Ohio", (gpointer*)key_ptr, (gpointer*)value_ptr);

    if (result) {
        printf("Found that the capital of %s is %s\n", capital, state);
    }

    result = g_hash_table_lookup_extended(
        hash, "Vermont", (gpointer*)key_ptr, (gpointer*)value_ptr)

    if (!result) {
        printf("Couldn't find Vermont in the hash table\n");
    }

    g_hash_table_destroy(hash);

    return 0;
}

Вывод программы:

Found that the capital of Columbus is Ohio
Couldn't find Vermont in the hash table

Код для инициализации переменной, которая будет получать данные ключ / значение, немного сложен, но его восприятие как способа возврата более одного значения из функции может сделать его более понятным. Обратите внимание, что если вы передадите NULL для двух последних аргументов, g_hash_table_lookup_extendedон все равно будет работать, он просто не заполнит аргументы NULL.

Несколько значений для каждого ключа

До сих пор вы видели хэши, которые имеют только одно значение для каждого ключа. Но иногда вам нужно держать несколько значений для ключа. Когда возникает такая необходимость, использование GSList в качестве значения и добавление новых значений в этот GSList часто является хорошим решением. Тем не менее, это займет немного больше работы, как вы можете видеть в этом примере:

//ex-ghashtable-7.c
#include <glib.h>

void print(gpointer key, gpointer value, gpointer data) {
    printf("Here are some cities in %s: ", key);
    g_slist_foreach((GSList*)value, (GFunc)printf, NULL);
    printf("\n");
}

void destroy(gpointer key, gpointer value, gpointer data) {
    printf("Freeing a GSList, first item is %s\n", ((GSList*)value)->data);
    g_slist_free(value);
}

int main(int argc, char** argv) 
{
    GHashTable* hash = g_hash_table_new(g_str_hash, g_str_equal);
    g_hash_table_insert(hash, "Texas",

    g_slist_append(g_hash_table_lookup(hash, "Texas"), "Austin "));
    g_hash_table_insert(hash, "Texas",

    g_slist_append(g_hash_table_lookup(hash, "Texas"), "Houston "));
    g_hash_table_insert(hash, "Virginia",

    g_slist_append(g_hash_table_lookup(hash, "Virginia"), "Richmond "));
    g_hash_table_insert(hash, "Virginia",

    g_slist_append(g_hash_table_lookup(hash, "Virginia"), "Keysville "));

    g_hash_table_foreach(hash, print, NULL);
    g_hash_table_foreach(hash, destroy, NULL);

    g_hash_table_destroy(hash);

    return 0;
}

Вывод программы:

Here are some cities in Texas: Austin Houston
Here are some cities in Virginia: Richmond Keysville
Freeing a GSList, first item is Austin
Freeing a GSList, first item is Richmond

Код «вставить новый город» в приведенном выше примере использует тот факт, что g_slist_appendв качестве допустимого аргумента для GSList используется NULL; не нужно проверять, является ли это первый город, добавляемый в список для данного штата.

Когда GHashTable уничтожен, вы должны помнить, чтобы освободить все эти списки GSL, прежде чем освободить саму хеш-таблицу. Обратите внимание, что это было бы немного более запутанным, если бы вы не использовали статические строки в этих списках; в этом случае вам нужно будет освободить каждый элемент в каждом списке GSList перед освобождением самого списка. В этом примере показано, насколько полезными foreachмогут быть различные функции - они могут сэкономить при печати.

Реальное использование хеш-таблиц

Вот пример того, как используются GHashTables.

В gaim:

  • gaim-1.2.1 / src / buddyicon.c использует GHashTable для отслеживания «значков друзей». Ключ - это имя пользователя собеседника, а значение - указатель на GaimBuddyIconструктуру.
  • gaim-1.2.1 / src / protocol / yahoo / yahoo.c - это единственное место в этих трех приложениях g_hash_table_steal. Он используется g_hash_table_stealкак часть раздела кода, который создает сопоставление имени учетной записи и списка друзей.

В эволюции:

  • evolution-2.0.2 / smime / gui / certificate-manager.c использует GHashTable для отслеживания корней сертификатов S / MIME; ключ - это название организации, а значение - указатель на GtkTreeIter.
  • evolution-data-server-1.0.2 / calendar / libecal / e-cal.c использует GHashTable для отслеживания часовых поясов; ключ - строка идентификатора часового пояса, а значение - строковое представление icaltimezoneструктуры.

В GIMP:

  • gimp-2.2.4 / libgimp / gimp.c использует GHashTable для отслеживания временных процедур. При единственном использовании g_hash_table_lookup_extendedво всей кодовой базе GIMP он использует вызов для g_hash_table_lookup_extendedпоиска процедуры, чтобы он мог сначала освободить память хеш-ключа перед удалением процедуры.
  • gimp-2.2.4 / app / core / gimp.c использует GHashTable для хранения изображений; ключ - это идентификатор изображения (целое число), а значение - указатель на GimpImageструктуру.

Массивы

Концепции массивов

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

Он называется GArray и предоставляет индексированную упорядоченную коллекцию одного типа, которая увеличивается по мере необходимости для размещения новых элементов.

В чем преимущество массива перед связанным списком? С одной стороны, индексированный доступ. То есть, если вы хотите получить пятый элемент в массиве, вы можете просто вызвать функцию для извлечения этого элемента за постоянное время; нет необходимости итерировать до этой точки вручную, что было бы операцией O (n). Массив знает свой собственный размер, поэтому запрос размера - это операция O (1), а не O (n).

Основные операции с массивами

Вот некоторые из основных способов получить данные в GArray и из него:

//ex-garray-1.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GArray* a = g_array_new(FALSE, FALSE, sizeof(char*));
    char* first = "hello", *second = "there", *third = "world";

    g_array_append_val(a, first);
    g_array_append_val(a, second);
    g_array_append_val(a, third);

    printf("There are now %d items in the array\n", a->len);
    printf("The first item is '%s'\n", g_array_index(a, char*, 0));
    printf("The third item is '%s'\n", g_array_index(a, char*, 2));

    g_array_remove_index(a, 1); 
    printf("There are now %d items in the array\n", a->len);

    g_array_free(a, FALSE);

    return 0;
}

Вывод программы:

There are now 3 items in the array
The first item is 'hello'
The third item is 'world'
There are now 2 items in the array

Некоторые моменты для размышления:

  • Есть несколько вариантов, которые следует учитывать при создании GArray. В приведенном выше примере первые два аргумента g_array_newуказывают, должен ли массив иметь нулевой элемент в качестве терминатора и должны ли новые элементы в массиве автоматически устанавливаться на ноль. Третий аргумент сообщает массиву, какой тип он будет содержать. В этом случае массив создается для хранения типа char*; помещение чего-либо еще в массив приведет к ошибкам сегмента.
  • g_array_append_valэто макрос, разработанный таким образом, что он не принимает буквальные значения, поэтому вы не можете вызывать его g_array_append_val(a, 42). Вместо этого значение должно быть помещено в переменную, и эта переменная передана в g_array_append_val. В качестве утешения за неудобства, g_array_append_valочень быстро.
  • GArray - это структура с переменной-членом len, поэтому, чтобы получить размер массива, вы можете просто обратиться к этой переменной напрямую; нет необходимости в вызове функции.
  • GArray растет в силах двух. То есть, если GArray содержит четыре элемента, а вы добавляете еще один, он внутренне создаст еще один GArray из восьми элементов, скопирует в него четыре существующих элемента и затем добавит новый элемент. Этот процесс изменения размера занимает много времени, поэтому, если вы знаете, что у вас будет определенное количество элементов, более эффективно создать GArray, предварительно выделенный для желаемого размера.

Больше новых / бесплатных опций

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

//ex-garray-2.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GArray* a = g_array_sized_new(TRUE, TRUE, sizeof(int), 16);
    printf("Array preallocation is hidden, so array size == %d\n", a->len);
    printf("Array was init'd to zeros, so 3rd item is = %d\n", g_array_index(a, int, 2));
    g_array_free(a, FALSE);

    // this creates an empty array, then resizes it to 16 elements
    a = g_array_new(FALSE, FALSE, sizeof(char));
    g_array_set_size(a, 16);
    g_array_free(a, FALSE);

    a = g_array_new(FALSE, FALSE, sizeof(char));
    char* x = g_strdup("hello world");
    g_array_append_val(a, x);
    g_array_free(a, TRUE);

    return 0;
}

Вывод программы:

Array preallocation is hidden, so array size == 0
Array was init'd to zeros, so 3rd item is = 0

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

Больше способов добавить данные

До сих пор вы видели данные, добавленные в массив с g_array_append_val. Но есть и другие способы получить данные в массив, как показано ниже:

//ex-garray-3.c
#include <glib.h>

void prt(GArray* a) {
    printf("Array holds: ");
    int i;
    for (i = 0; i < a->len; i++)
    printf("%d ", g_array_index(a, int, i));
    printf("\n");
}

int main(int argc, char** argv) 
{
    GArray* a = g_array_new(FALSE, FALSE, sizeof(int));
    printf("Array is empty, so appending some values\n");

    int x[2] = {4,5};
    g_array_append_vals(a, &x, 2);

    prt(a);
    printf("Now to prepend some values\n");

    int y[2] = {2,3};
    g_array_prepend_vals(a, &y, 2);

    prt(a);
    printf("And one more prepend\n");

    int z = 1;
    g_array_prepend_val(a, z);
    prt(a);
    g_array_free(a, FALSE);

    return 0;
}

Вывод программы:

Array is empty, so appending some values
Array holds: 4 5
Now to prepend some values
Array holds: 2 3 4 5
And one more prepend
Array holds: 1 2 3 4 5

Таким образом, вы можете добавить несколько значений в массив, вы можете добавить одно значение, и вы можете добавить несколько значений. Будьте осторожны с предваряющими значениями; это операция O (n), поскольку GArray должен сдвинуть все текущие значения вниз, чтобы освободить место для новых данных. Вам все еще нужно использовать переменные при добавлении или добавлении нескольких значений, но это довольно просто, так как вы можете добавить или добавить весь массив.

Вставка данных

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

//ex-garray-4.c
#include <glib.h>

void prt(GArray* a) {
    printf("Array holds: ");
    int i;
    for (i = 0; i < a->len; i++)
    printf("%d ", g_array_index(a, int, i));
    printf("\n");
}

int main(int argc, char** argv) 
{
    GArray* a = g_array_new(FALSE, FALSE, sizeof(int));
    int x[2] = {1,5};   
    g_array_append_vals(a, &x, 2);

    prt(a);
    printf("Inserting a '2'\n");

    int b = 2;
    g_array_insert_val(a, 1, b);

    prt(a);
    printf("Inserting multiple values\n");

    int y[2] = {3,4};
    g_array_insert_vals(a, 2, y, 2);

    prt(a);
    g_array_free(a, FALSE);

    return 0;
}

Вывод программы:

Array holds: 1 5
Inserting a '2'
Array holds: 1 2 5
Inserting multiple values
Array holds: 1 2 3 4 5

Обратите внимание, что эти insertфункции включают в себя копирование текущих элементов в списке вниз для размещения новых элементов, поэтому использование g_array_insert_valsнамного лучше, чем g_array_insert_valповторное использование .

Удаление данных

Существует три способа удаления данных из GArray:

  • g_array_remove_indexи g_array_remove_rangeоба из которых сохраняют существующий порядок
  • g_array_remove_index_fast , который не сохраняет существующий порядок

Вот примеры всех трех:

//ex-garray-5.c
#include <glib.h>

void prt(GArray* a) {
    int i;
    printf("Array holds: ");

    for (i = 0; i < a->len; i++)
        printf("%d ", g_array_index(a, int, i));

    printf("\n");
}

int main(int argc, char** argv) 
{
    GArray* a = g_array_new(FALSE, FALSE, sizeof(int));
    int x[6] = {1,2,3,4,5,6};
    g_array_append_vals(a, &x, 6);

    prt(a);
    printf("Removing the first item\n");
    g_array_remove_index(a, 0);

    prt(a);
    printf("Removing the first two items\n");
    g_array_remove_range(a, 0, 2);

    prt(a);
    printf("Removing the first item very quickly\n");
    g_array_remove_index_fast(a, 0);

    prt(a);
    g_array_free(a, FALSE);

    return 0;
}

Вывод программы:

Array holds: 1 2 3 4 5 6
Removing the first item
Array holds: 2 3 4 5 6
Removing the first two items
Array holds: 4 5 6
Removing the first item very quickly
Array holds: 6 5

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

Сортировка массивов

Сортировка массива проста; он использует то GCompareFunc, что вы уже видели на работе в разделах GList и GSList:

//ex-garray-6.c
#include <glib.h>

void prt(GArray* a) {
    int i;
    printf("Array holds: ");

    for (i = 0; i < a->len; i++)
        printf("%d ", g_array_index(a, int, i));

    printf("\n");
}
int compare_ints(gpointer a, gpointer b) {
    int* x = (int*)a;
    int* y = (int*)b;
    return *x - *y;
}
int main(int argc, char** argv) 
{
    GArray* a = g_array_new(FALSE, FALSE, sizeof(int));
    int x[6] = {2,1,6,5,4,3};
    g_array_append_vals(a, &x, 6);

    prt(a);
    printf("Sorting\n");
    g_array_sort(a, (GCompareFunc)compare_ints);
    prt(a);

    g_array_free(a, FALSE);
    return 0;
}

Вывод программы:

Array holds: 2 1 6 5 4 3
Sorting
Array holds: 1 2 3 4 5 6

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

Кстати, ни одно из трех примеров приложений не использует ни, g_array_sortни g_array_sort_with_data. Но, как всегда, приятно знать, что они доступны.

Массивы указателей

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

//ex-garray-7.c
#include <glib.h>
#include <stdio.h>

int main(int argc, char** argv) 
{
    GPtrArray* a = g_ptr_array_new();

    g_ptr_array_add(a, g_strdup("hello "));
    g_ptr_array_add(a, g_strdup("again "));
    g_ptr_array_add(a, g_strdup("there "));
    g_ptr_array_add(a, g_strdup("world "));
    g_ptr_array_add(a, g_strdup("\n"));

    printf(">Here are the GPtrArray contents\n");
    g_ptr_array_foreach(a, (GFunc)printf, NULL);
    printf(">Removing the third item\n");

    g_ptr_array_remove_index(a, 2);
    g_ptr_array_foreach(a, (GFunc)printf, NULL);
    printf(">Removing the second and third item\n");

    g_ptr_array_remove_range(a, 1, 2);
    g_ptr_array_foreach(a, (GFunc)printf, NULL);

    printf("The first item is '%s'\n", g_ptr_array_index(a, 0));
    g_ptr_array_free(a, TRUE);

    return 0;
}

Вывод программы:

>Here are the GPtrArray contents
hello again there world
>Removing the third item
hello again world
>Removing the second and third item
hello
The first item is 'hello '

Вы можете видеть, как использование массива только с указателем делает API более простым. Это может объяснить, почему в Evolution g_ptr_array_newиспользуется 178 раз, тогда как g_array_newиспользуется только 45 раз. Большую часть времени контейнер только для указателя достаточно хорош!

Байтовые массивы

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

//ex-garray-8.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GByteArray* a = g_byte_array_new();

    guint8 x = 0xFF;
    g_byte_array_append(a, &x, sizeof(x));  
    printf("The first byte value (in decimal) is %d\n", a->data[0]);

    x = 0x01;   
    g_byte_array_prepend(a, &x, sizeof(x));
    printf("After prepending, the first value is %d\n", a->data[0]);

    g_byte_array_remove_index(a, 0);
    printf("After removal, the first value is again %d\n", a->data[0]);

    g_byte_array_append(g_byte_array_append(a, &x, sizeof(x)), &x, sizeof(x));  
    printf("After two appends, array length is %d\n", a->len);

    g_byte_array_free(a, TRUE);

    return 0;
}

Вывод программы:

The first byte value (in decimal) is 255
After prepending, the first value is 1
After removal, the first value is again 255
After two appends, array length is 3

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

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

Реальное использование массивов

Различные типы массивов GLib используются в примерах приложений, хотя и не так широко, как другие контейнеры, которые вы видели.

Gaim использует только GPtrArrays и только в одном или двух случаях. gaim-1.2.1 / src / gtkpounce.c использует GPtrArray для отслеживания нескольких виджетов с графическим интерфейсом, которые могут запускаться при возникновении различных событий (например, входа в систему).

Evolution использует в основном GPtrArrays, хотя также появляется несколько GArrays и GByteArrays:

  • evolution-2.0.2 / widgets / misc / e-filter-bar.h содержит несколько типов поисковых фильтров в GPtrArrays.
  • evolution-2.0.2 / camel / provider / imap4 / camel-imap4-store.c использует GPtrArray для отслеживания элементов в папке IMAP; он использует g_ptr_array_sort с GCompareFunc, который делегирует strcmp.

GIMP использует достаточное количество GArrays и только несколько GPtrArrays и GByteArrays:

  • gimp-2.2.4 / app / tools / gimptransformtool.c использует GArray для отслеживания списка GimpCoordэкземпляров.
  • gimp-2.2.4 / app / base / border.c заполняет GArray точками как часть изящной simplify_subdivideфункции; дважды косвенный указатель на GArray рекурсивно передается как часть процедуры упрощения границ.

Деревья

Концепции деревьев

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

Примером древовидной структуры является файловая система или, возможно, почтовый клиент; у него есть папки, в которых есть папки, которые могут содержать больше папок. Кроме того, помните конец раздела хеш-таблицы, где вы видели пример многозначных ключей? (Например, String для ключа и GList для значения.) Поскольку эти значения GList могли содержать больше GHashTables, это был пример древовидной структуры, захваченной внутри GHashTable. Намного проще просто использовать GTree, а не сражаться с другим контейнером, чтобы заставить его работать как дерево.

GLib включает в себя два контейнера дерева: GTree, реализацию сбалансированного бинарного дерева , и GNode, реализацию n-арного дерева.

У бинарного дерева есть специальное свойство - каждый узел дерева имеет не более двух дочерних элементов; бинарное дерево означает , что элементы находятся в определенном порядке для быстрого поиска. Сохранение баланса элементов означает, что удаление и вставка могут быть медленными, поскольку дерево может нуждаться в внутреннем перебалансировании, но поиск элемента - это операция O (log n).

Узел n-арного дерева , напротив, может иметь много дочерних элементов. Этот урок фокусируется в основном на двоичных деревьях, но вы также увидите несколько примеров n-арных деревьев.

Основные древовидные операции

Вот некоторые основные операции, которые вы можете выполнять над деревом:

//ex-gtree-1.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GTree* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);

    g_tree_insert(t, "c", "Chicago");
    printf("The tree height is %d because there's only one node\n", g_tree_height(t));

    g_tree_insert(t, "b", "Boston");
    g_tree_insert(t, "d", "Detroit");

    printf("Height is %d since c is root; b and d are children\n", g_tree_height(t));
    printf("There are %d nodes in the tree\n", g_tree_nnodes(t));

    g_tree_remove(t, "d");
    printf("After remove(), there are %d nodes in the tree\n", g_tree_nnodes(t));

    g_tree_destroy(t);

    return 0;
}

Вывод программы:

The tree height is 1 because there's only one node
Height is 2 since c is root; b and d are children
There are 3 nodes in the tree
After remove(), there are 2 nodes in the tree

Несколько замечаний по этому коду:

  • Вы можете видеть, как каждый узел в GTree состоит из пары ключ-значение. Ключ используется для обеспечения сбалансированности дерева, вставки узла в нужное место, а значение является указателем на «полезную нагрузку», которую вы хотите отслеживать.
  • Вы должны предоставить , GCompareFuncчтобы g_tree_newтаким образом GTree умеет сравнивать ключи. Это может быть встроенная функция, как показано выше, или вы можете свернуть свою собственную.
  • Дерево "высота" - это просто число узлов сверху вниз, включительно. Чтобы выполнить эту функцию, GTree должен начать с корня и двигаться вниз, пока не достигнет конечного узла. g_tree_nnodesФункция еще дороже; это требует полного обхода всего дерева.

Заменить и украсть

Вы уже видели имена replaceи stealфункций в GHashTable; те, что на GTree, работают примерно так же. g_tree_replaceзаменяет ключ и значение записи GTree, а не g_tree_insertтолько значение, если введенный ключ является дубликатом. И g_tree_stealудаляет узел без вызова каких-либо GDestroyNotifyфункций. Вот пример:

//ex-gtree-2.c
#include <glib.h>

void key_d(gpointer data) {
    printf("Key %s destroyed\n", data);
}

void value_d(gpointer data) {
    printf("Value %s destroyed\n", data);
}

int main(int argc, char** argv) 
{
    GTree* t = g_tree_new_full((GCompareDataFunc)g_ascii_strcasecmp,
    NULL, (GDestroyNotify)key_d, (GDestroyNotify)value_d);

    g_tree_insert(t, "c", "Chicago");
    g_tree_insert(t, "b", "Boston");
    g_tree_insert(t, "d", "Detroit");

    printf(">Replacing 'b', should get destroy callbacks\n");

    g_tree_replace(t, "b", "Billings");
    printf(">Stealing 'b', no destroy notifications will occur\n");

    g_tree_steal(t, "b");
    printf(">Destroying entire tree now\n");

    g_tree_destroy(t);

    return 0;
}

Вывод программы:

>Replacing 'b', should get destroy callbacks
Value Boston destroyed
Key b destroyed
>Stealing 'b', no destroy notifications will occur
>Destroying entire tree now
Key d destroyed
Value Detroit destroyed
Key c destroyed
Value Chicago destroyed

В этом примере вы создаете GTree, используя g_tree_new_full; Как и в случае с GHashTable, вы можете зарегистрироваться для получения уведомлений о любой комбинации уничтожения ключа или значения. Второй аргумент g_tree_new_fullможет содержать данные для передачи в GCompareFunc, но здесь это не нужно.

Поиск данных

GTree предоставляет способы поиска только ключа или ключа и значения. Это так же, как вы видели раньше в GHashTable; есть lookupи lookup_extended. Вот пример:

//ex-gtree-3.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GTree* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);
    g_tree_insert(t, "c", "Chicago");
    g_tree_insert(t, "b", "Boston");
    g_tree_insert(t, "d", "Detroit");

    printf("The data at 'b' is %s\n", g_tree_lookup(t, "b"));

    printf("%s\n",  g_tree_lookup(t, "a") ? 
    "My goodness!" : "As expected, couldn't find 'a'");

    gpointer* key = NULL;
    gpointer* value = NULL;
    g_tree_lookup_extended(t, "c", (gpointer*)&key, (gpointer*)&value);

    printf("The data at '%s' is %s\n", key, value);
    gboolean found = g_tree_lookup_extended(t, "a", (gpointer*)&key, (gpointer*)&value);
    printf("%s\n", found ? "My goodness!" : "As expected, couldn't find 'a'");

    g_tree_destroy(t);

    return 0;
}

Вывод программы:

The data at 'b' is Boston
As expected, couldn't find 'a'
The data at 'c' is Chicago
As expected, couldn't find 'a'

Здесь вы снова видите технику двунаправленного указателя. Поскольку множественные значения должны быть предоставлены g_tree_lookup_extended, он принимает два указателя на указатели, один на ключ и один на значение. И обратите внимание, что если g_tree_lookupне удается найти ключ, он возвращает NULL gpointer, тогда как, если g_tree_lookup_extendedне удается найти цель, он возвращает gbooleanзначение FALSE.

Листинг дерева с foreach

GTree предоставляет g_tree_foreachфункцию для перебора узлов дерева в отсортированном порядке. Вот пример:

//ex-gtree-4.c
#include <glib.h>

gboolean iter_all(gpointer key, gpointer value, gpointer data) {
    printf("%s, %s\n", key, value);
    return FALSE;
}

gboolean iter_some(gpointer key, gpointer value, gpointer data) {
printf("%s, %s\n", key, value);
    return g_ascii_strcasecmp(key, "b") == 0;
}

int main(int argc, char** argv) 
{
    GTree* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);

    g_tree_insert(t, "d", "Detroit");
    g_tree_insert(t, "a", "Atlanta");
    g_tree_insert(t, "c", "Chicago");
    g_tree_insert(t, "b", "Boston");

    printf("Iterating all nodes\n");
    g_tree_foreach(t, (GTraverseFunc)iter_all, NULL);

    printf("Iterating some of the nodes\n");
    g_tree_foreach(t, (GTraverseFunc)iter_some, NULL);

    g_tree_destroy(t);

    return 0;
}

Вывод программы:

Iterating all nodes
a, Atlanta
b, Boston
c, Chicago
d, Detroit
Iterating some of the nodes
a, Atlanta
b, Boston

Обратите внимание, что при iter_someвозврате TRUE итерация останавливается. Это делает g_tree_foreachполезным поиск до точки, накапливая первые 10 элементов, которые соответствуют условию, или тому подобное. И, конечно, вы можете просто пройти по всему дереву, вернув FALSE из GTraverseFunc.

Кроме того, обратите внимание, что вы не должны изменять дерево во время итерации по нему, используя g_tree_foreach.

Есть устаревшая функция g_tree_traverse, предназначенная для обеспечения других способов обхода дерева. Например, вы можете посещать узлы в почтовом порядке , то есть посещать дерево снизу вверх. Однако с 2001 года это считается устаревшим, поэтому в документации GTree предлагается заменить любое его использование на g_tree_foreachили n-арное дерево. Ни одно из приложений с открытым исходным кодом, рассмотренное здесь, не использует его, и это хорошо.

поиск

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

//ex-gtree-5.c
#include <glib.h>

gint finder(gpointer key, gpointer user_data) {
    int len = strlen((char*)key);
    if (len == 3) {
        return 0;
    }
    return (len < 3) ? 1 : -1;
}

int main(int argc, char** argv) 
{
    GTree* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);

    g_tree_insert(t, "dddd", "Detroit");
    g_tree_insert(t, "a", "Annandale");
    g_tree_insert(t, "ccc", "Cleveland");
    g_tree_insert(t, "bb", "Boston");   

    gpointer value = g_tree_search(t, (GCompareFunc)finder, NULL);
    printf("Located value %s; its key is 3 characters long\n", value);

    g_tree_destroy(t);

    return 0;
}

Вывод программы:

Located value Cleveland; its key is 3 characters long

Обратите внимание, что GCompareFuncпереданный в g_tree_searchфактически определяет, как происходит поиск, возвращая 0, 1 или -1 в зависимости от того, каким образом должен идти поиск. Эта функция может даже изменить условия в процессе поиска; Evolution делает именно это, когда использует g_tree_searchуправление памятью.

Больше, чем двоичные: n-арные деревья

Реализация n-арного дерева GLib основана на GNodeструктуре; как упоминалось ранее, он допускает множество дочерних узлов для каждого родительского узла. Похоже, что он редко используется, но для полноты, вот эстакада использования:

//ex-gtree-6.c
#include <glib.h>

gboolean iter(GNode* n, gpointer data) {
    printf("%s ", n->data);
    return FALSE;
}

int main(int argc, char** argv) 
{
    GNode* root = g_node_new("Atlanta");
    g_node_append(root, g_node_new("Detroit"));
    GNode* portland = g_node_prepend(root, g_node_new("Portland"));

    printf(">Some cities to start with\n");
    g_node_traverse(root, G_PRE_ORDER, G_TRAVERSE_ALL, -1, iter, NULL);
    printf("\n>Inserting Coos Bay before Portland\n");

    g_node_insert_data_before(root, portland, "Coos Bay");
    g_node_traverse(root, G_PRE_ORDER, G_TRAVERSE_ALL, -1, iter, NULL);

    printf("\n>Reversing the child nodes\n");

    g_node_reverse_children(root);
    g_node_traverse(root, G_PRE_ORDER, G_TRAVERSE_ALL, -1, iter, NULL);

    printf("\n>Root node is %s\n", g_node_get_root(portland)->data);
    printf(">Portland node index is %d\n", g_node_child_index(root, "Portland"));

    g_node_destroy(root);

    return 0;
}

Вывод программы:

>Some cities to start with
Atlanta Portland Detroit
>Inserting Coos Bay before Portland
Atlanta Coos Bay Portland Detroit
>Reversing the child nodes
Atlanta Detroit Portland Coos Bay
>Root node is Atlanta
>Portland node index is 1

Вы можете видеть, что это GNodeпозволяет вам размещать узлы практически в любом месте; это зависит от вас, чтобы получить доступ к ним, как вы считаете нужным. Он очень гибкий, но может быть настолько гибким, что немного сложно определить реальный сценарий использования. Фактически, он не используется ни в одном из трех приложений с открытым исходным кодом, рассмотренных здесь!

Реальное использование деревьев

GTree является сложной структурой и не так широко используется, как другие контейнеры, которые мы рассматривали до сих пор. Гаим не использует его вообще. У GIMP и Evolution есть некоторые способы использования.

GIMP:

  • gimp-2.2.4 / app / menus / plug-in-menus.c использует GTree для хранения пунктов меню плагина. Он использует g_tree_foreachи собственный GTraverseFunc для обхода GTree, чтобы добавить процедуру плагина в GimpUIManager. Он использует стандартную функцию библиотеки C в strcmpкачестве своей GCompareDataфункции.
  • gimp-2.2.4 / plug-ins / script-fu / script-fu-scripts.c использует GTree для хранения скриптов «script-fu». Каждое значение в GTree на самом деле является GList скриптов.

Evolution's evolution-2.0.2 / e-util / e-memory.c использует GTree как часть алгоритма, который вычисляет неиспользуемые фрагменты памяти. Он использует пользовательский GCompareFunc, tree_compareчтобы упорядочить _cleaninfoструктуры, которые указывают на свободные куски.

Очереди

Концепции очередей

Другая удобная структура данных - это очередь. Очередь содержит список элементов , и, как правило , доступна путем добавления элементов в конец и удаления элементов с фронта. Это полезно, когда у вас есть вещи, которые необходимо обработать в порядке поступления. Разновидностью стандартной очереди является «двусторонняя очередь», или очередь , которая позволяет добавлять или удалять элементы с любого конца очереди.

Однако иногда бывает полезно избежать очереди. Поиск в очереди не особенно быстрый (это O (n)), поэтому, если вы будете искать часто, хеш-таблица или дерево могут быть более полезными. То же самое относится и к ситуации, когда вам понадобится получить доступ к случайным элементам в очереди; если вы сделаете это, вы будете выполнять много линейных сканирований очереди.

GLib обеспечивает реализацию очереди с GQueue; он поддерживает стандартные операции с очередями. Он поддерживается двусвязным списком (GList), поэтому он также поддерживает множество других операций, таких как вставка и удаление из середины очереди. Но если вы обнаружите, что часто используете эти функции, вы можете переосмыслить свой выбор контейнера; возможно, другой контейнер может быть более подходящим.

Основные операции с очередями

Вот некоторые основные операции GQueue, использующие в качестве модели «тикет-линию»:

//ex-gqueue-1.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GQueue* q = g_queue_new();

    printf("Is the queue empty?  %s, adding folks\n",  g_queue_is_empty(q) ? "Yes" : "No");

    g_queue_push_tail(q, "Alice");
    g_queue_push_tail(q, "Bob");
    g_queue_push_tail(q, "Fred");

    printf("First in line is %s\n", g_queue_peek_head(q));
    printf("Last in line is %s\n", g_queue_peek_tail(q));
    printf("The queue is %d people long\n",  g_queue_get_length(q));
    printf("%s just bought a ticket\n", g_queue_pop_head(q));
    printf("Now %s is first in line\n", g_queue_peek_head(q));
    printf("Someone's cutting to the front of the line\n");

    g_queue_push_head(q, "Big Jim");
    printf("Now %s is first in line\n", g_queue_peek_head(q));

    g_queue_free(q);

    return 0;
}

Вывод программы:

Is the queue empty?  Yes, adding folks
First in line is Alice
Last in line is Fred
The queue is 3 people long
Alice just bought a ticket
Now Bob is first in line
Someone's cutting to the front of the line
Now Big Jim is first in line

Большинство имен методов довольно информативно, но некоторые из них более тонкие:

  • Различные методы для выталкивания и извлечения элементов из очереди ничего не возвращают, поэтому вам нужно сохранить этот указатель возвращенным, g_queue_newчтобы использовать очередь.
  • Любой конец очереди может использоваться как для добавления, так и для удаления. Если вы хотите смоделировать линию билета, когда люди в задней части отслаиваются, чтобы купить у другой линии, это вполне выполнимо.
  • Существуют неразрушающие peekоперации для проверки элемента в начале или в конце очереди.
  • g_queue_freeне принимает функцию для освобождения каждого элемента, поэтому вам придется делать это вручную; это так же, как с GSList.

Извлечение и вставка элементов

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

//ex-gqueue-2.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GQueue* q = g_queue_new();
    g_queue_push_tail(q, "Alice");
    g_queue_push_tail(q, "Bob");
    g_queue_push_tail(q, "Fred");

    printf("Queue is Alice, Bob, and Fred; removing Bob\n");
    int fred_pos = g_queue_index(q, "Fred");
    g_queue_remove(q, "Bob");

    printf("Fred moved from %d to %d\n", fred_pos, g_queue_index(q, "Fred"));
    printf("Bill is cutting in line\n");

    GList* fred_ptr = g_queue_peek_tail_link(q);
    g_queue_insert_before(q, fred_ptr, "Bill");

    printf("Middle person is now %s\n", g_queue_peek_nth(q, 1));
    printf("%s is still at the end\n", g_queue_peek_tail(q));

    g_queue_free(q);

    return 0;
}

Вывод программы:

Queue is Alice, Bob, and Fred; removing Bob
Fred moved from 2 to 1
Bill is cutting in line
Middle person is now Bill
Fred is still at the end

Там много новых функций:

  • g_queue_indexсканирует очередь на наличие элемента и возвращает индекс; если он не может найти элемент, он возвращает -1.
  • Чтобы вставить новый элемент в середину очереди, вам нужен указатель на место, куда вы хотите его вставить. Как вы можете видеть, вы можете получить ручку на этом, позвонив по одному из «заглядывать ссылку» функция: g_queue_peek_tail_link, g_queue_peek_head_linkили g_queue_peek_nth_link, которая возвращает GList. Затем вы можете вставить элемент до или после этого списка.
  • g_queue_removeпозволяет удалить элемент из любой точки очереди. Продолжая модель «билетной линии», это означает, что люди могут отказаться от линии; они не застряли в нем, как только они присоединятся.

Нахождение элементов

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

//ex-gqueue-3.c
#include <glib.h>

gint finder(gpointer a, gpointer b) {
    return strcmp(a,b);
}

int main(int argc, char** argv) 
{
    GQueue* q = g_queue_new();

    g_queue_push_tail(q, "Alice");
    g_queue_push_tail(q, "Bob");
    g_queue_push_tail(q, "Fred");
    g_queue_push_tail(q, "Jim");

    GList* fred_link = g_queue_find(q, "Fred");
    printf("The fred node indeed contains %s\n", fred_link->data);

    GList* joe_link = g_queue_find(q, "Joe");
    printf("Finding 'Joe' yields a %s link\n", joe_link ? "good" : "null");

    GList* bob = g_queue_find_custom(q, "Bob", (GCompareFunc)finder);
    printf("Custom finder found %s\n", bob->data);

    bob = g_queue_find_custom(q, "Bob", (GCompareFunc)g_ascii_strcasecmp);
    printf("g_ascii_strcasecmp also found %s\n", bob->data);

    g_queue_free(q);

    return 0;
}

Вывод программы:

The fred node indeed contains Fred
Finding 'Joe' yields a null link
Custom finder found Bob
g_ascii_strcasecmp also found Bob

Обратите внимание, что если g_queue_findне удается найти элемент, возвращается ноль. И вы можете передать в качестве аргумента либо библиотечную функцию, например g_ascii_strcasecmp, либо пользовательскую функцию, как finderв примере выше .GCompareFunc``g_queue_find_custom

Работа с очередью: копировать, перевернуть и foreach

Поскольку GQueue поддерживается GList, он поддерживает некоторые операции со списками. Вот пример того , как использовать g_queue_copy, g_queue_reverseи g_queue_foreach:

//ex-gqueue-4.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GQueue* q = g_queue_new();

    g_queue_push_tail(q, "Alice ");
    g_queue_push_tail(q, "Bob ");
    g_queue_push_tail(q, "Fred ");

    printf("Starting out, the queue is: ");

    g_queue_foreach(q, (GFunc)printf, NULL);
    g_queue_reverse(q);

    printf("\nAfter reversal, it's: ");
    g_queue_foreach(q, (GFunc)printf, NULL);

    GQueue* new_q = g_queue_copy(q);

    g_queue_reverse(new_q);
    printf("\nNewly copied and re-reversed queue is: ");

    g_queue_foreach(new_q, (GFunc)printf, NULL);
    g_queue_free(q);
    g_queue_free(new_q);

    return 0;
}

Вывод программы:

Starting out, the queue is: Alice Bob Fred
After reversal, it's: Fred Bob Alice
Newly copied and re-reversed queue is: Alice Bob Fred

g_queue_reverseи g_queue_foreachдовольно просты; вы уже видели, как они оба работают над другими заказанными коллекциями. g_queue_copyтребует некоторой осторожности, так как указатели копируются, но не данные. Поэтому, освобождая данные, не делайте двойного освобождения.

Больше веселья со ссылками

Вы видели несколько примеров ссылок; Вот несколько удобных функций удаления ссылок. Напомним, что каждый элемент в GQueue на самом деле представляет собой структуру GList с данными, хранящимися в элементе «data»:

//ex-gqueue-5.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GQueue* q = g_queue_new();

    g_queue_push_tail(q, "Alice ");
    g_queue_push_tail(q, "Bob ");
    g_queue_push_tail(q, "Fred ");
    g_queue_push_tail(q, "Jim ");

    printf("Starting out, the queue is: ");
    g_queue_foreach(q, (GFunc)printf, NULL);

    GList* fred_link = g_queue_peek_nth_link(q, 2);
    printf("\nThe link at index 2 contains %s\n", fred_link->data);

    g_queue_unlink(q, fred_link);
    g_list_free(fred_link);

    GList* jim_link = g_queue_peek_nth_link(q, 2);
    printf("Now index 2 contains %s\n", jim_link->data);

    g_queue_delete_link(q, jim_link);

    printf("Now the queue is: ");
    g_queue_foreach(q, (GFunc)printf, NULL);

    g_queue_free(q);

    return 0;
}

Вывод программы:

Starting out, the queue is: Alice Bob Fred Jim
The link at index 2 contains Fred
Now index 2 contains Jim
Now the queue is: Alice Bob

Обратите внимание, что g_queue_unlinkэто не освобождает несвязанную структуру GList, поэтому вам придется сделать это самостоятельно. А поскольку это структура GList, вам нужно использовать g_list_freeфункцию для ее освобождения, а не простую g_freeфункцию. Конечно, проще позвонить, g_queue_delete_linkи пусть это позаботится об освобождении памяти для вас.

Сортировка очередей

Сортировка очереди кажется немного странной, но так как разрешены различные другие операции со связанными списками (как insertи remove), так и эта. Это также может быть удобно, если вы хотите иногда переупорядочивать очередь, чтобы перемещать элементы с более высоким приоритетом вперед. Вот пример:

//ex-gqueue-6.c
#include <glib.h>

typedef struct {
    char* name;
    int priority;
} Task;

Task* make_task(char* name, int priority) {
    Task* t = g_new(Task, 1);
    t->name = name;
    t->priority = priority;
    return t;
}

void prt(gpointer item) {
    printf("%s   ", ((Task*)item)->name);
}

gint sorter(gconstpointer a, gconstpointer b, gpointer data) {
    return ((Task*)a)->priority - ((Task*)b)->priority;
}

int main(int argc, char** argv) 
{
    GQueue* q = g_queue_new();

    g_queue_push_tail(q, make_task("Reboot server", 2));
    g_queue_push_tail(q, make_task("Pull cable", 2));
    g_queue_push_tail(q, make_task("Nethack", 1));
    g_queue_push_tail(q, make_task("New monitor", 3));

    printf("Original queue: ");
    g_queue_foreach(q, (GFunc)prt, NULL);

    g_queue_sort(q, (GCompareDataFunc)sorter, NULL);
    printf("\nSorted queue: ");
    g_queue_foreach(q, (GFunc)prt, NULL);

    g_queue_free(q);

    return 0;
}

Вывод программы:

Original queue: Reboot server   Pull cable   Nethack   New monitor
Sorted queue: Nethack   Reboot server   Pull cable   New monitor

Теперь у вас есть GQueue, чтобы смоделировать вашу рабочую нагрузку, и время от времени вы можете сортировать ее, оставаясь довольными, зная, что Nethack будет повышен до своей законной позиции в начале очереди!

Реальное использование очередей

GQueue не используется в Evolution, но GIMP и Gaim используют его.

GIMP:

  • gimp-2.2.4 / app / core / gimpimage-contiguous-region.c использует GQueue для хранения серии координат в служебной функции, которая находит смежные сегменты. Пока сегмент остается непрерывным, новые точки помещаются в конец очереди, а затем извлекаются для проверки во время следующей итерации цикла.
  • gimp-2.2.4 / app / vectors / gimpvectors-import.c использует GQueue как часть синтаксического анализатора масштабируемой векторной графики (SVG). Он используется в качестве стека; элементы одновременно помещаются в головку очереди и извлекаются из нее.

Гейм:

  • gaim-1.2.1 / src / protocol / msn / switchboard.c использует GQueue для отслеживания исходящих сообщений. Новые сообщения помещаются в хвост и, когда отправляются, выскакивают с головы.
  • gaim-1.2.1 / src / proxy.c использует GQueue для отслеживания запросов поиска DNS. Он использует очередь как область временного хранения между кодом приложения и дочерним процессом DNS.

Связи

Концепции отношений

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

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

GRelation демонстрирует некоторую слабость в том, что каждый кортеж может содержать максимум два поля. Таким образом, использование его в качестве кэша таблиц базы данных в памяти не будет работать хорошо, если ваша таблица не достаточно тонкая. Я искал в gtk-app-devel-listсписке рассылки заметки по этому вопросу и обнаружил, что в феврале 2000 года обсуждался патч, который расширил бы его до четырех полей, но, похоже, он никогда не попал в дистрибутив.

GRelation представляется малоизвестной структурой; ни одно из приложений с открытым исходным кодом, рассматриваемых в этом руководстве, в настоящее время не использует его. Немного покопавшись в Интернете, обнаружил почтовый клиент с открытым исходным кодом (Sylpheed-claws), который использует его для различных целей, в том числе для отслеживания папок IMAP и потоков сообщений. Так что, возможно, просто нужно немного рекламы!

Основные операции отношений

Вот пример создания нового GRelation с двумя индексированными полями, а затем вставки нескольких записей и выполнения некоторых основных информационных запросов:

//ex-grelation-1.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GRelation* r = g_relation_new(2);

    g_relation_index(r, 0, g_str_hash, g_str_equal);
    g_relation_index(r, 1, g_str_hash, g_str_equal);
    g_relation_insert(r, "Virginia", "Richmond");
    g_relation_insert(r, "New Jersey", "Trenton");
    g_relation_insert(r, "New York", "Albany");
    g_relation_insert(r, "Virginia", "Farmville");
    g_relation_insert(r, "Wisconsin", "Madison");
    g_relation_insert(r, "Virginia", "Keysville");

    gboolean found = g_relation_exists(r, "New York", "Albany");
    printf("New York %s found in the relation\n", found ? "was" : "was not");

    gint count = g_relation_count(r, "Virginia", 0);
    printf("Virginia appears in the relation %d times\n", count);

    g_relation_destroy(r);

    return 0;
}

Вывод программы:

New York was found in the relation
Virginia appears in the relation 3 times

Обратите внимание, что индексы добавляются сразу после вызова g_relation_newи перед вызовом g_relation_insert. Это связано с тем, что другие функции GRelation, например g_relation_count, зависят от существующего индекса и потерпят неудачу во время выполнения, если он не существует.

Приведенный выше код содержит вызов, чтобы g_relation_existsувидеть, если "Нью-Йорк" в какой-либо GRelation. Это требует точного соответствия для каждого поля в отношении; Вы можете сопоставить любое индексированное поле, используя g_relation_count.

Вы видели g_str_hashи g_str_equalработали раньше в разделе GHashTable; они используются здесь для быстрого поиска проиндексированных полей в GRelation.

Выбор кортежей

Когда данные находятся в GRelation, их можно получить с помощью g_relation_selectфункции. Результатом является точка на GTuplesструктуру, которая может быть запрошена для получения фактических данных. Вот как это использовать:

//ex-grelation-2.c
#include <glib.h>

int main(int argc, char** argv) 
{
    GRelation* r = g_relation_new(2);

    g_relation_index(r, 0, g_str_hash, g_str_equal);
    g_relation_index(r, 1, g_str_hash, g_str_equal);
    g_relation_insert(r, "Virginia", "Richmond");
    g_relation_insert(r, "New Jersey", "Trenton");
    g_relation_insert(r, "New York", "Albany");
    g_relation_insert(r, "Virginia", "Farmville");
    g_relation_insert(r, "Wisconsin", "Madison");
    g_relation_insert(r, "Virginia", "Keysville");

    GTuples* t = g_relation_select(r, "Virginia", 0);
    printf("Some cities in Virginia:\n");

    int i;
    for (i=0; i < t->len; i++) {
        printf("%d) %s\n", i, g_tuples_index(t, i, 1));
    }

    g_tuples_destroy(t);
    t = g_relation_select(r, "Vermont", 0);
    printf("Number of Vermont cities in the GRelation: %d\n", t->len);

    g_tuples_destroy(t);
    g_relation_destroy(r);

    return 0;
}

Вывод программы:

Some cities in Virginia:
0) Farmville
1) Keysville
2) Richmond
Number of Vermont cities in the GRelation: 0

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

  • Записи в GTuplesструктуре, возвращаемые из, g_relation_selectрасположены в произвольном порядке. Чтобы узнать, сколько записей было возвращено, используйте lenчлен GTupleструктуры.
  • g_tuples_index принимает три аргумента:
    • Структура GTuple
    • Индекс записи, которую вы запрашиваете
    • Индекс поля, которое вы хотите получить
  • Обратите внимание, что вам нужно позвонить, g_tuples_destroyчтобы правильно освободить память, выделенную во время g_relation_select. Это прекрасно работает, даже если объект GTuples не ссылается ни на какие записи.

Заключение

Резюме

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

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