hash.c File Reference

Implementa??o de um hash gen?rico. More...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "str.h"
#include "cser.h"
#include "hash.h"

Include dependency graph for hash.c:

Go to the source code of this file.

Defines
#define	__HASH__IMPLEMENTATION__
Functions
HASH_TYPE *	HASH_CREATE (int sz)
	Cria um hash.
POS_HANDLER_TYPE	HASH_ADD (HASH_TYPE *h, KEY_TYPE key)
	Insere uma chave no hash (caso ela n?o exista).
POS_HANDLER_TYPE	HASH_GET (HASH_TYPE *h, KEY_TYPE key)
	Retorna um Handler da posi??o da chave key no hash h.
int	HASH_REMOVE (HASH_TYPE *h, KEY_TYPE removedKey)
	Removes a key from the hash.
void	HASH_DESTROY (HASH_TYPE *h)
	Destroy a hash.
void	HASH_CLEAN (HASH_TYPE *h)
	Limpa um hash, apagando todos os pares chave->valor.
void	HASH_REHASH (HASH_TYPE *h, int newSize)
	Grow the hash to newSize.
int	HASH_SERIALIZE (FILE *outputFile, HASH_TYPE *hash)
int	HASH_DESERIALIZE (FILE *inputFile, HASH_TYPE *hash)
int	WRITE_KEY (FILE *outputFile, HASH_TYPE *hash, POS_HANDLER_TYPE pos)
int	READ_KEY (FILE *inputFile, HASH_TYPE *hash, POS_HANDLER_TYPE pos)
int	WRITE_VALUE (FILE *outputFile, HASH_TYPE *hash, POS_HANDLER_TYPE pos)
int	READ_VALUE (FILE *inputFile, HASH_TYPE *hash, POS_HANDLER_TYPE pos)
void	LISTA_DESTROY (LISTA_TYPE *l)
	Destr?i a lista encadeada de um hash.
ITERATOR_TYPE *	CREATE_ITERATOR (HASH_TYPE *hash, int is_destructor)
	Cria um iterador de hash.
POS_HANDLER_TYPE	ITERATOR_NEXT (ITERATOR_TYPE *hdi, HASH_TYPE *hash)
	Retorna a posi??o do pr?ximo elemento no hash.
void	ITERATOR_DESTROY (ITERATOR_TYPE *hdi, HASH_TYPE *hash)
	Destroi um iterador de hash.

---

Detailed Description

Implementa??o de um hash gen?rico.

Este hash usa lista encadeada e permite edi??o do valor de uma chave. Para lidar com varia??es nos tipos de dados sem perder efici?ncia, o tipo da chave (pode ser string ou inteiro) e o tipo do valor (pode ser inteiro ou void *) s?o definidos atrav?s de ifdefs. A cada tipo de hash mudam os nomes dos tipos abstratos de dados e das fun??es para que diferentes tipos de hash possam ser usados dentro de um mesmo arquivo fonte, mas os algoritmos s?o os mesmos para todos os tipos(exceto que se chave ? um string deve-se chamar str_hash_code() para calcular o hash code, se ela ? inteiro ela ? seu pr?prio hash code). As fun??es desse arquivo t?m nomes como HASH_CREATE que o preprocessador do C substitui por hashKVCreate onde K ? o tipo da chave que pode ser Int(inteiro) ou Str(String) e V ? o tipo do valor que pode ser Int(inteiro) ou Void (void *). Nessa documenta??o e de hash.h K ? Str e V ? Int.

Complexidade das opera??es:

C?lculo do hashcode: A complexidade do c?lculo do hashcode ? O(n) onde n ? o tamanho do da chave (se ela for string). Mas como as chaves t?m tamanho m?dio de uns 10 caracteres e poucas devem ter 20 caracteres, a complexidade do c?lculo do hashcode pode ser considerada O(1).

Inser??o na lista encadeada de uma posi??o do hash: O(n) onde n ? o tamanho da lista.

Inser??o no hash: Para inserir uma chave no hash ? necess?rio calcular o hashcode dessa chave e inser?-la na lista encadeada de uma posi??o do hash. O c?lculo do hashcode ? O(1), enquanto a inser??o na lista ? O(n) onde n ? o tamanho da lista. Como o tamanho da lista ? 1 se o n?mero de chaves n?o for muito maior que o n?mero de posi??es da tabela hash a complexidade esperada de inser??o no hash ? O(1).

See also:

hash.h

Definition in file hash.c.

---

Define Documentation

#define __HASH__IMPLEMENTATION__

Definition at line 9 of file hash.c.

---

Function Documentation

ITERATOR_TYPE* CREATE_ITERATOR (  HASH_TYPE *  hash, int  is_destructor )

Cria um iterador de hash. Parameters: hash  Hash sobre o qual o iterador vai percorrer. is_destructor  se for =1 o iterador vai limpando o hash a medida que passa por ele. Returns: Ponteiro para o iterador. See also: hashStrIntIteratorNext() Definition at line 527 of file hash.c. Referenced by HASH_REHASH(), and HASH_SERIALIZE().

