GLib: Obousměrné seznamy

Seznam (angl. list) jako abstraktní datová struktura je velmi často používaný v oblasti nenumerického zpracování dat. Je tvořen dynamickou posloupností prvků, které jsou navzájem svázány pointery tak, že tvoří pomyslný řetěz položek. V programu pak stačí uchovávat pouze pointer na první prvek seznamu a díky němu se postupně přes jednotlivé pointery můžeme dostat ke každé položce seznamu.

V podstatě se rozeznávají dva druhy seznamů: jednosměrné a obousměrné. Oba dva druhy jsou knihovnou GLib dobře implementovány. V dnešním díle si probereme obousměrné seznamy a jednosměrné si necháme na jindy.

Obousměrný seznam – ostatně, i jeho název to napovídá – se od jednosměrného liší tím, že jej lze procházet oběma směry. Je tvořen položkami typu  GList:

struct GList
{
  gpointer data;
  GList *next;
  GList *prev;
};

Pointer data slouží k uložení ukazatele na data, které chceme v seznamu uchovávat. Potřebujeme-li vytvořit seznam integerů (ať už gint nebo guint), můžeme s výhodou využít konverzních maker mezi typy gint ( guint) a gpointer, které jsme si popsali v druhé části.

Položky next a prev jsou pointery na následující popř. předcházející prvek seznamu; můžou se používat při procházení seznamem v obou směrech.

U obousměrných seznamů – v kontrastu s tím, na co jsme byli dosud zvyklí – neexistuje funkce pro vytvoření GList u. Prázdný seznam je jednoduše GList* nastavený na NULL. Funkcím, které se seznamy pracují, se obvykle předává pointer na první položku seznamu.

Přidávání položek do obousměrného seznamu

K přidávání položek do seznamu slouží některá z následujících funkcí:

GList* g_list_append(GList *list, gpointer data);
GList* g_list_prepend(GList *list, gpointer data);
GList* g_list_insert(GList *list, gpointer data, gint position);

Pro všechny tři platí, že argument list je pointer na první položku seznamu, nebo NULL, vytváříme-li nový seznam. Argument data jsou ukládaná data (buď pointer na datovou položku nebo přetypovaný  gint/guint).

Funkce g_list_append() přidá prvek data na konec seznamu, g_list_prepend() na začátek seznamu a funkce g_list_insert() vloží položku data na pozici danou argumentem position. Je-li position, argument funkce g_list_insert(), záporná hodnota nebo hodnota větší než počet prvků v seznamu, uloží se nový prvek na konec. Volání g_list_insert() s  position rovno 0 je ekvivalentem volání g_list_prepend, position rovno 1 vytvoří novou položku hned za prvkem list a podobně.

Příklad:

/* Vytvoreni novych seznamu (inicializovanych jako prazdne) */
GList *list = NULL;
GList *number_list = NULL;

/* Seznam retezcu. Navratovou hodnotou je treba
 * vzdy aktualizovat pointer na prvni prvek seznamu: */
list = g_list_append(list, "druhy");
list = g_list_append(list, "treti");
list = g_list_prepend(list, "prvni");

/* Seznam integerovych hodnot */
number_list = g_list_append(number_list, GINT_TO_POINTER (27));
number_list = g_list_prepend (number_list, GINT_TO_POINTER (14));

Speciální možností, jak vložit položku do seznamu, je použití funkce:

GList* g_list_insert_sorted(GList *list, gpointer data,
                            GCompareFunc func);

Tato funkce přidá do obousměrného seznamu, na jehož začátek ukazuje list, položku data na pozici určenou funkcí func, která je předávaná jako poslední argument.

Funkce typu GCompareFunc:

gint (*GCompareFunc) (gconstpointer a, gconstpointer b); 

…se při práci s knihovnou GLib používá v různém kontextu, ale vždy ve spojení se řazením prvků. Jejím úkolem je rozhodnout, která z položek předaná jako parametr a nebo b je „větší“. Při použití na seznamy musí splňovat toto (a je na programátorovi, aby takovou funkci vytvořil):

• jestliže první argument ( a) má být umístěn před druhým ( b), musí funkce vrátit zápornou hodnotu,
• jestliže a a b jsou stejné, musí vrátit 0,
• a jestliže a patří za položku b, musí vrátit kladnou hodnotu.

