| /****************************************************************** |
| * |
| * 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__ */ |
