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

Branch : - branch - master v2.13 - tag -

• Show log

  Commit

• Author : David Turner
  Date : 2002-05-01 08:46:56
  Hash : 10937304
  Message : * include/freetype/internal/fthash.h, src/base/fthash.c: adding a generic implementation of dynamic hash tables using linear algorithm (to get rid of 'stalls' during resizes). This will be used in the future in at least three parts of the library: the cache sub-system, the object sub-system and the memory debugger. * include/freetype/internal/ftcore.h: added this header file to group all new definitions related to exception handling and memory management. It's very likely that this file will disappear or be renamed in the future.. * include/freetype/internal/ftobject.h, include/freetype/ftsysmem.h: adding comments to better explain the object sub-system as well as the new memory manager interface.

• 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;
      }
    }