From 37da2899f40661e3e9631e497da8dc59b971cbd0 Mon Sep 17 00:00:00 2001 From: "Charles.Forsyth" Date: Fri, 22 Dec 2006 17:07:39 +0000 Subject: 20060303a --- libfreetype/fthash.c | 246 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 246 insertions(+) create mode 100644 libfreetype/fthash.c (limited to 'libfreetype/fthash.c') diff --git a/libfreetype/fthash.c b/libfreetype/fthash.c new file mode 100644 index 00000000..c42b1dcf --- /dev/null +++ b/libfreetype/fthash.c @@ -0,0 +1,246 @@ +#include +#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; + } -- cgit v1.2.3