Dokumentace souboru white_box_code.cpp

Definice metod tridy reprezentujici hashovácí tabulku. ...

#include "white_box_code.h"
#include <stdio.h>

Funkce
size_t	hash_function (const char *str)
	Výpočet haše pro zadaný řetězec. ...
size_t	hash_map_lookup_handle (hash_map_t *self, const char *key, size_t hash, bool ignore_dummy)
	Výpočet indexu v hašovací tabulce v závislosti na dvojici klíč-hash. ...
size_t	hash_map_lookup (hash_map_t *self, const char *key, size_t hash)
	Výpočet indexu v hašovací tabulce v závislosti na dvojici klíč-hash. ...
hash_map_state_code_t	hash_map_init (hash_map_t *self, size_t size)
	Inicializace hašovací tabulky. ...
hash_map_t *	hash_map_ctor ()
	Konstruktor hašovací tabulky. ...
void	hash_map_clear (hash_map_t *self)
	Dealokace vytvořených položek a vymazání indexu. ...
void	hash_map_dtor (hash_map_t *self)
	Destruktor hašovací tabulky. ...
hash_map_state_code_t	hash_map_reserve (hash_map_t *self, size_t size)
	Realokace rezervovaného místa pro index. ...
size_t	hash_map_size (hash_map_t *self)
	Vrací počet vložených záznamů do tabulky. ...
size_t	hash_map_capacity (hash_map_t *self)
	Vrací alokované místa pro tabulku. ...
bool	hash_map_contains (hash_map_t *self, const char *key)
	Obsahuje tabulka záznam s daným klíčem? ...
hash_map_state_code_t	hash_map_put (hash_map_t *self, const char *key, int value)
	Vloží klíč a hodnotu do tabulky. ...
hash_map_state_code_t	hash_map_get (hash_map_t *self, const char *key, int *dst)
	Uloží hodnotu asociovanou se zadaným klíčem na určené místo v paměti. ...
hash_map_state_code_t	hash_map_remove (hash_map_t *self, const char *key)
	Odstranění položky z hašovací tabulky. ...
hash_map_state_code_t	hash_map_pop (hash_map_t *self, const char *key, int *dst)
	Uloží hodnotu z hašovací tabulky a odstraní záznam. ...

Detailní popis

Definice metod tridy reprezentujici hashovácí tabulku.

Autor

Karel Ondřej

Martin Dočekal

Dokumentace funkcí

hash_function()

size_t hash_function

(

const char *

str

)

Výpočet haše pro zadaný řetězec.

Parametry

[in]

str

klíč

Návratová hodnota

hash

hash_map_capacity()

size_t hash_map_capacity

(

hash_map_t *

self

)

Vrací alokované místa pro tabulku.

Pozor

hash_map_size(map) se nerovná hash_map_capacity(map) ! Jelikož je alokace (resp. realokace) paměti časově "drahá" operace, alokuje se vždy více paměti než je aktuálně potřeba. K realokaci tedy dochází jen když je potřeba a výrazně méně často.

Parametry

[in]

self

Ukazatel na strukturu hašovací tabulky.

Návratová hodnota

Velikost alokované hašovací tabulky.

Viz také

hash_map_reserve, hash_map_put, hash_map_pop, hash_map_remove

hash_map_clear()

void hash_map_clear

(

hash_map_t *

self

)

Dealokace vytvořených položek a vymazání indexu.

Parametry

[in]

self

Ukazatel na strukturu hašovací tabulky.

hash_map_contains()

bool hash_map_contains	(	hash_map_t *	self,
		const char *	key
	)

Obsahuje tabulka záznam s daným klíčem?

Vyhledá zadaný klíč v tabulce a pokud tabulka obsahuje pod daným klíčem záznam, vrátí nenulovou hodnotu.

Parametry

[in]	self	Ukazatel na strukturu hašovací tabulky.
[in]	key	Klíč do tabulky.

Návratová hodnota

Nenulová hodnota pokud se záznam asociován se zadaným klíčem nachází v tabulce.

hash_map_ctor()

hash_map_t* hash_map_ctor

