--- /dev/null
+/******************************************************************
+ *
+ * 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__ */
git://git.jankratochvil.net / reactos.git / blobdiff