BDE 4.14.0 Production release
Loading...
Searching...
No Matches
Static Public Member Functions | List of all members
bslalg::HashTableImpUtil Struct Reference

#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.

Member Function Documentation

◆ bucketContainsLink()

bool bslalg::HashTableImpUtil::bucketContainsLink ( const HashTableBucket &  bucket,
BidirectionalLink *  linkAddress 
)
inlinestatic

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

Return true the specified link is contained in the specified bucket and false otherwise.

◆ computeBucketIndex()

std::size_t bslalg::HashTableImpUtil::computeBucketIndex ( std::size_t  hashCode,
std::size_t  numBuckets 
)
inlinestatic

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.

◆ extractKey()

template<class KEY_CONFIG >
HashTableImpUtil_ExtractKeyResult< KEY_CONFIG >::Type bslalg::HashTableImpUtil::extractKey ( BidirectionalLink *  link)
inlinestatic

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);
bslalg::HashTableImpUtil::extractKey
static HashTableImpUtil_ExtractKeyResult< KEY_CONFIG >::Type extractKey(BidirectionalLink *link)
Definition bslalg_hashtableimputil.h:889

◆ extractValue()

template<class KEY_CONFIG >
KEY_CONFIG::ValueType & bslalg::HashTableImpUtil::extractValue ( BidirectionalLink *  link)
inlinestatic

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.

◆ find()

template<class KEY_CONFIG , class KEY_EQUAL >
BidirectionalLink * bslalg::HashTableImpUtil::find ( const HashTableAnchor &  anchor,
typename HashTableImpUtil_ExtractKeyResult< KEY_CONFIG >::Type  key,
const KEY_EQUAL &  equalityFunctor,
std::size_t  hashCode 
)
inlinestatic

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)

◆ findTransparent()

template<class KEY_CONFIG , class LOOKUP_KEY , class KEY_EQUAL >
BidirectionalLink * bslalg::HashTableImpUtil::findTransparent ( const HashTableAnchor &  anchor,
const LOOKUP_KEY &  key,
const KEY_EQUAL &  equalityFunctor,
std::size_t  hashCode 
)
inlinestatic

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)

◆ insertAtBackOfBucket()

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.

◆ insertAtFrontOfBucket()

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.

◆ insertAtPosition()

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.

◆ isWellFormed()

template<class KEY_CONFIG , class HASHER >
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:

  1. The anchor.listRootAddress() is the address of a well-formed doubly linked list (see bslalg_bidirectionallinklistutil ).
  2. 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().
  3. Links in the doubly linked list having the same hash value are contiguous.
  4. 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.

◆ rehash()

template<class KEY_CONFIG , class HASHER >
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.

An object of this proctor class guarantees that, on leaving scope, any remaining elements in the original specified elementList are spliced to the front of the list rooted in the specified newAnchor so that there is only one list for the client to clear if an exception is thrown by a user supplied hash functor. Note that it might be possible to avoid creating such a proctor in C++11 if the hash functor is determined to be noexcept.

See bslalg_hashtableimputil

◆ remove()

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.

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