#include <bslalg_hashtableimputil.h>

Static Public Member Functions
static bool	bucketContainsLink (const HashTableBucket &bucket, BidirectionalLink *linkAddress)
template<class KEY_CONFIG >
static HashTableImpUtil_ExtractKeyResult < KEY_CONFIG >::Type	extractKey (BidirectionalLink *link)
template<class KEY_CONFIG >
static KEY_CONFIG::ValueType &	extractValue (BidirectionalLink *link)
template<class KEY_CONFIG , class HASHER >
static bool	isWellFormed (const HashTableAnchor &anchor, const HASHER &hasher, bslma::Allocator *allocator=0)
static std::size_t	computeBucketIndex (std::size_t hashCode, std::size_t numBuckets)
static void	insertAtFrontOfBucket (HashTableAnchor anchor, BidirectionalLink link, std::size_t hashCode)
static void	insertAtBackOfBucket (HashTableAnchor anchor, BidirectionalLink link, std::size_t hashCode)
static void	insertAtPosition (HashTableAnchor anchor, BidirectionalLink link, std::size_t hashCode, BidirectionalLink *position)
static void	remove (HashTableAnchor anchor, BidirectionalLink link, std::size_t hashCode)
template<class KEY_CONFIG , class KEY_EQUAL >
static BidirectionalLink *	find (const HashTableAnchor &anchor, typename HashTableImpUtil_ExtractKeyResult< KEY_CONFIG >::Type key, const KEY_EQUAL &equalityFunctor, std::size_t hashCode)
template<class KEY_CONFIG , class LOOKUP_KEY , class KEY_EQUAL >
static BidirectionalLink *	findTransparent (const HashTableAnchor &anchor, const LOOKUP_KEY &key, const KEY_EQUAL &equalityFunctor, std::size_t hashCode)
template<class KEY_CONFIG , class HASHER >
static void	rehash (HashTableAnchor newAnchor, BidirectionalLink elementList, const HASHER &hasher)

Detailed Description

This struct provides a namespace for a suite of utility functions for creating and manipulating a hash table.

See Component bslalg_hashtableimputil

Member Function Documentation

static bool bslalg::HashTableImpUtil::bucketContainsLink	(	const HashTableBucket &	bucket,
		BidirectionalLink *	linkAddress
	)			`[static]`

Return true if the specified linkAddress is the address of one of the links in the list of elements in the closed range [bucket.first(), bucket.last()].

template<class KEY_CONFIG >

static HashTableImpUtil_ExtractKeyResult<KEY_CONFIG>::Type bslalg::HashTableImpUtil::extractKey ( BidirectionalLink * link ) [static]

Return a reference providing non-modifiable access to the key (of type KEY_CONFIG::KeyType) held by the specified link. The behavior is undefined unless link refers to a node of type BidirectionalNode<KEY_CONFIG::ValueType>. KEY_CONFIG shall be a namespace providing the type names KeyType and ValueType, as well as a function that can be called as if it had the following signature:

          const KeyType& extractKey(const ValueType& obj);

template<class KEY_CONFIG >

static KEY_CONFIG::ValueType& bslalg::HashTableImpUtil::extractValue ( BidirectionalLink * link ) [static]

Return a reference providing non-modifiable access to the value (of type KEY_CONFIG::ValueType) held by the specified link. The behavior is undefined unless link refers to a node of type BidirectionalNode<KEY_CONFIG::ValueType>. KEY_CONFIG shall be a namespace providing the type name ValueType.

template<class KEY_CONFIG , class HASHER >

static bool bslalg::HashTableImpUtil::isWellFormed	(	const HashTableAnchor &	anchor,
		const HASHER &	hasher,
		bslma::Allocator *	allocator = `0`
	)			`[static]`

Return true if the specified anchor is well-formed for the specified hasher. Use the specified allocator for temporary memory, or the default allocator if none is specified. For a HashTableAnchor to be considered well-formed for a particular key policy, KEY_CONFIG, and hash functor, hasher, all of the following must be true:

