[#BloombergLP-bslalg-HashTableImpUtil]
= xref:BloombergLP.adoc[BloombergLP]::xref:BloombergLP/bslalg.adoc[bslalg]::HashTableImpUtil
:relfileprefix: ../../
:mrdocs:

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

== Synopsis

Declared in `<bslalg_hashtableimputil.h>`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
struct HashTableImpUtil;
----

== Static Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/bslalg/HashTableImpUtil/bucketContainsLink.adoc[`bucketContainsLink`] 
| 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()]`.
| xref:BloombergLP/bslalg/HashTableImpUtil/computeBucketIndex.adoc[`computeBucketIndex`] 
| 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.
| xref:BloombergLP/bslalg/HashTableImpUtil/extractKey.adoc[`extractKey`] 
| 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); `
| xref:BloombergLP/bslalg/HashTableImpUtil/extractValue.adoc[`extractValue`] 
| 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`.
| xref:BloombergLP/bslalg/HashTableImpUtil/find.adoc[`find`] 
| 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) `
| xref:BloombergLP/bslalg/HashTableImpUtil/findTransparent.adoc[`findTransparent`] 
| 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)
| xref:BloombergLP/bslalg/HashTableImpUtil/insertAtBackOfBucket.adoc[`insertAtBackOfBucket`] 
| 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`.
| xref:BloombergLP/bslalg/HashTableImpUtil/insertAtFrontOfBucket.adoc[`insertAtFrontOfBucket`] 
| 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`.
| xref:BloombergLP/bslalg/HashTableImpUtil/insertAtPosition.adoc[`insertAtPosition`] 
| 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`.
| xref:BloombergLP/bslalg/HashTableImpUtil/isWellFormed.adoc[`isWellFormed`] 
| 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:
| xref:BloombergLP/bslalg/HashTableImpUtil/rehash.adoc[`rehash`] 
| 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.
| xref:BloombergLP/bslalg/HashTableImpUtil/remove.adoc[`remove`] 
| 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`.
|===



[.small]#Created with https://www.mrdocs.com[MrDocs]#