Hlavní navigace

GLib: Obousměrné seznamy

Michal Burda

Obousměrný seznam je datový typ jako vystřižený z učebnice programování. Obvykle se na něm učí použití pointerů a datových struktur. Všichni ale jistě s pointery pracovat umíme a tak ode dneška, když budeme potřebovat obousměrné seznamy, je nebudeme programovat sami, ale zkušeně sáhneme po knihovně GLib, která je pro nás implementuje.

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()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);
  printf("%f, %f, %f \n", *(gfloat*) (float_list->data),     *(gfloat*) (float_list->next->data),     *(gfloat*) (float_list->next->next->data));   g_free(float_list->data);   g_free(float_list->next->data);   g_free(float_list->next->next->data));
  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.

Našli jste v článku chybu?
DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Podnikatel.cz: Změny v cestovních náhradách 2017

Změny v cestovních náhradách 2017

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

Vitalia.cz: Potvrzeno: Pobyt v lese je skvělý na imunitu

Potvrzeno: Pobyt v lese je skvělý na imunitu

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Vitalia.cz: Proč vás každý zubař posílá na dentální hygienu

Proč vás každý zubař posílá na dentální hygienu