/******************************************************************
*
* fthash.h - fast dynamic hash tables
*
* Copyright 2002 by
* David Turner, Robert Wilhelm, and Werner Lemberg
*
* This file is part of the FreeType project, and may only be used,
* modified, and distributed under the terms of the FreeType project
* license, LICENSE.TXT. By continuing to use, modify, or distribute
* this file you indicate that you have read the license and
* understand and accept it fully.
*
*
* This header is used to define dynamic hash tables as described
* by the article "Main-Memory Linear Hashing - Some Enhancements
* of Larson's Algorithm" by Mikael Petterson.
*
* Basically, linear hashing prevents big "stalls" during
* resizes of the buckets array by only splitting one bucket
* at a time. This ensures excellent response time even when
* the table is frequently resized..
*
*
* Note that the use of the FT_Hash type is rather unusual in order
* to be as generic and efficient as possible. See the comments in the
* following definitions for more details.
*/
#ifndef __FT_HASH_H__
#define __FT_HASH_H__
#include <ft2build.h>
#include FT_TYPES_H
FT_BEGIN_HEADER
/***********************************************************
*
* @type: FT_Hash
*
* @description:
* handle to a @FT_HashRec structure used to model a
* dynamic hash table
*/
typedef struct FT_HashRec_* FT_Hash;
/***********************************************************
*
* @type: FT_HashNode
*
* @description:
* handle to a @FT_HashNodeRec structure used to model a
* single node of a hash table
*/
typedef struct FT_HashNodeRec_* FT_HashNode;
/***********************************************************
*
* @type: FT_HashLookup
*
* @description:
* handle to a @FT_HashNode pointer. This is returned by
* the @ft_hash_lookup function and can later be used by
* @ft_hash_add or @ft_hash_remove
*/
typedef FT_HashNode* FT_HashLookup;
/***********************************************************
*
* @type: FT_Hash_EqualFunc
*
* @description:
* a function used to compare two nodes of the hash table
*
* @input:
* node1 :: handle to first node
* node2 :: handle to second node
*
* @return:
* 1 iff the 'keys' in 'node1' and 'node2' are identical.
* 0 otherwise.
*/
typedef FT_Int (*FT_Hash_EqualFunc)( FT_HashNode node1,
FT_HashNode node2 );
/***********************************************************
*
* @struct: FT_HashRec
*
* @description:
* a structure used to model a dynamic hash table.
*
* @fields:
* memory :: memory manager used to allocate
* the buckets array and the hash nodes
*
* buckets :: array of hash buckets
*
* node_size :: size of node in bytes
* node_compare :: a function used to compare two nodes
* node_hash :: a function used to compute the hash
* value of a given node
* p ::
* mask ::
* slack ::
*
* @note:
* 'p', 'mask' and 'slack' are control values managed by
* the hash table. Do not try to interpret them directly.
*
* You can grab the hash table size by calling
* '@ft_hash_get_size'.
*/
typedef struct FT_HashRec_
{
FT_HashNode* buckets;
FT_UInt p;
FT_UInt mask; /* really maxp-1 */
FT_Long slack;
FT_Hash_EqualFunc node_equal;
FT_Memory memory;
} FT_HashRec;
/***********************************************************
*
* @struct: FT_HashNodeRec
*
* @description:
* a structure used to model the root fields of a dynamic
* hash table node.
*
* it's up to client applications to "sub-class" this
* structure to add relevant (key,value) definitions
*
* @fields:
* link :: pointer to next node in bucket's collision list
* hash :: 32-bit hash value for this node
*
* @note:
* it's up to client applications to "sub-class" this structure
* to add relevant (key,value) type definitions. For example,
* if we want to build a "string -> int" mapping, we could use
* something like:
*
* {
* typedef struct MyNodeRec_
* {
* FT_HashNodeRec hnode;
* const char* key;
* int value;
*
* } MyNodeRec, *MyNode;
* }
*
*/
typedef struct FT_HashNodeRec_
{
FT_HashNode link;
FT_UInt32 hash;
} FT_HashNodeRec;
/****************************************************************
*
* @function: ft_hash_init
*
* @description:
* initialize a dynamic hash table
*
* @input:
* table :: handle to target hash table structure
* node_equal :: node comparison function
* memory :: memory manager handle used to allocate the
* buckets array within the hash table
*
* @return:
* error code. 0 means success
*
* @note:
* the node comparison function should only compare node _keys_
* and ignore values !! with good hashing computation (which the
* user must perform itself), the comparison function should be
* pretty seldom called.
*
* here is a simple example:
*
* {
* static int my_equal( MyNode node1,
* MyNode node2 )
* {
* // compare keys of 'node1' and 'node2'
* return (strcmp( node1->key, node2->key ) == 0);
* }
*
* ....
*
* ft_hash_init( &hash, (FT_Hash_EqualFunc) my_compare, memory );
* ....
* }
*/
FT_BASE( FT_Error )
ft_hash_init( FT_Hash table,
FT_Hash_EqualFunc compare,
FT_Memory memory );
/****************************************************************
*
* @function: ft_hash_lookup
*
* @description:
* search a hash table to find a node corresponding to a given
* key.
*
* @input:
* table :: handle to target hash table structure
* keynode :: handle to a reference hash node that will be
* only used for key comparisons with the table's
* elements
*
* @return:
* a pointer-to-hash-node value, which must be used as followed:
*
* - if '*result' is NULL, the key wasn't found in the hash
* table. The value of 'result' can be used to add new elements
* through @ft_hash_add however..
*
* - if '*result' is not NULL, it's a handle to the first table
* node that corresponds to the search key. The value of 'result'
* can be used to remove this element through @ft_hash_remove
*
* @note:
* here is an example:
*
* {
* // maps a string to an integer with a hash table
* // returns -1 in case of failure
* //
* int my_lookup( FT_Hash table,
* const char* key )
* {
* MyNode* pnode;
* MyNodeRec noderec;
*
* // set-up key node. It's 'hash' and 'key' fields must
* // be set correctly.. we ignore 'link' and 'value'
* //
* noderec.hnode.hash = strhash( key );
* noderec.key = key;
*
* // perform search - return value
* //
* pnode = (MyNode) ft_hash_lookup( table, &noderec );
* if ( *pnode )
* {
* // we found it
* return (*pnode)->value;
* }
* return -1;
* }
* }
*/
FT_BASE_DEF( FT_HashLookup )
ft_hash_lookup( FT_Hash table,
FT_HashNode keynode );
/****************************************************************
*
* @function: ft_hash_add
*
* @description:
* add a new node to a dynamic hash table. the user must
* call @ft_hash_lookup and allocate a new node before calling
* this function.
*
* @input:
* table :: hash table handle
* lookup :: pointer-to-hash-node value returned by @ft_hash_lookup
* new_node :: handle to new hash node. All its fields must be correctly
* set, including 'hash'.
*
* @return:
* error code. 0 means success
*
* @note:
* this function should always be used _after_ a call to @ft_hash_lookup
* that returns a pointer to a NULL handle. Here's an example:
*
* {
* // sets the value corresponding to a given string key
* //
* void my_set( FT_Hash table,
* const char* key,
* int value )
* {
* MyNode* pnode;
* MyNodeRec noderec;
* MyNode node;
*
* // set-up key node. It's 'hash' and 'key' fields must
* // be set correctly..
* noderec.hnode.hash = strhash( key );
* noderec.key = key;
*
* // perform search - return value
* pnode = (MyNode) ft_hash_lookup( table, &noderec );
* if ( *pnode )
* {
* // we found it, simply replace the value in the node
* (*pnode)->value = value;
* return;
* }
*
* // allocate a new node - and set it up
* node = (MyNode) malloc( sizeof(*node) );
* if ( node == NULL ) .....
*
* node->hnode.hash = noderec.hnode.hash;
* node->key = key;
* node->value = value;
*
* // add it to the hash table
* error = ft_hash_add( table, pnode, node );
* if (error) ....
* }
*/
FT_BASE( FT_Error )
ft_hash_add( FT_Hash table,
FT_HashLookup lookup,
FT_HashNode new_node );
/****************************************************************
*
* @function: ft_hash_remove
*
* @description:
* try to remove the node corresponding to a given key from
* a hash table. This must be called after @ft_hash_lookup
*
* @input:
* table :: hash table handle
* lookup :: pointer-to-hash-node value returned by @ft_hash_lookup
*
* @note:
* this function doesn't free the node itself !! Here's an example:
*
* {
* // sets the value corresponding to a given string key
* //
* void my_remove( FT_Hash table,
* const char* key )
* {
* MyNodeRec noderec;
* MyNode node;
*
* noderec.hnode.hash = strhash(key);
* noderec.key = key;
* node = &noderec;
*
* pnode = ft_hash_lookup( table, &noderec );
* node = *pnode;
* if ( node != NULL )
* {
* error = ft_hash_remove( table, pnode );
* if ( !error )
* free( node );
* }
* }
* }
*/
FT_BASE( FT_Error )
ft_hash_remove( FT_Hash table,
FT_HashLookup lookup );
/****************************************************************
*
* @function: ft_hash_get_size
*
* @description:
* return the number of elements in a given hash table
*
* @input:
* table :: handle to target hash table structure
*
* @return:
* number of elements. 0 if empty
*/
FT_BASE( FT_UInt )
ft_hash_get_size( FT_Hash table );
/****************************************************************
*
* @functype: FT_Hash_ForeachFunc
*
* @description:
* a function used to iterate over all elements of a given
* hash table
*
* @input:
* node :: handle to target @FT_HashNodeRec node structure
* data :: optional argument to iteration routine
*
* @also: @ft_hash_foreach
*/
typedef void (*FT_Hash_ForeachFunc)( const FT_HashNode node,
const FT_Pointer data );
/****************************************************************
*
* @function: ft_hash_foreach
*
* @description:
* parse over all elements in a hash table
*
* @input:
* table :: handle to target hash table structure
* foreach_func :: iteration routine called for each element
* foreach_data :: optional argument to the iteration routine
*
* @note:
* this function is often used to release all elements from a
* hash table. See the example given for @ft_hash_done
*/
FT_BASE( void )
ft_hash_foreach( FT_Hash table,
FT_Hash_ForeachFunc foreach_func,
const FT_Pointer foreach_data );
/****************************************************************
*
* @function: ft_hash_done
*
* @description:
* finalize a given hash table
*
* @input:
* table :: handle to target hash table structure
* node_func :: optional iteration function pointer. this
* can be used to destroy all nodes explicitely
* node_data :: optional argument to the node iterator
*
* @note:
* this function simply frees the hash table's buckets.
* you probably will need to call @ft_hash_foreach to
* destroy all its elements before @ft_hash_done, as in
* the following example:
*
* {
* static void my_node_clear( const MyNode node )
* {
* free( node );
* }
*
* static void my_done( FT_Hash table )
* {
* ft_hash_done( table, (FT_Hash_ForeachFunc) my_node_clear, NULL );
* }
* }
*/
FT_BASE( void )
ft_hash_done( FT_Hash table,
FT_Hash_ForeachFunc item_func,
const FT_Pointer item_data );
/* */
/* compute bucket index from hash value in a dynamic hash table */
/* this is only used to break encapsulation to speed lookups in */
/* the FreeType cache manager !! */
/* */
#define FT_HASH_COMPUTE_INDEX(_table,_hash,_index) \
{ \
FT_UInt _mask = (_table)->mask; \
FT_UInt _hash0 = (_hash); \
\
(_index) = (FT_UInt)( (_hash0) & _mask ) ); \
if ( (_index) < (_table)->p ) \
(_index) = (FT_uInt)( (_hash0) & ( 2*_mask+1 ) ); \
}
FT_END_HEADER
#endif /* __FT_HASH_H__ */