GLib: Hash tabulky (2)

Vkládání dat do GHashTable

void g_hash_table_insert(GHashTable *hash_table,
                         gpointer key,
                         gpointer value);

…vloží do hash tabulky hash_table klíč key a data value. Jestliže už key v tabulce existuje, jeho stávající hodnota je nahrazena novou ( value).

Je třeba upozornit, že hodnoty key a value jsou v hash tabulce uchovány tak, jak je funkce g_hash_table_in­sert() dostane. Neprovádí se žádná kopie apod. Používáte-li pouze statická data, je vše v pořádku, ale s dynamickými daty nastávají potíže. Musíte ručně zajistit, že se dealokují při odstraňování z hash tabulky. Z tohoto důvodu se nedoporučuje do jedné GHashTable ukládat statické a dynamické hodnoty zároveň (ty statické realokujte na dynamické použitím funkce  g_strdup()).

S dynamickými daty je ještě trochu víc problémů. K tomu, abyste celou záležitost dobře pochopili, je třeba, abychom si trochu popsali, jak funkce g_hash_table_in­sert() funguje uvnitř. (Ostatně, zdrojáky knihovny GLib jsou samy o sobě docela zajímavé a rozhodně stojí za přečtení nebo alespoň nahlédnutí.)

Jak tedy g_hash_table_in­sert() funguje? Nejprve se v  hash_table pokusí nalézt data s klíčem key. Pokud takové nalezne, nahradí je novou hodnotou value. V opačném případě uloží key i  value na novou pozici v tabulce.

Vyplývá z toho následující: pokud do GHashTable ukládáte dynamicky alokovaná data, musíte se před operací vkládání přesvědčit, že tam žádná data s klíčem key ještě nejsou. Pokud by byly, musíte ta stará nejprve dealokovat.

Pokud navíc používáte i dynamicky alokované klíče, je lepší před operací vkládání stará data i s jejich klíčem dealokovat a z tabulky ručně odstranit. (Funkce pro tuto činnost budou popsány později.) Pokud byste tak neučinili, nemohli byste si nikdy být jisti tím, že někde nemáte nadbytečně alokovaný klíč. Jestli ten, který jste předali jako argument funkci g_hash_table_in­sert() byl skutečně použit a uložen do tabulky nebo jestli už v tabulce existuje starý stejný klíč a tedy ten nový zůstane nepoužit a je vhodné jej dealokovat.

Získání dat z  GHashTable

gpointer g_hash_table_lookup(GHashTable *hash_table,
                             gconstpointer key);

…v hash tabulce hash_table vyhledá záznam s klíčem key a vrátí pointer na jeho data nebo NULL, nebyl-li takový klíč nalezen.

gboolean g_hash_table_lookup_extended(GHashTable *hash_table,
                                      gconstpointer lookup_key,
                                      gpointer *orig_key,
                                      gpointer *value);

…tato funkce vyhledá v tabulce hash_table záznam odpovídající klíči lookup_key a do proměnných orig_key a value uloží původní klíč a jemu přiřazená data. Funkce vrátí TRUE, byl-li klíč v tabulce nalezen nebo FALSE v opačném případě. Tato funkce je užitečná, když potřebujete dealokovat originální klíč, třeba před voláním g_hash_table_remove() (viz později).

Odstranění dat z  GHashTable

void g_hash_table_remove(GHashTable *hash_table,
                         gconstpointer key);

…z  GHashTable hash_table odstraní klíč key a jemu asociovaná data. Pokud hash tabulka uchovává dynamicky alokovaná data, musíte se postarat o jejich uvolnění z paměti ručně.

guint g_hash_table_foreach_remove(GHashTable *hash_table,
                                  GHRFunc func,
                                  gpointer user_data);

gboolean(*GHRFunc)(gpointer key, gpointer value,
                   gpointer user_data);

Funkce g_hash_table_foreach_remove() slouží k odstranění i několika položek najednou. Na každou dvojici klíč–data tabulky hash_table zavolá uživatelskou funkci func, která musí odpovídat předpisu GHRFunc, a když ona vrátí TRUE, daný záznam bude z  hash_table odstraněn.

Parametr user_data bude v nezměněné podobě předán volané funkci  func.

Funkce g_hash_table_foreach_remove() vrací počet odstraněných položek.

Od funkce typu GHRFunc se tedy očekává, že rozhodne, který záznam bude odstraněn. Jako parametry jí je předán klíč key a jeho data ( value). Argument user_data je pointer, který je předán jako parametr se stejným jménem funkci  g_hash_table_foreach_remove().

Další funkce

Následující funkce slouží ke zjištění velikosti hash tabulky:

guint g_hash_table_size(GHashTable *hash_table); 

Funkce vrátí počet dvojic klíč–data uložených v tabulce hash_table.