POS_HANDLER_TYPE HASH_ADD (  HASH_TYPE *  h, KEY_TYPE  key )

Insere uma chave no hash (caso ela n?o exista). Parameters: h  Hash onde a chave ser? inserida. key  Chave a ser inserida (se a chave for um string, ele ser? copiado). Returns: Handler para edi??o da posi??o. Definition at line 120 of file hash.c. References HASH_REHASH(). Referenced by HASH_DESERIALIZE(). Here is the call graph for this function:

void HASH_CLEAN (  HASH_TYPE *  h  )

Limpa um hash, apagando todos os pares chave->valor. Definition at line 232 of file hash.c. References LISTA_DESTROY(). Here is the call graph for this function:

HASH_TYPE* HASH_CREATE (  int  sz  )

Cria um hash. Parameters: sz  Tamanho do hash. Returns: Ponteiro para o hash. Definition at line 95 of file hash.c.

int HASH_DESERIALIZE (  FILE *  inputFile, HASH_TYPE *  hash )

Definition at line 311 of file hash.c. References HASH_ADD(), READ_BEGIN, READ_BYTES, READ_KEY(), READ_NUM, and READ_VALUE(). Here is the call graph for this function:

void HASH_DESTROY (  HASH_TYPE *  h  )

Destroy a hash. Definition at line 216 of file hash.c. References LISTA_DESTROY(). Here is the call graph for this function:

POS_HANDLER_TYPE HASH_GET (  HASH_TYPE *  h, KEY_TYPE  key )

Retorna um Handler da posi??o da chave key no hash h. Definition at line 165 of file hash.c.

void HASH_REHASH (  HASH_TYPE *  h, int  newSize )

Grow the hash to newSize. Definition at line 246 of file hash.c. References CREATE_ITERATOR(), and ITERATOR_NEXT(). Referenced by HASH_ADD(). Here is the call graph for this function:

int HASH_REMOVE (  HASH_TYPE *  h, KEY_TYPE  removedKey )

Removes a key from the hash. Parameters: h  Hash where the key will be removed. removedKey  Key to be removed. Returns: 0 on success, -1 on error. Todo: Test removal on the begining, middle and end of a >3 node linked list Definition at line 187 of file hash.c.

int HASH_SERIALIZE (  FILE *  outputFile, HASH_TYPE *  hash )

Definition at line 287 of file hash.c. References CREATE_ITERATOR(), ITERATOR_NEXT(), WRITE_BYTES, WRITE_KEY(), WRITE_NUM, and WRITE_VALUE(). Here is the call graph for this function:

void ITERATOR_DESTROY (  ITERATOR_TYPE *  hdi, HASH_TYPE *  hash )

Destroi um iterador de hash. Se o iterador foi criado com o argumento is_destructor =1 e tiver acabado de percorrer uma lista encadeada do hash, acaba com ela. Definition at line 579 of file hash.c. References LISTA_DESTROY(). Here is the call graph for this function:

POS_HANDLER_TYPE ITERATOR_NEXT (  ITERATOR_TYPE *  hdi, HASH_TYPE *  hash )

Retorna a posi??o do pr?ximo elemento no hash. Se o iterador foi criado com o argumento is_destructor =1 destr?i toda lista encadeada do hash que terminar de percorrer. Parameters: hdi  Iterador. hash  Hash sobre o qual o iterador vai percorrer. Returns: Ponteiro para a posi??o do pr?ximo elemento do hash. Definition at line 547 of file hash.c. References LISTA_DESTROY(). Referenced by HASH_REHASH(), and HASH_SERIALIZE(). Here is the call graph for this function:

void LISTA_DESTROY (  LISTA_TYPE *  l  )

Destr?i a lista encadeada de um hash. Definition at line 507 of file hash.c. Referenced by HASH_CLEAN(), HASH_DESTROY(), ITERATOR_DESTROY(), and ITERATOR_NEXT().

int READ_KEY (  FILE *  inputFile, HASH_TYPE *  hash, POS_HANDLER_TYPE  pos )

Definition at line 385 of file hash.c. References READ_BEGIN, READ_BYTES, READ_END, READ_NUM, and READ_STR. Referenced by HASH_DESERIALIZE().

int READ_VALUE (  FILE *  inputFile, HASH_TYPE *  hash, POS_HANDLER_TYPE  pos )

Definition at line 444 of file hash.c. References READ_BEGIN, READ_BYTES, READ_END, READ_FLOAT, and READ_NUM. Referenced by HASH_DESERIALIZE().

int WRITE_KEY (  FILE *  outputFile, HASH_TYPE *  hash, POS_HANDLER_TYPE  pos )

Definition at line 363 of file hash.c. References WRITE_BYTES, WRITE_NUM, and WRITE_STR. Referenced by HASH_SERIALIZE().

int WRITE_VALUE (  FILE *  outputFile, HASH_TYPE *  hash, POS_HANDLER_TYPE  pos )

Definition at line 418 of file hash.c. References WRITE_BYTES, WRITE_FLOAT, and WRITE_NUM. Referenced by HASH_SERIALIZE().

---