A hash map usable by ATS core. More...

#include <Map.h>

Collaboration diagram for TSHashTable< H >:

Data Structures
struct	Bucket
	Hash bucket. More...
struct	iterator
	Standard iterator for walking the table. More...
struct	Location
	Information about locating a value in the hash table. More...
Public Types
enum	ExpansionPolicy { MANUAL, AVERAGE, MAXIMUM }
	When the hash table is expanded. More...
typedef TSHashTable	self
	Self reference type.
typedef H	Hasher
	Rename and promote.
typedef Hasher::ID	ID
	ID type.
typedef Hasher::Key	Key
	Key type.
typedef Hasher::Value	Value
	Stored value (element) type.
typedef Hasher::ListHead	ListHead
	Anchor for chain.
Public Member Functions
iterator	begin ()
	First element.
iterator	end ()
	Past last element.
	TSHashTable (size_t nb=DEFAULT_BUCKET_COUNT)
	Constructor (also default).
void	insert (Value *value)
	Insert a value in to the table.
Location	find (Key key)
	Find a value that matches key.
Location	find (Value *value)
	Get a `Location` for value.
bool	remove (Location const &location)
	Remove the value at location from the table.
bool	remove (Key key)
	Remove all values with key.
void	clear ()
	Remove all values from the table.
size_t	count () const
	Get the number of elements in the table.
size_t	bucketCount () const
	Get the number of buckets in the table.
void	setExpansionPolicy (ExpansionPolicy p)
	Enable or disable expanding the table when chains are long.
void	expansionPolicy () const
	Get the current expansion policy.
void	setExpansionLimit (size_t n)
	Set the limit value for the expansion policy.
size_t	expansionLimit () const
	Set the limit value for the expansion policy.
void	expand ()
	Expand the hash.
Static Public Attributes
static size_t const	DEFAULT_BUCKET_COUNT = 7
	The default starting number of buckets.
static size_t const	DEFAULT_EXPANSION_LIMIT = 4
	The default expansion policy limit.
Protected Types
typedef Vec< Bucket, DefaultAlloc, 0 >	Array
	Bucket array.
typedef DLL< Bucket, typename Bucket::Link_m_link >	BucketChain
	Make available to nested classes statically.
Protected Member Functions
void	findBucket (Key key, Location &location)
	Get the ID and bucket for key.
Protected Attributes
size_t	m_count
	# of elements stored in the table.
ExpansionPolicy	m_expansion_policy
	When to exand the table.
size_t	m_expansion_limit
	Limit value for expansion.
Array	m_array
	Bucket storage.
BucketChain	m_bucket_chain
	List of non-empty buckets.

Detailed Description

template<typename H>
class TSHashTable< H >

A hash map usable by ATS core.

This class depends on the DLL class from List.h. It assumes it can uses instances of that class to store chains of elements.

Values stored in this container are not destroyed when the container is destroyed. These must be released by the client.

Duplicate keys are allowed. Clients must walk the list for multiple entries.

See also:: Location::operator++()

By default the table automatically expands to limit the average chain length. This can be tuned. If set to MANUAL then the table will expand only when explicitly requested to do so by the client.

See also:: ExpansionPolicy; setExpansionPolicy(); setExpansionLimit(); expand()

All the parameters for the hash map are passed via the template argument H. This is a struct that contains both type definitions and static methods. It must have

No state (cheap and risk free to copy).

All required methods are static methods.

ID is a typedef for the hash type. This is the type of the value produced by the hash function. It must be a numeric type.

Key is a typedef for the key type. This is passed to the hash function and used for equality checking of elements. It is presumed cheap to copy. If the underlying key is not a simple type then Key should be declared as a constant pointer or a constant reference. The hash table will never attempt to modify a key.

Value is a typedef for the value type, the type of the element stored in the hash table.

ListHead is typedef for the DLL compatible class that can serve as the anchor for a chain of Value instances. This is use both as data to be stored in a bucket and for access to next and previous pointers from instances of Value.

Method hash converts a Key to a hash value. The key argument can be by value or by constant reference.

    ID hash(Key key);

Method key extracts the key from a Value instance.

    Key key(Value const*);

Method equal checks for equality between a Key and a Value. The key argument can be a constant reference or by value. The arguments should be const if not by value.

    bool equal (Key lhs, Key rhs);
    bool equal (Key key, Value const* value);

