summaryrefslogtreecommitdiff
path: root/include/freetype/internal/fthash.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/freetype/internal/fthash.h')
-rw-r--r--include/freetype/internal/fthash.h595
1 files changed, 114 insertions, 481 deletions
diff --git a/include/freetype/internal/fthash.h b/include/freetype/internal/fthash.h
index b95b6c92..622ec76b 100644
--- a/include/freetype/internal/fthash.h
+++ b/include/freetype/internal/fthash.h
@@ -1,502 +1,135 @@
-/******************************************************************
+/****************************************************************************
*
- * fthash.h - fast dynamic hash tables
+ * fthash.h
*
- * Copyright 2002 by
- * David Turner, Robert Wilhelm, and Werner Lemberg
+ * Hashing functions (specification).
*
- * This file is part of the FreeType project, and may only be used,
- * modified, and distributed under the terms of the FreeType project
- * license, LICENSE.TXT. By continuing to use, modify, or distribute
- * this file you indicate that you have read the license and
- * understand and accept it fully.
- *
- *
- * This header is used to define dynamic hash tables as described
- * by the article "Main-Memory Linear Hashing - Some Enhancements
- * of Larson's Algorithm" by Mikael Petterson.
+ */
+
+/*
+ * Copyright 2000 Computing Research Labs, New Mexico State University
+ * Copyright 2001-2015
+ * Francesco Zappa Nardelli
*
- * Basically, linear hashing prevents big "stalls" during
- * resizes of the buckets array by only splitting one bucket
- * at a time. This ensures excellent response time even when
- * the table is frequently resized..
+ * 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.
*
- * Note that the use of the FT_Hash type is rather unusual in order
- * to be as generic and efficient as possible. See the comments in the
- * following definitions for more details.
+ * 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.
*/
-#ifndef __FT_HASH_H__
-#define __FT_HASH_H__
+ /**************************************************************************
+ *
+ * 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
+ *
+ */
+
+
+#ifndef FTHASH_H_
+#define FTHASH_H_
+
+
+#include <freetype/freetype.h>
-#include <ft2build.h>
-#include FT_TYPES_H
FT_BEGIN_HEADER
- /***********************************************************
- *
- * @type: FT_Hash
- *
- * @description:
- * handle to a @FT_HashRec structure used to model a
- * dynamic hash table
- */
- typedef struct FT_HashRec_* FT_Hash;
-
-
- /***********************************************************
- *
- * @type: FT_HashNode
- *
- * @description:
- * handle to a @FT_HashNodeRec structure used to model a
- * single node of a hash table
- */
- typedef struct FT_HashNodeRec_* FT_HashNode;
-
-
- /***********************************************************
- *
- * @type: FT_HashLookup
- *
- * @description:
- * handle to a @FT_HashNode pointer. This is returned by
- * the @ft_hash_lookup function and can later be used by
- * @ft_hash_add or @ft_hash_remove
- */
- typedef FT_HashNode* FT_HashLookup;
-
-
- /***********************************************************
- *
- * @type: FT_Hash_EqualFunc
- *
- * @description:
- * a function used to compare two nodes of the hash table
- *
- * @input:
- * node1 :: handle to first node
- * node2 :: handle to second node
- *
- * @return:
- * 1 iff the 'keys' in 'node1' and 'node2' are identical.
- * 0 otherwise.
- */
- typedef FT_Int (*FT_Hash_EqualFunc)( FT_HashNode node1,
- FT_HashNode node2 );
-
-
- /***********************************************************
- *
- * @struct: FT_HashRec
- *
- * @description:
- * a structure used to model a dynamic hash table.
- *
- * @fields:
- * memory :: memory manager used to allocate
- * the buckets array and the hash nodes
- *
- * buckets :: array of hash buckets
- *
- * node_size :: size of node in bytes
- * node_compare :: a function used to compare two nodes
- * node_hash :: a function used to compute the hash
- * value of a given node
- * p ::
- * mask ::
- * slack ::
- *
- * @note:
- * 'p', 'mask' and 'slack' are control values managed by
- * the hash table. Do not try to interpret them directly.
- *
- * You can grab the hash table size by calling
- * '@ft_hash_get_size'.
- */
- typedef struct FT_HashRec_
+
+ typedef union FT_Hashkey_
{
- FT_HashNode* buckets;
- FT_UInt p;
- FT_UInt mask; /* really maxp-1 */
- FT_Long slack;
- FT_Hash_EqualFunc node_equal;
- FT_Memory memory;
+ FT_Int num;
+ const char* str;
- } FT_HashRec;
+ } FT_Hashkey;
+
+
+ typedef struct FT_HashnodeRec_
+ {
+ FT_Hashkey key;
+ size_t data;
+
+ } FT_HashnodeRec;
+
+ typedef struct FT_HashnodeRec_ *FT_Hashnode;
+
+
+ typedef FT_ULong
+ (*FT_Hash_LookupFunc)( FT_Hashkey* key );
+
+ typedef FT_Bool
+ (*FT_Hash_CompareFunc)( FT_Hashkey* a,
+ FT_Hashkey* b );
- /***********************************************************
- *
- * @struct: FT_HashNodeRec
- *
- * @description:
- * a structure used to model the root fields of a dynamic
- * hash table node.
- *
- * it's up to client applications to "sub-class" this
- * structure to add relevant (key,value) definitions
- *
- * @fields:
- * link :: pointer to next node in bucket's collision list
- * hash :: 32-bit hash value for this node
- *
- * @note:
- * it's up to client applications to "sub-class" this structure
- * to add relevant (key,value) type definitions. For example,
- * if we want to build a "string -> int" mapping, we could use
- * something like:
- *
- * {
- * typedef struct MyNodeRec_
- * {
- * FT_HashNodeRec hnode;
- * const char* key;
- * int value;
- *
- * } MyNodeRec, *MyNode;
- * }
- *
- */
- typedef struct FT_HashNodeRec_
+ typedef struct FT_HashRec_
{
- FT_HashNode link;
- FT_UInt32 hash;
-
- } FT_HashNodeRec;
-
-
- /****************************************************************
- *
- * @function: ft_hash_init
- *
- * @description:
- * initialize a dynamic hash table
- *
- * @input:
- * table :: handle to target hash table structure
- * node_equal :: node comparison function
- * memory :: memory manager handle used to allocate the
- * buckets array within the hash table
- *
- * @return:
- * error code. 0 means success
- *
- * @note:
- * the node comparison function should only compare node _keys_
- * and ignore values !! with good hashing computation (which the
- * user must perform itself), the comparison function should be
- * pretty seldom called.
- *
- * here is a simple example:
- *
- * {
- * static int my_equal( MyNode node1,
- * MyNode node2 )
- * {
- * // compare keys of 'node1' and 'node2'
- * return (strcmp( node1->key, node2->key ) == 0);
- * }
- *
- * ....
- *
- * ft_hash_init( &hash, (FT_Hash_EqualFunc) my_compare, memory );
- * ....
- * }
- */
- FT_BASE( FT_Error )
- ft_hash_init( FT_Hash table,
- FT_Hash_EqualFunc compare,
- FT_Memory memory );
-
-
- /****************************************************************
- *
- * @function: ft_hash_lookup
- *
- * @description:
- * search a hash table to find a node corresponding to a given
- * key.
- *
- * @input:
- * table :: handle to target hash table structure
- * keynode :: handle to a reference hash node that will be
- * only used for key comparisons with the table's
- * elements
- *
- * @return:
- * a pointer-to-hash-node value, which must be used as followed:
- *
- * - if '*result' is NULL, the key wasn't found in the hash
- * table. The value of 'result' can be used to add new elements
- * through @ft_hash_add however..
- *
- * - if '*result' is not NULL, it's a handle to the first table
- * node that corresponds to the search key. The value of 'result'
- * can be used to remove this element through @ft_hash_remove
- *
- * @note:
- * here is an example:
- *
- * {
- * // maps a string to an integer with a hash table
- * // returns -1 in case of failure
- * //
- * int my_lookup( FT_Hash table,
- * const char* key )
- * {
- * MyNode* pnode;
- * MyNodeRec noderec;
- *
- * // set-up key node. It's 'hash' and 'key' fields must
- * // be set correctly.. we ignore 'link' and 'value'
- * //
- * noderec.hnode.hash = strhash( key );
- * noderec.key = key;
- *
- * // perform search - return value
- * //
- * pnode = (MyNode) ft_hash_lookup( table, &noderec );
- * if ( *pnode )
- * {
- * // we found it
- * return (*pnode)->value;
- * }
- * return -1;
- * }
- * }
- */
- FT_BASE_DEF( FT_HashLookup )
- ft_hash_lookup( FT_Hash table,
- FT_HashNode keynode );
-
-
- /****************************************************************
- *
- * @function: ft_hash_add
- *
- * @description:
- * add a new node to a dynamic hash table. the user must
- * call @ft_hash_lookup and allocate a new node before calling
- * this function.
- *
- * @input:
- * table :: hash table handle
- * lookup :: pointer-to-hash-node value returned by @ft_hash_lookup
- * new_node :: handle to new hash node. All its fields must be correctly
- * set, including 'hash'.
- *
- * @return:
- * error code. 0 means success
- *
- * @note:
- * this function should always be used _after_ a call to @ft_hash_lookup
- * that returns a pointer to a NULL handle. Here's an example:
- *
- * {
- * // sets the value corresponding to a given string key
- * //
- * void my_set( FT_Hash table,
- * const char* key,
- * int value )
- * {
- * MyNode* pnode;
- * MyNodeRec noderec;
- * MyNode node;
- *
- * // set-up key node. It's 'hash' and 'key' fields must
- * // be set correctly..
- * noderec.hnode.hash = strhash( key );
- * noderec.key = key;
- *
- * // perform search - return value
- * pnode = (MyNode) ft_hash_lookup( table, &noderec );
- * if ( *pnode )
- * {
- * // we found it, simply replace the value in the node
- * (*pnode)->value = value;
- * return;
- * }
- *
- * // allocate a new node - and set it up
- * node = (MyNode) malloc( sizeof(*node) );
- * if ( node == NULL ) .....
- *
- * node->hnode.hash = noderec.hnode.hash;
- * node->key = key;
- * node->value = value;
- *
- * // add it to the hash table
- * error = ft_hash_add( table, pnode, node );
- * if (error) ....
- * }
- */
- FT_BASE( FT_Error )
- ft_hash_add( FT_Hash table,
- FT_HashLookup lookup,
- FT_HashNode new_node );
-
-
- /****************************************************************
- *
- * @function: ft_hash_remove
- *
- * @description:
- * try to remove the node corresponding to a given key from
- * a hash table. This must be called after @ft_hash_lookup
- *
- * @input:
- * table :: hash table handle
- * lookup :: pointer-to-hash-node value returned by @ft_hash_lookup
- *
- * @note:
- * this function doesn't free the node itself !! Here's an example:
- *
- * {
- * // sets the value corresponding to a given string key
- * //
- * void my_remove( FT_Hash table,
- * const char* key )
- * {
- * MyNodeRec noderec;
- * MyNode node;
- *
- * noderec.hnode.hash = strhash(key);
- * noderec.key = key;
- * node = &noderec;
- *
- * pnode = ft_hash_lookup( table, &noderec );
- * node = *pnode;
- * if ( node != NULL )
- * {
- * error = ft_hash_remove( table, pnode );
- * if ( !error )
- * free( node );
- * }
- * }
- * }
- */
- FT_BASE( FT_Error )
- ft_hash_remove( FT_Hash table,
- FT_HashLookup lookup );
-
-
-
- /****************************************************************
- *
- * @function: ft_hash_get_size
- *
- * @description:
- * return the number of elements in a given hash table
- *
- * @input:
- * table :: handle to target hash table structure
- *
- * @return:
- * number of elements. 0 if empty
- */
- FT_BASE( FT_UInt )
- ft_hash_get_size( FT_Hash table );
-
-
-
- /****************************************************************
- *
- * @functype: FT_Hash_ForeachFunc
- *
- * @description:
- * a function used to iterate over all elements of a given
- * hash table
- *
- * @input:
- * node :: handle to target @FT_HashNodeRec node structure
- * data :: optional argument to iteration routine
- *
- * @also: @ft_hash_foreach
- */
- typedef void (*FT_Hash_ForeachFunc)( const FT_HashNode node,
- const FT_Pointer data );
-
-
- /****************************************************************
- *
- * @function: ft_hash_foreach
- *
- * @description:
- * parse over all elements in a hash table
- *
- * @input:
- * table :: handle to target hash table structure
- * foreach_func :: iteration routine called for each element
- * foreach_data :: optional argument to the iteration routine
- *
- * @note:
- * this function is often used to release all elements from a
- * hash table. See the example given for @ft_hash_done
- */
- FT_BASE( void )
- ft_hash_foreach( FT_Hash table,
- FT_Hash_ForeachFunc foreach_func,
- const FT_Pointer foreach_data );
-
-
-
- /****************************************************************
- *
- * @function: ft_hash_done
- *
- * @description:
- * finalize a given hash table
- *
- * @input:
- * table :: handle to target hash table structure
- * node_func :: optional iteration function pointer. this
- * can be used to destroy all nodes explicitely
- * node_data :: optional argument to the node iterator
- *
- * @note:
- * this function simply frees the hash table's buckets.
- * you probably will need to call @ft_hash_foreach to
- * destroy all its elements before @ft_hash_done, as in
- * the following example:
- *
- * {
- * static void my_node_clear( const MyNode node )
- * {
- * free( node );
- * }
- *
- * static void my_done( FT_Hash table )
- * {
- * ft_hash_done( table, (FT_Hash_ForeachFunc) my_node_clear, NULL );
- * }
- * }
- */
- FT_BASE( void )
- ft_hash_done( FT_Hash table,
- FT_Hash_ForeachFunc item_func,
- const FT_Pointer item_data );
-
- /* */
-
- /* compute bucket index from hash value in a dynamic hash table */
- /* this is only used to break encapsulation to speed lookups in */
- /* the FreeType cache manager !! */
- /* */
-
-#define FT_HASH_COMPUTE_INDEX(_table,_hash,_index) \
- { \
- FT_UInt _mask = (_table)->mask; \
- FT_UInt _hash0 = (_hash); \
- \
- (_index) = (FT_UInt)( (_hash0) & _mask ) ); \
- if ( (_index) < (_table)->p ) \
- (_index) = (FT_uInt)( (_hash0) & ( 2*_mask+1 ) ); \
- }
+ FT_UInt limit;
+ FT_UInt size;
+ FT_UInt used;
+
+ FT_Hash_LookupFunc lookup;
+ FT_Hash_CompareFunc compare;
+
+ FT_Hashnode* table;
+
+ } FT_HashRec;
+
+ typedef struct FT_HashRec_ *FT_Hash;
+
+
+ FT_Error
+ ft_hash_str_init( FT_Hash hash,
+ FT_Memory memory );
+
+ FT_Error
+ ft_hash_num_init( FT_Hash hash,
+ FT_Memory memory );
+
+ void
+ ft_hash_str_free( FT_Hash hash,
+ FT_Memory memory );
+
+#define ft_hash_num_free ft_hash_str_free
+
+ FT_Error
+ ft_hash_str_insert( const char* key,
+ size_t data,
+ FT_Hash hash,
+ FT_Memory memory );
+
+ FT_Error
+ ft_hash_num_insert( FT_Int num,
+ size_t data,
+ FT_Hash hash,
+ FT_Memory memory );
+
+ size_t*
+ ft_hash_str_lookup( const char* key,
+ FT_Hash hash );
+
+ size_t*
+ ft_hash_num_lookup( FT_Int num,
+ FT_Hash hash );
FT_END_HEADER
-#endif /* __FT_HASH_H__ */
+
+#endif /* FTHASH_H_ */
+
+
+/* END */
generated by cgit v1.2.3 (git 2.46.0) at 2025-12-10 14:46:16 +0000