The anchor.listRootAddress() is the address of a well-formed doubly linked list (see bslalg_bidirectionallinklistutil).
Links in the doubly linked list having the same adjusted hash value are contiguous, where the adjusted hash value is the value returned by computeBucketIndex, for extractKey<KEY_CONFIG>(link) and anchor.bucketArraySize().
Links in the doubly linked list having the same hash value are contiguous.
The first and last links in each bucket (in the bucket array, anchor.bucketArrayAddress()') refer to a the first and last element in the well-formed doubly linked list of all nodes in the list having an adjusted hash value equal to that bucket's array index. If no values in the doubly linked list have an adjusted hash value equal to a bucket's index, then the addresses of the first and last links for that bucket are 0.

static std::size_t bslalg::HashTableImpUtil::computeBucketIndex	(	std::size_t	hashCode,
		std::size_t	numBuckets
	)			`[static]`

Return the index of the bucket referring to the elements whose adjusted hash codes are the same as the adjusted value of the specified hashCode, where hashCode (and the hash-codes of the elements) are adjusted for the specified numBuckets. The behavior is undefined if numBuckets is 0.

static void bslalg::HashTableImpUtil::insertAtFrontOfBucket	(	HashTableAnchor *	anchor,
		BidirectionalLink *	link,
		std::size_t	hashCode
	)			`[static]`

Insert the specified link, having the specified (non-adjusted) hashCode, into the specified anchor, at the front of the bucket with index computeBucketIndex(hashCode, anchor->bucketArraySize()). The behavior is undefined unless anchor is well-formed (see isWellFormed) for some combination of KEY_CONFIG and HASHER such that link refers to a node of type BidirectionalNode<KEY_CONFIG::ValueType> and HASHER(extractKey<KEY_CONFIG>(link)) returns hashCode.

static void bslalg::HashTableImpUtil::insertAtBackOfBucket	(	HashTableAnchor *	anchor,
		BidirectionalLink *	link,
		std::size_t	hashCode
	)			`[static]`

Insert the specified link, having the specified (non-adjusted) hashCode, into the specified anchor, into the bucket with index computeBucketIndex(hashCode, anchor->bucketArraySize()), after the last node in the bucket. The behavior is undefined unless anchor is well-formed (see isWellFormed) for some combination of KEY_CONFIG and HASHER such that link refers to a node of type BidirectionalNode<KEY_CONFIG::ValueType> and HASHER(extractKey<KEY_CONFIG>(link)) returns hashCode.

static void bslalg::HashTableImpUtil::insertAtPosition	(	HashTableAnchor *	anchor,
		BidirectionalLink *	link,
		std::size_t	hashCode,
		BidirectionalLink *	position
	)			`[static]`

Insert the specified link, having the specified (non-adjusted) hashCode, into the specified anchor immediately before the specified position in the bi-directional linked list of anchor. The behavior is undefined unless position is in the bucket having index computeBucketIndex(hashCode, anchor->bucketArraySize()) and anchor is well-formed (see isWellFormed) for some combination of KEY_CONFIG and HASHER such that link refers to a node of type BidirectionalNode<KEY_CONFIG::ValueType> and HASHER(extractKey<KEY_CONFIG>(link)) returns hashCode.

static void bslalg::HashTableImpUtil::remove	(	HashTableAnchor *	anchor,
		BidirectionalLink *	link,
		std::size_t	hashCode
	)			`[static]`

Remove the specified link, having the specified (non-adjusted) hashCode, from the specified anchor. The behavior is undefined unless anchor is well-formed (see isWellFormed) for some combination of KEY_CONFIG and HASHER such that link refers to a node of type BidirectionalNode<KEY_CONFIG::ValueType> and HASHER(extractKey<KEY_CONFIG>(link)) returns hashCode.

template<class KEY_CONFIG , class KEY_EQUAL >

static BidirectionalLink* bslalg::HashTableImpUtil::find	(	const HashTableAnchor &	anchor,
		typename HashTableImpUtil_ExtractKeyResult< KEY_CONFIG >::Type	key,
		const KEY_EQUAL &	equalityFunctor,
		std::size_t	hashCode
	)			`[static]`

Return the address of the first link in the list element of the specified anchor, having a value matching (according to the specified equalityFunctor) the specified key in the bucket that holds elements with the specified hashCode if such a link exists, and return 0 otherwise. The behavior is undefined unless, for the provided KEY_CONFIG and some hash function, HASHER, anchor is well-formed (see isWellFormed) and HASHER(key) returns hashCode. KEY_CONFIG shall be a namespace providing the type names KeyType and ValueType, as well as a function that can be called as if it had the following signature:

          const KeyType& extractKey(const ValueType& obj);

KEY_EQUAL shall be a functor that can be called as if it had the following signature:

          bool operator()(const KEY_CONFIG::KeyType& key1,
                          const KEY_CONFIG::KeyType& key2)

template<class KEY_CONFIG , class LOOKUP_KEY , class KEY_EQUAL >

static BidirectionalLink* bslalg::HashTableImpUtil::findTransparent	(	const HashTableAnchor &	anchor,
		const LOOKUP_KEY &	key,
		const KEY_EQUAL &	equalityFunctor,
		std::size_t	hashCode
	)			`[static]`

Return the address of the first link in the list element of the specified anchor having a value matching (according to the specified transparent equalityFunctor) the specified key in the bucket that holds elements with the specified hashCode if such a link exists, and return 0 otherwise. The behavior is undefined unless, for the provided KEY_CONFIG and some hash function, HASHER, anchor is well-formed (see isWellFormed) and HASHER(key) returns hashCode. KEY_CONFIG shall be a namespace providing the type names KeyType and ValueType, as well as a function that can be called as if it had the following signature:

          const KeyType& extractKey(const ValueType& obj);

KEY_EQUAL shall be a functor that can be called as if it had the following signature:

          bool operator()(const LOOKUP_KEY&          key1,
                          const KEY_CONFIG::KeyType& key2)

template<class KEY_CONFIG , class HASHER >

static void bslalg::HashTableImpUtil::rehash	(	HashTableAnchor *	newAnchor,
		BidirectionalLink *	elementList,
		const HASHER &	hasher
	)			`[static]`

Populate the specified newHashTable with all the elements in the specified elementList, using the specified hasher to determine the (non-adjusted) hash code for each element. This operation provides the strong exception guarantee unless the supplied hasher throws, in which case it provides no exception safety guarantee. The buckets in the array in newAnchor and the list root address in newAnchor are assumed to be garbage and overwritten. The behavior is undefined unless, newHashTable holds no elements and has one or more (empty) buckets, and elementList is a well-formed bi-directional list (see BidirectionalLinkListUtil::isWellFormed) whose nodes are each of type BidirectionalNode<KEY_CONFIG::ValueType>, the previous address of the first node and the next address of the last node are 0.

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

bslalg_hashtableimputil.h

bslalg::HashTableImpUtil Struct Reference

Static Public Member Functions

Detailed Description

Member Function Documentation