Při práci s hash tabulkami máte i mechanizmus „for each“ známý třeba z kapitoly o seznamech. Jeho implementace do hash tabulek je obvyklá a drží se zavedených konvencí.

void g_hash_table_foreach(GHashTable *hash_table,
                          GHFunc func,
                          gpointer user_data);

void(*GHFunc) (gpointer key, gpointer value,
               gpointer user_data);

Funkce g_hash_table_foreach() zavolá na každý záznam (dvojici klíč–data) tabulky hash_table funkci func, které předá klíč ( key), jeho data ( value) a uživatelská data ( user_data).

Poslední dvojice funkcí slouží k optimalizaci výkonu.

void g_hash_table_freeze(GHashTable *hash_table);
void g_hash_table_thaw(GHashTable *hash_table);

Standardně, po každém vložení nebo odebrání prvku z tabulky se provádí vnitřní přeuspořádání položek. Tato operace ukrádá kousek strojového času, takže když hodláte v hash tabulce provést najednou větší množství změn, je vhodné nejprve zavolat funkci g_hash_table_fre­eze(), která tabulku hash_table zmrazí, takže se po každém přidání či odebrání prvku nebude přebudovávat vnitřní struktura položek. Po dokončení úprav zavolejte g_hash_table_thaw(), přebudovávání obnovíte.

Hash tabulky si pamatují, kolikrát byly „zmrazeny“ a proto kolikrát zavoláte funkci g_hash_table_fre­eze(), tolikrát musíte zavolat i  g_hash_table_thaw(), aby se tabulka „rozmrazila“, tedy aktivovala vnitřní přeuspořádává­ní prvků.

Příklad:

#include <glib.h>

/* "bezpecna" verze funkce g_hash_table_insert()
 * pro praci s dynamickymi daty i klici */
void my_hash_insert_safe(GHashTable *table,
       gchar *key, gchar *value)
{
  gpointer orig_key;
  gpointer orig_value;

  /* podivej se, jestli uz takovy zaznam neexistuje */
  if (g_hash_table_lookup_extended(table, (gpointer) key,
        &orig_key, &orig_value)) {
    /* existuje, proto jej odstran a dealokuj */
    g_hash_table_remove(table, orig_key);
    g_free(orig_key);
    g_free(orig_value);
  }
  /* vlozeni polozky (mame jistotu, ze tam data
   * s klicem key jeste nejsou...) */
  g_hash_table_insert(table, key, value);
}

/* dealokace klicu i dat */
gboolean dealokuj_vse(gpointer key, gpointer val,
                      gpointer user_data)
{
  g_free(key);
  g_free(val);
  return (TRUE);
}

/* hlavni program */
gint main(void)
{
  GHashTable *table;

  /* hash tabulka, kde klicem i daty budou retezce */
  table = g_hash_table_new(g_str_hash, g_str_equal);

  /* uloz nejake hodnoty */
  my_hash_insert_safe(table,
    g_strdup("Reditel"), g_strdup("Josef Rak"));
  my_hash_insert_safe(table,
    g_strdup("Sekretarka"), g_strdup("Alena Mlzova"));
  my_hash_insert_safe(table,
    g_strdup("Mistr"), g_strdup("Jan Stika"));
  my_hash_insert_safe(table,
    g_strdup("Delnik"), g_strdup("Petr Klepeto"));
  my_hash_insert_safe(table,
    g_strdup("Ucen"), g_strdup("Pepa Kos"));

  /* ukazka pristupu k datum */
  printf("Tabulka ma %d zaznamu, mistrem je: %s\n",
    g_hash_table_size(table),
    g_hash_table_lookup(table, "Mistr"));

  /* prepsani ulozene hodnoty */
  my_hash_insert_safe(table,
    g_strdup("Mistr"), g_strdup("Hugo Boss"));

  /* kontrolni vypis */
  printf("Tabulka ma %d zaznamu, mistrem je: %s\n",
    g_hash_table_size(table),
    g_hash_table_lookup(table, "Mistr"));

  /* dealokace vsech polozek */
  g_hash_table_foreach_remove(table, dealokuj_vse, NULL);

  printf("Tabulka ma %d zaznamu, mistrem je: %s\n",
    g_hash_table_size(table),
    g_hash_table_lookup(table, "Mistr"));

  /* dealokace hash tabulky */
  g_hash_table_destroy(table);
}

Na příkladu jsem se pokusil ukázat jednu z možností, jak se vypořádat s dynamickými daty i klíči. Spustíte-li si tuto malou ukázku, mělo by se vám na terminál vypsat:

Tabulka ma 5 zaznamu, mistrem je: Jan Stika
Tabulka ma 5 zaznamu, mistrem je: Hugo Boss
Tabulka ma 0 zaznamu, mistrem je: (null)

A to je o hash tabulkách opravdu vše. U dalšího pokračování se těší