Вперед: 2.2.2 Деревья Назад: 2.2 Структуры данных

2.2.1 Списки

glib предоставляет универсальные одно- и двусвязные списки, соответственно GSList и GList. Они реализованы как списки, содержащие gpointer; вы можете использовать их, чтобы хранить целые числа с помощью макросов "GINT_TO_POINTER" и "GPOINTER_TO_INT". GSList и GList имеют идентичный API за исключением того, что есть функция "g_list_previous()", но нет "g_slist_previous()". В этом разделе будет обсуждаться GSList, но все это применимо и к двусвязным спискам.

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

GSList *list = NULL; gchar *element = g_strdup("a string"); list = g_slist_append(list, element);

Списки в glib реализованы под заметным влиянием Lisp'а; пустой список равен специальному значению "nil" по этой причине. "g_slist_prepend()" работает почти как cons -- это постоянная по времени операция, которая добавляет новую ячейку в начало списка.

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

Например, следующий код удалит элемент, добавленный в примере выше, и, таким образом, очистит список:

list = g_slist_remove(list, element);

list не равен NULL. Вы также, естественно, сами должны освободить element. Для очистки всего списка воспользуйтесь "g_slist_free()", который удалит все связи за раз. "g_slist_free()" не имеет возвращаемого значения, потому что оно всегда будет NULL, и вы можете просто присвоить это значение своему списку, если захотите. Очевидно, функция "g_slist_free()" освобождает только ячейки списка; она ничего не знает про то, что делать с содержимым списка.

Для доступа к элементу списка, ссылайтесь на структуру GSList напрямую: gchar *my_data = list->data;

Для хождения по списку, можно писать примерно следующий код:

GSList *tmp = list; while (tmp != NULL) { printf("List data: %p\n", tmp->data); tmp = g_slist_next(tmp); }

Список функций 2..8 показывает базовые функции для изменения содержимого GSList. Вы должны присваивать своей переменной-списку возвращаемое значение всех этих функций на случай, если голова списка изменится. Учтите, что glib не хранит указатель на хвост списка, поэтому добавление в начало -- это постоянная по времени операция, тогда как время выполнения добавления в конец, вставки и удаления пропорционально длине списка.

В частности, это означает, что создание списка с использованием "g_slist_append()" -- ужасная идея; используйте "g_slist_prepend()" и затем вызывайте "g_slist_reverse()", если вам важно расположение элементов. Если вы собираетесь часто добавлять элементы к концу списка, вы можете хранить указатель на последний элемент. Следующий код может быть использован для организации эффективного добавления в конец списка:

void efficient_append(GSList **list, GSList **list_end, gpointer data) { g_return_if_fail(list != NULL); g_return_if_fail(list_end != NULL); if (*list == NULL) { g_assert(*list_end == NULL); *list = g_slist_append(*list, data); *list_end = *list; } else *list_end = g_slist_append(*list_end, data)->next; }

Чтобы воспользоваться этой функцией, храните список и его хвост где-нибудь, и передавайте их адреса в "efficient_append()":

GSList *list = NULL; GSList *list_end = NULL; efficient_append(&list, &list_end, g_strdup("Foo")); efficient_append(&list, &list_end, g_strdup("Bar")); efficient_append(&list, &list_end, g_strdup("Baz"));

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

Для доступа к элементам списка в списке функций 2..9 приведены соответствующие функции. Ни одна из них не меняет структуру списка. "g_slist_foreach()" применяет GFunc к каждому элементу списка. GFunc определена следующим образом: typedef void (*GFunc) (gpointer data, gpointer user_data); При использовании из "g_slist_foreach()", ваша GFunc будет вызвана для каждого "list->data" в списке list, с передачей ваших данных "user_data". "g_slist_foreach()" сравнима с функцией "map" из Scheme.

Например, вы имеете список строк, и, возможно, хотите создать параллельный список из трансформированных некоторым образом строк из первого списка. Вот код, использующий "efficient_append()" из предыдущего примера: typedef struct _AppendContext AppendContext; struct _AppendContext { GSList *list; GSList *list_end; const gchar *append; }; static void append_foreach(gpointer data, gpointer user_data) { AppendContext *ac = (AppendContext *) user_data; gchar *oldstring = (gchar *) data; efficient_append(&ac_list, &ac->list_end, g_strconcat(oldstring, ac->append, NULL)); } GSList *copy_with_append(GSList *list_of_strings, const gchar *append) { AppendContext ac; ac.list = NULL; ac.list_end = NULL; ac.append = append; g_slist_foreach(list_of_strings, append_foreach, &ac); return ac.list; }

glib и Gtk+ широко используют идиому указатель на функцию и данные пользователя. Если у вас есть опыт функционального программирования, это наподобие использования 4#4-выражений для создания клаузы. (Клауза сочетает функцию со средой -- набором пар имя-значение. В этом случае средой являются данные пользователя, которые вы передаете в "append_foreach()", а клаузой -- комбинация из указателя на функцию и данных пользователя.)

Существует также несколько удобных процедур для манипулирования списком, приведенные в списке функций 2..10. За исключением "g_slist_copy()", все эти функции действуют на списки на месте. Это означает, что вы должны присвоить возвращенное значение и забыть о переданном указателе, как вы делаете когда добавляете или удаляете элементы в/из списка. "g_slist_copy()" возвращает уже выделенный в памяти список, поэтому вы можете продолжать пользоваться обоими списками, и в конце концов должны удалить оба списка.

И, наконец, существуют некоторые возможности для сортировки списков, показанные в списке функций 2..11. Чтобы воспользоваться ими, вы должны написать GCompareFunc, которая похожа на функцию сравнения в стандартном qsort(). С использованием типов glib она становится такой: typedef gint (*GCompareFunc) (gconstpointer a, gconstpointer b);

Если "a < b", функция должна возвратить отрицательное значение; если "a > b" -- положительное; если "a == b" -- должна возвратить 0.

Как только у вас появилась функция сравнения, вы можете вставлять элемент в уже отсортированный список, или сортировать список целиком. Списки сортируются в порядке возрастания. Вы даже можете переработать вашу GCompareFunc, чтобы находить элементы списка, используя "g_slist_find_custom()". (Предупреждение: GCompareFunc используется несогласованно в glib; иногда glib ожидает предикат равенства вместо функции в "qsort()"-стиле. Однако, использование согласованно внутри спискового API.)

Будьте осторожны с сортированными списками; неправильное их использование может стать очень неэффективным. Например, "g_slist_insert_sorted()" -- это O(n)-операция, но если вы ее используете в цикле для вставки большого количества элементов, цикл замедляется экспоненциально. Лучше добавить все ваши элементы в начало списка, а затем вызвать "g_slist_sort()".

---