Various implementations of hash table functions. More...

Detailed Description

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.

Collaboration diagram for Hash Tables:

Files
file	hash_tables.h
	Implementations of hash table functions.

Data Structures
struct	vrna_ht_entry_db_t
	Default hash table entry. More...

Abstract interface
typedef struct vrna_hash_table_s *	vrna_hash_table_t
	A hash table object. More...

typedef int(	vrna_callback_ht_compare_entries) (void x, void y)
	Callback function to compare two hash table entries. More...

typedef unsigned int(	vrna_callback_ht_hash_function) (void *x, unsigned long hashtable_size)
	Callback function to generate a hash key, i.e. hash function. More...

typedef int(	vrna_callback_ht_free_entry) (void *x)
	Callback function to free a hash table entry. More...

vrna_hash_table_t	vrna_ht_init (unsigned int b, vrna_callback_ht_compare_entries compare_function, vrna_callback_ht_hash_function hash_function, vrna_callback_ht_free_entry *free_hash_entry)
	Get an initialized hash table. More...

unsigned long	vrna_ht_size (vrna_hash_table_t ht)
	Get the size of the hash table. More...

unsigned long	vrna_ht_collisions (struct vrna_hash_table_s *ht)
	Get the number of collisions in the hash table. More...

void *	vrna_ht_get (vrna_hash_table_t ht, void *x)
	Get an element from the hash table. More...

int	vrna_ht_insert (vrna_hash_table_t ht, void *x)
	Insert an object into a hash table. More...

void	vrna_ht_remove (vrna_hash_table_t ht, void *x)
	Remove an object from the hash table. More...

void	vrna_ht_clear (vrna_hash_table_t ht)
	Clear the hash table. More...

void	vrna_ht_free (vrna_hash_table_t ht)
	Free all memory occupied by the hash table. More...

Dot-Bracket / Free Energy entries
int	vrna_ht_db_comp (void x, void y)
	Default hash table entry comparison. More...

unsigned int	vrna_ht_db_hash_func (void *x, unsigned long hashtable_size)
	Default hash function. More...

int	vrna_ht_db_free_entry (void *hash_entry)
	Default function to free memory occupied by a hash entry. More...

Data Structure Documentation

struct vrna_ht_entry_db_t

Default hash table entry.

See also: vrna_ht_init(), vrna_ht_db_comp(), vrna_ht_db_hash_func(), vrna_ht_db_free_entry()

Data Fields
char *	structure

float	energy

Field Documentation

char* vrna_ht_entry_db_t::structure

A secondary structure in dot-bracket notation

float vrna_ht_entry_db_t::energy

The free energy of structure

Typedef Documentation

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_callback_ht_compare_entries) (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()

Parameters

x	A hash table entry
y	A hash table entry

Returns: -1 if x is smaller, +1 if x is larger than y. 0 if

typedef unsigned int( vrna_callback_ht_hash_function) (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()

Parameters

x	A hash table entry
hashtable_size	The size of the hash table

Returns: The hash table key for entry x

typedef int( vrna_callback_ht_free_entry) (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()

Parameters

x	A hash table entry

Returns: 0 on success

Function Documentation

vrna_hash_table_t vrna_ht_init	(	unsigned int	b,
		vrna_callback_ht_compare_entries *	compare_function,
		vrna_callback_ht_hash_function *	hash_function,
		vrna_callback_ht_free_entry *	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.

vrna_ht_db_comp() for the compare_function,
vrna_ht_db_hash_func() for the hash_function, and
vrna_ht_db_free_entry() for the free_hash_entry

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

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

See also: vrna_ht_init(), vrna_hash_delete(), vrna_ht_clear()

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 () 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_callback_ht_free_entry() function for each entry. Finally, the memory occupied by the hash table itself is free'd as well.

Parameters

ht	The hash table

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

x	A hash table entry of type vrna_ht_entry_db_t
y	A hash table entry of type vrna_ht_entry_db_t

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

Detailed Description

Files

Data Structures

Abstract interface

Dot-Bracket / Free Energy entries

Data Structure Documentation

Data Fields

Field Documentation

Typedef Documentation

Function Documentation