H:/Class/11756/HLab/sphinxbase-0.4/include/hash_table.h File Reference

Hash table implementation. More...

#include <sphinxbase_export.h>
#include <prim_type.h>
#include <glist.h>

Classes
struct	hash_entry_s
struct	hash_table_t
struct	hash_iter_s
Defines
#define	hash_entry_val(e) ((e)->val)
#define	hash_entry_key(e) ((e)->key)
#define	hash_entry_len(e) ((e)->len)
#define	hash_table_inuse(h) ((h)->inuse)
#define	hash_table_size(h) ((h)->size)
#define	HASH_CASE_YES 0
#define	HASH_CASE_NO 1
#define	hash_table_enter_int32(h, k, v) ((int32)(long)hash_table_enter((h),(k),(void *)(long)(v)))
#define	hash_table_replace_int32(h, k, v) ((int32)(long)hash_table_replace((h),(k),(void *)(long)(v)))
#define	hash_table_enter_bkey_int32(h, k, l, v) ((int32)(long)hash_table_enter_bkey((h),(k),(l),(void *)(long)(v)))
Typedefs
typedef struct hash_entry_s	hash_entry_t
typedef struct hash_iter_s	hash_iter_t
Functions
SPHINXBASE_EXPORT hash_table_t *	hash_table_new (int32 size, int32 casearg)
SPHINXBASE_EXPORT void	hash_table_free (hash_table_t *h)
SPHINXBASE_EXPORT void *	hash_table_enter (hash_table_t h, const char key, void *val)
SPHINXBASE_EXPORT void *	hash_table_replace (hash_table_t h, const char key, void *val)
SPHINXBASE_EXPORT void *	hash_table_delete (hash_table_t h, const char key)
SPHINXBASE_EXPORT void	hash_table_empty (hash_table_t *h)
SPHINXBASE_EXPORT void *	hash_table_enter_bkey (hash_table_t h, const char key, size_t len, void *val)
SPHINXBASE_EXPORT int32	hash_table_lookup (hash_table_t h, const char key, void **val)
SPHINXBASE_EXPORT int32	hash_table_lookup_int32 (hash_table_t h, const char key, int32 *val)
SPHINXBASE_EXPORT int32	hash_table_lookup_bkey (hash_table_t h, const char key, size_t len, void **val)
SPHINXBASE_EXPORT int32	hash_table_lookup_bkey_int32 (hash_table_t h, const char key, size_t len, int32 *val)
SPHINXBASE_EXPORT hash_iter_t *	hash_table_iter (hash_table_t *h)
SPHINXBASE_EXPORT hash_iter_t *	hash_table_iter_next (hash_iter_t *itor)
SPHINXBASE_EXPORT void	hash_table_iter_free (hash_iter_t *itor)
SPHINXBASE_EXPORT glist_t	hash_table_tolist (hash_table_t h, int32 count)
SPHINXBASE_EXPORT void	hash_table_display (hash_table_t *h, int32 showkey)

Detailed Description

Hash table implementation.

This hash tables are intended for associating a pointer/integer "value" with a char string "key", (e.g., an ID with a word string). Subsequently, one can retrieve the value by providing the string key. (The reverse functionality--obtaining the string given the value--is not provided with the hash table module.)

Define Documentation

#define HASH_CASE_NO 1

#define HASH_CASE_YES 0

#define hash_entry_key ( e ) ((e)->key)

#define hash_entry_len ( e ) ((e)->len)

#define hash_entry_val ( e ) ((e)->val)

Access macros

#define hash_table_enter_bkey_int32	(	h,
		k,
		l,
		v	)	((int32)(long)hash_table_enter_bkey((h),(k),(l),(void *)(long)(v)))

Enter a 32-bit integer value in a hash table.

This macro is the clean way to do this and avoid compiler warnings on 64-bit platforms.

#define hash_table_enter_int32	(	h,
		k,
		v	)	((int32)(long)hash_table_enter((h),(k),(void *)(long)(v)))

Add a 32-bit integer value to a hash table.

This macro is the clean way to do this and avoid compiler warnings on 64-bit platforms.

#define hash_table_inuse ( h ) ((h)->inuse)

