summaryrefslogtreecommitdiffstats
path: root/src/base/fthash.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/base/fthash.c')
-rw-r--r--src/base/fthash.c339
1 files changed, 339 insertions, 0 deletions
diff --git a/src/base/fthash.c b/src/base/fthash.c
new file mode 100644
index 0000000..21bc8dd
--- /dev/null
+++ b/src/base/fthash.c
@@ -0,0 +1,339 @@
+/***************************************************************************/
+/* */
+/* 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 <ft2build.h>
+#include FT_INTERNAL_HASH_H
+#include FT_INTERNAL_MEMORY_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 */
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-18 19:42:05 +0000