From 6bf0a5cb5034a7e684dcc3500e841785237ce2dd Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 19:32:43 +0200 Subject: Adding upstream version 1:115.7.0. Signed-off-by: Daniel Baumann --- modules/freetype2/src/base/fthash.c | 338 ++++++++++++++++++++++++++++++++++++ 1 file changed, 338 insertions(+) create mode 100644 modules/freetype2/src/base/fthash.c (limited to 'modules/freetype2/src/base/fthash.c') diff --git a/modules/freetype2/src/base/fthash.c b/modules/freetype2/src/base/fthash.c new file mode 100644 index 0000000000..313bbbb4b2 --- /dev/null +++ b/modules/freetype2/src/base/fthash.c @@ -0,0 +1,338 @@ +/**************************************************************************** + * + * 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 +#include + + +#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 */ -- cgit v1.2.3