Referência ao Ficheiro hashmap.h

Descrição Detalhada

Implementação de uma tabela de hash.

Esta biblioteca disponibiliza um conjunto de funções que permitem manipular uma tabela de hash.

Sempre que existam colisões os elementos são inseridos numa lista ligada. Quando o número de elementos atingir uma determinada percentagem do número de posições da tabela, a sua dimensão é aumentada.

Na criação de uma tabela de hash é necessário especificar algumas funções que manipulam os tipos de dados utilizados. De seguida descrevem-se essas funções e apresentam-se exemplos (para o tipo char*):

int hash(void *)
Função de hash (usada pelas funções hashInsert, hashRemove e hashGet). Associa a uma chave um número único.

int hash(void* key)
{
  int i,x;
  char* aux=key;
  for(i=0,x=0;i<32&&aux[i]!='\0';x+=aux[i],i++);

  return x;
}

int keyEquals(void* key1,void* key2)
Função que compara duas chaves (usada pelas funções hashInsert , hashRemove e hashGet); deve devolver 0 se key1 igual a key2 e um valor diferente de 0 caso contrário; pode ser alterada através da função hashSetEquals.
```
int keyEquals(void* key1,void* key2)
{
  if(key1&&key2) return srtcmp((char*)key1,(char*)key2);
  else return 1;
}
```

Autor:: Rui Carlos A. Gonçalves <rcgoncalves.pt@gmail.com>

Versão:: 2.0.2

Data:: 02/2009

Definido no ficheiro hashmap.h.

Ir para o código fonte deste ficheiro.

Estruturas de Dados

struct SHashNode

Estrutura do nodo de uma tabela de hash. Mais...

struct SHashMap

Estrutura de uma tabela de hash. Mais...

Definições de Tipos

typedef SHashNode * HashNode

Definição do apontador para os nodos da tabela de hash.

typedef SHashMap * HashMap

Definição da tabela de hash.

Funções

HashMap newHash (int size, float factor, int(*hash)(void *), int(*equals)(void *, void *))

Cria uma tabela de hash.

int hashSetHash (HashMap hmap, int(*hash)(void *))

Altera a função de hash associada a uma tabela.

int hashSetEquals (HashMap hmap, int(*equals)(void *, void *))

Altera a função que compara duas chaves de uma tabela.

int hashSetFactor (HashMap hmap, int factor)

Altera o factor de "reestruturação" da tabela.

void hashDelete (HashMap hmap)

Elimina uma tabela de hash.

int hashInsert (HashMap hmap, void *key, void *value, int replace)

Insere um par chave/valor numa tabela de hash.

int hashRemove (HashMap hmap, void *key, void **value, void(*del)(void *))

Remove um elemento de uma tabela de hash.

int hashGet (HashMap hmap, void *key, void **value)

Procura um elemento numa tabela de hash.

int hashSize (HashMap hmap)

Determina o número de elementos de uma tabela de hash.

Iterator hashKeys (HashMap hmap)

Cria um iterador a partir das chaves de uma tabela de hash.

Iterator hashValues (HashMap hmap)

Cria um iterador a partir dos valores associados às chaves de uma tabela de hash.

Documentação das Funções

void hashDelete ( HashMap hmap )

Elimina uma tabela de hash.

Atenção:: apenas liberta a memória referente à estrutura da tabela; não liberta o espaço ocupado pelos elementos nela contidos.

Parâmetros:

hmap

tabela de hash.

Definido na linha 122 do ficheiro hashmap.c.

int hashGet	(	HashMap	hmap,
		void *	key,
		void **	value
	)

Procura um elemento numa tabela de hash.

Devolve o valor associado a uma chave se ela existir. Se a chave não existir é colocado o valor NULL em value.

Atenção:: esta função coloca em value o endereço do valor pretendido; depois de executar esta função é aconselhável fazer uma cópia do mesmo e passar a trabalhar com a cópia para que não haja problemas de partilha de referências.

Parâmetros:

	hmap	tabela de hash.
	key	chave que procuramos.
	value	endereço onde é colocado o resultado.

Retorna:: 0 se o elemento existir;
1 se o elemento não existir.

Definido na linha 210 do ficheiro hashmap.c.

int hashInsert	(	HashMap	hmap,
		void *	key,
		void *	value,
		int	replace
	)

Insere um par chave/valor numa tabela de hash.

Caso a chave já exista, a variável replace determina se o valor antigo é ou não substituído (caso seja 0 não há substituição, caso tenha outro valor o novo elemento é inserido).

Parâmetros:

	hmap	tabela de hash.
	key	chave.
	value	valor associado à chave.
	replace	variável que determina se elementos já existente são ou não substituídos.

Retorna:: 0 se o elemento for inserido;
1 se a tabela já possuia a chave indicada;
2 se não for possível alocar memória para o novo elemento.

Definido na linha 141 do ficheiro hashmap.c.

Iterator hashKeys ( HashMap hmap )

Cria um iterador a partir das chaves de uma tabela de hash.

Coloca as referência para as chaves num iterador. Se ocorrer algum erro devolve NULL.

Ver Também:: Iterator

Parâmetros:

hmap

tabela de hash.

Retorna:: iterador criado ou NULL.

Definido na linha 239 do ficheiro hashmap.c.

