Dokumentace souboru white_box_code.h

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

#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include <stdbool.h>

Následující graf ukazuje, které soubory přímo nebo nepřímo vkládají tento soubor:

Zobrazit zdrojový text tohoto souboru.

Datové struktry
struct	hash_map_item
	Záznam v hašovací tabulce. ...
struct	hash_map
	Datový typ hašovací tabulky. ...

Definice maker
#define	HASH_MAP_INIT_SIZE   8
	Inicializační velikost tabulky.
#define	HASH_MAP_PERTURB_SHIFT   5
	Parametr použit v hledání dalšího indexu při kolizi.
#define	HASH_MAP_REALLOCATION_THRESHOLD   3/5.
	Mez zaplnění kdy se má realokovat velikost tabulky.
#define	HASH_FUNCTION_PARAM_A   1794967309
	Hyperparametr v hašovácí funkci.
#define	HASH_FUNCTION_PARAM_B   7
	Hyperparametr v hašovácí funkci.

Definice typů
typedef struct hash_map_item	hash_map_item_t
	Záznam v hašovací tabulce. ...
typedef struct hash_map	hash_map_t
	Datový typ hašovací tabulky. ...

Výčty
enum	hash_map_state_code_t {   OK, MEMORY_ERROR, VALUE_ERROR, KEY_ERROR,   KEY_ALREADY_EXISTS }
	Výčet návratových hodnot. ...

Funkce
hash_map_t *	hash_map_ctor ()
	Konstruktor hašovací tabulky. ...
void	hash_map_dtor (hash_map_t *self)
	Destruktor hašovací tabulky. ...
void	hash_map_clear (hash_map_t *self)
	Dealokace vytvořeních položek a vymazání indexu. ...
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 *value)
	Uloží hodnotu asociovanou se zadaným klíčem na určené místo v paměti. ...
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. ...
hash_map_state_code_t	hash_map_remove (hash_map_t *self, const char *key)
	Odstranění položky z hašovací tabulky. ...

Detailní popis

Deklarace metod tridy reprezentujici hashovácí tabulku.

Hasovaci tabulka je vyhledavaci datova struktura, ktera asociuje hasovaci klice s hodnotami.

Autor

Karel Ondřej

Martin Dočekal

Dokumentace definic typů

hash_map_item_t

typedef struct hash_map_item hash_map_item_t

Záznam v hašovací tabulce.

Položka v hašovací tabulce. Pro efektivnější procházení (např. při dealokaci paměti) a prací s pamětí (projeví se při velkých indexech) jsou vložené položky implementované formou obousměrně vázaného seznamu a index obsahuje pouze ukazatele do tohoto seznamu. Pořadí položek v seznamu odpovídá pořadí vložení daného klíče do tabulky.

Uživatel by k položkám struktury neměl přistupovat přímo, ale pomocí definovaného rozhraní níže. Nicméně v rámci testování můžete přímo testovat, zda rozhraní pracuje s tímto datovým typem korektně.

hash_map_t

typedef struct hash_map hash_map_t

Datový typ hašovací tabulky.

Uživatel by k položkám struktury neměl přistupovat přímo, ale pomocí definovaného rozhraní níže. Nicméně v rámci testování můžete přímo testovat, zda rozhraní pracuje s tímto datovým typem korektně.

Dokumentace výčtových typů

hash_map_state_code_t

enum hash_map_state_code_t

Výčet návratových hodnot.

Výčet obsahující návratové hodnoty funkcí. Pokud nedojde k chybě, funkce vrací hodnotu OK. V případě problémů s alokací paměti se vrátí návratová hodnota MEMORY_ERROR. Podrobnější sémantika ostatních hodnot je popsána u jednotlivých funkcí.

Hodnoty výčtu
OK	Vše v pořádku.
MEMORY_ERROR	Problém při alokaci paměti.
VALUE_ERROR	Neplatná hodnota argumentu.
KEY_ERROR	Přístup ke klíči který není vložen v tabulce.
KEY_ALREADY_EXISTS	Klíč již v hašovací tabulce existuje.

Dokumentace funkcí

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_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