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