GLib: Kvarky

Motivace aneb vykonstruovaný příklad ne nepodobný klíčovaným seznamům dat knihovny GLib

Představte si, že máte v paměti nějaký seznam dat, jejichž prvkem je mimo jiné i jakýsi klíč, který je v podstatě jen nějaký řetězec, a že tento seznam velmi často prohledáváte. Porovnání jedné položky s hledaným klíčem tedy znamená porovnávat řetězce – a to není zrovna dvakrát efektivní. Jak algoritmus zrychlit?

Pokud říkáte, že použijete hash tabulku, máte patrně pravdu. Co když ale takových seznamů budete mít desítky nebo stovky a každý bude udržovat jen několik málo záznamů?

Potřebujeme se přece zbavit jen zdlouhavého porovnávání řetězců. Co kdyby existoval způsob, jak řetězec „přeložit“ na číselnou konstantu, se kterou pracovat by už byla jedna radost? – Přesně k tomu jsou kvarky (quarks).

Co jsou to kvarky

Kvarky je mechanizmus obousměrné asociace mezi řetězcem a jednoznačným přirozeným kladným číslem. Máte-li k dispozici číselnou konstantu, můžete z ní odvodit přiřazený řetězec a naopak, podle řetězce lze zjistit jeho identifikační čís­lo.

Kvarky jsou tedy jakési dvojice řetězec – přirozené číslo.

Jednoznačné integerové konstantě je přiřazen speciální typ – GQuark. Jeho přesná definice zní:

typedef guint32 GQuark;

Kvůli maximální rychlosti jsou kvarky vnitřně v paměti uchovávány nadvakrát. Pro snazší konverzi z řetězce na číslo se ukládají do hash tabulky a pro převod z  GQuark u na řetězec do pole řetězců, jehož indexem je právě ona jednoznačná celočíselná konstanta.

V celém programu je vždy jen jedno pole a jedna hash tabulka uchovávající všechny kvarky. Knihovna GLib si pro tyto účely (a není to poprvé ani naposled) zakládá vnitřní globální pole a hash tabulku, ke kterým není z vnějšku přístup.

Kvarky se používají při práci s některými dalšími mechanizmy knihovny GLib, o kterých bude řeč v příštích článcích. Konkrétně to jsou klíčované seznamy dat (Keyed Data Lists) a soupravy dat (Datasets).

Patrně by se dalo přijít i na další způsoby použití, nedomnívám se ale, že samostatné kvarky budete používat příliš často. Jejich nevýhodu spatřuji v tom, že nemáte kontrolu nad tím, jak se číselné konstanty řetězcům přiřazují. Je to sice popořadě vzestupně (1, 2, 3 atd.), nemůžete však explicitně přikázat, který řetězec má mít jaké číslo. Při troše smůly to může být při každém spuštění programu něco jiného. Ve většině případů si jistě vystačíte s klasickými konstantami a makry preprocesoru.

Práce s  GQuark y

GQuark g_quark_from_string(const gchar *string); 

…vrátí GQuark (jednoznačnou číselnou konstantu) řetězce string. Jestliže daný řetězec nemá ještě přiřazen žádný GQuark, vytvoří se nový kvark s kopií řetězce string (podrobněji: kopie řetězce string se uloží do výše zmíněného pole a hash tabulky). S původním string em si potom můžete dělat co chcete – asociace s kvarkem se nijak nenaruší.

GQuark g_quark_from_static_string(const gchar *string); 

…vrátí GQuark identifikující řetězec string. Jestliže string ještě není asociován s žádným GQuark em, vytvoří se nová dvojice s použitím řetězce string přímo. Do pole a hash tabulky se uloží rovnou řetězec string. Šetří se tím paměť, musíte však zaručit, že string bude existovat po celou dobu běhu programu (např. statický řetězec).

gchar* g_quark_to_string(GQuark quark); 

…vrátí řetězec, který je asociovaný s daným GQuark em quark. Pozor! S vráceným řetězcem byste měli pracovat obezřetně a používat ho raději jen ke čtení, protože je uložen přímo v poli i hash tabulce kvarků.

GQuark g_quark_try_string(const gchar *string); 

Tato funkce se pokusí najít GQuark asociovaný s řetezcem string. V případě úspěchu jej použije jako návratovou hodnotu. Nemá-li string asociovaný ještě žádný GQuark, vrátí 0. Tuto funkci použijte, chcete-li zjistit, jestli už je řetězec string „očíslován“. Chcete-li, aby byla v případě nenalezení GQuark u vytvořena nová asociace, použijte raději funkci g_quark_from_string() nebo  g_quark_from_static_string().

Jelikož kvarky existují po celou dobu běhu programu a není možné je nijak zničit, s jejich dealokováním si nelamte hlavu. Obstará to za vás operační systém při ukončení aplikace.

Příklad:

/* Priklad pouziti GQuark */

/* Nejaka struktura (uchovava pohlavi a vek) */
typedef struct {
  GQuark sex;
  guint age;
} MyStruct;

gint main(void)
{
  MyStruct item1, item2, item3;
  GQuark male, female;
  gchar *female_str;

  /* Vytvoreni kvarku ze statickeho retezce */
  male = g_quark_from_static_string("Male");

  /* Vytvoreni kvarku z dynamickeho retezce */
  female_str = g_strdup("Female");
  female = g_quark_from_string(female_str);
  g_free(female_str);

  /* Pouziti kvarku */
  item1.sex = male;
  item2.sex = g_quark_from_string("Male");
    /* (hodnoty item1.sex i item2.sex se rovnaji) */
  item3.sex = g_quark_from_string("Female");

  /* Ziskani retezce z kvarku */
  printf("item1 ma pohlavi: %s\n", g_quark_to_string(item1.sex));
  printf("item2 ma pohlavi: %s\n", g_quark_to_string(item2.sex));
  printf("item3 ma pohlavi: %s\n", g_quark_to_string(item3.sex));
}

Uvedený příklad by měl po spuštění vypsat:

item1 ma pohlavi: Male
item2 ma pohlavi: Male
item3 ma pohlavi: Female

Tímto máme „předsíň“ ke klíčovaným seznamům a soupravám dat za sebou. V příštím díle se do nich pustíme a GQuark y s úspěchem použijeme.