A dynamic association table implemented by hashing. More...

#include <ccl/ccl-common.h>
#include <ccl/ccl-protos.h>
#include <ccl/ccl-iterator.h>

Typedefs
typedef struct ccl_hash_st	ccl_hash
	abstract type of an hash table.

typedef struct ccl_hash_entry_st	ccl_hash_entry
	Entries of the table that are returned by ad-hoc iterator.

Functions
	CCL_ITERATOR_TYPEDEF (ccl_hash_entry_iterator, ccl_hash_entry)
	Abstract type of iterators that visit entries of an hash table. The iterator returns objects of type ccl_hash_entry.

ccl_hash *	ccl_hash_create (ccl_hash_func key_hash, ccl_compare_func key_compare, ccl_delete_proc key_delete, ccl_delete_proc object_delete)
	Creates a new hash table. More...

void	ccl_hash_delete (ccl_hash *ht)
	Deletes the table ht. More...

int	ccl_hash_find (ccl_hash ht, void key)
	Looks for key in the table ht. More...

void *	ccl_hash_get (ccl_hash *ht)
	Returns the object of the entry pointed by the cursor. More...

void	ccl_hash_insert (ccl_hash ht, void object)
	Inserts at the cursor position the object. More...

void	ccl_hash_remove (ccl_hash *ht)
	Removes the object at the cursor position. More...

int	ccl_hash_get_size (const ccl_hash *ht)
	Returns the number of elements in the table. More...

ccl_pointer_iterator *	ccl_hash_get_keys (const ccl_hash *ht)
	Builds an iterator over keys of ht. More...

ccl_pointer_iterator *	ccl_hash_get_elements (const ccl_hash *ht)
	Builds an iterator over objects stored in ht. More...

ccl_hash_entry_iterator *	ccl_hash_get_entries (const ccl_hash *ht)
	Builds an iterator over entries of ht. More...

Detailed Description

A dynamic association table implemented by hashing.

ccl_hash tables associates keys and objects. Keys are hashed into a hashing-table; objects are stored into entries pointed by keys. The size of the underlying hash table evolves according to its fill degree (i.e. the mean length of collision chains). That means that if the fill degree exceeds a pre-defined value then the size of the table is increased; and conversely, if the fill degree falls under the pre-defined level the size of the table is reduced.

In order to optimize find-add operations, the implementation uses a cursor that is moved by find operations. The insertion operation is then made at the position pointed by the cursor. Example:

if (ccl_hash_find (ht, k)
  ccl_hash_insert (ht, object);
else
  {
     ... the key k is already present in the table
  }

On should note the key k is not an argument of insert operation; indeed, k has been attached to the cursor by the find call.

Definition in file ccl-hash.h.

Function Documentation

ccl_hash* ccl_hash_create	(	ccl_hash_func *	key_hash,
		ccl_compare_func *	key_compare,
		ccl_delete_proc *	key_delete,
		ccl_delete_proc *	object_delete
	)

Creates a new hash table.

Parameters

key_hash	pointer to a function that computes a hashing value for keys
key_compare	pointer to a comparison function for keys
key_delete	pointer to a deletion function for keys
object_delete	pointer to a deletion function for objects

Returns: the new hash table

void ccl_hash_delete ( ccl_hash * ht )

Deletes the table ht.

The function releases resources allocated for the table ht. The key_delete and object_delete function used to create the table are applied to keys and objects.

Parameters

ht	the table to delete

Precondition: ht != NULL

int ccl_hash_find	(	ccl_hash *	ht,
		void *	key
	)

Looks for key in the table ht.

The function looks for entry containing the key key. During the search the cursor of the table is moved to position where key should be placed.

Parameters

ht	the hash table
key	the key that is looked for.

Precondition: ht != NULL

Returns: a non-null if an entry with the key key has been found.

void* ccl_hash_get ( ccl_hash * ht )

Returns the object of the entry pointed by the cursor.

The function should be call after a positive result of the function ccl_hash_find; in that case, the cursor is placed in a valid position.

Parameters

ht	the hash table

Precondition: ht != NULL

Returns: the object at the cursor position

ccl_pointer_iterator* ccl_hash_get_elements ( const ccl_hash * ht )

Builds an iterator over objects stored in ht.

Attention: If an object is added or removed from ht the behavior of the iterator is undefined.

Parameters

ht	the hash table

Precondition: ht != NULL

Returns: an iterator over elements of ht.

ccl_hash_entry_iterator* ccl_hash_get_entries ( const ccl_hash * ht )

Builds an iterator over entries of ht.

Attention: If an object is added or removed from ht the behavior of the iterator is undefined.

Parameters

ht	the hash table

Precondition: ht != NULL

Returns: an iterator over entries of ht.

ccl_pointer_iterator* ccl_hash_get_keys ( const ccl_hash * ht )

Builds an iterator over keys of ht.

Attention: If an object is added or removed from ht the behavior of the iterator is undefined.

Parameters

ht	the hash table

Precondition: ht != NULL

Returns: an iterator over keys of ht.

int ccl_hash_get_size ( const ccl_hash * ht )

Returns the number of elements in the table.

Parameters

ht	the hash table

Precondition: ht != NULL

Returns: the number of elements in the table.

void ccl_hash_insert	(	ccl_hash *	ht,
		void *	object
	)

Inserts at the cursor position the object.

The function should be call after a use of the function ccl_hash_find. If the cursor indicates an non-empty entry (i.e. the call ccl_hash_find gives a positive answer), then the object currently stored in the table is removed (and deleted if a function has been furnished to ccl_hash_create) and replaced by object.

Parameters

ht	the hash table
object	the object to insert in the table

Precondition: ht != NULL

void ccl_hash_remove ( ccl_hash * ht )

Removes the object at the cursor position.

The function should be call after a positive result of the function ccl_hash_find; in that case, the cursor is placed in a valid position. The function removes (and deletes if a function has been furnished to ccl_hash_create) the object placed under the cursor. The key associated with the object is also deleted.

Parameters

ht	the hash table

Precondition: ht != NULL

Typedefs

Functions

Detailed Description

Function Documentation