hash_table.h File Reference

Hash table implementation. More...

`#include <sphinxbase/sphinxbase_export.h>`
`#include <sphinxbase/prim_type.h>`
`#include <sphinxbase/glist.h>`

Go to the source code of this file.

## Data Structures

struct | hash_entry_s
| 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. More...
struct | hash_table_s
struct | hash_iter_s

## Macros

#define | hash_entry_val(e)
| Access macros.
#define | hash_entry_key(e)
#define | hash_entry_len(e)
#define | hash_table_inuse(h)
#define | hash_table_size(h)
#define | HASH_CASE_YES 0
#define | HASH_CASE_NO 1
#define | hash_table_enter_int32(h, k, v)
| Add a 32-bit integer value to a hash table.
#define | hash_table_replace_int32(h, k, v)
| Replace a 32-bit integer value in a hash table.
#define | hash_table_enter_bkey_int32(h, k, l, v)
| Enter a 32-bit integer value in a hash table.
#define | hash_table_replace_bkey_int32(h, k, l, v)
| Replace a 32-bit integer value in a hash table.

## Typedefs

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.
typedef struct hash_table_s | hash_table_t
typedef struct hash_iter_s | hash_iter_t

## Functions

SPHINXBASE_EXPORT hash_table_t * | hash_table_new (int32 size, int32 casearg)
| Allocate a new hash table for a given expected size.
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.
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.
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.
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.
SPHINXBASE_EXPORT void * | hash_table_delete_bkey (hash_table_t *h, const char *key, size_t len)
| Like hash_table_delete, but with an explicitly specified key length, instead of a NULL-terminated, C-style key string.
SPHINXBASE_EXPORT void | hash_table_empty (hash_table_t *h)
| Delete all entries from a hash_table.
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.
SPHINXBASE_EXPORT void * | hash_table_replace_bkey (hash_table_t *h, const char *key, size_t len, void *val)
| Like hash_table_replace, but with an explicitly specified key length, instead of a NULL-terminated, C-style key string.
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.
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.
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.
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.
SPHINXBASE_EXPORT hash_iter_t * | hash_table_iter (hash_table_t *h)
| Start iterating over key-value pairs in a hash table.
SPHINXBASE_EXPORT hash_iter_t * | hash_table_iter_next (hash_iter_t *itor)
| Get the next key-value pair in iteration.
SPHINXBASE_EXPORT void | hash_table_iter_free (hash_iter_t *itor)
| Delete an unfinished iterator.
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.
SPHINXBASE_EXPORT void | hash_table_display (hash_table_t *h, int32 showkey)
| Display a hash-with-chaining representation on the screen.

## 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.)

Definition in file hash_table.h.

## Macro Definition Documentation

## HASH_CASE_NO

#define HASH_CASE_NO 1

Definition at line 198 of file hash_table.h.

## HASH_CASE_YES

#define HASH_CASE_YES 0

Definition at line 197 of file hash_table.h.

## hash_entry_key

#define hash_entry_key | ( |  | e | ) |

Value:
((e)->key)

Definition at line 176 of file hash_table.h.

## hash_entry_len

#define hash_entry_len | ( |  | e | ) |

Value:
((e)->len)

Definition at line 177 of file hash_table.h.

## hash_entry_val

#define hash_entry_val | ( |  | e | ) |

Value:
((e)->val)

Access macros.

Definition at line 175 of file hash_table.h.

## hash_table_enter_bkey_int32

#define hash_table_enter_bkey_int32 | ( |  | h,
|  |  | k,
|  |  | l,
|  |  | v )

Value:
((int32)(long)hash_table_enter_bkey((h),(k),(l),(void *)(long)(v)))
hash_table_enter_bkey
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,...
Definition hash_table.c:535

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.

Definition at line 315 of file hash_table.h.

## hash_table_enter_int32

#define hash_table_enter_int32 | ( |  | h,
|  |  | k,
|  |  | v )

Value:
((int32)(long)hash_table_enter((h),(k),(void *)(long)(v)))
hash_table_enter
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.
Definition hash_table.c:501

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.

Definition at line 228 of file hash_table.h.

Referenced by ngram_model_casefold(), and ngram_model_set_map_words().

## hash_table_inuse

#define hash_table_inuse | ( |  | h | ) |

Value:
((h)->inuse)

Definition at line 178 of file hash_table.h.

## hash_table_replace_bkey_int32

#define hash_table_replace_bkey_int32 | ( |  | h,
|  |  | k,
|  |  | l,
|  |  | v )

Value:
((int32)(long)hash_table_replace_bkey((h),(k),(l),(void *)(long)(v)))
hash_table_replace_bkey
SPHINXBASE_EXPORT void * hash_table_replace_bkey(hash_table_t *h, const char *key, size_t len, void *val)
Like hash_table_replace, but with an explicitly specified key length, instead of a NULL-terminated,...
Definition hash_table.c:548

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.

Definition at line 338 of file hash_table.h.

## hash_table_replace_int32

#define hash_table_replace_int32 | ( |  | h,
|  |  | k,
|  |  | v )

Value:
((int32)(long)hash_table_replace((h),(k),(void *)(long)(v)))
hash_table_replace
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.
Definition hash_table.c:512

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.

Definition at line 257 of file hash_table.h.

## hash_table_size

#define hash_table_size | ( |  | h | ) |

Value:
((h)->size)

Definition at line 179 of file hash_table.h.

