kc3-lang/freetype/src/base/fthash.c

• Show log

  Commit

• Hash : 7acd73fd
  Author :
  Date : 2002-07-11T23:41:14
  

  * src/sfnt/ttload.c, src/sfnt/ttload.h, src/sfnt/ttdriver.c: changing the SFNT loader to check for SFNT-based font files differently. We now ignore the range "helper" fields and check the "head" table's magic number instead.

Download

• src/base/fthash.c

• #include <ft2build.h>
  #include FT_TYPES_H
  #include FT_INTERNAL_HASH_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->node_equal = 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( FT_Error )
    ft_hash_init( FT_Hash            table,
                  FT_Hash_EqualFunc  equal,
                  FT_Memory          memory )
    {
      FT_Error  error;
  
      table->memory     = memory;
      table->p          = 0;
      table->mask       = FT_HASH_INITIAL_SIZE-1;
      table->slack      = FT_HASH_INITIAL_SIZE*FT_HASH_MAX_LOAD;
      table->node_equal = equal;
  
      (void)FT_NEW_ARRAY( table->buckets, FT_HASH_INITIAL_SIZE*2 );
  
      return error;
    }
  
  
  
    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_HashLookup )
    ft_hash_lookup( FT_Hash      table,
                    FT_HashNode  keynode )
    {
      FT_UInt       index;
      FT_UInt32     hash = keynode->hash;
      FT_HashNode   node, *pnode;
  
      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->node_equal( node, keynode ) )
          break;
  
        pnode = &node->link;
      }
  
      return pnode;
    }
  
  
  
  
    FT_BASE_DEF( FT_Error )
    ft_hash_add( FT_Hash        table,
                 FT_HashLookup  lookup,
                 FT_HashNode    new_node )
    {
      FT_Error     error = 0;
  
      /* add it to the hash table */
      new_node->link = *lookup;
      *lookup        = new_node;
  
      if ( --table->slack < 0 )
      {
        FT_UInt       p     = table->p;
        FT_UInt       mask  = table->mask;
        FT_HashNode   new_list, node, *pnode;
  
        /* 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_Memory  memory = table->memory;
  
  
          if (FT_RENEW_ARRAY( table->buckets, (mask+1)*2, (mask+1)*4 ))
            goto Exit;
  
          table->mask = 2*mask + 1;
          table->p    = 0;
        }
        else
          table->p = p + 1;
      }
    Exit:
      return error;
    }
  
  
  
    FT_BASE_DEF( FT_Error )
    ft_hash_remove( FT_Hash        table,
                    FT_HashLookup  lookup )
    {
      FT_HashNode  node;
      FT_UInt      num_buckets;
      FT_Error     error = 0;
  
      FT_ASSERT( pnode != NULL && node != NULL );
  
      node       = *lookup;
      *lookup    = node->link;
      node->link = NULL;
  
      num_buckets = ( table->p + table->mask + 1) ;
  
      if ( ++ table->slack > (FT_Long)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 )
          goto Exit;
  
        if ( p == 0 )
        {
          FT_Memory  memory = table->memory;
  
          table->mask >>= 1;
          p             = table->mask;
  
          if ( FT_RENEW_ARRAY( table->buckets, (mask+1)*2, (mask+1) ) )
          {
            /* this should never happen normally, but who knows :-)   */
            /* we need to re-inject the node in the hash table before */
            /* returning there, since it's safer                      */
            pnode      = table->buckets;
            node->link = *pnode;
            *pnode     = node;
  
            goto Exit;
          }
        }
        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;
      }
    Exit:
      return error;
    }
  

Download