xref: /inferno-os/include/freetype/internal/fthash.h (revision 37da2899f40661e3e9631e497da8dc59b971cbd0)

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