[ новости /+++ | форум | теги | ]

Каталог документации / Раздел "Программирование, языки" / Оглавление документа

Вперед: 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".

GSList *g_slist_append(GSList *list, gpointer data)
GSList *g_slist_prepend(GSList *list, gpointer data)
GSList *g_slist_insert(GSList *list, gpointer data, gint position)
GSList *g_slist_remove(GSList *list, gpointer data)

Для доступа к элементам списка в списке функций 2..9 приведены соответствующие функции. Ни одна из них не меняет структуру списка. "g_slist_foreach()" применяет GFunc к каждому элементу списка. GFunc определена следующим образом:

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

Например, вы имеете список строк, и, возможно, хотите создать параллельный список из трансформированных некоторым образом строк из первого списка. Вот код, использующий "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()", а клаузой -- комбинация из указателя на функцию и данных пользователя.)

GSList *g_slist_find(GSList *list, gpointer data)
GSList *g_slist_nth(GSList *list, guint n)
gpointer g_slist_nth_data(GSList *list, guint n)
GSList *g_slist_last(GSList *list)
gint g_slist_index(GSList *list, gpointer data)
void g_slist_foreach(GSList *list, GFunc func, gpointer user_data)

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

guint g_slist_length(GSList *list)
GSList *g_slist_concat(GSList *list1, GSList *list2)
GSList *g_slist_reverse(GSList *list)
GSList *g_slist_copy(GSList *list)

И, наконец, существуют некоторые возможности для сортировки списков, показанные в списке функций 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()".

GSList *g_slist_insert_sorted(GSList *list, gpointer data,
                              GCompareFunc func)
GSList *g_slist_sort(GSList *list, GCompareFunc func)
GSList *g_slist_find_custom(GSList *list, gpointer data,
                            GCompareFunc func)

---

Партнёры:

Хостинг: