Hash Tables

Various implementations of hash table functions.

Hash tables are common data structures that allow for fast random access to the data that is stored within.

Here, we provide an abstract implementation of a hash table interface and a concrete implementation for pairs of secondary structure and corresponding free energy value.

Abstract interface

typedef struct vrna_hash_table_s *vrna_hash_table_t
#include <ViennaRNA/datastructures/hash_tables.h>

A hash table object.

See also

vrna_ht_init(), vrna_ht_free()

typedef int (*vrna_ht_cmp_f)(void *x, void *y)
#include <ViennaRNA/datastructures/hash_tables.h>

Callback function to compare two hash table entries.

See also

vrna_ht_init(), vrna_ht_db_comp()

Param x:

A hash table entry

Param y:

A hash table entry

Return:

-1 if x is smaller, +1 if x is larger than y. 0 if \(x == y \)

int() vrna_callback_ht_compare_entries (void *x, void *y)
#include <ViennaRNA/datastructures/hash_tables.h>
typedef unsigned int (*vrna_ht_hashfunc_f)(void *x, unsigned long hashtable_size)
#include <ViennaRNA/datastructures/hash_tables.h>

Callback function to generate a hash key, i.e. hash function.

See also

vrna_ht_init(), vrna_ht_db_hash_func()

Param x:

A hash table entry

Param hashtable_size:

The size of the hash table

Return:

The hash table key for entry x

unsigned int() vrna_callback_ht_hash_function (void *x, unsigned long hashtable_size)
#include <ViennaRNA/datastructures/hash_tables.h>
typedef int (*vrna_ht_free_f)(void *x)
#include <ViennaRNA/datastructures/hash_tables.h>

Callback function to free a hash table entry.

See also

vrna_ht_init(), vrna_ht_db_free_entry()

Param x:

A hash table entry

Return:

0 on success

int() vrna_callback_ht_free_entry (void *x)
#include <ViennaRNA/datastructures/hash_tables.h>
vrna_hash_table_t vrna_ht_init(unsigned int b, vrna_ht_cmp_f compare_function, vrna_ht_hashfunc_f hash_function, vrna_ht_free_f free_hash_entry)
#include <ViennaRNA/datastructures/hash_tables.h>

Get an initialized hash table.

This function returns a ready-to-use hash table with pre-allocated memory for a particular number of entries.

Note

If all function pointers are NULL, this function initializes the hash table with default functions, i.e.

arguments.

Warning

If hash_bits is larger than 27 you have to compile it with the flag gcc -mcmodel=large.

Parameters:

  • b – Number of bits for the hash table. This determines the size ( \(2^b -1\)).

  • compare_function – A function pointer to compare any two entries in the hash table (may be NULL)

  • hash_function – A function pointer to retrieve the hash value of any entry (may be NULL)

  • free_hash_entry – A function pointer to free the memory occupied by any entry (may be NULL)

Returns:

An initialized, empty hash table, or NULL on any error

unsigned long vrna_ht_size(vrna_hash_table_t ht)
#include <ViennaRNA/datastructures/hash_tables.h>

Get the size of the hash table.

Parameters:

  • ht – The hash table

Returns:

The size of the hash table, i.e. the maximum number of entries

unsigned long vrna_ht_collisions(struct vrna_hash_table_s *ht)
#include <ViennaRNA/datastructures/hash_tables.h>

Get the number of collisions in the hash table.

Parameters:

  • ht – The hash table

Returns:

The number of collisions in the hash table

void *vrna_ht_get(vrna_hash_table_t ht, void *x)
#include <ViennaRNA/datastructures/hash_tables.h>

Get an element from the hash table.

This function takes an object x and performs a look-up whether the object is stored within the hash table ht. If the object is already stored in ht, the function simply returns the entry, otherwise it returns NULL.

See also

vrna_ht_insert(), vrna_hash_delete(), vrna_ht_init()

Parameters:

  • ht – The hash table

  • x – The hash entry to look-up

Returns:

The entry x if it is stored in ht, NULL otherwise

int vrna_ht_insert(vrna_hash_table_t ht, void *x)
#include <ViennaRNA/datastructures/hash_tables.h>

Insert an object into a hash table.

Writes the pointer to your hash entry into the table.

See also

vrna_ht_init(), vrna_hash_delete(), vrna_ht_clear()

Warning

In case of collisions, this function simply increments the hash key until a free entry in the hash table is found.

Parameters:

  • ht – The hash table

  • x – The hash entry

Returns:

0 on success, 1 if the value is already in the hash table, -1 on error.

void vrna_ht_remove(vrna_hash_table_t ht, void *x)
#include <ViennaRNA/datastructures/hash_tables.h>

Remove an object from the hash table.

Deletes the pointer to your hash entry from the table.

Note

This function doesn’t free any memory occupied by the hash entry.

Parameters:

  • ht – The hash table

  • x – The hash entry

void vrna_ht_clear(vrna_hash_table_t ht)
#include <ViennaRNA/datastructures/hash_tables.h>

Clear the hash table.

This function removes all entries from the hash table and automatically free’s the memory occupied by each entry using the bound vrna_ht_free_f() function.

See also

vrna_ht_free(), vrna_ht_init()

Parameters:

  • ht – The hash table

void vrna_ht_free(vrna_hash_table_t ht)
#include <ViennaRNA/datastructures/hash_tables.h>

Free all memory occupied by the hash table.

This function removes all entries from the hash table by calling the vrna_ht_free_f() function for each entry. Finally, the memory occupied by the hash table itself is free’d as well.

Parameters:

  • ht – The hash table

Dot-Bracket / Free Energy entries

int vrna_ht_db_comp(void *x, void *y)
#include <ViennaRNA/datastructures/hash_tables.h>

Default hash table entry comparison.

This is the default comparison function for hash table entries. It assumes the both entries x and y are of type vrna_ht_entry_db_t and compares the structure attribute of both entries

See also

vrna_ht_entry_db_t, vrna_ht_init(), vrna_ht_db_hash_func(), vrna_ht_db_free_entry()

Parameters:
Returns:

-1 if x is smaller, +1 if x is larger than y. 0 if both are equal.

unsigned int vrna_ht_db_hash_func(void *x, unsigned long hashtable_size)
#include <ViennaRNA/datastructures/hash_tables.h>

Default hash function.

This is the default hash function for hash table insertion/lookup. It assumes that entries are of type vrna_ht_entry_db_t and uses the Bob Jenkins 1996 mix function to create a hash key from the structure attribute of the hash entry.

See also

vrna_ht_entry_db_t, vrna_ht_init(), vrna_ht_db_comp(), vrna_ht_db_free_entry()

Parameters:

  • x – A hash table entry to compute the key for

  • hashtable_size – The size of the hash table

Returns:

The hash key for entry x

int vrna_ht_db_free_entry(void *hash_entry)
#include <ViennaRNA/datastructures/hash_tables.h>

Default function to free memory occupied by a hash entry.

This function assumes that hash entries are of type vrna_ht_entry_db_t and free’s the memory occupied by that entry.

See also

vrna_ht_entry_db_t, vrna_ht_init(), vrna_ht_db_comp(), vrna_ht_db_hash_func()

Parameters:

  • hash_entry – The hash entry to remove from memory

Returns:

0 on success

struct vrna_ht_entry_db_t
#include <ViennaRNA/datastructures/hash_tables.h>

Default hash table entry.

See also

vrna_ht_init(), vrna_ht_db_comp(), vrna_ht_db_hash_func(), vrna_ht_db_free_entry()

Public Members

char *structure

A secondary structure in dot-bracket notation

float energy

The free energy of structure