Edit
kc3-lang/freetype/src/base/fthash.c
Werner Lemberg
- src/base/fthash.c
-
/**************************************************************************** * * 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_NEW( 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 */