Main Page | Class Hierarchy | Class List | File List | Class Members | File Members

Hash_table< Key, Value, Hash_func, Compare_func > Class Template Reference

This is a basic non-growable hash table that maps keys to values. More...

#include <hash.h>

Inheritance diagram for Hash_table< Key, Value, Hash_func, Compare_func >:

Inheritance graph
[legend]
Collaboration diagram for Hash_table< Key, Value, Hash_func, Compare_func >:

Collaboration graph
[legend]
List of all members.

Public Types

typedef Hash_iterator< Key,
Value > 		Iterator

Public Member Functions

 Hash_table (bool physical=false, Size init_buckets=0, bool alloc_nodes=false)
void init (bool physical=false, Size init_buckets=0, bool alloc_nodes=false)
void clear ()
void free_and_clear ()
bool has_key (Key key)
Value * get (Key key)
void insert (Hash_node< Key, Value > &node)
bool remove (Key key)
bool grow ()
Iterator begin ()
Iterator end ()
void print ()
void unit_test ()

Public Attributes

Array< List< Hash_node< Key,
Value > > > 		buckets

Protected Member Functions

unsigned get_bucket_index (Key key)
List_iterator< Hash_node<
Key, Value > > 		find (unsigned bucket_index, Key key)

Protected Attributes

Hash_func hash_func
Compare_func compare_func
bool physical_memory
bool alloc_nodes
bool physical

Static Protected Attributes

const Size MAX_KEY_SIZE = 1024

Detailed Description

template<class Key, class Value, class Hash_func, class Compare_func>
class Hash_table< Key, Value, Hash_func, Compare_func >

This is a basic non-growable hash table that maps keys to values.

Member Typedef Documentation

template<class Key, class Value, class Hash_func, class Compare_func>
typedef Hash_iterator<Key, Value> Hash_table< Key, Value, Hash_func, Compare_func >::Iterator
 

Constructor & Destructor Documentation

template<class Key, class Value, class Hash_func, class Compare_func>
Hash_table< Key, Value, Hash_func, Compare_func >::Hash_table (  bool  physical = false,
Size  init_buckets = 0,
bool  alloc_nodes = false
)  [inline]
 

Call init() with the given arguments.

Member Function Documentation

template<class Key, class Value, class Hash_func, class Compare_func>
Hash_iterator< Key, Value > Hash_table< Key, Value, Hash_func, Compare_func >::begin (   )  [inline]
 

Return a hash iterator pointing at the first element of the hash.

template<class Key, class Value, class Hash_func, class Compare_func>
void Hash_table< Key, Value, Hash_func, Compare_func >::clear (   )  [inline]
 

Clear the hash table and free its memory.

template<class Key, class Value, class Hash_func, class Compare_func>
Hash_iterator< Key, Value > Hash_table< Key, Value, Hash_func, Compare_func >::end (   )  [inline]
 

Return a hash iterator indicating the end of the hash (after the last element).

template<class Key, class Value, class Hash_func, class Compare_func>
List_iterator< Hash_node< Key, Value > > Hash_table< Key, Value, Hash_func, Compare_func >::find (  unsigned  bucket_index,
Key  key
)  [protected]
 

Attempt to find the given key in the hash, and if it's found, return an iterator pointing at its bucket position.

template<class Key, class Value, class Hash_func, class Compare_func>
void Hash_table< Key, Value, Hash_func, Compare_func >::free_and_clear (   ) 
 

Free each node in the hash, and then clear the hash.

This function assumes that the hash nodes were initially allocated from virtual memory and that nothing else is going to free them.

template<class Key, class Value, class Hash_func, class Compare_func>
Value * Hash_table< Key, Value, Hash_func, Compare_func >::get (  Key  key  ) 
 

Return the value that corresponds to the given key.

template<class Key, class Value, class Hash_func, class Compare_func>
unsigned Hash_table< Key, Value, Hash_func, Compare_func >::get_bucket_index (  Key  key  )  [inline, protected]
 

Return the bucket index corresponding to the given key.

template<class Key, class Value, class Hash_func, class Compare_func>
bool Hash_table< Key, Value, Hash_func, Compare_func >::grow (   )  [inline]
 

template<class Key, class Value, class Hash_func, class Compare_func>
bool Hash_table< Key, Value, Hash_func, Compare_func >::has_key (  Key  key  ) 
 

Return true if the hash table contains the given key, and false otherwise.

template<class Key, class Value, class Hash_func, class Compare_func>
void Hash_table< Key, Value, Hash_func, Compare_func >::init (  bool  physical = false,
Size  init_buckets = 0,
bool  alloc_nodes = false
)  [inline]
 

Allocate memory for the hash table's buckets.

Set physical to true if the bucket data should be allocated from physical memory. Otherwise leave physical false and data will be allocated from persistent virtual memory. init_buckets is the initial number of buckets to create. The hash table is currently not growable, so choose init_buckets wisely. If alloc_nodes is true, then the hash table is responsible for managing the memory for the actual hash nodes within each bucket. This includes both allocating memory for the nodes and deallocating them upon removal.

template<class Key, class Value, class Hash_func, class Compare_func>
void Hash_table< Key, Value, Hash_func, Compare_func >::insert (  Hash_node< Key, Value > &  node  ) 
 

Insert a key/value pair into the hash table.

If the key/value pair is already present, then it will be replaced with the new value.

template<class Key, class Value, class Hash_func, class Compare_func>
void Hash_table< Key, Value, Hash_func, Compare_func >::print (   ) 
 

Print a hash table as its address and all of its key/value pairs.

template<class Key, class Value, class Hash_func, class Compare_func>
bool Hash_table< Key, Value, Hash_func, Compare_func >::remove (  Key  key  ) 
 

Remove the given key from the hash table.

Return true on success, or false if the given key could not be found.

template<class Key, class Value, class Hash_func, class Compare_func>
void Hash_table< Key, Value, Hash_func, Compare_func >::unit_test (   ) 
 

Perform some basic tests to make sure this works as it should.

Member Data Documentation

template<class Key, class Value, class Hash_func, class Compare_func>
bool Hash_table< Key, Value, Hash_func, Compare_func >::alloc_nodes [protected]
 

responsible for nodes allocs

template<class Key, class Value, class Hash_func, class Compare_func>
Array< List< Hash_node<Key, Value> > > Hash_table< Key, Value, Hash_func, Compare_func >::buckets
 

an array of Hash_node buckets

template<class Key, class Value, class Hash_func, class Compare_func>
Compare_func Hash_table< Key, Value, Hash_func, Compare_func >::compare_func [protected]
 

desired comparison function to use

template<class Key, class Value, class Hash_func, class Compare_func>
Hash_func Hash_table< Key, Value, Hash_func, Compare_func >::hash_func [protected]
 

desired hashing function to use

template<class Key, class Value, class Hash_func, class Compare_func>
const Size Hash_table< Key, Value, Hash_func, Compare_func >::MAX_KEY_SIZE = 1024 [static, protected]
 

maximum size of a data key

template<class Key, class Value, class Hash_func, class Compare_func>
bool Hash_table< Key, Value, Hash_func, Compare_func >::physical [protected]
 

template<class Key, class Value, class Hash_func, class Compare_func>
bool Hash_table< Key, Value, Hash_func, Compare_func >::physical_memory [protected]
 

physical or virtual memory used

The documentation for this class was generated from the following file:

Torsion Operating System, Copyright (C) 2000-2004 Dan Helfman