shithub: freetype+ttf2subf

ref: 0460c1d97e4f45f1b1fb1022cd6dda067d34161b
dir: /src/base/fthash.c/

#include "fthash.h"
#include FT_INTERNAL_MEMORY_H
#include FT_INTERNAL_DEBUG_H

#define  FT_HASH_MAX_LOAD  2
#define  FT_HASH_MIN_LOAD  1
#define  FT_HASH_SUB_LOAD  (FT_HASH_MAX_LOAD-FT_HASH_MIN_LOAD)

/* this one _must_ be a power of 2 !! */
#define  FT_HASH_INITIAL_SIZE  8


  FT_BASE_DEF( void )
  ft_hash_done( FT_Hash              table,
                FT_Hash_ForeachFunc  node_func,
                const FT_Pointer     node_data )
  {
    if ( table )
    {
      FT_Memory  memory = table->memory;

      if ( node_func )
        ft_hash_foreach( table, node_func, node_data );

      FT_FREE( table->buckets );
      table->p     = 0;
      table->mask  = 0;
      table->slack = 0;

      table->compare = NULL;
    }
  }


  FT_BASE_DEF( FT_UInt )
  ft_hash_get_size( FT_Hash  table )
  {
    FT_UInt  result = 0;

    if ( table )
      result = (table->p + table->mask + 1)*FT_HASH_MAX_LOAD - table->slack;

    return result;
  }



  FT_BASE_DEF( void )
  ft_hash_init( FT_Hash              table,
                FT_Hash_CompareFunc  compare,
                FT_Memory            memory )
  {
    hash->memory  = memory;
    hash->compare = node_compare;
    hash->p       = 0;
    hash->mask    = FT_HASH_INITIAL_SIZE-1;
    hash->slack   = FT_HASH_INITIAL_SIZE*FT_HASH_MAX_LOAD;

    FT_NEW_ARRAY( hash->buckets, FT_HASH_INITIAL_SIZE*2 );
  }



  FT_BASE_DEF( void )
  ft_hash_foreach( FT_Hash              table,
                   FT_Hash_ForeachFunc  foreach_func,
                   const FT_Pointer     foreach_data )
  {
    FT_UInt       count = table->p + table->mask + 1;
    FT_HashNode*  pnode = table->buckets;
    FT_HashNode   node, next;

    for ( ; count > 0; count--, pnode++ )
    {
      node = *pnode;
      while ( node )
      {
        next = node->link;
        foreach_func( node, foreach_data );
        node = next;
      }
    }
  }



  FT_BASE_DEF( FT_HashNode* )
  ft_hash_lookup( FT_Hash      table,
                  FT_HashNode  keynode )
  {
    FT_UInt    index;
    FT_UInt23  hash = keynode->hash;

    index = (FT_UInt)(hash & table->mask);
    if ( index < table->p )
      index = (FT_UInt)(hash & (2*table->mask+1));

    pnode = &table->buckets[index];
    for (;;)
    {
      node = *pnode;
      if ( node == NULL )
        break;

      if ( node->hash == hash && table->compare( node, keynode ) )
        break;

      pnode = &node->link;
    }

    return pnode;
  }




  FT_BASE_DEF( void )
  ft_hash_add( FT_Hash       table,
               FT_HashNode*  pnode,
               FT_HashNode   new_node )
  {
    /* add it to the hash table */
    new_node->link = *pnode;
    *pnode         = new_node;

    if ( --table->slack < 0 )
    {
      FT_UInt       p     = table->p;
      FT_UInt       mask  = table->mask;
      FT_HashNode   new_list;

      /* split a single bucket */
      new_list = NULL;
      pnode    = table->buckets + p;
      for (;;)
      {
        node = *pnode;
        if ( node == NULL )
          break;

        if ( node->hash & mask )
        {
          *pnode     = node->link;
          node->link = new_list;
          new_list   = node;
        }
        else
          pnode = &node->link;
      }

      table->buckets[ p + mask + 1 ] = new_list;

      table->slack += FT_HASH_MAX_LOAD;

      if ( p >= mask )
      {
        FT_RENEW_ARRAY( hash->buckets, (mask+1)*2, (mask+1)*4 );
        table->mask = 2*mask + 1;
        table->p    = 0;
      }
      else
        table->p = p + 1;
    }
  }



  FT_BASE_DEF( FT_Int )
  ft_hash_remove( FT_Hash      table,
                  FT_HashNode* pnode )
  {
    FT_HashNode  node;
    FT_UInt      num_buckets;

    FT_ASSERT( pnode != NULL && node != NULL );

    node         = *pnode;
    *pnode->link = node->link;
    node->link   = NULL;

    num_buckets = ( table->p + table->mask + 1) ;

    if ( ++ table->slack > num_buckets*FT_HASH_SUB_LOAD )
    {
      FT_UInt       p         = table->p;
      FT_UInt       mask      = table->mask;
      FT_UInt       old_index = p + mask;
      FT_HashNode*  pnode;
      FT_HashNode*  pold;

      if ( old_index < FT_HASH_INITIAL_SIZE )
        return;

      if ( p == 0 )
      {
        table->mask >>= 1;
        p             = table->mask;

        FT_RENEW_ARRAY( hash->buckets, (mask+1)*2, (mask) );
      }
      else
        p--;

      pnode = table->buckets + p;
      while ( *pnode )
        pnode = &(*pnode)->link;

      pold   = table->buckets + old_index;
      *pnode = *pold;
      *pold  = NULL;

      table->slack -= FT_HASH_MAX_LOAD;
      table->p      = p;
    }
  }