int hashRemove	(	HashMap	hmap,
		void *	key,
		void **	value,
		void()(void )	del
	)

Remove um elemento de uma tabela de hash.

Permite devolver o valor removido, caso o valor de value seja diferente de NULL. Se a chave não existir ou o elemento não for removido é colocado o valor NULL em value.

Atenção:: esta função não liberta o espaço ocupado pelo valor associado à chave; já o espaço ocupado pela chave removida, se del for diferente de NULL, será libertado.

Parâmetros:

	hmap	tabela de hash.
	key	chave que queremos remover.
	value	endereço onde é colocado o elemento removido (ou NULL).
	del	função que elimina uma chave (ou NULL).

Retorna:: 0 se o elemento for removido;
1 se a chave não existir.

Definido na linha 180 do ficheiro hashmap.c.

int hashSetEquals	(	HashMap	hmap,
		int()(void , void *)	equals
	)

Altera a função que compara duas chaves de uma tabela.

O valor de equals não pode ser NULL.

Parâmetros:

	hmap	tabela de hash.
	equals	nova função.

Retorna:: 1 se equals for NULL (não é efectuada qualquer alteração);
0 caso contrário.

Definido na linha 98 do ficheiro hashmap.c.

int hashSetFactor	(	HashMap	hmap,
		int	factor
	)

Altera o factor de "reestruturação" da tabela.

O novo valor tem que ser maior do 0.1.

Parâmetros:

	hmap	tabela de hash.
	factor	novo valor.

Retorna:: 1 se factor for menor do que 0.1;
0 caso contrário.

Definido na linha 110 do ficheiro hashmap.c.

int hashSetHash	(	HashMap	hmap,
		int()(void )	hash
	)

Altera a função de hash associada a uma tabela.

O valor de hash não pode ser NULL.

Parâmetros:

	hmap	tabela de hash.
	hash	nova função.

Retorna:: 1 se hash for NULL (não é efectuada qualquer alteração);
0 caso contrário.

Definido na linha 86 do ficheiro hashmap.c.

int hashSize ( HashMap hmap )

Determina o número de elementos de uma tabela de hash.

Devolve o valor do campo size da tabela.

Parâmetros:

hmap

tabela de hash.

Retorna:: número de elementos da tabela.

Definido na linha 232 do ficheiro hashmap.c.

Iterator hashValues ( HashMap hmap )

Cria um iterador a partir dos valores associados às chaves de uma tabela de hash.

Coloca as referências para os "valores" num iterador. Se ocorrer algum erro a função devolve NULL.

Ver Também:: Iterator

Parâmetros:

hmap

tabela de hash.

Retorna:: iterador criado ou NULL.

Definido na linha 262 do ficheiro hashmap.c.

HashMap newHash	(	int	size,
		float	factor,
		int()(void )	hash,
		int()(void , void *)	equals
	)

Cria uma tabela de hash.

Se não for possível criar a tabela devolve NULL. Têm que ser especificadas a função de hash e a função que compara chaves, caso contrário a tabela não será criada. Estas funções podem ser alteradas a qualquer momento, utilizando as funções hashSetHash e hashSetEquals.

(Ver descrição das funções)

É ainda necessário indicar um valor (factor) que determina quando a dimensão da tabela deve ser aumentada; isso acontecerá quando:
size>factor*length
Esta variável terá que ser superior a 0.1.

Parâmetros:

	size	dimensão inicial da tabela.
	factor	factor de "reestruturação" da tabela.
	hash	função de hash.
	equals	função que compara duas chaves.

Retorna:: tabela inicializada ou NULL.

Definido na linha 58 do ficheiro hashmap.c.


Estruturas de Dados
struct	SHashNode
	Estrutura do nodo de uma tabela de hash. Mais...
struct	SHashMap
	Estrutura de uma tabela de hash. Mais...
Definições de Tipos
typedef SHashNode *	HashNode
	Definição do apontador para os nodos da tabela de hash.
typedef SHashMap *	HashMap
	Definição da tabela de hash.
Funções
HashMap	newHash (int size, float factor, int(hash)(void ), int(equals)(void , void *))
	Cria uma tabela de hash.
int	hashSetHash (HashMap hmap, int(hash)(void ))
	Altera a função de hash associada a uma tabela.
int	hashSetEquals (HashMap hmap, int(equals)(void , void *))
	Altera a função que compara duas chaves de uma tabela.
int	hashSetFactor (HashMap hmap, int factor)
	Altera o factor de "reestruturação" da tabela.
void	hashDelete (HashMap hmap)
	Elimina uma tabela de hash.
int	hashInsert (HashMap hmap, void key, void value, int replace)
	Insere um par chave/valor numa tabela de hash.
int	hashRemove (HashMap hmap, void key, void value, void(del)(void *))
	Remove um elemento de uma tabela de hash.
int	hashGet (HashMap hmap, void key, void *value)
	Procura um elemento numa tabela de hash.
int	hashSize (HashMap hmap)
	Determina o número de elementos de uma tabela de hash.
Iterator	hashKeys (HashMap hmap)
	Cria um iterador a partir das chaves de uma tabela de hash.
Iterator	hashValues (HashMap hmap)
	Cria um iterador a partir dos valores associados às chaves de uma tabela de hash.