## Typedef Documentation

## hash_entry_t

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.

## Function Documentation

## hash_table_delete()

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

Definition at line 523 of file hash_table.c.

References hash_table_delete().

Referenced by hash_table_delete().

## hash_table_delete_bkey()

SPHINXBASE_EXPORT void * hash_table_delete_bkey | ( | hash_table_t * | h,
|  | const char * | key,
|  | size_t | len )

Like hash_table_delete, 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 a key will be deleted
  key | In: C-style NULL-terminated key string for the new entry

Definition at line 561 of file hash_table.c.

References ckd_free(), and hash_table_delete_bkey().

Referenced by hash_table_delete_bkey().

## hash_table_display()

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.

Definition at line 574 of file hash_table.c.

References hash_table_display(), hash_entry_s::len, hash_entry_s::next, hash_table_s::size, and hash_entry_s::val.

Referenced by hash_table_display().

## hash_table_empty()

SPHINXBASE_EXPORT void hash_table_empty | ( | hash_table_t * | h | ) |

Delete all entries from a hash_table.

Parameters

  h | In: Handle of hash table

Definition at line 483 of file hash_table.c.

References ckd_free(), hash_table_empty(), hash_table_s::inuse, hash_entry_s::next, and hash_table_s::size.

Referenced by hash_table_empty(), and ngram_model_set_map_words().

## hash_table_enter()

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

Definition at line 501 of file hash_table.c.

References hash_table_enter().

Referenced by cmd_ln_parse_r(), cmd_ln_set_str_extra_r(), and hash_table_enter().

## hash_table_enter_bkey()

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

Definition at line 535 of file hash_table.c.

References ckd_free(), and hash_table_enter_bkey().

Referenced by hash_table_enter_bkey().

## hash_table_free()

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

Definition at line 688 of file hash_table.c.

References ckd_free(), hash_table_free(), hash_entry_s::next, and hash_table_s::size.

Referenced by cmd_ln_free_r(), cmd_ln_parse_r(), hash_table_free(), jsgf_grammar_free(), ngram_model_casefold(), ngram_model_free(), ngram_model_read_classdef(), and ngram_model_set_read().

## hash_table_iter()

SPHINXBASE_EXPORT hash_iter_t * hash_table_iter | ( | hash_table_t * | h | ) |

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

Definition at line 646 of file hash_table.c.

References ckd_calloc, hash_table_iter(), hash_table_iter_next(), and hash_iter_s::ht.

Referenced by hash_table_iter(), jsgf_grammar_free(), and jsgf_rule_iter().

## hash_table_iter_free()

SPHINXBASE_EXPORT void hash_table_iter_free | ( | hash_iter_t * | itor | ) |

Delete an unfinished iterator.

Definition at line 682 of file hash_table.c.

References ckd_free(), and hash_table_iter_free().

Referenced by hash_table_iter_free(), and hash_table_iter_next().

## hash_table_iter_next()

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.

Definition at line 656 of file hash_table.c.

References hash_iter_s::ent, hash_table_iter_free(), hash_table_iter_next(), hash_iter_s::ht, hash_iter_s::idx, hash_entry_s::next, and hash_table_s::size.

Referenced by hash_table_iter(), hash_table_iter_next(), and jsgf_grammar_free().

## hash_table_lookup()

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.

Definition at line 302 of file hash_table.c.

References hash_table_lookup(), and hash_entry_s::val.

Referenced by cmd_ln_access_r(), cmd_ln_exists_r(), cmd_ln_parse_r(), cmd_ln_set_str_extra_r(), hash_table_lookup(), hash_table_lookup_int32(), jsgf_get_rule(), and ngram_model_set_read().

## hash_table_lookup_bkey()

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.

Definition at line 337 of file hash_table.c.

References ckd_free(), hash_table_lookup_bkey(), and hash_entry_s::val.

Referenced by hash_table_lookup_bkey(), and hash_table_lookup_bkey_int32().

## hash_table_lookup_bkey_int32()

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.

Definition at line 358 of file hash_table.c.

References hash_table_lookup_bkey(), and hash_table_lookup_bkey_int32().

Referenced by hash_table_lookup_bkey_int32().

## hash_table_lookup_int32()

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.

Definition at line 322 of file hash_table.c.

References hash_table_lookup(), and hash_table_lookup_int32().

Referenced by hash_table_lookup_int32(), ngram_unknown_wid(), and ngram_wid().

## hash_table_new()

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.

Definition at line 158 of file hash_table.c.

References ckd_calloc, hash_table_new(), hash_table_s::nocase, and hash_table_s::size.

Referenced by cmd_ln_parse_r(), hash_table_new(), jsgf_grammar_new(), ngram_model_casefold(), ngram_model_read_classdef(), and ngram_model_set_read().

## hash_table_replace()

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

Definition at line 512 of file hash_table.c.

References hash_table_replace().

Referenced by cmd_ln_parse_r(), and hash_table_replace().

## hash_table_replace_bkey()

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

Like hash_table_replace, 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

Definition at line 548 of file hash_table.c.

References ckd_free(), and hash_table_replace_bkey().

Referenced by hash_table_replace_bkey().

## hash_table_tolist()

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.

Definition at line 616 of file hash_table.c.

References glist_add_ptr(), hash_table_tolist(), and hash_table_s::size.

Referenced by cmd_ln_free_r(), hash_table_tolist(), ngram_model_read_classdef(), and ngram_model_set_read().