(

)

Konstruktor hašovací tabulky.

Vytvoří a inicializuje hašovací tabulku s velikostí indexu 8, tzn. hašovací tabulka může obsahovat 8 záznamů s různými klíči.

Příklad užití:

hash_map_t* map = hash_map_ctor();
// do something
hash_map_dtor(map);

Návratová hodnota

Ukazatel na inicializovanou hašovací tabulku. V případě chyby alokace vrací hodnotu NULL.

Viz také

hash_map_init

hash_map_dtor()

void hash_map_dtor

(

hash_map_t *

self

)

Destruktor hašovací tabulky.

Uklidí a uvolní paměť alokovanou hašovací tabulkou, tzn. jednotlivé položky seznamu, index a následně samotnou tabulku self .

Příklad užití:

hash_map_t* map = hash_map_ctor();
// do something
hash_map_dtor(map);

Parametry

[in]

self

Ukazatel na hašovací tabulku

Viz také

hash_map_clear

hash_map_get()

hash_map_state_code_t hash_map_get	(	hash_map_t *	self,
		const char *	key,
		int *	value
	)

Uloží hodnotu asociovanou se zadaným klíčem na určené místo v paměti.

Vyhledá klíč v tabulce a uloží hodnotu přiřazenou ke klíči na místo kde ukazuje argument value . Pokud tabulka neobsahuje k danému klíči žádný záznam, vrací hodnotu KEY_ERROR .

Příklad užití:

int value;
hash_map_state_code_t error = hash_map_get(map, "aloha", &value);

Parametry

[in]	self	Ukazatel na strukturu hašovací tabulky.
[in]	key	Klíč do tabulky.
[out]	value	Ukazatel na místo, kde se uloží hodnota.

Návratová hodnota

Vrací KEY_ERROR pokud se klíč nenachází v tabulce, jinak OK.

hash_map_init()

hash_map_state_code_t hash_map_init	(	hash_map_t *	self,
		size_t	size
	)

Inicializace hašovací tabulky.

Metoda alokuje a inicializuje položky struktury hašovací tabulky.

Parametry

self[in]	Ukazatel na neinicializovanou hašovací tabulku
size[in]	Počet prvků v tabulce.

Návratová hodnota

MEMORY_ERROR v případě chyby v alokaci paměti, jinak OK.

hash_map_lookup()

size_t hash_map_lookup	(	hash_map_t *	self,
		const char *	key,
		size_t	hash
	)

Výpočet indexu v hašovací tabulce v závislosti na dvojici klíč-hash.

Parametry

[in]	self	Ukazatel na strukturu hašovací tabulky.
[in]	str	Klíč.
[in]	str	Haš zadaného klíče.

Návratová hodnota

Index záznamu asociovaný k zadanému klíči a haši, nebo prázdné místo v tabulce.

Viz také

hash_map_lookup_handle

hash_map_lookup_handle()

size_t hash_map_lookup_handle	(	hash_map_t *	self,
		const char *	key,
		size_t	hash,
		bool	ignore_dummy
	)

Výpočet indexu v hašovací tabulce v závislosti na dvojici klíč-hash.

V případě kolize funkce nalezne další volný index v tabulce. V případě vyhledávání považujeme dummy objekt jako jakýkoliv jiný záznam, tedy ignore_dummy je nastaveno na false . Při vkládání je dummy objekt ekvivalentní prázdnému místu, tedy ignore_dummy je nastaveno na true . Tento jev je způsoben kvůli kolizím klíčů. Když je záznam odstraněn, je nahrazen za dummy objekt, aby bylo možné vyřešit případné kolize.

Parametry

[in]	self	Ukazatel na strukturu hašovací tabulky.
[in]	str	Klíč.
[in]	str	Haš zadaného klíče.
[in]	ignore_dummy	Pokud true, dummy objekt je vždy přeskočen, pokud false, dummy objekt je interpretován jako NULL.

Návratová hodnota

Index záznamu asociovaný k zadanému klíči a haši, nebo prázdné místo v tabulce.

hash_map_pop()

