lib/freetype/include/freetype/internal/fthash.h

   1 /******************************************************************
   2  *
   3  *  fthash.h  - fast dynamic hash tables
   4  *
   5  *  Copyright 2002 by
   6  *  David Turner, Robert Wilhelm, and Werner Lemberg
   7  *
   8  *  This file is part of the FreeType project, and may only be used,
   9  *  modified, and distributed under the terms of the FreeType project
  10  *  license, LICENSE.TXT.  By continuing to use, modify, or distribute
  11  *  this file you indicate that you have read the license and
  12  *  understand and accept it fully.
  13  *
  14  *
  15  *  This header is used to define dynamic hash tables as described
  16  *  by the article "Main-Memory Linear Hashing - Some Enhancements
  17  *  of Larson's Algorithm" by Mikael Petterson.
  18  *
  19  *  Basically, linear hashing prevents big "stalls" during
  20  *  resizes of the buckets array by only splitting one bucket
  21  *  at a time. This ensures excellent response time even when
  22  *  the table is frequently resized..
  23  *
  24  *
  25  *  Note that the use of the FT_Hash type is rather unusual in order
  26  *  to be as generic and efficient as possible. See the comments in the
  27  *  following definitions for more details.
  28  */
  29
  30 #ifndef __FT_HASH_H__
  31 #define __FT_HASH_H__
  32
  33 #include <ft2build.h>
  34 #include FT_TYPES_H
  35
  36 FT_BEGIN_HEADER
  37
  38  /***********************************************************
  39   *
  40   * @type: FT_Hash
  41   *
  42   * @description:
  43   *   handle to a @FT_HashRec structure used to model a
  44   *   dynamic hash table
  45   */
  46   typedef struct FT_HashRec_*      FT_Hash;
  47
  48
  49  /***********************************************************
  50   *
  51   * @type: FT_HashNode
  52   *
  53   * @description:
  54   *   handle to a @FT_HashNodeRec structure used to model a
  55   *   single node of a hash table
  56   */
  57   typedef struct FT_HashNodeRec_*  FT_HashNode;
  58
  59
  60  /***********************************************************
  61   *
  62   * @type: FT_HashLookup
  63   *
  64   * @description:
  65   *   handle to a @FT_HashNode pointer. This is returned by
  66   *   the @ft_hash_lookup function and can later be used by
  67   *   @ft_hash_add or @ft_hash_remove
  68   */
  69   typedef FT_HashNode*     FT_HashLookup;
  70
  71
  72  /***********************************************************
  73   *
  74   * @type: FT_Hash_EqualFunc
  75   *
  76   * @description:
  77   *   a function used to compare two nodes of the hash table
  78   *
  79   * @input:
  80   *   node1 :: handle to first node
  81   *   node2 :: handle to second node
  82   *
  83   * @return:
  84   *   1 iff the 'keys' in 'node1' and 'node2' are identical.
  85   *   0 otherwise.
  86   */
  87   typedef FT_Int  (*FT_Hash_EqualFunc)( FT_HashNode  node1,
  88                                         FT_HashNode  node2 );
  89
  90
  91  /***********************************************************
  92   *
  93   * @struct: FT_HashRec
  94   *
  95   * @description:
  96   *   a structure used to model a dynamic hash table.
  97   *
  98   * @fields:
  99   *   memory       :: memory manager used to allocate
 100   *                   the buckets array and the hash nodes
 101   *
 102   *   buckets      :: array of hash buckets
 103   *
 104   *   node_size    :: size of node in bytes
 105   *   node_compare :: a function used to compare two nodes
 106   *   node_hash    :: a function used to compute the hash
 107   *                   value of a given node
 108   *   p            ::
 109   *   mask         ::
 110   *   slack        ::
 111   *
 112   * @note:
 113   *   'p', 'mask' and 'slack' are control values managed by
 114   *   the hash table. Do not try to interpret them directly.
 115   *
 116   *   You can grab the hash table size by calling
 117   *   '@ft_hash_get_size'.
 118   */
 119   typedef struct FT_HashRec_
 120   {
 121     FT_HashNode*         buckets;
 122     FT_UInt              p;
 123     FT_UInt              mask;  /* really maxp-1 */
 124     FT_Long              slack;
 125     FT_Hash_EqualFunc    node_equal;
 126     FT_Memory            memory;
 127
 128   } FT_HashRec;
 129
 130
 131  /***********************************************************
 132   *
 133   * @struct: FT_HashNodeRec
 134   *
 135   * @description:
 136   *   a structure used to model the root fields of a dynamic
 137   *   hash table node.
 138   *
 139   *   it's up to client applications to "sub-class" this
 140   *   structure to add relevant (key,value) definitions
 141   *
 142   * @fields:
 143   *   link :: pointer to next node in bucket's collision list
 144   *   hash :: 32-bit hash value for this node
 145   *
 146   * @note:
 147   *   it's up to client applications to "sub-class" this structure
 148   *   to add relevant (key,value) type definitions. For example,
 149   *   if we want to build a "string -> int" mapping, we could use
 150   *   something like:
 151   *
 152   *   {
 153   *     typedef struct MyNodeRec_
 154   *     {
 155   *       FT_HashNodeRec  hnode;
 156   *       const char*     key;
 157   *       int             value;
 158   *
 159   *     } MyNodeRec, *MyNode;
 160   *   }
 161   *
 162   */
 163   typedef struct FT_HashNodeRec_
 164   {
 165     FT_HashNode  link;
 166     FT_UInt32    hash;
 167
 168   } FT_HashNodeRec;
 169
 170
 171  /****************************************************************
 172   *
 173   * @function: ft_hash_init
 174   *
 175   * @description:
 176   *   initialize a dynamic hash table
 177   *
 178   * @input:
 179   *   table      :: handle to target hash table structure
 180   *   node_equal :: node comparison function
 181   *   memory     :: memory manager handle used to allocate the
 182   *                 buckets array within the hash table
 183   *
 184   * @return:
 185   *   error code. 0 means success
 186   *
 187   * @note:
 188   *   the node comparison function should only compare node _keys_
 189   *   and ignore values !! with good hashing computation (which the
 190   *   user must perform itself), the comparison function should be
 191   *   pretty seldom called.
 192   *
 193   *   here is a simple example:
 194   *
 195   *   {
 196   *     static int my_equal( MyNode  node1,
 197   *                          MyNode  node2 )
 198   *     {
 199   *       // compare keys of 'node1' and 'node2'
 200   *       return (strcmp( node1->key, node2->key ) == 0);
 201   *     }
 202   *
 203   *     ....
 204   *
 205   *     ft_hash_init( &hash, (FT_Hash_EqualFunc) my_compare, memory );
 206   *     ....
 207   *   }
 208   */
 209   FT_BASE( FT_Error )
 210   ft_hash_init( FT_Hash              table,
 211                 FT_Hash_EqualFunc  compare,
 212                 FT_Memory            memory );
 213
 214
 215  /****************************************************************
 216   *
 217   * @function: ft_hash_lookup
 218   *
 219   * @description:
 220   *   search a hash table to find a node corresponding to a given
 221   *   key.
 222   *
 223   * @input:
 224   *   table   :: handle to target hash table structure
 225   *   keynode :: handle to a reference hash node that will be
 226   *              only used for key comparisons with the table's
 227   *              elements
 228   *
 229   * @return:
 230   *   a pointer-to-hash-node value, which must be used as followed:
 231   *
 232   *   - if '*result' is NULL, the key wasn't found in the hash
 233   *     table. The value of 'result' can be used to add new elements
 234   *     through @ft_hash_add however..
 235   *
 236   *   - if '*result' is not NULL, it's a handle to the first table
 237   *     node that corresponds to the search key. The value of 'result'
 238   *     can be used to remove this element through @ft_hash_remove
 239   *
 240   * @note:
 241   *   here is an example:
 242   *
 243   *   {
 244   *     // maps a string to an integer with a hash table
 245   *     // returns -1 in case of failure
 246   *     //
 247   *     int  my_lookup( FT_Hash      table,
 248   *                     const char*  key )
 249   *     {
 250   *       MyNode*    pnode;
 251   *       MyNodeRec  noderec;
 252   *
 253   *       // set-up key node. It's 'hash' and 'key' fields must
 254   *       // be set correctly.. we ignore 'link' and 'value'
 255   *       //
 256   *       noderec.hnode.hash = strhash( key );
 257   *       noderec.key        = key;
 258   *
 259   *       // perform search - return value
 260   *       //
 261   *       pnode = (MyNode) ft_hash_lookup( table, &noderec );
 262   *       if ( *pnode )
 263   *       {
 264   *         // we found it
 265   *         return (*pnode)->value;
 266   *       }
 267   *       return -1;
 268   *     }
 269   *   }
 270   */
 271   FT_BASE_DEF( FT_HashLookup )
 272   ft_hash_lookup( FT_Hash      table,
 273                   FT_HashNode  keynode );
 274
 275
 276  /****************************************************************
 277   *
 278   * @function: ft_hash_add
 279   *
 280   * @description:
 281   *   add a new node to a dynamic hash table. the user must
 282   *   call @ft_hash_lookup and allocate a new node before calling
 283   *   this function.
 284   *
 285   * @input:
 286   *   table    :: hash table handle
 287   *   lookup   :: pointer-to-hash-node value returned by @ft_hash_lookup
 288   *   new_node :: handle to new hash node. All its fields must be correctly
 289   *               set, including 'hash'.
 290   *
 291   * @return:
 292   *   error code. 0 means success
 293   *
 294   * @note:
 295   *   this function should always be used _after_ a call to @ft_hash_lookup
 296   *   that returns a pointer to a NULL  handle. Here's an example:
 297   *
 298   *   {
 299   *     // sets the value corresponding to a given string key
 300   *     //
 301   *     void  my_set( FT_Hash      table,
 302   *                   const char*  key,
 303   *                   int          value )
 304   *     {
 305   *       MyNode*    pnode;
 306   *       MyNodeRec  noderec;
 307   *       MyNode     node;
 308   *
 309   *       // set-up key node. It's 'hash' and 'key' fields must
 310   *       // be set correctly..
 311   *       noderec.hnode.hash = strhash( key );
 312   *       noderec.key        = key;
 313   *
 314   *       // perform search - return value
 315   *       pnode = (MyNode) ft_hash_lookup( table, &noderec );
 316   *       if ( *pnode )
 317   *       {
 318   *         // we found it, simply replace the value in the node
 319   *         (*pnode)->value = value;
 320   *         return;
 321   *       }
 322   *
 323   *       // allocate a new node - and set it up
 324   *       node = (MyNode) malloc( sizeof(*node) );
 325   *       if ( node == NULL ) .....
 326   *
 327   *       node->hnode.hash = noderec.hnode.hash;
 328   *       node->key        = key;
 329   *       node->value      = value;
 330   *
 331   *       // add it to the hash table
 332   *       error = ft_hash_add( table, pnode, node );
 333   *       if (error) ....
 334   *     }
 335   */
 336   FT_BASE( FT_Error )
 337   ft_hash_add( FT_Hash        table,
 338                FT_HashLookup  lookup,
 339                FT_HashNode    new_node );
 340
 341
 342  /****************************************************************
 343   *
 344   * @function: ft_hash_remove
 345   *
 346   * @description:
 347   *   try to remove the node corresponding to a given key from
 348   *   a hash table. This must be called after @ft_hash_lookup
 349   *
 350   * @input:
 351   *   table   :: hash table handle
 352   *   lookup  :: pointer-to-hash-node value returned by @ft_hash_lookup
 353   *
 354   * @note:
 355   *   this function doesn't free the node itself !! Here's an example:
 356   *
 357   *   {
 358   *     // sets the value corresponding to a given string key
 359   *     //
 360   *     void  my_remove( FT_Hash      table,
 361   *                      const char*  key )
 362   *     {
 363   *       MyNodeRec  noderec;
 364   *       MyNode     node;
 365   *
 366   *       noderec.hnode.hash = strhash(key);
 367   *       noderec.key        = key;
 368   *       node               = &noderec;
 369   *
 370   *       pnode = ft_hash_lookup( table, &noderec );
 371   *       node  = *pnode;
 372   *       if ( node != NULL )
 373   *       {
 374   *         error = ft_hash_remove( table, pnode );
 375   *         if ( !error )
 376   *           free( node );
 377   *       }
 378   *     }
 379   *   }
 380   */
 381   FT_BASE( FT_Error )
 382   ft_hash_remove( FT_Hash        table,
 383                   FT_HashLookup  lookup );
 384
 385
 386
 387  /****************************************************************
 388   *
 389   * @function: ft_hash_get_size
 390   *
 391   * @description:
 392   *   return the number of elements in a given hash table
 393   *
 394   * @input:
 395   *   table   :: handle to target hash table structure
 396   *
 397   * @return:
 398   *   number of elements. 0 if empty
 399   */
 400   FT_BASE( FT_UInt )
 401   ft_hash_get_size( FT_Hash  table );
 402
 403
 404
 405  /****************************************************************
 406   *
 407   * @functype: FT_Hash_ForeachFunc
 408   *
 409   * @description:
 410   *   a function used to iterate over all elements of a given
 411   *   hash table
 412   *
 413   * @input:
 414   *   node :: handle to target @FT_HashNodeRec node structure
 415   *   data :: optional argument to iteration routine
 416   *
 417   * @also:  @ft_hash_foreach
 418   */
 419   typedef void  (*FT_Hash_ForeachFunc)( const FT_HashNode  node,
 420                                         const FT_Pointer   data );
 421
 422
 423  /****************************************************************
 424   *
 425   * @function: ft_hash_foreach
 426   *
 427   * @description:
 428   *   parse over all elements in a hash table
 429   *
 430   * @input:
 431   *   table        :: handle to target hash table structure
 432   *   foreach_func :: iteration routine called for each element
 433   *   foreach_data :: optional argument to the iteration routine
 434   *
 435   * @note:
 436   *   this function is often used to release all elements from a
 437   *   hash table. See the example given for @ft_hash_done
 438   */
 439   FT_BASE( void )
 440   ft_hash_foreach( FT_Hash              table,
 441                    FT_Hash_ForeachFunc  foreach_func,
 442                    const FT_Pointer     foreach_data );
 443
 444
 445
 446  /****************************************************************
 447   *
 448   * @function: ft_hash_done
 449   *
 450   * @description:
 451   *   finalize a given hash table
 452   *
 453   * @input:
 454   *   table     :: handle to target hash table structure
 455   *   node_func :: optional iteration function pointer. this
 456   *                can be used to destroy all nodes explicitely
 457   *   node_data :: optional argument to the node iterator
 458   *
 459   * @note:
 460   *   this function simply frees the hash table's buckets.
 461   *   you probably will need to call @ft_hash_foreach to
 462   *   destroy all its elements before @ft_hash_done, as in
 463   *   the following example:
 464   *
 465   *   {
 466   *     static void  my_node_clear( const MyNode  node )
 467   *     {
 468   *       free( node );
 469   *     }
 470   *
 471   *     static void  my_done( FT_Hash  table )
 472   *     {
 473   *       ft_hash_done( table, (FT_Hash_ForeachFunc) my_node_clear, NULL );
 474   *     }
 475   *   }
 476   */
 477   FT_BASE( void )
 478   ft_hash_done( FT_Hash              table,
 479                 FT_Hash_ForeachFunc  item_func,
 480                 const FT_Pointer     item_data );
 481
 482  /* */
 483
 484  /* compute bucket index from hash value in a dynamic hash table */
 485  /* this is only used to break encapsulation to speed lookups in */
 486  /* the FreeType cache manager !!                                */
 487  /*                                                              */
 488
 489 #define  FT_HASH_COMPUTE_INDEX(_table,_hash,_index)                  \
 490              {                                                       \
 491                FT_UInt  _mask  = (_table)->mask;                     \
 492                FT_UInt  _hash0 = (_hash);                            \
 493                                                                      \
 494                (_index) = (FT_UInt)( (_hash0) & _mask ) );           \
 495                if ( (_index) < (_table)->p )                         \
 496                  (_index) = (FT_uInt)( (_hash0) & ( 2*_mask+1 ) );   \
 497              }
 498
 499
 500 FT_END_HEADER
 501
 502 #endif /* __FT_HASH_H__ */