Example for HttpServerSession keyed by the origin server IP address.

    struct Hasher {
      typedef uint32_t ID;
      typedef sockaddr const* Key;
      typedef HttpServerSession Value;
      typedef DList(HttpServerSession, ip_hash_link) ListHead;

      static uint32_t hash(sockaddr const* key) { return ats_ip_hash(key); }
      static sockaddr const* key(HttpServerSession const* value) { return &value->ip.sa }
      static bool equal(sockaddr const* lhs, sockaddr const* rhs) { return ats_ip_eq(lhs, rhs); }
      // Alternatively
      // static ID hash(Key* key);
      // static Key key(Value* value);
      // static bool equal(Key lhs, Key rhs);

In HttpServerSession is the definition

    LINK(HttpServerSession, ip_hash_link);

which creates the internal links used by TSHashTable.

Definition at line 1030 of file Map.h.

Member Typedef Documentation

template<typename H>

typedef Vec<Bucket, DefaultAlloc, 0> TSHashTable< H >::Array [protected]

Bucket array.

Definition at line 1233 of file Map.h.

template<typename H>

typedef DLL<Bucket, typename Bucket::Link_m_link> TSHashTable< H >::BucketChain [protected]

Make available to nested classes statically.

Definition at line 1244 of file Map.h.

template<typename H>

typedef H TSHashTable< H >::Hasher

Rename and promote.

Definition at line 1035 of file Map.h.

template<typename H>

typedef Hasher::ID TSHashTable< H >::ID

ID type.

Definition at line 1036 of file Map.h.

template<typename H>

typedef Hasher::Key TSHashTable< H >::Key

Key type.

Definition at line 1037 of file Map.h.

template<typename H>

typedef Hasher::ListHead TSHashTable< H >::ListHead

Anchor for chain.

Definition at line 1039 of file Map.h.

template<typename H>

typedef TSHashTable TSHashTable< H >::self

Self reference type.

Definition at line 1032 of file Map.h.

template<typename H>

typedef Hasher::Value TSHashTable< H >::Value

Stored value (element) type.

Definition at line 1038 of file Map.h.

Member Enumeration Documentation

template<typename H>

enum TSHashTable::ExpansionPolicy

When the hash table is expanded.

Enumerator:

MANUAL	Client must explicitly expand the table.
AVERAGE	Table expands if average chain length exceeds limit. [default].
MAXIMUM	Table expands if any chain length exceeds limit.

Definition at line 1042 of file Map.h.

Constructor & Destructor Documentation

template<typename H >

TSHashTable< H >::TSHashTable ( size_t nb = DEFAULT_BUCKET_COUNT )

Constructor (also default).

Constructs an empty table with at least nb buckets.

Definition at line 1282 of file Map.h.

References Vec< C, A, S >::i, TSHashTable< H >::m_array, Vec< C, A, S >::n, prime2, and Vec< C, A, S >::set_expand().

Member Function Documentation

template<typename H >

TSHashTable< H >::iterator TSHashTable< H >::begin ( )

First element.

Definition at line 1255 of file Map.h.

References TSHashTable< H >::end(), DLL< C, L >::head, TSHashTable< H >::m_bucket_chain, and TSHashTable< H >::Bucket::m_chain.

Referenced by ServerSessionPool::purge().

template<typename H>

size_t TSHashTable< H >::bucketCount ( ) const [inline]

Get the number of buckets in the table.

Definition at line 1215 of file Map.h.

template<typename H >

void TSHashTable< H >::clear ( void )

Remove all values from the table.

The values are not cleaned up. The values are not touched in this method, therefore it is safe to destroy them first and then clear this table.

Definition at line 1385 of file Map.h.

References DLL< C, L >::clear(), TSHashTable< H >::m_array, TSHashTable< H >::m_bucket_chain, TSHashTable< H >::m_count, and Vec< C, A, S >::n.

Referenced by ServerSessionPool::purge().

template<typename H>

size_t TSHashTable< H >::count ( ) const [inline]

Get the number of elements in the table.

Definition at line 1212 of file Map.h.

template<typename H >

TSHashTable< H >::iterator TSHashTable< H >::end ( )

Past last element.

Definition at line 1265 of file Map.h.

Referenced by TSHashTable< H >::begin(), and ServerSessionPool::purge().

template<typename H >

void TSHashTable< H >::expand ( )

Expand the hash.

Useful primarily when the expansion policy is set to MANUAL.

Definition at line 1397 of file Map.h.

References DLL< C, L >::clear(), DLL< C, L >::head, Vec< C, A, S >::i, TSHashTable< H >::insert(), TSHashTable< H >::m_array, TSHashTable< H >::m_bucket_chain, TSHashTable< H >::Bucket::m_chain, TSHashTable< H >::m_count, TSHashTable< H >::m_expansion_policy, Vec< C, A, S >::move(), Vec< C, A, S >::n, DLL< Bucket, typename Bucket::Link_m_link >::next(), and Vec< C, A, S >::set_expand().

Referenced by TSHashTable< H >::insert().

template<typename H>

size_t TSHashTable< H >::expansionLimit ( ) const [inline]

Set the limit value for the expansion policy.

Definition at line 1224 of file Map.h.

template<typename H>

void TSHashTable< H >::expansionPolicy ( ) const [inline]

Get the current expansion policy.

Definition at line 1220 of file Map.h.

template<typename H >

TSHashTable< H >::Location TSHashTable< H >::find ( Key key )

Find a value that matches key.

Note:: This finds the first value with a matching key. No other properties of the value are examined.

Returns:: The Location of the value. Use Location::isValid() to check for success.

Definition at line 1310 of file Map.h.

References TSHashTable< H >::findBucket(), TSHashTable< H >::Location::m_bucket, TSHashTable< H >::Bucket::m_chain, and TSHashTable< H >::Location::m_value.

Referenced by ServerSessionPool::acquireSession(), ServerSessionPool::eventHandler(), and TSHashTable< H >::remove().

template<typename H >

TSHashTable< H >::Location TSHashTable< H >::find ( Value * value )

Get a Location for value.

This is a bit obscure but needed in certain cases. It should only be used on a value that is already known to be in the table. It just does the bucket lookup and uses that and the value to construct a Location that can be used with other methods. The m_distance value is not set in this case for performance reasons.

Definition at line 1324 of file Map.h.

References TSHashTable< H >::findBucket(), TSHashTable< H >::Location::m_bucket, TSHashTable< H >::Bucket::m_chain, and TSHashTable< H >::Location::m_value.

template<typename H >