| /**************************************************************************** |
| * |
| * fthash.c |
| * |
| * Hashing functions (body). |
| * |
| */ |
| |
| /* |
| * Copyright 2000 Computing Research Labs, New Mexico State University |
| * Copyright 2001-2015 |
| * Francesco Zappa Nardelli |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice and this permission notice shall be included in |
| * all copies or substantial portions of the Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| * THE COMPUTING RESEARCH LAB OR NEW MEXICO STATE UNIVERSITY BE LIABLE FOR ANY |
| * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT |
| * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR |
| * THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| */ |
| |
| /************************************************************************** |
| * |
| * This file is based on code from bdf.c,v 1.22 2000/03/16 20:08:50 |
| * |
| * taken from Mark Leisher's xmbdfed package |
| * |
| */ |
| |
| |
| #include <freetype/internal/fthash.h> |
| #include <freetype/internal/ftmemory.h> |
| |
| |
| #define INITIAL_HT_SIZE 241 |
| |
| |
| static FT_ULong |
| hash_str_lookup( FT_Hashkey* key ) |
| { |
| const char* kp = key->str; |
| FT_ULong res = 0; |
| |
| |
| /* Mocklisp hash function. */ |
| while ( *kp ) |
| res = ( res << 5 ) - res + (FT_ULong)*kp++; |
| |
| return res; |
| } |
| |
| |
| static FT_ULong |
| hash_num_lookup( FT_Hashkey* key ) |
| { |
| FT_ULong num = (FT_ULong)key->num; |
| FT_ULong res; |
| |
| |
| /* Mocklisp hash function. */ |
| res = num & 0xFF; |
| res = ( res << 5 ) - res + ( ( num >> 8 ) & 0xFF ); |
| res = ( res << 5 ) - res + ( ( num >> 16 ) & 0xFF ); |
| res = ( res << 5 ) - res + ( ( num >> 24 ) & 0xFF ); |
| |
| return res; |
| } |
| |
| |
| static FT_Bool |
| hash_str_compare( FT_Hashkey* a, |
| FT_Hashkey* b ) |
| { |
| if ( a->str[0] == b->str[0] && |
| ft_strcmp( a->str, b->str ) == 0 ) |
| return 1; |
| |
| return 0; |
| } |
| |
| |
| static FT_Bool |
| hash_num_compare( FT_Hashkey* a, |
| FT_Hashkey* b ) |
| { |
| if ( a->num == b->num ) |
| return 1; |
| |
| return 0; |
| } |
| |
| |
| static FT_Hashnode* |
| hash_bucket( FT_Hashkey key, |
| FT_Hash hash ) |
| { |
| FT_ULong res = 0; |
| FT_Hashnode* bp = hash->table; |
| FT_Hashnode* ndp; |
| |
| |
| res = (hash->lookup)( &key ); |
| |
| ndp = bp + ( res % hash->size ); |
| while ( *ndp ) |
| { |
| if ( (hash->compare)( &(*ndp)->key, &key ) ) |
| break; |
| |
| ndp--; |
| if ( ndp < bp ) |
| ndp = bp + ( hash->size - 1 ); |
| } |
| |
| return ndp; |
| } |
| |
| |
| static FT_Error |
| hash_rehash( FT_Hash hash, |
| FT_Memory memory ) |
| { |
| FT_Hashnode* obp = hash->table; |
| FT_Hashnode* bp; |
| FT_Hashnode* nbp; |
| |
| FT_UInt i, sz = hash->size; |
| FT_Error error = FT_Err_Ok; |
| |
| |
| hash->size <<= 1; |
| hash->limit = hash->size / 3; |
| |
| if ( FT_NEW_ARRAY( hash->table, hash->size ) ) |
| goto Exit; |
| |
| for ( i = 0, bp = obp; i < sz; i++, bp++ ) |
| { |
| if ( *bp ) |
| { |
| nbp = hash_bucket( (*bp)->key, hash ); |
| *nbp = *bp; |
| } |
| } |
| |
| FT_FREE( obp ); |
| |
| Exit: |
| return error; |
| } |
| |
| |
| static FT_Error |
| hash_init( FT_Hash hash, |
| FT_Bool is_num, |
| FT_Memory memory ) |
| { |
| FT_UInt sz = INITIAL_HT_SIZE; |
| FT_Error error; |
| |
| |
| hash->size = sz; |
| hash->limit = sz / 3; |
| hash->used = 0; |
| |
| if ( is_num ) |
| { |
| hash->lookup = hash_num_lookup; |
| hash->compare = hash_num_compare; |
| } |
| else |
| { |
| hash->lookup = hash_str_lookup; |
| hash->compare = hash_str_compare; |
| } |
| |
| FT_MEM_NEW_ARRAY( hash->table, sz ); |
| |
| return error; |
| } |
| |
| |
| FT_Error |
| ft_hash_str_init( FT_Hash hash, |
| FT_Memory memory ) |
| { |
| return hash_init( hash, 0, memory ); |
| } |
| |
| |
| FT_Error |
| ft_hash_num_init( FT_Hash hash, |
| FT_Memory memory ) |
| { |
| return hash_init( hash, 1, memory ); |
| } |
| |
| |
| void |
| ft_hash_str_free( FT_Hash hash, |
| FT_Memory memory ) |
| { |
| if ( hash ) |
| { |
| FT_UInt sz = hash->size; |
| FT_Hashnode* bp = hash->table; |
| FT_UInt i; |
| |
| |
| for ( i = 0; i < sz; i++, bp++ ) |
| FT_FREE( *bp ); |
| |
| FT_FREE( hash->table ); |
| } |
| } |
| |
| |
| /* `ft_hash_num_free' is the same as `ft_hash_str_free' */ |
| |
| |
| static FT_Error |
| hash_insert( FT_Hashkey key, |
| size_t data, |
| FT_Hash hash, |
| FT_Memory memory ) |
| { |
| FT_Hashnode nn; |
| FT_Hashnode* bp = hash_bucket( key, hash ); |
| FT_Error error = FT_Err_Ok; |
| |
| |
| nn = *bp; |
| if ( !nn ) |
| { |
| if ( FT_QNEW( nn ) ) |
| goto Exit; |
| *bp = nn; |
| |
| nn->key = key; |
| nn->data = data; |
| |
| if ( hash->used >= hash->limit ) |
| { |
| error = hash_rehash( hash, memory ); |
| if ( error ) |
| goto Exit; |
| } |
| |
| hash->used++; |
| } |
| else |
| nn->data = data; |
| |
| Exit: |
| return error; |
| } |
| |
| |
| FT_Error |
| ft_hash_str_insert( const char* key, |
| size_t data, |
| FT_Hash hash, |
| FT_Memory memory ) |
| { |
| FT_Hashkey hk; |
| |
| |
| hk.str = key; |
| |
| return hash_insert( hk, data, hash, memory ); |
| } |
| |
| |
| FT_Error |
| ft_hash_num_insert( FT_Int num, |
| size_t data, |
| FT_Hash hash, |
| FT_Memory memory ) |
| { |
| FT_Hashkey hk; |
| |
| |
| hk.num = num; |
| |
| return hash_insert( hk, data, hash, memory ); |
| } |
| |
| |
| static size_t* |
| hash_lookup( FT_Hashkey key, |
| FT_Hash hash ) |
| { |
| FT_Hashnode* np = hash_bucket( key, hash ); |
| |
| |
| return (*np) ? &(*np)->data |
| : NULL; |
| } |
| |
| |
| size_t* |
| ft_hash_str_lookup( const char* key, |
| FT_Hash hash ) |
| { |
| FT_Hashkey hk; |
| |
| |
| hk.str = key; |
| |
| return hash_lookup( hk, hash ); |
| } |
| |
| |
| size_t* |
| ft_hash_num_lookup( FT_Int num, |
| FT_Hash hash ) |
| { |
| FT_Hashkey hk; |
| |
| |
| hk.num = num; |
| |
| return hash_lookup( hk, hash ); |
| } |
| |
| |
| /* END */ |