Při práci s jinými typy (např. hash tabulkami) se na funkce tohoto typu mohou klást jiné nároky, ale to zdůrazníme, až se těmito typy budeme zabývat.

Příklad:

#include <glib.h>

/* Porovnani float hodnot */
gint MyCompare (gconstpointer a, gconstpointer b)
{
  return ( *((gfloat *) a) - *((gfloat *) b) );
}

gint main(void)
{
  GList *float_list = NULL;
  gfloat *item;

  item = g_new(gfloat, 1);
  *item = 12.98;
  float_list = g_list_insert_sorted(float_list, item, MyCompare);

  item = g_new(gfloat, 1);
  *item = 1.54;
  float_list = g_list_insert_sorted(float_list, item, MyCompare);

  item = g_new(gfloat, 1);
  *item = 33.35;
  float_list = g_list_insert_sorted(float_list, item, MyCompare);

  g_list_free(float_list);
}

Pozor! Všechny funkce sloužící k přidávání prvků (a nejen ty) jako návratovou hodnotu předávají pointer na nový počátek seznamu, který se díky použitému způsobu alokace může kdykoliv změnit. Vždy se proto raději ujistěte, že jste novou hodnotu zaznamenali.

Odstraňování položek z obousměrného seznamu

GList* g_list_remove(GList *list, gpointer data); 

…tato funkce odstraní z obousměrného seznamu list položku s daty data. Argument list je tedy pointer na první položku seznamu a data pointer na uložená data. Navrácená hodnota je nový počátek seznamu. Jestliže se v seznamu vyskytují dvě položky se stejnými daty, je odstraněna pouze první z nich. Jestliže v seznamu neexistuje položka, která by data obsahovala, zůstane seznam nezměněn.

Funkcí g_list_remove() se prvek GList dealokuje. data však zůstanou nedotčena – v případě, že už nejsou potřeba, je nutno je dealokovat zvlášť.

GList* g_list_remove_link(GList *list, GList *llink); 

…ze seznamu, na jehož počátek ukazuje parametr list, odstraní prvek llink, ale nedealokuje ho. Položky prev a next (viz struktura GList) odstraněného prvku llist se nastaví na NULL, takže se z  llist u vlastně stane samostatný seznam o jednom prvku. Není-li již takto odstraněné položky potřeba, je nutno ji dealokovat voláním funkce  g_list_free_1().

Dealokace obousměrných seznamů

Vnitřní mechanizmus alokace a dealokace paměti pro seznamy je trochu netypický a jistě si zaslouží podrobnější popis. V příštích dílech, až budeme se seznamy trochu více obeznámeni, se na něj podíváme. Pro dnešek si pouze povíme, jak uvolnit z paměti celý seznam – voláním funkce:

void g_list_free(GList *list); 

…kde list je pointer na počátek seznamu.

Uvolnění jedné položky ( list) se provede:

void g_list_free_1 (GList *list); 

Pozor! Není možné libovolnou položku seznamu pouze takto jednoduše dealokovat. Musíme ji nejprve ze seznamu odstranit voláním funkce  g_list_remove_link().

Je třeba podotknout, že voláním předchozích funkcí se dealokují pouze uzly seznamu – prvky reprezentované strukturou GList. Uchovávaná data zůstanou nedotčena, proto by měla být dealokována dříve.

Procházení obousměrným seznamem

GList* g_list_first(GList *list); 

…vrátí první položku seznamu. list je jeho libovolný prvek.

GList* g_list_last (GList *list); 

…vrátí poslední položku seznamu. list je libovolný prvek.

K získání následujícího nebo předcházejícího prvku můžete využívat přímý přístup k položkám next popř. prev struktury GList nebo použít následující makra, která navíc provádějí kontrolu na (nechtěné) předání NULL:

#define g_list_previous(list) 

g_list_previous(list) 

GList* g_list_nth(GList *list, guint n); 

…vrátí n-tý prvek v pořadí od prvku list ( list je chápán jako nultý) nebo NULL, není-li v seznamu tolik prvků. Záporné hodnoty n nejsou povoleny.

gpointer g_list_nth_data (GList *list, guint n); 

…vrátí pointer na data n-tého prvku v pořadí od prvku list ( list je chápán jako nultý) nebo NULL, není-li v seznamu tolik prvků. Záporné hodnoty n nejsou povoleny.

A to je pro dnešek vše. V příštím díle povídání o obousměrných seznamech GList dokončíme.