ref: a8e4563c3418ed74d39019a6c5e2122d12c8f56f
dir: /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_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 */