TaPAS  0.2
Typedefs | Functions
ccl-hash.h File Reference

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

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

Go to the source code of this file.

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_hashccl_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_hashpointer to a function that computes a hashing value for keys
key_comparepointer to a comparison function for keys
key_deletepointer to a deletion function for keys
object_deletepointer 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
htthe 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
htthe hash table
keythe 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
htthe 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
htthe 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
htthe 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
htthe 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
htthe 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
htthe hash table
objectthe 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
htthe hash table
Precondition
ht != NULL