/****************************************************************** * *  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_HFT_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_Hash_CompareFunc  *  * @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_CompareFunc)( const FT_HashNode  node1,                                          const 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_Memory            memory;    FT_HashNode*         buckets;    FT_UInt              p;    FT_UInt              mask;  /* really maxp-1 */    FT_UInt              slack;    FT_UInt              node_size;    FT_Hash_CompareFunc  node_compare;    FT_Hash_ComputeFunc  node_hash;  } FT_HashRec, *FT_Hash; /***********************************************************  *  * @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  *   compare :: node comparison function  *   memory  :: memory manager handle used to allocate the  *              buckets array within the hash table  *  * @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 selfom called.  *  *   here is a simple example:  *  *   {  *     static int my_compare( const MyNode  node1,  *                            const MyNode  node2 )  *     {  *       // compare keys of 'node1' and 'node2'  *       return strcmp( node1->key, node2->key );  *     }  *  *     ....  *  *     ft_hash_init( &hash, (FT_Hash_CompareFunc) my_compare, memory );  *     ....  *   }  */  FT_BASE( void )  ft_hash_init( FT_Hash              table,                FT_Hash_CompareFunc  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_HashNode* )  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  *   pnode    :: 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'.  *  * @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) );  *       node->hnode.hash = noderec.hnode.hash;  *       node->key        = key;  *       node->value      = value;  *  *       // add it to the hash table  *       ft_hash_add( table, pnode, node );  *     }  */  FT_BASE( void )  ft_hash_add( FT_Hash       table,               FT_HashNode*  pnode,               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  *   pnode   :: 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 )  *       {  *         ft_hash_remove( table, pnode );  *         free( node );  *       }  *     }  *   }  */  FT_BASE( void )  ft_hash_remove( FT_Hash       table,                  FT_HashNode*  pnode ); /****************************************************************  *  * @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__ */