#define hash_table_replace_int32	(	h,
		k,
		v	)	((int32)(long)hash_table_replace((h),(k),(void *)(long)(v)))

Replace a 32-bit integer value in a hash table.

This macro is the clean way to do this and avoid compiler warnings on 64-bit platforms.

#define hash_table_size ( h ) ((h)->size)

Typedef Documentation

typedef struct hash_entry_s hash_entry_t

A note by ARCHAN at 20050510: Technically what we use is so-called "hash table with buckets" which is very nice way to deal with external hashing. There are definitely better ways to do internal hashing (i.e. when everything is stored in the memory.) In Sphinx 3, this is a reasonable practice because hash table is only used in lookup in initialization or in lookups which is not critical for speed. Another note by ARCHAN at 20050703: To use this data structure properly, it is very important to realize that the users are required to handle memory allocation of the C-style keys. The hash table will not make a copy of the memory allocated for any of the C-style key. It will not allocate memory for it. It will not delete memory for it. As a result, the following code sniplet will cause memory leak.

while (1){ str=(char*)ckd_calloc(str_length,sizeof(char*)) if(hash_enter(ht,str,id)!=id){ printf("fail to add key str %s with val id %d\n",str,id)} } A note by dhuggins on 20061010: Changed this to use void * instead of int32 as the value type, so that arbitrary objects can be inserted into a hash table (in a way that won't crash on 64-bit machines ;) The hash table structures. Each hash table is identified by a hash_table_t structure. hash_table_t.table is pre-allocated for a user-controlled max size, and is initially empty. As new entries are created (using hash_enter()), the empty entries get filled. If multiple keys hash to the same entry, new entries are allocated and linked together in a linear list.

typedef struct hash_iter_s hash_iter_t

Function Documentation

SPHINXBASE_EXPORT void* hash_table_delete	(	hash_table_t *	h,
		const char *	key
	)

Delete an entry with given key and associated value to hash table h. Return the value associated with the key (NULL if it did not exist)

Parameters:

	h	In: Handle of hash table in which a key will be deleted
	key	In: C-style NULL-terminated key string for the new entry

SPHINXBASE_EXPORT void hash_table_display	(	hash_table_t *	h,
		int32	showkey
	)

Display a hash-with-chaining representation on the screen. Currently, it will only works for situation where hash_enter was used to enter the keys.

Parameters:

	h	In: Hash table to display
	showkey	In: Show the string or not, Use 0 if hash_enter_bkey was used.

SPHINXBASE_EXPORT void hash_table_empty ( hash_table_t * h )

Delete all entries from a hash_table.

Parameters:

h

In: Handle of hash table

SPHINXBASE_EXPORT void* hash_table_enter	(	hash_table_t *	h,
		const char *	key,
		void *	val
	)

Try to add a new entry with given key and associated value to hash table h. If key doesn't already exist in hash table, the addition is successful, and the return value is val. But if key already exists, return its existing associated value. (The hash table is unchanged; it is up to the caller to resolve the conflict.)

Parameters:

	h	In: Handle of hash table in which to create entry
	key	In: C-style NULL-terminated key string for the new entry
	val	In: Value to be associated with above key

SPHINXBASE_EXPORT void* hash_table_enter_bkey	(	hash_table_t *	h,
		const char *	key,
		size_t	len,
		void *	val
	)

Like hash_table_enter, but with an explicitly specified key length, instead of a NULL-terminated, C-style key string. So the key string is a binary key (or bkey). Hash tables containing such keys should be created with the HASH_CASE_YES option. Otherwise, the results are unpredictable.

Parameters:

	h	In: Handle of hash table in which to create entry
	key	In: Key buffer
	len	In: Length of above key buffer
	val	In: Value to be associated with above key

SPHINXBASE_EXPORT void hash_table_free ( hash_table_t * h )

Free the specified hash table; the caller is responsible for freeing the key strings pointed to by the table entries.

Parameters:

h

In: Handle of hash table to free

SPHINXBASE_EXPORT hash_iter_t* hash_table_iter ( hash_table_t * h )

Start iterating over key-value pairs in a hash table.

SPHINXBASE_EXPORT void hash_table_iter_free ( hash_iter_t * itor )

Delete an unfinished iterator.

SPHINXBASE_EXPORT hash_iter_t* hash_table_iter_next ( hash_iter_t * itor )

Get the next key-value pair in iteration.

This function automatically frees the iterator object upon reaching the final entry.

Returns:: the next entry in the hash table, or NULL if done.

SPHINXBASE_EXPORT int32 hash_table_lookup	(	hash_table_t *	h,
		const char *	key,
		void **	val
	)

Look up a key in a hash table and optionally return the associated value.

Returns:: 0 if key found in hash table, else -1.

Parameters:

	h	In: Handle of hash table being searched
	key	In: C-style NULL-terminated string whose value is sought
	val	Out: *val = value associated with key. If this is NULL, no value will be returned.

SPHINXBASE_EXPORT int32 hash_table_lookup_bkey	(	hash_table_t *	h,
		const char *	key,
		size_t	len,
		void **	val
	)

Like hash_lookup, but with an explicitly specified key length, instead of a NULL-terminated, C-style key string. So the key string is a binary key (or bkey). Hash tables containing such keys should be created with the HASH_CASE_YES option. Otherwise, the results are unpredictable.

Parameters:

	h	In: Handle of hash table being searched
	key	In: Key buffer
	len	In: Length of above key buffer
	val	Out: *val = value associated with key. If this is NULL, no value will be returned.

SPHINXBASE_EXPORT int32 hash_table_lookup_bkey_int32	(	hash_table_t *	h,
		const char *	key,
		size_t	len,
		int32 *	val
	)

Look up a 32-bit integer value in a hash table.

This function is the clean way to do this and avoid compiler warnings on 64-bit platforms.

Parameters:

	h	In: Handle of hash table being searched
	key	In: Key buffer
	len	In: Length of above key buffer
	val	Out: *val = value associated with key. If this is NULL, no value will be returned.

SPHINXBASE_EXPORT int32 hash_table_lookup_int32	(	hash_table_t *	h,
		const char *	key,
		int32 *	val
	)

Look up a 32-bit integer value in a hash table.

This function is the clean way to do this and avoid compiler warnings on 64-bit platforms.

Parameters:

	h	In: Handle of hash table being searched
	key	In: C-style NULL-terminated string whose value is sought
	val	Out: *val = value associated with key. If this is NULL, no value will be returned.

SPHINXBASE_EXPORT hash_table_t* hash_table_new	(	int32	size,
		int32	casearg
	)

Allocate a new hash table for a given expected size.

Note:: Case sensitivity of hash keys applies to 7-bit ASCII characters only, and is not locale-dependent.

Returns:: handle to allocated hash table.

Parameters:

	size	In: Expected number of entries in the table
	casearg	In: Whether case insensitive for key comparisons. When 1, case is insentitive, 0, case is sensitive.

SPHINXBASE_EXPORT void* hash_table_replace	(	hash_table_t *	h,
		const char *	key,
		void *	val
	)

Add a new entry with given key and value to hash table h. If the key already exists, its value is replaced with the given value, and the previous value is returned, otherwise val is returned.

A very important but subtle point: The key pointer in the hash table is replaced with the pointer passed to this function. In general you should always pass a pointer to hash_table_enter() whose lifetime matches or exceeds that of the hash table. In some rare cases it is convenient to initially enter a value with a short-lived key, then later replace that with a long-lived one. This behaviour allows this to happen.

Parameters:

	h	In: Handle of hash table in which to create entry
	key	In: C-style NULL-terminated key string for the new entry
	val	In: Value to be associated with above key

SPHINXBASE_EXPORT glist_t hash_table_tolist	(	hash_table_t *	h,
		int32 *	count
	)

Build a glist of valid hash_entry_t pointers from the given hash table. Return the list.

Parameters:

	h	In: Hash table from which list is to be generated
	count	Out: Number of entries in the list. If this is NULL, no count will be returned.

H:/Class/11756/HLab/sphinxbase-0.4/include/hash_table.h File Reference

Classes

Defines

Typedefs

Functions

Detailed Description

Define Documentation

Typedef Documentation

Function Documentation