hash_map_state_code_t hash_map_pop	(	hash_map_t *	self,
		const char *	key,
		int *	value
	)

Uloží hodnotu z hašovací tabulky a odstraní záznam.

Vyhledá klíč v tabulce, uloží hodnotu přiřazenou ke klíči na místo kde ukazuje parametr value a odstraní záznam z tabulky. Pokud tabulka neobsahuje k danému klíči žádný záznam, vrací hodnotu KEY_ERROR .

Příklad užití:

int value;
hash_map_state_code_t error = hash_map_pop(map, "aloha", &value);
// hash_map_contains(map, "aloha") == false

Pozor

Odstranění záznamu z tabulky neovlivňuje alokované místo pro tabulku.

Parametry

[in]	self	Ukazatel na strukturu hašovací tabulky.
[in]	key	Klíč do tabulky.
[out]	value	Ukazatel na místo, kde se uloží hodnota.

Návratová hodnota

Vrací KEY_ERROR pokud se klíč nenachází v tabulce, jinak OK.

Viz také

hash_map_remove

hash_map_put()

hash_map_state_code_t hash_map_put	(	hash_map_t *	self,
		const char *	key,
		int	value
	)

Vloží klíč a hodnotu do tabulky.

Pokud je již index tabulky zaplněn ze 2/3, realokuje pro index 2x větší místo v paměti a provede reindexaci. Pokud tabulka již obsahuje k danému klíči záznam, hodnota záznamu se přepíše a funkce vrací hodnotu KEY_ALREADY_EXISTS .

Příklad užití:

hash_map_state_code_t is_value_overwritten = hash_map_put(map, "aloha", 5);

Parametry

[in]	self	Ukazatel na strukturu hašovací tabulky.
[in]	key	Klíč do tabulky.
[in]	value	Hodnota k uložení.

Návratová hodnota

Vrací KEY_ALREADY_EXISTS pokud se klíč nachází v tabulce, jinak OK.

Viz také

hash_map_reserve

hash_map_remove()

hash_map_state_code_t hash_map_remove	(	hash_map_t *	self,
		const char *	key
	)

Odstranění položky z hašovací tabulky.

Vyhledá klíč v tabulce a odstraní záznam z tabulky. Pokud tabulka neobsahuje k danému klíči žádný záznam, vrací hodnotu KEY_ERROR}.

Příklad užití:

hash_map_state_code_t error = hash_map_remove(map, "aloha");
// hash_map_contains(map, "aloha") == false

Pozor

Odstranění záznamu z tabulky neovlivňuje alokované místo pro tabulku.

Parametry

[in]	self	Ukazatel na strukturu hašovací tabulky.
[in]	key	Klíč do tabulky.

Návratová hodnota

Vrací KEY_ERROR pokud se klíč nenachází v tabulce, jinak OK.

Viz také

hash_map_pop

hash_map_reserve()

hash_map_state_code_t hash_map_reserve	(	hash_map_t *	self,
		size_t	size
	)

Realokace rezervovaného místa pro index.

Funkce je implicitně volána ve funci hash_map_put, když je potřeba.

Příklad užití:

hash_map_t* map = hash_map_ctor();
// hash_map_capacity(map) == 8
hash_map_reserve(map, 16);
// hash_map_capacity(map) == 16

Pozor

Velikost indexu nemůže být menší než počet vložených položek, v takovém případě funkce nic nevykoná a vrátí hodnotu VALUE_ERROR .

Parametry

[in]	self	Ukazatel na strukturu hašovací tabulky.
[in]	size	Velikost indexu.

Návratová hodnota

VALUE_ERROR pokud bude nová rezervovaná velikost hašovací tabulky menší jak počet doposud vložených prvků, jinak OK.

Viz také

hash_map_put

hash_map_size()

size_t hash_map_size

(

hash_map_t *

self

)

Vrací počet vložených záznamů do tabulky.

Parametry

[in]

self

Ukazatel na strukturu hašovací tabulky.

Návratová hodnota

Počet vložených záznamů do tabulky.

Viz také

hash_map_put, hash_map_pop, hash_map_remove