GLib: Obousměrné seznamy (2)

Prohledávání

Budete-li kdy potřebovat v seznamech vyhledávat položky, práci vám usnadní čtveřice funkcí, které jsou pro tyto účely implementovány.

Následující dvě funkce procházejí seznamem list a vracejí gint ovou hodnotu – pořadí, nebo chcete-li index daného prvku. V čem se jejich práce liší, je identifikace „dané“ položky. Zatímco funkce

gint g_list_position(GList *list, GList *llink); 

jako parametr požaduje přímo prvek llink seznamu (jehož index určí), funkci

gint g_list_index(GList *list, gpointer data); 

stačí k nalezení indexu prvku pouze pointer na jeho  data.

Číslování probíhá od nuly a tedy bude-li odpovídajícím prvkem právě první položka seznamu, vrátí se 0. Nepodaří-li se stanovenou položku v seznamu najít, bude návratová hodnota –1.

Trochu z jiného úhlu se na hledání v seznamu dívají následující dvě funkce:

GList* g_list_find(GList *list, gpointer data);
GList* g_list_find_custom(GList *list, gpointer data,
                          GCompareFunc func);

Obě vracejí pointer na nalezenou položku seznamu, obě požadují jako parametr list počátek tohoto seznamu stejně tak jako pointer na data hledaného prvku. Odlišný však je způsob, jakým položku GList vyhledají.

g_list_find() 

Použitím funkce g_list_find_cus­tom() máte nad vyhledáváním úplnou kontrolu. Jako poslední argument této funkce se předává nám již známá funkce typu GCompareFunc a právě ona rozhoduje o relaci mezi dvěma položkami seznamu a tak potažmo i o tom, který prvek seznamu bude prohlášen za ten pravý. Jak se taková funkce vytváří, jsme si popsali minule. V tomto případě jako parametry dostane dva gconstpointer y: data položky seznamu (struktury GList) a uživatelská data (pointer, který je předán funkci g_list_find_cus­tom()). Funkce func pak musí rozhodnout, jsou-li tyto dvě položky shodné a v případě rovnosti vrátit 0. (V případě nerovnosti nenulovou hodnotu.)

Příklad:

/* Priklad pouziti funkce g_list_find_custom() */

#include <glib.h>

gint rovno(gconstpointer a, gconstpointer b)
{
  return (strcmp(a, b));
}

gint main(void)
{
  GList* list = NULL;
  GList* nalezeno;

  list = g_list_append(list, "Josef");
  list = g_list_append(list, "Karel");
  list = g_list_append(list, "Petr");
  list = g_list_append(list, "Hugo");

  nalezeno = g_list_find_custom(list, "Petr", rovno);
  if (nalezeno)
    printf("Nalezeno: %s\n", nalezeno->data);

  g_list_free(list);
}

Foreach

Při práci se seznamy se často opakuje kód, ve kterém provádíme nějakou operaci na každou položku seznamu: třeba nějaké výpočty, tisk a podobně. Knihovna GLib pro tyto účely disponuje funkcí

void g_list_foreach(GList *list, GFunc func, gpointer user_data); 

…která na každý prvek seznamu list zavolá funkci func a mimo jiné jí předá i data  user_data.

A jak se s touto konstrukcí pracuje? Pochopitelně, nejprve si musíme vytvořit funkci, která bude provádět námi požadované operace. Předpis GFunc takové funkce je:

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

Tedy je to funkce nevracející nic, která vyžaduje dva argumenty. Prvním z nich, data, je pointer na data položky seznamu. Parametr user_data pak zase uživatelská data, které se předávají funkci g_list_foreach().

Máme-li funkci func definovánu, můžeme zavolat funkci g_list_foreach(). Ta vezme každý prvek obousměrného seznamu list a na jeho data zavolá funkci func, pro kterou jako argumenty použije právě data aktuální položky a parametr  user_data.

Příklad:

/* Ukazka pouziti funkce g_list_foreach() */

#include <glib.h>

/* Funkce odpovidajici typu GFunc - tisk polozky seznamu */
void print_item(gpointer data, gpointer user_data)
{
  printf("%s - jmeno: %s\n", user_data, data);
}

gint main(void)
{
  GList* list = NULL;

  list = g_list_append(list, "Josef");
  list = g_list_append(list, "Karel");
  list = g_list_append(list, "Petr");
  list = g_list_append(list, "Silvestr");
  list = g_list_append(list, "Emil");
  list = g_list_append(list, "Hugo");

  g_list_foreach(list, print_item, "Seznam hracu");

  g_list_free(list);
}

Po spuštění této malé ukázky by se mělo vypsat:

Seznam hracu - jmeno: Josef
Seznam hracu - jmeno: Karel
Seznam hracu - jmeno: Petr
Seznam hracu - jmeno: Silvestr
Seznam hracu - jmeno: Emil
Seznam hracu - jmeno: Hugo

Další funkce

guint g_list_length(GList *list); 

…vrátí počet prvků v obousměrném seznamu list.

GList* g_list_copy(GList *list); 

…vytvoří nově alokovanou kopii seznamu list. Pointery na data se do nového seznamu pouze jednoduše kopírují, takže ukazují-li na nějaké dynamické datové položky, budou mít oba seznamy všechny ukazatele na stejná data (jinými slovy, kopie dynamických dat se neprovádí).

GList* g_list_reverse(GList *list); 

…obrátí pořadí prvků v seznamu list a vrátí pointer na nový počátek. (Tzn. první položka bude poslední, druhá bude předposlední atd.)

GList* g_list_sort(GList *list, GCompareFunc compare_func); 

…seřadí seznam list podle kritéria definovaného funkcí compare_func. Tato funkce musí být typu GCompareFunc a více jste se o ní mohli dočíst v minulém díle. Funkce vrátí pointer na nový začátek seznamu nebo NULL, je-li argument list roven NULL.

GList* g_list_concat(GList *list1, GList *list2); 

…seznam list2 připojí na konec seznamu list1. Pozor: položky druhého seznamu nejsou duplikovány. Prvky seznamu list2 se použijí přímo.

Pokud jste dočetli až sem, víte už o obousměrných seznamech téměř vše. Záměrně jsem však ještě vynechal několik fakt o alokaci položek seznamů do paměti. Jelikož se tento způsob v knihovně GLib používá častěji, nechám si jej někdy na později, až budeme mít více znalostí. Příště se můžete těšit na praktickou ukázku použití obousměrných seznamů: na implementaci mechanizmu automatického doplňování řetězců (automatic string completion).