bslstl_hashtable.h

Go to the documentation of this file.

/// @file bslstl_hashtable.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslstl_hashtable.h                                                 -*-C++-*-
#ifndef INCLUDED_BSLSTL_HASHTABLE
#define INCLUDED_BSLSTL_HASHTABLE
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslstl_hashtable bslstl_hashtable
/// @brief  Provide a hash-container with support for duplicate values.
/// @addtogroup bsl
/// @{
/// @addtogroup bslstl
/// @{
/// @addtogroup bslstl_hashtable
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslstl_hashtable-purpose"> Purpose</a>
/// * <a href="#bslstl_hashtable-classes"> Classes </a>
/// * <a href="#bslstl_hashtable-description"> Description </a>
///   * <a href="#bslstl_hashtable-requirements-on-key_config"> Requirements on KEY_CONFIG </a>
///   * <a href="#bslstl_hashtable-memory-allocation"> Memory Allocation </a>
///     * <a href="#bslstl_hashtable-bslma-style-allocators"> bslma-Style Allocators </a>
///   * <a href="#bslstl_hashtable-exception-safety"> Exception Safety </a>
///   * <a href="#bslstl_hashtable-internal-data-structure"> Internal Data Structure </a>
///   * <a href="#bslstl_hashtable-usage"> Usage </a>
///   * <a href="#bslstl_hashtable-example-1-implementing-a-hashed-set-container"> Example 1: Implementing a Hashed Set Container </a>
///   * <a href="#bslstl_hashtable-example-2-implementing-a-hashed-map-container"> Example 2: Implementing a Hashed Map Container </a>
///   * <a href="#bslstl_hashtable-example-3-implementing-a-hashed-multi-map-container"> Example 3: Implementing a Hashed Multi-Map Container </a>
///   * <a href="#bslstl_hashtable-example-4-implementing-a-custom-container"> Example 4: Implementing a Custom Container </a>
///
/// # Purpose {#bslstl_hashtable-purpose}
/// Provide a hash-container with support for duplicate values.
///
/// # Classes {#bslstl_hashtable-classes}
///
/// -   bslstl::HashTable : hashed-table container for user-supplied object types
///
/// @see  package bos+stdhdrs in the bos package group
///
/// # Description {#bslstl_hashtable-description}
/// This component defines a single class template, `HashTable`,
/// implementing a value-semantic container that can be used to easily implement
/// the four `unordered` containers specified by the C++11 standard.
///
/// An instantiation of `HashTable` is an allocator-aware, value-semantic type
/// whose salient attributes are its size (number of keys) and the ordered
/// sequence of keys the `HashTable` contains.  If `HashTable` is instantiated
/// with a key type that is not itself value-semantic, then it will not retain
/// all of its value-semantic qualities.  In particular, if the key type cannot
/// be tested for equality, then a HashTable containing that type cannot be
/// tested for equality.  It is even possible to instantiate `HashTable` with a
/// key type that does not have a copy-constructor, in which case the
/// `HashTable` will not be copyable.
///
/// ## Requirements on KEY_CONFIG {#bslstl_hashtable-requirements-on-key_config}
///
///
/// The elements stored in a `HashTable` and the key by which they are indexed
/// are defined by a `KEY_CONFIG` template type parameter.  The user-supplied
/// `KEY_CONFIG` type must provide two type aliases named `ValueType` and
/// `KeyType` that name the type of element stored and its associated key type
/// respectively.  In addition, a `KEY_CONFIG` class shall provide a static
/// member function which may be called as if it had the following signature:
/// @code
/// /// Return a reference offering non-modifiable access to the key for the
/// /// specified `value`.
/// static const KeyType& extractKey(const ValueType& value);
/// @endcode
/// Optionally, the `KEY_CONFIG` class might provide an `extractKey` function
/// with the alternative signature:
/// @code
/// /// Return a reference to the key for the specified `value`.
/// static KeyType& extractKey(ValueType& value);
/// @endcode
/// This alternative signature is necessary to support the rare case that a hash
/// function or comparator used to configure the `HashTable` template below take
/// their arguments by non-`const` reference.  This is subject to additional
/// constraints that these functions may not modify the passed arguments, and is
/// inherently a fragile interface and not recommended.  It is supported only
/// for C++ Standard conformance.
///
/// A `HashTable` is a "Value-Semantic Type" (see @ref bsldoc_glossary ) only if
/// the configured `ValueType` is value-semantic.  It is possible to instantiate
/// a `HashTable` configured with a `ValueType` that does not provide a full
/// `HashTable` of value-semantic operations, but then some methods of the
/// container may not be instantiable.  The following terminology, adopted from
/// the C++11 standard, is used in the function documentation of `HashTable` to
/// describe a function's requirements for the `KEY` template parameter.  These
/// terms are also defined in [utility.arg.requirements] (section 17.6.3.1 of
/// the C++11 standard).  Note that, in the context of a `HashTable`
/// instantiation, the requirements apply specifically to the `HashTable`s
/// element type, `ValueType`.
///
/// Legend
/// ------
/// `X`    - denotes an allocator-aware container type (e.g., `unordered_set`)
/// `T`    - `value_type` associated with `X`
/// `A`    - type of the allocator used by `X`
/// `m`    - lvalue of type `A` (allocator)
/// `p`    - address (`T *`) of uninitialized storage for a `T` within an `X`
/// `rv`   - rvalue of type (non-`const`) `T`
/// `v`    - rvalue or lvalue of type (possibly `const`) `T`
/// `args` - 0 or more arguments
///
/// The following terms are used to more precisely specify the requirements on
/// template parameter types in function-level documentation.
/// 
///  *default-insertable*: `T` has a default constructor.  More precisely, `T`
///      is `default-insertable` into `X` means that the following expression is
///      well-formed:
/// 
///       `allocator_traits<A>::construct(m, p)`
/// 
///  *move-insertable*: `T` provides a constructor that takes an rvalue of type
///      (non-`const`) `T`.  More precisely, `T` is `move-insertable` into `X`
///      means that the following expression is well-formed:
/// 
///       `allocator_traits<A>::construct(m, p, rv)`
/// 
///  *copy-insertable*: `T` provides a constructor that takes an lvalue or
///      rvalue of type (possibly `const`) `T`.  More precisely, `T` is
///      `copy-insertable` into `X` means that the following expression is
///      well-formed:
/// 
///       `allocator_traits<A>::construct(m, p, v)`
/// 
///  *move-assignable*: `T` provides an assignment operator that takes an rvalue
///      of type (non-`const`) `T`.
/// 
///  *copy-assignable*: `T` provides an assignment operator that takes an lvalue
///      or rvalue of type (possibly `const`) `T`.
/// 
///  *emplace-constructible*: `T` is `emplace-constructible` into `X` from
///      `args` means that the following expression is well-formed:
/// 
///       `allocator_traits<A>::construct(m, p, args)`
/// 
///  *erasable*: `T` provides a destructor.  More precisely, `T` is `erasable`
///      from `X` means that the following expression is well-formed:
/// 
///       `allocator_traits<A>::destroy(m, p)`
/// 
///  *equality-comparable*: The type provides an equality-comparison operator
///      that defines an equivalence relationship and is both reflexive and
///      transitive.
///
/// ## Memory Allocation {#bslstl_hashtable-memory-allocation}
///
///
/// The type supplied as a HashTable's `ALLOCATOR` template parameter determines
/// how that HashTable will allocate memory.  The `HashTable` template supports
/// allocators meeting the requirements of the C++ standard allocator
/// requirements ([allocator.requirements], C++11 17.6.3.5); in addition it
/// supports scoped-allocators derived from the `bslma::Allocator` memory
/// allocation protocol.  Clients intending to use `bslma` style allocators
/// should use the template's default `ALLOCATOR` type: The default type for the
/// `ALLOCATOR` template parameter, `bsl::allocator`, provides a C++11
/// standard-compatible adapter for a `bslma::Allocator` object.
///
/// ### bslma-Style Allocators {#bslstl_hashtable-bslma-style-allocators}
///
///
/// If the parameterized `ALLOCATOR` type of an `HashTable` instantiation is
/// `bsl::allocator`, then objects of that HashTable type will conform to the
/// standard behavior of a `bslma`-allocator-enabled type.  Such a HashTable
/// accepts an optional `bslma::Allocator` argument at construction.  If the
/// address of a `bslma::Allocator` object is explicitly supplied at
/// construction, it will be used to supply memory for the HashTable throughout
/// its lifetime; otherwise, the HashTable will use the default allocator
/// installed at the time of the HashTable's construction (see @ref bslma_default ).
/// In addition to directly allocating memory from the indicated
/// `bslma::Allocator`, a HashTable supplies that allocator's address to the
/// constructors of contained objects of the configured `ValueType` with the
/// `bslalg::TypeTraitUsesBslmaAllocator` trait.
///
/// ## Exception Safety {#bslstl_hashtable-exception-safety}
///
///
/// The operations of a `HashTable` provide the strong exception guarantee (see
/// @ref bsldoc_glossary ) except in the presence of a hash-functor or
/// equality-comparator that throws exceptions.  If either the hash-functor or
/// equality-comparator throws an exception from a non-`const` method,
/// `HashTable` provides only the basic exception guarantee, and the operation
/// will leave the container in a valid but unspecified (potentially empty)
/// state.
///
/// ## Internal Data Structure {#bslstl_hashtable-internal-data-structure}
///
///
/// This implementation of a hash-table uses a single bidirectional list, to
/// hold all the elements stored in the container, and the elements in this list
/// are indexed by a dynamic array of buckets, each of which holds a pointer to
/// the first and last element in the linked-list whose adjusted hash-values are
/// equal to that bucket's index.
///
/// As we do not cache the hashed value, if any hash function throws we will
/// either do nothing and allow the exception to propagate, or, if some change
/// of state has already been made, clear the whole container to provide the
/// basic exception guarantee.  There are similar concerns for the `COMPARATOR`
/// predicate.
///
/// ## Usage {#bslstl_hashtable-usage}
///
///
/// This section illustrates intended use of this component.  The
/// `bslstl::HashTable` class template provides a common foundation for
/// implementing the four standard unordered containers:
/// * `bsl::unordered_map`
/// * `bsl::unordered_multiset`
/// * `bsl::unordered_multimap`
/// * `bsl::unordered_set`
/// This and the subsequent examples in this component use the
/// `bslstl::HashTable` class to implement several model container classes, each
/// providing a small but representative sub-set of the functionality of one of
/// the standard unordered containers.
///
/// ## Example 1: Implementing a Hashed Set Container {#bslstl_hashtable-example-1-implementing-a-hashed-set-container}
///
///
/// Suppose we wish to implement, `MyHashedSet`, a greatly abbreviated version
/// of `bsl::unordered_set`.  The `bslstl::HashTable` class template can be used
/// as the basis of that implementation.
///
/// First, we define `UseEntireValueAsKey`, a class template we can use to
/// configure `bslstl::HashTable` to use its entire elements as keys for its
/// hasher, a policy suitable for a set container.  (Later, in {Example 2}, we
/// will define `UseFirstValueOfPairAsKey` for use in a map container.  Note
/// that, in practice, developers can use the existing classes in
/// @ref bslstl_unorderedmapkeyconfiguration  and
/// @ref bslstl_unorderedsetkeyconfiguration .)
/// @code
///                         // ==========================
///                         // struct UseEntireValueAsKey
///                         // ==========================
///
/// // This `struct` provides a namespace for types and methods that define
/// // the policy by which the key value of a hashed container (i.e., the
/// // value passed to the hasher) is extracted from the objects stored in
/// // the hashed container (the `value` type).
/// template <class VALUE_TYPE>
/// struct UseEntireValueAsKey {
///
///     /// Alias for `VALUE_TYPE`, the type stored in the hashed container.
///     typedef VALUE_TYPE ValueType;
///
///     /// Alias for the type passed to the hasher by the hashed container.
///     /// In this policy, that type is `ValueType`.
///     typedef ValueType KeyType;
///
///     /// Return the key value for the specified `value`.  In this policy,
///     /// that is `value` itself.
///     static const KeyType& extractKey(const ValueType& value);
/// };
///
///                         // --------------------------
///                         // struct UseEntireValueAsKey
///                         // --------------------------
///
/// template <class VALUE_TYPE>
/// inline
/// const typename UseEntireValueAsKey<VALUE_TYPE>::KeyType&
///                UseEntireValueAsKey<VALUE_TYPE>::extractKey(
///                                                     const ValueType& value)
/// {
///     return value;
/// }
/// @endcode
/// Next, we define our `MyHashedSet` class template with an instance of
/// `bslstl::HashTable` (configured using `UseEntireValueAsKey`) as its sole
/// data member.  We provide `insert` method, to allow us to populate these
/// sets, and the `find` method to allow us to examine those elements.  We also
/// provide `size` and @ref bucket_count  accessor methods to let us check the inner
/// workings of our class.
///
/// Note that the standard classes define aliases for the templated parameters
/// and other types.  In the interest of brevity, this model class (and the
/// classes in the subsequent examples) do not define such aliases except where
/// strictly needed for the example.
/// @code
///                         // =================
///                         // class MyHashedSet
///                         // =================
///
/// template <class KEY,
///           class HASHF     = bsl::hash<     KEY>,
///           class EQUAL     = bsl::equal_to< KEY>,
///           class ALLOCATOR = bsl::allocator<KEY> >
/// class MyHashedSet
/// {
///   private:
///     // PRIVATE TYPES
///     typedef bsl::allocator_traits<ALLOCATOR>               AllocatorTraits;
///     typedef typename AllocatorTraits::difference_type      difference_type;
///     typedef BloombergLP::bslstl::HashTableIterator<
///                                       const KEY, difference_type> iterator;
///
///     typedef UseEntireValueAsKey<KEY>                               HashKey;
///
///     typedef BloombergLP::bslstl::HashTable<HashKey,
///                                            HASHF,
///                                            EQUAL,
///                                            ALLOCATOR>         ImpHashTable;
///
///
///     // DATA
///     ImpHashTable d_impl;
///
///   public:
///     // TYPES
///     typedef typename AllocatorTraits::size_type size_type;
///     typedef iterator                            const_iterator;
///
///     // CREATORS
///
///     /// Create an empty `MyHashedSet` object having a maximum load
///     /// factor of 1.  Optionally specify at least `initialNumBuckets` in
///     /// this container's initial array of buckets.  If
///     /// `initialNumBuckets` is not supplied, an implementation defined
///     /// value is used.  Optionally specify a `hash` used to generate the
///     /// hash values associated to the keys extracted from the values
///     /// contained in this object.  If `hash` is not supplied, a
///     /// default-constructed object of type `HASHF` is used.  Optionally
///     /// specify a key-equality functor `keyEqual` used to verify that
///     /// two key values are the same.  If `keyEqual` is not supplied, a
///     /// default-constructed object of type `EQUAL` is used.  Optionally
///     /// specify an `allocator` used to supply memory.  If `allocator` is
///     /// not supplied, a default-constructed object of the (template
///     /// parameter) type `ALLOCATOR` is used.  If the `ALLOCATOR` is
///     /// `bsl::allocator` (the default), then `allocator` shall be
///     /// convertible to `bslma::Allocator *`.  If the `ALLOCATOR` is
///     /// `bsl::allocator` and `allocator` is not supplied, the currently
///     /// installed default allocator is used to supply memory.
///     explicit MyHashedSet(size_type        initialNumBuckets = 0,
///                          const HASHF&     hash              = HASHF(),
///                          const EQUAL&     keyEqual          = EQUAL(),
///                          const ALLOCATOR& allocator         = ALLOCATOR());
///
///     /// Destroy this object.
///     //! ~MyHashedSet() = default;
///
///     // MANIPULATORS
///
///     /// Insert the specified `value` into this set if the `value` does
///     /// not already exist in this set; otherwise, this method has no
///     /// effect.  Return a pair whose `first` member is an iterator
///     /// providing non-modifiable access to the (possibly newly inserted)
///     /// `KEY` object having `value` (according to `EQUAL`) and whose
///     /// `second` member is `true` if a new element was inserted, and
///     /// `false` if `value` was already present.
///     bsl::pair<const_iterator, bool> insert(const KEY& value);
///
///     // ACCESSORS
///
///     /// Return the number of buckets in this set.
///     size_type bucket_count() const;
///
///     /// Return an iterator providing non-modifiable access to the
///     /// past-the-end element (in the sequence of `KEY` objects)
///     /// maintained by this set.
///     const_iterator cend() const;
///
///     /// Return an iterator providing non-modifiable access to the `KEY`
///     /// object in this set having the specified `value`, if such an
///     /// entry exists, and the iterator returned by the `cend` method
///     /// otherwise.
///     const_iterator find(const KEY& value) const;
///
///     /// Return the number of elements in this set.
///     size_type size() const;
/// };
/// @endcode
/// Next, we implement the methods of `MyHashedSet`.  In many cases, the
/// implementations consist mainly in forwarding arguments to and returning
/// values from the underlying `bslstl::HashTable`.
/// @code
///                         // =================
///                         // class MyHashedSet
///                         // =================
///
/// // CREATORS
/// template <class KEY, class HASHF, class EQUAL, class ALLOCATOR>
/// inline
/// MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::MyHashedSet(
///                                         size_type        initialNumBuckets,
///                                         const HASHF&     hash,
///                                         const EQUAL&     keyEqual,
///                                         const ALLOCATOR& allocator)
/// : d_impl(hash, keyEqual, initialNumBuckets, allocator)
/// {
/// }
/// @endcode
/// Note that the `insertIfMissing` method of `bslstl::HashTable` provides the
/// semantics needed for adding values (unique values only) to sets.
/// @code
/// // MANIPULATORS
/// template <class KEY, class HASHF, class EQUAL, class ALLOCATOR>
/// inline
/// bsl::pair<typename MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::iterator,
///           bool>    MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::insert(
///                                                           const KEY& value)
/// {
///     typedef bsl::pair<iterator, bool> ResultType;
///
///     bool                       isInsertedFlag = false;
///     bslalg::BidirectionalLink *result         = d_impl.insertIfMissing(
///                                                            &isInsertedFlag,
///                                                            value);
///     return ResultType(iterator(result), isInsertedFlag);
/// }
///
/// // ACCESSORS
/// template <class KEY, class HASHF, class EQUAL, class ALLOCATOR>
/// inline
/// typename MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::size_type
///          MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::bucket_count() const
/// {
///     return d_impl.numBuckets();
/// }
///
/// template <class KEY, class HASHF, class EQUAL, class ALLOCATOR>
/// inline
/// typename MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::const_iterator
///          MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::cend() const
/// {
///     return const_iterator();
/// }
///
/// template <class KEY, class HASHF, class EQUAL, class ALLOCATOR>
/// inline
/// typename MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::const_iterator
///          MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::find(const KEY& key)
///                                                                       const
/// {
///     return const_iterator(d_impl.find(key));
/// }
///
/// template <class KEY, class HASHF, class EQUAL, class ALLOCATOR>
/// inline
/// typename MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::size_type
///          MyHashedSet<KEY, HASHF, EQUAL, ALLOCATOR>::size() const
/// {
///     return d_impl.size();
/// }
/// @endcode
/// Finally, we create `mhs`, an instance of `MyHashedSet`, exercise it, and
/// confirm that it behaves as expected.
/// @code
/// MyHashedSet<int> mhs;
/// assert( 0    == mhs.size());
/// assert( 1    == mhs.bucket_count());
/// @endcode
/// Notice that the newly created set is empty and has a single bucket.
///
/// Inserting a value (10) succeeds the first time but correctly fails on the
/// second attempt.
/// @code
/// bsl::pair<MyHashedSet<int>::const_iterator, bool> status;
///
/// status = mhs.insert(10);
/// assert( 1    ==  mhs.size());
/// assert(10    == *status.first);
/// assert(true  ==  status.second);
///
/// status = mhs.insert(10);
/// assert( 1    ==  mhs.size());
/// assert(10    == *status.first);
/// assert(false ==  status.second);
/// @endcode
/// We can insert a different value (20) and thereby increase the set size to 2.
/// @code
/// status = mhs.insert(20);
/// assert( 2    ==  mhs.size());
/// assert(20    == *status.first);
/// assert(true  ==  status.second);
/// @endcode
/// Each of the inserted values (10, 20) can be found in the set.
/// @code
/// MyHashedSet<int>::const_iterator itr, end = mhs.cend();
///
/// itr = mhs.find(10);
/// assert(end !=  itr);
/// assert(10  == *itr);
///
/// itr = mhs.find(20);
/// assert(end !=  itr);
/// assert(20  == *itr);
/// @endcode
/// However, a value known to absent from the set (0), is correctly reported as
/// not there.
/// @code
/// itr = mhs.find(0);
/// assert(end ==  itr);
/// @endcode
///
/// ## Example 2: Implementing a Hashed Map Container {#bslstl_hashtable-example-2-implementing-a-hashed-map-container}
///
///
/// Suppose we wish to implement, `MyHashedMap`, a greatly abbreviated version
/// of `bsl::unordered_map`.  As with `MyHashedSet` (see {Example 1}), the
/// `bslstl::HashTable` class template can be used as the basis of our
/// implementation.
///
/// First, we define `UseFirstValueOfPairAsKey`, a class template we can use to
/// configure `bslstl::HashTable` to use the `first` member of each element,
/// each a `bsl::pair`, as the key-value for hashing.  Note that, in practice,
/// developers can use class defined in @ref bslstl_unorderedmapkeyconfiguration .
/// @code
///                         // ===============================
///                         // struct UseFirstValueOfPairAsKey
///                         // ===============================
///
/// template <class VALUE_TYPE>
/// struct UseFirstValueOfPairAsKey {
///     // This 'struct' provides a namespace for types and methods that define
///     // the policy by which the key value of a hashed container (i.e., the
///     // value passed to the hasher) is extracted from the objects stored in
///     // the hashed container (the 'value' type).
///
///     typedef VALUE_TYPE ValueType;
///         // Alias for 'VALUE_TYPE', the type stored in the hashed container.
///         // For this policy 'ValueType' must define a public member named
///         // 'first' of type 'first_type'.
///
///     typedef typename ValueType::first_type KeyType;
///         // Alias for the type passed to the hasher by the hashed container.
///         // In this policy, that type is the type of the 'first' element of
///         // 'ValueType'.
///
///     static const KeyType& extractKey(const ValueType& value);
///         // Return the key value for the specified 'value'.  In this policy,
///         // that is the value of the 'first' member of 'value'.
/// };
///
///                         // -------------------------------
///                         // struct UseFirstValueOfPairAsKey
///                         // -------------------------------
///
/// template <class VALUE_TYPE>
/// inline
/// const typename UseFirstValueOfPairAsKey<VALUE_TYPE>::KeyType&
///                UseFirstValueOfPairAsKey<VALUE_TYPE>::extractKey(
///                                                     const ValueType& value)
/// {
///     return value.first;
/// }
/// @endcode
/// Next, we define our `MyHashedMap` class template with an instance of
/// `bslstl::HashTable` (configured using `UseFirstValueOfPairAsKey`) as its
/// sole data member.  In this example, we choose to implement `operator[]`
/// (corresponding to the signature method of `bsl::unordered_map`) to allow us
/// to populate our maps and to examine their elements.
/// @code
///                         // =================
///                         // class MyHashedMap
///                         // =================
///
/// template <class KEY,
///           class VALUE,
///           class HASHF     = bsl::hash<     KEY>,
///           class EQUAL     = bsl::equal_to< KEY>,
///           class ALLOCATOR = bsl::allocator<KEY> >
/// class MyHashedMap
/// {
///   private:
///     // PRIVATE TYPES
///     typedef bsl::allocator_traits<ALLOCATOR>               AllocatorTraits;
///
///     typedef UseFirstValueOfPairAsKey<bsl::pair<const KEY, VALUE> > HashKey;
///     typedef BloombergLP::bslstl::HashTable<HashKey,
///                                            HASHF,
///                                            EQUAL,
///                                            ALLOCATOR>         ImpHashTable;
///
///     // DATA
///     ImpHashTable d_impl;
///
///   public:
///     // TYPES
///     typedef typename AllocatorTraits::size_type size_type;
///
///     // CREATORS
///     explicit MyHashedMap(size_type        initialNumBuckets = 0,
///                          const HASHF&     hash              = HASHF(),
///                          const EQUAL&     keyEqual          = EQUAL(),
///                          const ALLOCATOR& allocator         = ALLOCATOR());
///     // Create an empty 'MyHashedMap' object having a maximum load factor
///     // of 1.  Optionally specify at least 'initialNumBuckets' in this
///     // container's initial array of buckets.  If 'initialNumBuckets' is not
///     // supplied, one empty bucket shall be used and no memory allocated.
///     // Optionally specify 'hash' to generate the hash values associated
///     // with the key-value pairs contained in this unordered map.  If 'hash'
///     // is not supplied, a default-constructed object of (template
///     // parameter) 'HASHF' is used.  Optionally specify a key-equality
///     // functor 'keyEqual' used to determine whether two keys have the same
///     // value.  If 'keyEqual' is not supplied, a default-constructed object
///     // of (template parameter) 'EQUAL' is used.  Optionally specify an
///     // 'allocator' used to supply memory.  If 'allocator' is not supplied,
///     // a default-constructed object of the (template parameter) type
///     // 'ALLOCATOR' is used.  If 'ALLOCATOR' is 'bsl::allocator' (the
///     // default), then 'allocator' shall be convertible to
///     // 'bslma::Allocator *'.  If 'ALLOCATOR' is 'bsl::allocator' and
///     // 'allocator' is not supplied, the currently installed default
///     // allocator is used to supply memory.  Note that more than
///     // 'initialNumBuckets' buckets may be created in order to preserve the
///     // bucket allocation strategy of the hash-table (but never fewer).
///
///     //! ~MyHashedMap() = default;
///         // Destroy this object.
///
///     // MANIPULATORS
///     VALUE& operator[](const KEY& key);
///         // Return a reference providing modifiable access to the
///         // mapped-value associated with the specified 'key' in this
///         // unordered map; if this unordered map does not already contain a
///         // 'value_type' object with 'key', first insert a new 'value_type'
///         // object having 'key' and a default-constructed 'VALUE' object.
///         // Note that this method requires that the (template parameter)
///         // type 'KEY' is "copy-constructible" and the (template parameter)
///         // 'VALUE' is "default-constructible".
/// };
/// @endcode
/// Then, we implement the methods `MyHashedMap`.  The construct need merely
/// forward its arguments to the constructor of `d_impl`,
/// @code
///                         // =================
///                         // class MyHashedMap
///                         // =================
///
/// // CREATORS
/// template <class KEY,
///           class VALUE,
///           class HASHF,
///           class EQUAL,
///           class ALLOCATOR>
/// inline
/// MyHashedMap<KEY, VALUE, HASHF, EQUAL, ALLOCATOR>::MyHashedMap(
///                                         size_type        initialNumBuckets,
///                                         const HASHF&     hash,
///                                         const EQUAL&     keyEqual,
///                                         const ALLOCATOR& allocator)
/// : d_impl(hash, keyEqual, initialNumBuckets, allocator)
/// {
/// }
/// @endcode
/// As with `MyHashedSet`, the `insertIfMissing` method of `bslstl::HashTable`
/// provides the semantics we need: an element is inserted only if no such
/// element (no element with the same key) in the container, and a reference to
/// that element (`node`) is returned.  Here, we use `node` to obtain and return
/// a reference offering modifiable access to the `second` member of the
/// (possibly newly added) element.  Note that the @ref static_cast  from
/// `HashTableLink *` to `HashTableNode *` is valid because the nodes derive
/// from the link type (see @ref bslalg_bidirectionallink  and
/// @ref bslalg_hashtableimputil ).
/// @code
/// // MANIPULATORS
/// template <class KEY,
///           class VALUE,
///           class HASHF,
///           class EQUAL,
///           class ALLOCATOR>
/// inline
/// VALUE& MyHashedMap<KEY, VALUE, HASHF, EQUAL, ALLOCATOR>::operator[](
///                                                             const KEY& key)
/// {
///     typedef typename HashTable::NodeType           HashTableNode;
///     typedef BloombergLP::bslalg::BidirectionalLink HashTableLink;
///
///     HashTableLink *node = d_impl.insertIfMissing(key);
///     return static_cast<HashTableNode *>(node)->value().second;
/// }
/// @endcode
/// Finally, we create `mhm`, an instance of `MyHashedMap`, exercise it, and
/// confirm that it behaves as expected.  We can add an element (with key value
/// of 0).
/// @code
/// MyHashedMap<int, double> mhm;
///
/// mhm[0] = 1.234;
/// assert(1.234 == mhm[0]);
/// @endcode
/// We can change the value of the element with key value 0.
/// @code
/// mhm[0] = 4.321;
/// assert(4.321 == mhm[0]);
/// @endcode
/// We can add a new element (key value 1), without changing the previously
/// existing element (key value 0).
/// @code
/// mhm[1] = 5.768;
/// assert(5.768 == mhm[1]);
/// assert(4.321 == mhm[0]);
/// @endcode
/// Accessing a non-existing element (key value 2) creates that element and
/// populates it with the default value of the mapped value (0.0).
/// @code
/// assert(0.000 == mhm[2]);
/// @endcode
///
/// ## Example 3: Implementing a Hashed Multi-Map Container {#bslstl_hashtable-example-3-implementing-a-hashed-multi-map-container}
///
///
/// Suppose we wish to implement, `MyHashedMultiMap`, a greatly abbreviated
/// version of `bsl::unordered_multimap`.  As with `MyHashedSet` and
/// `MyHashedMap` (see {Example 1}, and {Example 2}, respectively), the
/// `bslstl::HashTable` class template can be used as the basis of our
/// implementation.
///
/// First, we need a class template to configure `bslstl::HashTable` to extract
/// key values in manner appropriate for maps.  The previously defined
/// `UseFirstValueOfPairAsKey` class template (see {Example 2}) suits perfectly.
///
/// Next, we define our `MyHashedMultiMap` class template with an instance of
/// `bslstl::HashTable` (configured using `UseFirstValueOfPairAsKey`) as its
/// sole data member.  In this example, we choose to implement an `insert`
/// method to populate our container, and an @ref equal_range  method (a signature
/// method of the multi containers) to provide access to those elements.
/// @code
///                         // ======================
///                         // class MyHashedMultiMap
///                         // ======================
///
/// template <class KEY,
///           class VALUE,
///           class HASHF     = bsl::hash<     KEY>,
///           class EQUAL     = bsl::equal_to< KEY>,
///           class ALLOCATOR = bsl::allocator<KEY> >
/// class MyHashedMultiMap
/// {
///   private:
///     // PRIVATE TYPES
///     typedef bsl::pair<const KEY, VALUE>                         value_type;
///     typedef bsl::allocator_traits<ALLOCATOR>               AllocatorTraits;
///     typedef typename AllocatorTraits::difference_type      difference_type;
///
///     typedef UseFirstValueOfPairAsKey<bsl::pair<const KEY, VALUE> > HashKey;
///     typedef BloombergLP::bslstl::HashTable<HashKey,
///                                            HASHF,
///                                            EQUAL,
///                                            ALLOCATOR>         ImpHashTable;
///
///     // DATA
///     ImpHashTable d_impl;
///
///   public:
///     // TYPES
///     typedef typename AllocatorTraits::size_type                  size_type;
///     typedef BloombergLP::bslstl::HashTableIterator<
///                                     value_type, difference_type>  iterator;
///     typedef BloombergLP::bslstl::HashTableIterator<
///                          const value_type, difference_type> const_iterator;
///
///     // CREATORS
///     explicit MyHashedMultiMap(
///                          size_type        initialNumBuckets = 0,
///                          const HASHF&     hash              = HASHF(),
///                          const EQUAL&     keyEqual          = EQUAL(),
///                          const ALLOCATOR& allocator         = ALLOCATOR());
///     // Create an empty 'MyHashedMultiMap' object having a maximum load
///     // factor of 1.  Optionally specify at least 'initialNumBuckets' in
///     // this container's initial array of buckets.  If 'initialNumBuckets'
///     // is not supplied, an implementation defined value is used.
///     // Optionally specify a 'hash', a hash-functor used to generate the
///     // hash values associated to the key-value pairs contained in this
///     // object.  If 'hash' is not supplied, a default-constructed object of
///     // (template parameter) 'HASHF' type is used.  Optionally specify a
///     // key-equality functor 'keyEqual' used to verify that two key values
///     // are the same.  If 'keyEqual' is not supplied, a default-constructed
///     // object of (template parameter) 'EQUAL' type is used.  Optionally
///     // specify an 'allocator' used to supply memory.  If 'allocator' is not
///     // supplied, a default-constructed object of the (template parameter)
///     // 'ALLOCATOR' type is used.  If 'ALLOCATOR' is 'bsl::allocator' (the
///     // default), then 'allocator' shall be convertible to
///     // 'bslma::Allocator *'.  If the 'ALLOCATOR' is 'bsl::allocator' and
///     // 'allocator' is not supplied, the currently installed default
///     // allocator is used to supply memory.
///
///     //! ~MyHashedMultiMap() = default;
///         // Destroy this object.
///
///     // MANIPULATORS
///     template <class SOURCE_TYPE>
///     iterator insert(const SOURCE_TYPE& value);
///         // Insert the specified 'value' into this multi-map, and return an
///         // iterator to the newly inserted element.  Note that this method
///         // requires that the (class template parameter) types 'KEY' and
///         // 'VALUE' types both be "copy-constructible", and that the
///         // (function template parameter) 'SOURCE_TYPE' be convertible to
///         // the (class template parameter) 'VALUE' type.
///
///     // ACCESSORS
///     bsl::pair<const_iterator, const_iterator> equal_range(const KEY& key)
///                                                                      const;
///         // Return a pair of iterators providing non-modifiable access to
///         // the sequence of 'value_type' objects in this container matching
///         // the specified 'key', where the first iterator is positioned at
///         // the start of the sequence and the second iterator is positioned
///         // one past the end of the sequence.  If this container contains no
///         // 'value_type' objects matching 'key', then the two returned
///         // iterators will have the same value.
/// };
/// @endcode
/// Then, we implement the methods `MyHashedMultiMap`.  The construct need
/// merely forward its arguments to the constructor of `d_impl`,
/// @code
///                         // ======================
///                         // class MyHashedMultiMap
///                         // ======================
///
/// // CREATORS
/// template <class KEY,
///           class VALUE,
///           class HASHF,
///           class EQUAL,
///           class ALLOCATOR>
/// inline
/// MyHashedMultiMap<KEY, VALUE, HASHF, EQUAL, ALLOCATOR>::MyHashedMultiMap(
///                                         size_type        initialNumBuckets,
///                                         const HASHF&     hash,
///                                         const EQUAL&     keyEqual,
///                                         const ALLOCATOR& allocator)
/// : d_impl(hash, keyEqual, initialNumBuckets, allocator)
/// {
/// }
/// @endcode
/// Note that here we forgo use of the `insertIfMissing` method and use the
/// `insert` method of `bslstl::HashTable`.  This method supports the semantics
/// of the multi containers: there can be more than one element with the same
/// key value.
/// @code
/// // MANIPULATORS
/// template <class KEY,
///           class VALUE,
///           class HASHF,
///           class EQUAL,
///           class ALLOCATOR>
/// template <class SOURCE_TYPE>
/// inline
/// typename MyHashedMultiMap<KEY, VALUE, HASHF, EQUAL, ALLOCATOR>::iterator
///          MyHashedMultiMap<KEY, VALUE, HASHF, EQUAL, ALLOCATOR>::insert(
///                                                   const SOURCE_TYPE& value)
/// {
///     return iterator(d_impl.insert(value));
/// }
/// @endcode
/// The @ref equal_range  method need only convert the values returned by the
/// `findRange` method to the types expected by the caller.
/// @code
/// // ACCESSORS
/// template <class KEY,
///           class VALUE,
///           class HASHF,
///           class EQUAL,
///           class ALLOCATOR>
/// bsl::pair<typename MyHashedMultiMap<KEY,
///                                  VALUE,
///                                  HASHF,
///                                  EQUAL,
///                                  ALLOCATOR>::const_iterator,
///        typename MyHashedMultiMap<KEY,
///                                  VALUE,
///                                  HASHF,
///                                  EQUAL, ALLOCATOR>::const_iterator>
/// MyHashedMultiMap<KEY, VALUE, HASHF, EQUAL, ALLOCATOR>::equal_range(
///                                                       const KEY& key) const
/// {
///     typedef bsl::pair<const_iterator, const_iterator>  ResultType;
///     typedef BloombergLP::bslalg::BidirectionalLink     HashTableLink;
///
///     HashTableLink *first;
///     HashTableLink *last;
///     d_impl.findRange(&first, &last, key);
///     return ResultType(const_iterator(first), const_iterator(last));
/// }
/// @endcode
/// Finally, we create `mhmm`, an instance of `MyHashedMultiMap`, exercise it,
/// and confirm that it behaves as expected.
///
/// We define several aliases to make our code more concise.
/// @code
/// typedef MyHashedMultiMap<int, double>::iterator        Iterator;
/// typedef MyHashedMultiMap<int, double>::const_iterator  ConstIterator;
/// typedef bsl::pair<ConstIterator, ConstIterator>        ConstRange;
/// @endcode
/// Searching for an element (key value 10) in a newly created, empty container
/// correctly shows the absence of any such element.
/// @code
/// MyHashedMultiMap<int, double> mhmm;
///
/// ConstRange range;
/// range = mhmm.equal_range(10);
/// assert(range.first == range.second);
/// @endcode
/// We can insert a value (the pair 10, 100.00) into the container...
/// @code
/// bsl::pair<const int, double> value(10, 100.00);
///
/// Iterator itr;
///
/// itr = mhmm.insert(value);
/// assert(value == *itr);
/// @endcode
/// ... and we can do so again.
/// @code
/// itr = mhmm.insert(value);
/// assert(value == *itr);
/// @endcode
/// We can now find elements with the key value of 10.
/// @code
/// range = mhmm.equal_range(10);
/// assert(range.first != range.second);
/// @endcode
/// As expected, there are two such elements, and both are identical in key
/// value (10) and mapped value (100.00).
/// @code
/// int count = 0;
/// for (ConstIterator cur  = range.first,
///                    end  = range.second;
///                    end != cur; ++cur, ++count) {
///     assert(value == *cur);
/// }
/// assert(2 == count);
/// @endcode
///  }
///
/// ## Example 4: Implementing a Custom Container {#bslstl_hashtable-example-4-implementing-a-custom-container}
///
///
/// Although the `bslstl::HashTable` class was created to be a common
/// implementation for the standard unordered classes, this class can also be
/// used in its own right to address other user problems.
///
/// Suppose that we wish to retain a record of sales orders, that each record is
/// characterized by several integer attributes, and that we must be able to
/// find records based on *any* of those attributes.  We can use
/// `bslstl::HashTable` to implement a custom container supporting multiple
/// key-values.
///
/// First, we define `MySalesRecord`, our record class:
/// @code
/// enum { MAX_DESCRIPTION_SIZE = 16 };
///
/// typedef struct MySalesRecord {
///     int  orderNumber;                        // unique
///     int  customerId;                         // no constraint
///     int  vendorId;                           // no constraint
///     char description[MAX_DESCRIPTION_SIZE];  // ASCII string
/// } MySalesRecord;
/// @endcode
/// Notice that only each `orderNumber` is unique.  We expect multiple sales to
/// any given customer (`customerId`) and multiple sales by any given vendor
/// (`vendorId`).
///
/// We will use a `bslstl::HashTable` object (a hashtable) to save record values
/// based on the unique `orderNumber`, and two auxiliary hashtables to provide
/// map `customerId` and `vendorId` values to the addresses of the records in
/// the first `bslstl::HashTable` object.  Note that this implementation relies
/// on the fact that nodes in our hashtables remain stable until they are
/// removed and that in this application we do *not* allow the removal (or
/// modification) of records once they are inserted.
///
/// To configure these hashtables, we will need several policy objects to
/// extract relevant portions the `MySalesRecord` objects for hashing.
///
/// Next, define `UseOrderNumberAsKey`, a policy class for the hashtable holding
/// the sales record objects.  Note that the `ValueType` is `MySalesRecord` and
/// that the `extractKey` method selects the `orderNumber` attribute:
/// @code
///                         // ==========================
///                         // struct UseOrderNumberAsKey
///                         // ==========================
///
/// struct UseOrderNumberAsKey {
///     // This 'struct' provides a namespace for types and methods that define
///     // the policy by which the key value of a hashed container (i.e., the
///     // value passed to the hasher) is extracted from the objects stored in
///     // the hashed container (the 'value' type).
///
///     typedef MySalesRecord ValueType;
///         // Alias for 'MySalesRecord', the type stored in the first
///         // hashtable.
///
///     typedef int KeyType;
///         // Alias for the type passed to the hasher by the hashed container.
///         // In this policy, the value passed to the hasher is the
///         // 'orderNumber' attribute, an 'int' type.
///
///     static const KeyType& extractKey(const ValueType& value);
///         // Return the key value for the specified 'value'.  In this policy,
///         // that is the 'orderNumber' attribute of 'value'.
/// };
///
///                         // --------------------------
///                         // struct UseOrderNumberAsKey
///                         // --------------------------
///
/// inline
/// const UseOrderNumberAsKey::KeyType&
///       UseOrderNumberAsKey::extractKey(const ValueType& value)
/// {
///     return value.orderNumber;
/// }
/// @endcode
/// Then, we define `UseCustomerIdAsKey`, the policy class for the hashtable
/// that will multiply map `customerId` to the addresses of records in the first
/// hashtable.  Note that in this policy class the `ValueType` is
/// `const MySalesRecord *`.
/// @code
///                         // =========================
///                         // struct UseCustomerIdAsKey
///                         // =========================
///
/// /// This `struct` provides a namespace for types and methods that define
/// /// the policy by which the key value of a hashed container (i.e., the
/// /// value passed to the hasher) is extracted from the objects stored in
/// /// the hashed container (the `value` type).
/// struct UseCustomerIdAsKey {
///
///     typedef const MySalesRecord *ValueType;
///         // Alias for 'const MySalesRecord *', the type stored in second
///         // hashtable, a pointer to the record stored in the first
///         // hashtable.
///
///     typedef int KeyType;
///         // Alias for the type passed to the hasher by the hashed container.
///         // In this policy, the value passed to the hasher is the
///         // 'orderNumber' attribute, an 'int' type.
///
///     static const KeyType& extractKey(const ValueType& value);
///         // Return the key value for the specified 'value'.  In this policy,
///         // that is the 'customerId' attribute of 'value'.
/// };
///
///                         // -------------------------
///                         // struct UseCustomerIdAsKey
///                         // -------------------------
///
/// inline
/// const UseCustomerIdAsKey::KeyType&
///       UseCustomerIdAsKey::extractKey(const ValueType& value)
/// {
///     return value->customerId;
/// }
/// @endcode
/// Notice that, since the values in the second hashtable are addresses, the
/// key-value is extracted by reference.  This second hashtable allows what
/// map-like semantics, *without* having to store key-values; those reside in
/// the records in the first hashtable.
///
/// The `UseVendorIdAsKey` class, the policy class for the hashtable providing
/// an index by `vendorId`, is almost a near clone of `UseCustomerIdAsKey`.  It
/// is shown for completeness:
/// @code
///                         // =======================
///                         // struct UseVendorIdAsKey
///                         // ========================
///
/// /// This `struct` provides a namespace for types and methods that define
/// /// the policy by which the key value of a hashed container (i.e., the
/// /// value passed to the hasher) is extracted from the objects stored in
/// /// the hashed container (the `value` type).
/// struct UseVendorIdAsKey {
///
///     typedef const MySalesRecord *ValueType;
///         // Alias for 'const MySalesRecord *', the type stored in second
///         // hashtable, a pointer to the record stored in the first
///         // hashtable.
///
///     typedef int KeyType;
///         // Alias for the type passed to the hasher by the hashed container.
///         // In this policy, the value passed to the hasher is the
///         // 'vendorId' attribute, an 'int' type.
///
///     static const KeyType& extractKey(const ValueType& value);
///         // Return the key value for the specified 'value'.  In this policy,
///         // that is the 'vendorId' attribute of 'value'.
/// };
///
///                         // -----------------------
///                         // struct UseVendorIdAsKey
///                         // -----------------------
///
/// inline
/// const UseVendorIdAsKey::KeyType&
///       UseVendorIdAsKey::extractKey(const ValueType& value)
/// {
///     return value->vendorId;
/// }
/// @endcode
/// Next, we define `MySalesRecordContainer`, our customized container:
/// @code
///                         // ----------------------------
///                         // class MySalesRecordContainer
///                         // ----------------------------
///
/// class MySalesRecordContainer
/// {
///   private:
///     // PRIVATE TYPES
///     typedef BloombergLP::bslstl::HashTable<
///                   UseOrderNumberAsKey,
///                   bsl::hash<    UseOrderNumberAsKey::KeyType>,
///                   bsl::equal_to<UseOrderNumberAsKey::KeyType> >
///                                                       RecordsByOrderNumber;
///     typedef bsl::allocator_traits<
///           bsl::allocator<UseOrderNumberAsKey::ValueType> > AllocatorTraits;
///     typedef AllocatorTraits::difference_type               difference_type;
/// @endcode
/// The `ItrByOrderNumber` type is used to provide access to the elements of the
/// first hash table, the one that stores the records.
/// @code
///
///       typedef BloombergLP::bslstl::HashTableIterator<const MySalesRecord,
///                                                      difference_type>
///                                                             ItrByOrderNumber;
/// @endcode
/// The `ItrPtrById` type is used to provide access to the elements of the other
/// hashtables, the ones that store pointers into the first hashtable.
/// @code
///     typedef BloombergLP::bslstl::HashTableIterator<const MySalesRecord *,
///                                                    difference_type>
///                                                                 ItrPtrById;
/// @endcode
/// If we were to provide iterators of type `ItrPtrById` to our users,
/// dereferencing the iterator would provide a `MySalesRecord` pointer, which
/// would then have to be dereferences.  Instead, we use `ItrPtrById` to define
/// `ItrById` in which accessors have been overridden to provide that extra
/// dereference implicitly.
/// @code
///     class ItrById : public ItrPtrById
///     {
///       public:
///         // CREATORS
///         explicit ItrById(bslalg::BidirectionalLink *node)
///         : ItrPtrById(node)
///         {
///         }
///
///         // ACCESSORS
///         const MySalesRecord& operator*() const
///         {
///             return *ItrPtrById::operator*();
///         }
///
///         const MySalesRecord *operator->() const
///         {
///             return &(*ItrPtrById::operator*());
///         }
///     };
///
///     typedef BloombergLP::bslstl::HashTable<
///                   UseCustomerIdAsKey,
///                   bsl::hash<    UseCustomerIdAsKey::KeyType>,
///                   bsl::equal_to<UseCustomerIdAsKey::KeyType> >
///                                                    RecordsPtrsByCustomerId;
///     typedef BloombergLP::bslstl::HashTable<
///                   UseVendorIdAsKey,
///                   bsl::hash<    UseVendorIdAsKey::KeyType>,
///                   bsl::equal_to<UseVendorIdAsKey::KeyType> >
///                                                      RecordsPtrsByVendorId;
///     // DATA
///     RecordsByOrderNumber    d_recordsByOrderNumber;
///     RecordsPtrsByCustomerId d_recordptrsByCustomerId;
///     RecordsPtrsByVendorId   d_recordptrsByVendorId;
///
///   public:
///     // PUBLIC TYPES
///     typedef ItrByOrderNumber  ConstItrByOrderNumber;
///     typedef ItrById           ConstItrById;
///
///     // CREATORS
///     explicit MySalesRecordContainer(bslma::Allocator *basicAllocator = 0);
///         // Create an empty 'MySalesRecordContainer' object.  If
///         // 'basicAllocator' is 0, the currently installed default allocator
///         // is used.
///
///     //! ~MySalesRecordContainer() = default;
///         // Destroy this object.
///
///     // MANIPULATORS
///     bsl::pair<ConstItrByOrderNumber, bool> insert(
///                                                const MySalesRecord& value);
///         // Insert the specified 'value' into this set if the 'value' does
///         // not already exist in this set; otherwise, this method has no
///         // effect.  Return a pair whose 'first' member is an iterator
///         // providing non-modifiable access to the (possibly newly inserted)
///         // 'MySalesRecord' object having 'value' and whose 'second' member
///         // is 'true' if a new element was inserted, and 'false' if 'value'
///         // was already present.
///
///     // ACCESSORS
///     ConstItrByOrderNumber cend() const;
///         // Return an iterator providing non-modifiable access to the
///         // past-the-end element (in the sequence of 'MySalesRecord'
///         // objects) maintained by this set.
///
///     ConstItrByOrderNumber findByOrderNumber(int value) const;
///         // Return an iterator providing non-modifiable access to the
///         // 'MySalesRecord' object in this set having the specified 'value',
///         // if such an entry exists, and the iterator returned by the 'cend'
///         // method otherwise.
/// @endcode
/// Notice that this interface provides map-like semantics for finding records.
/// We need only specify the `orderNumber` attribute of the record of interest;
/// however, the return value is set-like: we get access to the record, not the
/// more complicated key-value/record pair that a map would have provided.
///
/// Internally, the hash table need only store the records themselves.  A map
/// would have had to manage key-value/record pairs, where the key-value would
/// be a copy of part of the record.
/// @code
///     bsl::pair<ConstItrById, ConstItrById> findByCustomerId(int value)
///                                                                      const;
///         // Return a pair of iterators providing non-modifiable access to
///         // the sequence of 'MySalesRecord' objects in this container having
///         // a 'customerId' attribute equal to the specified 'value' where
///         // the first iterator is positioned at the start of the sequence
///         // and the second iterator is positioned one past the end of the
///         // sequence.  If this container has no such objects, then the two
///         // iterators will be equal.
///
///     bsl::pair<ConstItrById, ConstItrById> findByVendorId(int value) const;
///         // Return a pair of iterators providing non-modifiable access to
///         // the sequence of 'MySalesRecord' objects in this container having
///         // a 'vendorId' attribute equal to the specified 'value' where the
///         // first iterator is positioned at the start of the sequence and
///         // the second iterator is positioned one past the end of the
///         // sequence.  If this container has no such objects, then the two
///         // iterators will be equal.
/// };
/// @endcode
/// Then, we implement the methods of `MySalesRecordContainer`, our customized
/// container:
/// @code
///                         // ----------------------------
///                         // class MySalesRecordContainer
///                         // ----------------------------
///
/// // CREATORS
/// inline
/// MySalesRecordContainer::MySalesRecordContainer(
///                                           bslma::Allocator *basicAllocator)
/// : d_recordsByOrderNumber(basicAllocator)
/// , d_recordptrsByCustomerId(basicAllocator)
/// , d_recordptrsByVendorId(basicAllocator)
/// {
/// }
///
/// // MANIPULATORS
/// inline
/// bsl::pair<MySalesRecordContainer::ConstItrByOrderNumber, bool>
/// MySalesRecordContainer::insert(const MySalesRecord& value)
/// {
///     // Insert into internal container that will own the record.
///
///     bool                                    isInsertedFlag = false;
///     BloombergLP::bslalg::BidirectionalLink *result         =
///             d_recordsByOrderNumber.insertIfMissing(&isInsertedFlag, value);
///
///     // Index by other record attributes
///
///     RecordsByOrderNumber::NodeType *nodePtr =
///                      static_cast<RecordsByOrderNumber::NodeType *>(result);
///
///     d_recordptrsByCustomerId.insert(&nodePtr->value());
///       d_recordptrsByVendorId.insert(&nodePtr->value());
///
///     // Return of insertion.
///
///     return bsl::pair<ConstItrByOrderNumber, bool>(
///                                              ConstItrByOrderNumber(result),
///                                              isInsertedFlag);
/// }
///
/// // ACCESSORS
/// inline
/// MySalesRecordContainer::ConstItrByOrderNumber
/// MySalesRecordContainer::cend() const
/// {
///     return ConstItrByOrderNumber();
/// }
///
/// inline
/// MySalesRecordContainer::ConstItrByOrderNumber
/// MySalesRecordContainer::findByOrderNumber(int value) const
/// {
///     return ConstItrByOrderNumber(d_recordsByOrderNumber.find(value));
/// }
///
/// inline
/// bsl::pair<MySalesRecordContainer::ConstItrById,
///        MySalesRecordContainer::ConstItrById>
/// MySalesRecordContainer::findByCustomerId(int value) const
/// {
///     typedef BloombergLP::bslalg::BidirectionalLink HashTableLink;
///
///     HashTableLink *first;
///     HashTableLink *last;
///     d_recordptrsByCustomerId.findRange(&first, &last, value);
///
///     return bsl::pair<ConstItrById, ConstItrById>(ConstItrById(first),
///                                                  ConstItrById(last));
/// }
///
/// inline
/// bsl::pair<MySalesRecordContainer::ConstItrById,
///        MySalesRecordContainer::ConstItrById>
/// MySalesRecordContainer::findByVendorId(int value) const
/// {
///     typedef BloombergLP::bslalg::BidirectionalLink HashTableLink;
///
///     HashTableLink *first;
///     HashTableLink *last;
///     d_recordptrsByVendorId.findRange(&first, &last, value);
///
///     return bsl::pair<ConstItrById, ConstItrById>(ConstItrById(first),
///                                                  ConstItrById(last));
/// }
/// @endcode
/// Now, create an empty container and load it with some sample data.
/// @code
///     MySalesRecordContainer msrc;
///
///     const MySalesRecord DATA[] = {
///         { 1000, 100, 10, "hello" },
///         { 1001, 100, 20, "world" },
///         { 1002, 200, 10, "how" },
///         { 1003, 200, 20, "are" },
///         { 1004, 100, 10, "you" },
///         { 1005, 100, 20, "today" }
///     };
///     const int numDATA = sizeof DATA / sizeof *DATA;
///
///     printf("Insert sales records into container.\n");
///
///     for (int i = 0; i < numDATA; ++i) {
///         const int orderNumber   = DATA[i].orderNumber;
///         const int customerId    = DATA[i].customerId;
///         const int vendorId      = DATA[i].vendorId;
///         const char *description = DATA[i].description;
///
///         printf("%d: %d %d %s\n",
///                orderNumber, customerId, vendorId, description);
///
///         typedef MySalesRecordContainer::ConstItrByOrderNumber MyConstItr;
///         typedef bsl::pair<MyConstItr, bool>                   InsertResult;
///
///         const InsertResult status = msrc.insert(DATA[i]);
///         assert(msrc.cend() != status.first);
///         assert(true        == status.second);
///     }
/// @endcode
/// We find on standard output:
/// @code
/// Insert sales records into container.
/// 1000: 100 10 hello
/// 1001: 100 20 world
/// 1002: 200 10 how
/// 1003: 200 20 are
/// 1004: 100 10 you
/// 1005: 100 20 today
/// @endcode
/// We can search our container by order number and find the expected records.
/// @code
///     printf("Find sales records by order number.\n");
///     for (int i = 0; i < numDATA; ++i) {
///         const int orderNumber   = DATA[i].orderNumber;
///         const int customerId    = DATA[i].customerId;
///         const int vendorId      = DATA[i].vendorId;
///         const char *description = DATA[i].description;
///
///         printf("%d: %d %d %s\n",
///                orderNumber, customerId, vendorId, description);
///
///         MySalesRecordContainer::ConstItrByOrderNumber itr =
///                                        msrc.findByOrderNumber(orderNumber);
///         assert(msrc.cend() != itr);
///         assert(orderNumber == itr->orderNumber);
///         assert(customerId  == itr->customerId);
///         assert(vendorId    == itr->vendorId);
///         assert(0 == strcmp(description, itr->description));
///     }
/// @endcode
/// We find on standard output:
/// @code
/// Find sales records by order number.
/// 1000: 100 10 hello
/// 1001: 100 20 world
/// 1002: 200 10 how
/// 1003: 200 20 are
/// 1004: 100 10 you
/// 1005: 100 20 today
/// @endcode
/// We can search our container by customer identifier and find the expected
/// records.
/// @code
///     printf("Find sales records by customer identifier.\n");
///
///     typedef MySalesRecordContainer::ConstItrById MyConstItrById;
///
///     for (int customerId = 100; customerId <= 200; customerId += 100) {
///         bsl::pair<MyConstItrById, MyConstItrById> result =
///                                          msrc.findByCustomerId(customerId);
///         typedef bsl::iterator_traits<
///                                 MyConstItrById>::difference_type CountType;
///         const CountType count = bsl::distance(result.first, result.second);
///         printf("customerId %d, count %d\n", customerId, count);
///
///         for (MySalesRecordContainer::ConstItrById itr  = result.first,
///                                                   end  = result.second;
///                                                   end != itr; ++itr) {
///             printf("\t\t%d %d %d %s\n",
///                    itr->orderNumber,
///                    itr->customerId,
///                    itr->vendorId,
///                    itr->description);
///         }
///     }
/// @endcode
/// We find on standard output:
/// @code
/// Find sales records by customer identifier.
/// customerId 100, count 4
///             1005 100 20 today
///             1004 100 10 you
///             1001 100 20 world
///             1000 100 10 hello
/// customerId 200, count 2
///             1003 200 20 are
///             1002 200 10 how
/// @endcode
/// Lastly, we can search our container by vendor identifier and find the
/// expected records.
/// @code
///     printf("Find sales records by vendor identifier.\n");
///
///     typedef MySalesRecordContainer::ConstItrById MyConstItrById;
///
///     for (int vendorId = 10; vendorId <= 20; vendorId += 10) {
///         bsl::pair<MyConstItrById, MyConstItrById> result =
///                                              msrc.findByVendorId(vendorId);
///         typedef bsl::iterator_traits<
///                                 MyConstItrById>::difference_type CountType;
///         const CountType count = bsl::distance(result.first, result.second);
///
///         printf("vendorId %d, count %d\n", vendorId, count);
///
///         for (MySalesRecordContainer::ConstItrById itr  = result.first,
///                                                   end  = result.second;
///                                                   end != itr; ++itr) {
///             printf("\t\t%d %d %d %s\n",
///                    (*itr).orderNumber,
///                    (*itr).customerId,
///                    (*itr).vendorId,
///                    (*itr).description);
///         }
///     }
/// @endcode
/// We find on standard output:
/// @code
/// Find sales records by vendor identifier.
/// vendorId 10, count 3
///             1004 100 10 you
///             1002 200 10 how
///             1000 100 10 hello
/// vendorId 20, count 3
///             1005 100 20 today
///             1003 200 20 are
///             1001 100 20 world
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslstl
 * @{
 */
/** @addtogroup bslstl_hashtable
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bslstl_bidirectionalnodepool.h>
 
#include <bslalg_bidirectionallink.h>
#include <bslalg_bidirectionalnode.h>
#include <bslalg_functoradapter.h>
#include <bslalg_hashtableanchor.h>
#include <bslalg_hashtablebucket.h>
#include <bslalg_hashtableimputil.h>
 
#include <bslma_allocatortraits.h>
#include <bslma_allocatorutil.h>
#include <bslma_destructorguard.h>
#include <bslma_bslallocator.h>
#include <bslma_usesbslmaallocator.h>
 
#include <bslmf_addlvaluereference.h>
#include <bslmf_assert.h>
#include <bslmf_conditional.h>
#include <bslmf_enableif.h>
#include <bslmf_isbitwisemoveable.h>
#include <bslmf_isfunction.h>
#include <bslmf_ispointer.h>
#include <bslmf_istransparentpredicate.h>
#include <bslmf_movableref.h>
#include <bslmf_util.h>    // 'forward(V)'
 
#include <bsls_assert.h>
#include <bsls_bslexceptionutil.h>
#include <bsls_compilerfeatures.h>
#include <bsls_objectbuffer.h>
#include <bsls_performancehint.h>
#include <bsls_platform.h>
#include <bsls_util.h>     // 'forward<T>(V)'
 
#include <algorithm>  // for fill_n, max, swap (C++03)
#include <cstddef>    // for 'size_t'
#include <cstring>    // for 'memset'
#include <limits>     // for numeric_limits
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
#include <tuple>      // for forward_as_tuple (C++11)
#endif
#include <utility>    // for swap (C++17)
 
#ifndef BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
#include <bsls_nativestd.h>
#endif // BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
 
#if BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
// Include version that can be compiled with C++03
// Generated on Thu Oct 21 10:11:37 2021
// Command line: sim_cpp11_features.pl bslstl_hashtable.h
# define COMPILING_BSLSTL_HASHTABLE_H
# include <bslstl_hashtable_cpp03.h>
# undef COMPILING_BSLSTL_HASHTABLE_H
#else
 
 
 
namespace bslstl {
 
template <class KEY_CONFIG,
          class HASHER,
          class COMPARATOR,
          class ALLOCATOR = ::bsl::allocator<typename KEY_CONFIG::ValueType> >
class HashTable;
 
template <class FACTORY>
class HashTable_ArrayProctor;
 
template <class FACTORY>
class HashTable_NodeProctor;
 
template <class FUNCTOR>
class HashTable_ComparatorWrapper;
 
template <class FUNCTOR>
class HashTable_ComparatorWrapper<const FUNCTOR>;
 
template <class FUNCTOR>
class HashTable_ComparatorWrapper<FUNCTOR &>;
 
template <class FUNCTOR>
class HashTable_HashWrapper;
 
template <class FUNCTOR>
class HashTable_HashWrapper<const FUNCTOR>;
 
template <class FUNCTOR>
class HashTable_HashWrapper<FUNCTOR &>;
 
struct HashTable_ImpDetails;
struct HashTable_Util;
 
                       // ======================
                       // class CallableVariable
                       // ======================
 
/// This metafunction returns a `type` that is an alias for `CALLABLE`
/// unless that is a function type, in which case it is an alias for
/// `CALLABLE &`.  This should be used to declare variables of an arbitrary
/// callable type, typically a template type parameter, that may turn out to
/// be a function type.  Note that this metafunction is necessary as the C++
/// language does not allow variables of function type, nor may functions
/// return a function type.
template <class CALLABLE>
struct CallableVariable {
 
    // TYPES
    typedef typename bsl::conditional<
                            bsl::is_function<CALLABLE>::value,
                            typename bsl::add_lvalue_reference<CALLABLE>::type,
                            CALLABLE>::type type;
};
 
                           // ===========================
                           // class HashTable_HashWrapper
                           // ===========================
 
/// This class provides a wrapper around a functor satisfying the `Hash`
/// requirements (@ref bslstl_hash ) such that the function call operator is
/// always declared as `const` qualified.
///
/// TBD Provide an optimization for the case of an empty base functor, where
///     we can safely const_cast want calling the base class operator.
///
/// Note that we would only one class, not two, with C++11 variadic
/// templates and perfect forwarding, and we could also easily detect
/// whether or not `FUNCTOR` provided a const-qualified `operator()`.
///
/// See @ref bslstl_hashtable 
template <class FUNCTOR>
class HashTable_HashWrapper {
 
  private:
    mutable FUNCTOR d_functor;
 
  public:
    // CREATORS
 
    /// Create a `HashTable_HashWrapper` object wrapping a `FUNCTOR` that
    /// has its default value.
    HashTable_HashWrapper();
 
    /// Create a `HashTable_HashWrapper` object wrapping a `FUNCTOR` that is
    /// a copy of the specified `fn`.
    explicit HashTable_HashWrapper(const FUNCTOR& fn);
 
    // MANIPULATORS
 
    /// Exchange the value of this object with the specified `other` object.
    void swap(HashTable_HashWrapper &other);
 
    // ACCESSORS
 
    /// Call the wrapped `functor` with the specified `arg` and return the
    /// result.  Note that `ARG_TYPE` will typically be deduced as a `const`
    /// type.
    template <class ARG_TYPE>
    std::size_t operator()(ARG_TYPE& arg) const;
 
    /// Return a reference providing non-modifiable access to the hash
    /// functor wrapped by this object.
    const FUNCTOR& functor() const;
};
 
/// This partial specialization handles `const` qualified functors, that may
/// not be stored as a `mutable` member in the primary template.  The need
/// to wrap such functors diminishes greatly, as there is no need to play
/// mutable tricks to invoke the function call operator.  An alternative to
/// providing this specialization would be to skip the wrapper entirely if
/// using a `const` qualified functor in a `HashTable`.  Note that this type
/// has a `const` qualified data member, so is neither assignable nor
/// swappable.
template <class FUNCTOR>
class HashTable_HashWrapper<const FUNCTOR> {
 
  private:
    const FUNCTOR d_functor;
 
  public:
    // CREATORS
 
    /// Create a `HashTable_HashWrapper` object wrapping a `FUNCTOR` that
    /// has its default value.
    HashTable_HashWrapper();
 
    /// Create a `HashTable_HashWrapper` object wrapping a `FUNCTOR` that is
    /// a copy of the specified `fn`.
    explicit HashTable_HashWrapper(const FUNCTOR& fn);
 
    // ACCESSORS
 
    /// Call the wrapped `functor` with the specified `arg` and return the
    /// result.  Note that `ARG_TYPE` will typically be deduced as a `const`
    /// type.
    template <class ARG_TYPE>
    std::size_t operator()(ARG_TYPE& arg) const;
 
    /// Return a reference providing non-modifiable access to the hash
    /// functor wrapped by this object.
    const FUNCTOR& functor() const;
};
 
/// This partial specialization handles `const` qualified functors, that may
/// not be stored as a `mutable` member in the primary template.  Note that
/// the `FUNCTOR` type itself may be `const`-qualified, so this one partial
/// template specialization also handles `const FUNCTOR&` references.  In
/// order to correctly parse with the reference-binding rules, we drop the
/// `const` in front of many of the references to `FUNCTOR` seen in the
/// primary template definition.  Note that this type has a reference data
/// member, so is not default constructible, assignable or swappable.
template <class FUNCTOR>
class HashTable_HashWrapper<FUNCTOR &> {
 
  private:
    FUNCTOR& d_functor;
 
  public:
    // CREATORS
 
    /// Create a `HashTable_HashWrapper` object wrapping a `FUNCTOR` that is
    /// a copy of the specified `fn`.
    explicit HashTable_HashWrapper(FUNCTOR& fn);
 
    // ACCESSORS
 
    /// Call the wrapped `functor` with the specified `arg` and return the
    /// result.  Note that `ARG_TYPE` will typically be deduced as a `const`
    /// type.
    template <class ARG_TYPE>
    std::size_t operator()(ARG_TYPE& arg) const;
 
    /// Return a reference providing non-modifiable access to the hash
    /// functor wrapped by this object.
    FUNCTOR& functor() const;
};
 
/// Swap the functor wrapped by the specified `a` object with the functor
/// wrapped by the specified `b` object.
template <class FUNCTOR>
void swap(HashTable_HashWrapper<FUNCTOR> &a,
          HashTable_HashWrapper<FUNCTOR> &b);
 
                           // =================================
                           // class HashTable_ComparatorWrapper
                           // =================================
 
/// This class provides a wrapper around a functor that can compare two
/// values and return a `bool`, so that the function call operator is always
/// declared as `const` qualified.
///
/// TBD Provide an optimization for the case of an empty base functor, where
///     we can safely const_cast want calling the base class operator.
///
/// See @ref bslstl_hashtable 
template <class FUNCTOR>
class HashTable_ComparatorWrapper {
 
  private:
    mutable FUNCTOR d_functor;
 
  public:
    // CREATORS
 
    /// Create a `HashTable_ComparatorWrapper` object wrapping a `FUNCTOR`
    /// that has its default value.
    HashTable_ComparatorWrapper();
 
    /// Create a `HashTable_ComparatorWrapper` object wrapping a `FUNCTOR`
    /// that is a copy of the specified `fn`.
    explicit HashTable_ComparatorWrapper(const FUNCTOR& fn);
 
    // MANIPULATORS
 
    /// Exchange the value of this object with the specified `other` object.
    void swap(HashTable_ComparatorWrapper &other);
 
    // ACCESSORS
 
    /// Call the wrapped `functor` with the specified `arg1` and `arg2` (in
    /// that order) and return the result.  Note that `ARGn_TYPE` will
    /// typically be deduced as a `const` type.
    template <class ARG1_TYPE, class ARG2_TYPE>
    bool operator()(ARG1_TYPE& arg1, ARG2_TYPE& arg2) const;
 
    /// Return a reference providing non-modifiable access to the hash
    /// functor wrapped by this object.
    const FUNCTOR& functor() const;
};
 
/// This partial specialization handles `const` qualified functors, that may
/// not be stored as a `mutable` member in the primary template.  The need
/// to wrap such functors diminishes greatly, as there is no need to play
/// mutable tricks to invoke the function call operator.  An alternative to
/// providing this specialization would be to skip the wrapper entirely if
/// using a `const` qualified functor in a `HashTable`.  Note that this type
/// has a `const` qualified data member, so is neither assignable nor
/// swappable.
template <class FUNCTOR>
class HashTable_ComparatorWrapper<const FUNCTOR> {
 
  private:
    const FUNCTOR d_functor;
 
  public:
    // CREATORS
 
    /// Create a `HashTable_ComparatorWrapper` object wrapping a `FUNCTOR`
    /// that has its default value.
    HashTable_ComparatorWrapper();
 
    /// Create a `HashTable_ComparatorWrapper` object wrapping a `FUNCTOR`
    /// that is a copy of the specified `fn`.
    explicit HashTable_ComparatorWrapper(const FUNCTOR& fn);
 
    // ACCESSORS
 
    /// Call the wrapped `functor` with the specified `arg1` and `arg2` (in
    /// that order) and return the result.  Note that `ARGn_TYPE` will
    /// typically be deduced as a `const` type.
    template <class ARG1_TYPE, class ARG2_TYPE>
    bool operator()(ARG1_TYPE& arg1, ARG2_TYPE& arg2) const;
 
    /// Return a reference providing non-modifiable access to the hash
    /// functor wrapped by this object.
    const FUNCTOR& functor() const;
};
 
/// This partial specialization handles `const` qualified functors, that may
/// not be stored as a `mutable` member in the primary template.  Note that
/// the `FUNCTOR` type itself may be `const`-qualified, so this one partial
/// template specialization also handles `const FUNCTOR&` references.  In
/// order to correctly parse with the reference-binding rules, we drop the
/// `const` in front of many of the references to `FUNCTOR` seen in the
/// primary template definition.  Note that this type has a reference data
/// member, so is not default constructible, assignable or swappable.
template <class FUNCTOR>
class HashTable_ComparatorWrapper<FUNCTOR &> {
 
  private:
    FUNCTOR& d_functor;
 
  public:
    // CREATORS
 
    /// Create a `HashTable_ComparatorWrapper` object wrapping a `FUNCTOR`
    /// that is a copy of the specified `fn`.
    explicit HashTable_ComparatorWrapper(FUNCTOR& fn);
 
    // ACCESSORS
 
    /// Call the wrapped `functor` with the specified `arg1` and `arg2` (in
    /// that order) and return the result.  Note that `ARGn_TYPE` will
    /// typically be deduced as a `const` type.
    template <class ARG1_TYPE, class ARG2_TYPE>
    bool operator()(ARG1_TYPE& arg1, ARG2_TYPE& arg2) const;
 
    /// Return a reference providing non-modifiable access to the hash
    /// functor wrapped by this object.
    FUNCTOR& functor() const;
};
 
/// Swap the functor wrapped by the specified `lhs` object with the functor
/// wrapped by the specified `rhs` object.
template <class FUNCTOR>
void swap(HashTable_ComparatorWrapper<FUNCTOR> &lhs,
          HashTable_ComparatorWrapper<FUNCTOR> &rhs);
 
                           // ===============
                           // class HashTable
                           // ===============
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
class HashTable_ImplParameters;
 
/// This class template implements a value-semantic container type holding
/// an unordered sequence of (possibly duplicate) elements, that can be
/// rapidly accessed using their key, with the constraint on the container
/// that elements whose keys compare equal according to the specified
/// `COMPARATOR` will be stored in a stable, contiguous sequence within the
/// container.  The value type and key type of the elements maintained by a
/// `HashTable` are determined by aliases provided through the (template
/// parameter) type `KEY_CONFIG`.  Elements in a `HashTable` are stored in
/// "nodes" that are allocated using an allocator of the specified
/// `ALLOCATOR` type (rebound to the node type), and elements are
/// constructed directly in the node using the allocator as described in the
/// C++11 standard under the allocator-aware container requirements in
/// ([container.requirements.general], C++11 23.2.1).  The (template
/// parameter) types `HASHER` and `COMPARATOR` shall be `copy-constructible`
/// function-objects.  `HASHER` shall support a function call operator
/// compatible with the following statements:
/// @code
/// HASHER              hash;
/// KEY_CONFIG::KeyType key;
/// std::size_t result = hash(key);
/// @endcode
/// where the definition of the called function meets the requirements of a
/// hash function, as specified in @ref bslstl_hash .  `COMPARATOR` shall
/// support the a function call operator compatible with the following
/// statements:
/// @code
/// COMPARATOR          compare;
/// KEY_CONFIG::KeyType key1, key2;
/// bool result = compare(key1, key2);
/// @endcode
/// where the definition of the called function defines an equivalence
/// relationship on keys that is both reflexive and transitive.  The
/// `HASHER` and `COMPARATOR` attributes of this class are further
/// constrained, such for any two objects whose keys compare equal by the
/// comparator, shall produce the same value from the hasher.
///
/// This class:
/// * supports a complete set of *value-semantic* operations
///   - except for `bdex` serialization
/// * is *exception-neutral* (agnostic except for the `at` method)
/// * is *alias-safe*
/// * is `const` *thread-safe*
/// For terminology see @ref bsldoc_glossary .
///
/// See @ref bslstl_hashtable 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
class HashTable {
 
  public:
    // TYPES
    typedef ALLOCATOR                                 AllocatorType;
    typedef ::bsl::allocator_traits<AllocatorType>    AllocatorTraits;
    typedef typename KEY_CONFIG::KeyType              KeyType;
    typedef typename KEY_CONFIG::ValueType            ValueType;
    typedef bslalg::BidirectionalNode<ValueType>      NodeType;
    typedef typename AllocatorTraits::size_type       SizeType;
    typedef typename bsl::remove_const<KeyType>::type NonConstKeyType;
 
  private:
    // PRIVATE TYPES
    typedef
    HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>
                                                                ImplParameters;
 
    /// This typedef is a convenient alias for the utility associated with
    /// movable references.
    typedef bslmf::MovableRefUtil                               MoveUtil;
 
    // CONSISTENCY CHECKS
 
    // Assert consistency checks against Machiavellian users, specializing an
    // allocator for a specific type to have different propagation traits to
    // the primary template.
 
    typedef typename AllocatorTraits::template rebind_traits<NodeType>
        ReboundTraits;
 
    BSLMF_ASSERT(
        ReboundTraits::propagate_on_container_copy_assignment::value ==
        AllocatorTraits::propagate_on_container_copy_assignment::value);
 
    BSLMF_ASSERT(
        ReboundTraits::propagate_on_container_move_assignment::value ==
        AllocatorTraits::propagate_on_container_move_assignment::value);
 
    BSLMF_ASSERT(ReboundTraits::propagate_on_container_swap::value ==
                 AllocatorTraits::propagate_on_container_swap::value);
 
  private:
    // DATA
    ImplParameters      d_parameters;    // policies governing table behavior
    bslalg::HashTableAnchor
                        d_anchor;        // list root and bucket array
    SizeType            d_size;          // number of elements in this table
    SizeType            d_capacity;      // max number of elements before a
                                         // rehash is required (computed from
                                         // 'd_maxLoadFactor')
    float               d_maxLoadFactor; // maximum permitted load factor
 
  private:
    // PRIVATE MANIPULATORS
 
    /// Copy the sequence of elements from the list starting at the
    /// specified `cursor` and having `size` elements.  Allocate a bucket
    /// array sufficiently large to store `size` elements while respecting
    /// the `maxLoadFactor`, and index the copied list into that new array
    /// of hash buckets.  This hash table then takes ownership of the list
    /// and bucket array.  Note that this method is intended to be called
    /// from copy constructors, which will have assigned some initial values
    /// for the `size` and other attributes that may not be consistent with
    /// the class invariants until after this method is called.
    void copyDataStructure(bslalg::BidirectionalLink *cursor);
 
    /// Recreate the sequence of elements from the list starting at the
    /// specified `cursor` and having (member) `d_size` elements, ensuring
    /// that each `ValueType` object in the source list is move-inserted
    /// into the new sequence.  Allocate a bucket array sufficiently large
    /// to store `d_size` elements, while respecting the `maxLoadFactor`,
    /// and index the new list into that new array of hash buckets.  This
    /// hash table then takes ownership of the list and bucket array.  Note
    /// that this method is intended to be called from move constructors
    /// (where the source and target allocators do not match), which will
    /// have assigned some initial values for the `size` and other
    /// attributes that may not be consistent with the class invariants
    /// until after this method completes.  If an exception is thrown during
    /// this operation, this object is left in a valid but unspecified
    /// state; it is the caller's responsibility, however, to ensure the
    /// source hash-table is in a valid state if an exception is thrown
    void moveDataStructure(bslalg::BidirectionalLink *cursor);
 
    /// Efficiently exchange the value, functors, and allocator of this
    /// object with those of the specified `other` object.  This method
    /// provides the no-throw exception-safety guarantee.
    void quickSwapExchangeAllocators(HashTable *other);
 
    /// Efficiently exchange the value and functors this object with those
    /// of the specified `other` object.  This method provides the no-throw
    /// exception-safety guarantee.  The behavior is undefined unless this
    /// object was created with the same allocator as `other`.
    void quickSwapRetainAllocators(HashTable *other);
 
    /// Re-organize this hash-table to have exactly the specified
    /// `newNumBuckets`, which will then be able to store the specified
    /// `capacity` number of elements without exceeding the `maxLoadFactor`.
    /// This operation provides the strong exception guarantee (see
    /// @ref bsldoc_glossary ) unless the `hasher` throws, in which case this
    /// operation provides the basic exception guarantee, leaving the
    /// hash-table in a valid, but otherwise unspecified (and potentially
    /// empty), state.  The behavior is undefined unless
    /// `size / newNumBuckets <= maxLoadFactor`.  Note that the caller is
    /// responsible for correctly computing the `capacity` supported by the
    /// new number of buckets.  This allows for a minor optimization where
    /// the value is computed only once per rehash.
    void rehashIntoExactlyNumBuckets(SizeType newNumBuckets,
                                     SizeType capacity);
 
    /// Erase all the nodes in this hash-table, and deallocate their memory
    /// via the supplied node-factory.  Destroy the array of buckets owned
    /// by this hash-table.  If `d_anchor.bucketAddress()` is the default
    /// bucket address (`HashTable_ImpDetails::defaultBucketAddress`), then
    /// this hash-table does not own its array of buckets, and it will not
    /// be destroyed.
    void removeAllAndDeallocate();
 
    /// Erase all the nodes in this table and deallocate their memory via
    /// the node factory, without performing the necessary bookkeeping to
    /// reflect such change.  Note that this (private) method explicitly
    /// leaves the HashTable in an inconsistent state, and is expected to be
    /// useful when the anchor of this hash table is about to be overwritten
    /// with a new value, or when the hash table is going out of scope and
    /// the extra bookkeeping is not necessary.
    void removeAllImp();
 
    // PRIVATE ACCESSORS
 
    /// Return the address of the first node in this hash table having a key
    /// that compares equal (according to this hash-table's `comparator`) to
    /// the specified `key`.  The behavior is undefined unless the specified
    /// `hashValue` is the hash code for the `key` according to the `hasher`
    /// functor of this hash table.  Note that this function's
    /// implementation relies on the supplied `hashValue` rather than
    /// recomputing it, eliminating some redundant computation for the
    /// public methods.
    template <class DEDUCED_KEY>
    bslalg::BidirectionalLink *find(DEDUCED_KEY& key,
                                    std::size_t  hashValue) const;
 
    /// Return the address of the bucket at the specified `bucketIndex` in
    /// bucket array of this hash table.  The behavior is undefined unless
    /// `bucketIndex < this->numBuckets()`.
    bslalg::HashTableBucket *getBucketAddress(SizeType bucketIndex) const;
 
    /// Return the hash code for the element stored in the specified `node`
    /// using a copy of the hash functor supplied at construction.  The
    /// behavior is undefined unless `node` points to a list-node of type
    /// `bslalg::BidirectionalNode<KEY_CONFIG::ValueType>`.
    std::size_t hashCodeForNode(bslalg::BidirectionalLink *node) const;
 
  public:
    // CREATORS
 
    /// Create an empty hash-table.  Optionally specify a `basicAllocator`
    /// used to supply memory.  If `basicAllocator` is not supplied, a
    /// default-constructed object of the (template parameter) type
    /// `ALLOCATOR` is used.  If the type `ALLOCATOR` is `bsl::allocator`
    /// and `basicAllocator` is not supplied, the currently installed
    /// default allocator is used to supply memory.  Use 1.0 for the
    /// `maxLoadFactor`.  Use a default constructed object of the (template
    /// parameter) type `HASHER` and a default constructed object of the
    /// (template parameter) type `COMPARATOR` to organize elements in the
    /// table.  No memory is allocated unless the `HASHER` or `COMPARATOR`
    /// types allocate memory in their default constructor.  Note that a
    /// `bslma::Allocator *` can be supplied for `basicAllocator` if the
    /// type `ALLOCATOR` is `bsl::allocator` (the default).
    explicit HashTable(const ALLOCATOR& basicAllocator = ALLOCATOR());
 
    /// Create an empty hash-table using the specified `hash` and `compare`
    /// functors to organize elements in the table, which will initially
    /// have at least the specified `initialNumBuckets` and a
    /// `maxLoadFactor` of the specified `initialMaxLoadFactor`.  Optionally
    /// specify a `basicAllocator` used to supply memory.  If
    /// `basicAllocator` is not supplied, a default-constructed object of
    /// the (template parameter) type `ALLOCATOR` is used.  If the type
    /// `ALLOCATOR` is `bsl::allocator` and `basicAllocator` is not
    /// supplied, the currently installed default allocator is used to
    /// supply memory.  If this constructor tries to allocate a number of
    /// buckets larger than can be represented by this hash-table's
    /// `SizeType`, a `std::length_error` exception is thrown.  The behavior
    /// is undefined unless `0 < initialMaxLoadFactor`.  Note that more than
    /// `initialNumBuckets` buckets may be created in order to preserve the
    /// bucket allocation strategy of the hash-table (but never fewer).
    /// Also note that a `bslma::Allocator *` can be supplied for
    /// `basicAllocator` if the type `ALLOCATOR` is `bsl::allocator` (the
    /// default).
    HashTable(const HASHER&     hash,
              const COMPARATOR& compare,
              SizeType          initialNumBuckets,
              float             initialMaxLoadFactor,
              const ALLOCATOR&  basicAllocator = ALLOCATOR());
 
    /// Create a hash-table having the same value (and `maxLoadFactor`) as
    /// the specified `original` object.  Use a copy of `original.hasher()`
    /// and a copy of `original.comparator()` to organize elements in this
    /// hash-table.  Use the allocator returned by
    /// 'bsl::allocator_traits<ALLOCATOR>::
    ///  select_on_container_copy_construction(original.allocator())'
    /// to allocate memory.  This method requires that the `ValueType`
    /// defined by the (template parameter) type `KEY_CONFIG` be
    /// `copy-insertable` into this hash-table (see '{Requirements on
    /// `KEY_CONFIG`}).   Note that this hash-table may have fewer buckets
    /// than `original`, and a correspondingly higher `loadFactor`, so long
    /// as `maxLoadFactor` is not exceeded.  Also note that the created hash
    /// table may have a different `numBuckets` than `original`, and a
    /// correspondingly different `loadFactor`, as long as `maxLoadFactor`
    /// is not exceeded.
    HashTable(const HashTable& original);
 
    /// Create a hash-table having the same value (and `maxLoadFactor`) as
    /// the specified `original` object by moving (in constant time) the
    /// contents of `original` to the new hash-table.  Use a copy of
    /// `original.hasher()` and a copy of `original.comparator()` to
    /// organize elements in this hash-table.  The allocator associated with
    /// `original` is propagated for use in the newly created hash-table.
    /// `original` is left in a valid but unspecified state.
    HashTable(BloombergLP::bslmf::MovableRef<HashTable> original);
 
    /// Create a hash-table having the same value (and `maxLoadFactor`) as
    /// the specified `original` object that uses the specified
    /// `basicAllocator` to supply memory.  Use a copy of
    /// `original.hasher()` and a copy of `original.comparator()` to
    /// organize elements in this hash-table.  This method requires that the
    /// `ValueType` defined by the (template parameter) type `KEY_CONFIG` be
    /// `move-insertable` into this hash-table.  Note that this hash-table
    /// may have a different `numBuckets` than `original`, and a
    /// correspondingly different `loadFactor`, as long as `maxLoadFactor`
    /// is not exceeded.
    HashTable(const HashTable& original, const ALLOCATOR& basicAllocator);
 
    /// Create a hash table having the same value (and `maxLoadFactor`) as
    /// the specified `original` object that uses the specified
    /// `basicAllocator` to supply memory.  The contents of `original` are
    /// moved (in constant time) to the new hash-table if
    /// `basicAllocator == original.get_allocator()`, and are move-inserted
    /// (in linear time) using `basicAllocator` otherwise.  `original` is
    /// left in a valid but unspecified state.  Use a copy of
    /// `original.hasher()` and a copy of `original.comparator()` to
    /// organize elements in this hash-table.  This method requires that the
    /// `ValueType` defined by the (template parameter) type `KEY_CONFIG` be
    /// `move-insertable` into this hash-table.  Note that this hash-table
    /// may have a different `numBuckets` than `original`, and a
    /// correspondingly different `loadFactor`, as long as `maxLoadFactor`
    /// is not exceeded.  Also note that a `bslma::Allocator *` can be
    /// supplied for `basicAllocator` if the (template parameter)
    /// `ALLOCATOR` is `bsl::allocator` (the default).
    HashTable(BloombergLP::bslmf::MovableRef<HashTable> original,
              const ALLOCATOR&                          basicAllocator);
 
    /// Destroy this object.
    ~HashTable();
 
    // MANIPULATORS
 
    /// Assign to this object the value, hasher, comparator and
    /// `maxLoadFactor` of the specified `rhs` object, propagate to this
    /// object the allocator of `rhs` if the `ALLOCATOR` type has trait
    /// `propagate_on_container_copy_assignment`, and return a reference
    /// providing modifiable access to this object.  This method requires
    /// that the `ValueType` defined by the (template parameter) type
    /// `KEY_CONFIG` be `copy-assignable` and `copy-insertable` into this
    /// hash-table (see {Requirements on `KEY_CONFIG`}).  This method
    /// requires that the (template parameter) types `HASHER` and
    /// `COMPARATOR` be `copy-constructible` and `copy-assignable`.  Note
    /// that these requirements are modeled after the unordered container
    /// requirements table in the C++11 standard, which is imprecise on this
    /// operation; these requirements might simplify in the future, if the
    /// standard is updated.
    HashTable& operator=(const HashTable& rhs);
 
    /// Assign to this object the value, hasher, comparator, and
    /// `maxLoadFactor` of the specified `rhs` object, propagate to this
    /// object the allocator of `rhs` if the `ALLOCATOR` type has trait
    /// `propagate_on_container_move_assignment`, and return a reference
    /// providing modifiable access to this object.  If this hash-table and
    /// `rhs` use the same allocator (after considering the aforementioned
    /// trait), all of the contents of `rhs` are moved to this hash-table in
    /// constant time; otherwise, all elements in this hash table are either
    /// destroyed or move-assigned to and each additional element in `rhs`
    /// is move-inserted into this hash-table.  `rhs` is left in a valid but
    /// unspecified state.  This method requires that the `ValueType`
    /// defined by the (template parameter) type `KEY_CONFIG` be both
    /// `move-assignable` and `move-insertable` into this hash-table (see
    /// {Requirements on `KEY_CONFIG`}).
    HashTable& operator=(BloombergLP::bslmf::MovableRef<HashTable> rhs);
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
    /// Insert into this hash-table a newly-created `ValueType` object,
    /// constructed by forwarding the specified (variable number of)
    /// `arguments` to the corresponding constructor of `ValueType`, and
    /// return the address of the newly inserted node.  If a key equivalent
    /// to that of the newly-created object already exists in this
    /// hash-table, then insert the newly-created object immediately before
    /// the first such element.  Additional buckets are allocated, as
    /// needed, to preserve the invariant `loadFactor <= maxLoadFactor`.  If
    /// this function tries to allocate a number of buckets larger than can
    /// be represented by this hash-table's `SizeType`, a
    /// `std::length_error` exception is thrown.  This method requires that
    /// the `ValueType` defined in the (template parameter) type
    /// `KEY_CONFIG` be `emplace-constructible` into this hash-table from
    /// `arguments` (see {Requirements on `KEY_CONFIG`});
    template <class... Args>
    bslalg::BidirectionalLink *emplace(Args&&... arguments);
 
    /// Insert into this hash-table a newly-created `ValueType` object,
    /// constructed by forwarding the specified (variable number of)
    /// `arguments` to the corresponding constructor of `ValueType`
    /// (immediately preceding the specified `hint` if `hint` is not null
    /// and the key of the node pointed to by `hint` is equivalent to that
    /// of the newly-created object), and return the address of the newly
    /// inserted node.  If `hint` is null or the key of the node pointed to
    /// by `hint` is not equivalent to that of the newly created object, and
    /// a key equivalent to that of the newly-created object already exists
    /// in this hash-table, then insert the newly-created object immediately
    /// before the first such element.  Additional buckets will be
    /// allocated, as needed, to preserve the invariant
    /// `loadFactor <= maxLoadFactor`.  If this function tries to allocate a
    /// number of buckets larger than can be represented by this hash
    /// table's `SizeType`, a `std::length_error` exception is thrown.  This
    /// method requires that `ValueType` defined in the (template parameter)
    /// type `KEY_CONFIG` be `emplace-constructible` into this hash-table
    /// from `arguments` (see {Requirements on `KEY_CONFIG`}).  The behavior
    /// is undefined unless `hint` is either null or points to a node in
    /// this hash table.
    template <class... Args>
    bslalg::BidirectionalLink *emplaceWithHint(
                                         bslalg::BidirectionalLink *hint,
                                         Args&&...                  arguments);
 
    /// Insert into this hash-table a newly-created `ValueType` object,
    /// constructed by forwarding the specified (variable number of)
    /// `arguments` to the corresponding constructor of `ValueType`, if a
    /// key equivalent to that of the newly-created object does not already
    /// exist in this hash-table.  Return the address of the (possibly newly
    /// created and inserted) element in this hash table whose key is
    /// equivalent to that of an object created from `arguments`.  Load
    /// `true` into the specified `isInsertedFlag` if a new value was
    /// inserted, and `false` if an equivalent key was already present.  If
    /// this hash-table contains more than one element with an equivalent
    /// key, return the first such element (from the contiguous sequence of
    /// elements having a matching key).  Additional buckets are allocated,
    /// as needed, to preserve the invariant `loadFactor <= maxLoadFactor`.
    /// If this function tries to allocate a number of buckets larger than
    /// can be represented by this hash-table's `SizeType`, a
    /// `std::length_error` exception is thrown.  This method requires that
    /// the `ValueType` defined in the (template parameter) type
    /// `KEY_CONFIG` be `emplace-constructible` into this hash-table from
    /// `arguments` (see {Requirements on `KEY_CONFIG`});
    template <class... Args>
    bslalg::BidirectionalLink *emplaceIfMissing(bool     *isInsertedFlag,
                                                Args&&... arguments);
#endif
 
    /// Insert into this hash-table a newly-created `ValueType` object,
    /// constructed by forwarding the specified `key` and a
    /// default-constructed object of the type `ValueType::second_type`, to
    /// the corresponding constructor of `ValueType`, if `key` does not
    /// already exist in this hash-table.  Return the address of the
    /// (possibly newly created and inserted) element in this hash-table
    /// whose key is equivalent to `key`.  If this hash-table contains more
    /// than one element with the supplied `key`, return the first such
    /// element (from the contiguous sequence of elements having a matching
    /// key).  Additional buckets are allocated, as needed, to preserve the
    /// invariant `loadFactor <= maxLoadFactor`.  If this function tries to
    /// allocate a number of buckets larger than can be represented by this
    /// hash table's `SizeType`, a `std::length_error` exception is thrown.
    /// This method requires that the `ValueType` defined in the (template
    /// parameter) type `KEY_CONFIG` be `emplace-constructible` into this
    /// hash-table from a `pair` of arguments representing the key and
    /// value, respectively (see {Requirements on `KEY_CONFIG`});
    bslalg::BidirectionalLink *insertIfMissing(const KeyType&             key);
    bslalg::BidirectionalLink *insertIfMissing(
                                       bslmf::MovableRef<NonConstKeyType> key);
 
    /// Insert the specified `value` into this hash-table if a key
    /// equivalent to that of `value` does not already exist in this
    /// hash-table.  Return the address of the (possibly newly inserted)
    /// element in this hash-table whose key is equivalent to that of
    /// `value`.  If this hash-table contains more than one element with a
    /// matching key, return the first such element (from the contiguous
    /// sequence of elements having a matching key).  Additional buckets are
    /// allocated, as needed, to preserve the invariant
    /// `loadFactor <= maxLoadFactor`.  If this function tries to allocate a
    /// number of buckets larger than can be represented by this
    /// hash-table's `SizeType`, a `std::length_error` exception is thrown.
    /// This method requires that the `ValueType` defined in the (template
    /// parameter) type `KEY_CONFIG` be `copy-insertable` into this
    /// hash-table (see {Requirements on `KEY_CONFIG`});
    bslalg::BidirectionalLink *insertIfMissing(
                                              bool             *isInsertedFlag,
                                              const ValueType&  value);
 
    /// Insert the specified `value` into this hash-table if a key
    /// equivalent to that of `value` does not already exist in this
    /// hash-table.  Return the address of the (possibly newly inserted)
    /// element in this hash-table whose key is equivalent to that of
    /// `value`.  `value` is left in a valid but unspecified state.  If this
    /// hash-table contains more than one element with a matching key,
    /// return the first such element (from the contiguous sequence of
    /// elements having a matching key).  Additional buckets are allocated,
    /// as needed, to preserve the invariant `loadFactor <= maxLoadFactor`.
    /// If this function tries to allocate a number of buckets larger than
    /// can be represented by this hash-table's `SizeType`, a
    /// `std::length_error` exception is thrown.  This method requires that
    /// the `ValueType` defined in the (template parameter) type
    /// `KEY_CONFIG` be `move-insertable` into this hash-table (see
    /// {Requirements on `KEY_CONFIG`});
    bslalg::BidirectionalLink *insertIfMissing(
                                   bool                        *isInsertedFlag,
                                   bslmf::MovableRef<ValueType> value);
 
    /// Insert into this hash-table a `ValueType` object created from the
    /// specified `value` if a key equivalent to that of such an object does
    /// not already exist in this hash-table.  Return the address of the
    /// (possibly newly inserted) element in this hash-table whose key is
    /// equivalent to that of the object created from `value`.  Load `true`
    /// into the specified `isInsertedFlag` if a new value was inserted, and
    /// `false` if an equivalent key was already present.  If this
    /// hash-table contains more than one element with an equivalent key,
    /// return the first such element (from the contiguous sequence of
    /// elements having a matching key).  Additional buckets are allocated,
    /// as needed, to preserve the invariant `loadFactor <= maxLoadFactor`.
    /// If this function tries to allocate a number of buckets larger than
    /// can be represented by this hash-table's `SizeType`, a
    /// `std::length_error` exception is thrown.  This method requires that
    /// the `ValueType` defined in the (template parameter) type
    /// `KEY_CONFIG` be `move-insertable` into this hash-table (see
    /// {Requirements on `KEY_CONFIG`}) and the (template parameter) type
    /// `SOURCE_TYPE` be implicitly convertible to `ValueType`.
    template <class SOURCE_TYPE>
    bslalg::BidirectionalLink *
    insertIfMissing(
                 bool                                          *isInsertedFlag,
                 BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE) value);
 
    /// Insert into this hash-table a `ValueType` object created from the
    /// specified `value` and return the address of the newly inserted node.
    /// If a key equivalent to that of the newly-created object already
    /// exists in this hash-table, then insert the new object immediately
    /// before the first such element.  Additional buckets are allocated, as
    /// needed, to preserve the invariant `loadFactor <= maxLoadFactor`.  If
    /// this function tries to allocate a number of buckets larger than can
    /// be represented by this hash-table's `SizeType`, a
    /// `std::length_error` exception is thrown.  This method requires that
    /// the `ValueType` defined in the (template parameter) type
    /// `KEY_CONFIG` be `move-insertable` into this hash-table (see
    /// {Requirements on `KEY_CONFIG`}) and the (template parameter) type
    /// `SOURCE_TYPE` be implicitly convertible to `ValueType`.  Note that
    /// this method is deprecated is provided only to ensure backward
    /// compatibility with existing clients; use the `emplace` method
    /// instead.
    template <class SOURCE_TYPE>
    bslalg::BidirectionalLink *insert(
                         BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE) value);
 
    /// Insert into this hash-table a `ValueType` object created from the
    /// specified `value` (immediately preceding the specified `hint` if
    /// `hint` is not null and the key of the node pointed to by `hint` is
    /// equivalent to that of the newly-created object), and return the
    /// address of the newly inserted node.  If `hint` is null or the key of
    /// the node pointed to by `hint` is not equivalent to that of the newly
    /// created object, and a key equivalent to that of the newly-created
    /// object already exists in this hash-table, then insert the
    /// newly-created object immediately before the first such element.
    /// Additional buckets will be allocated, as needed, to preserve the
    /// invariant `loadFactor <= maxLoadFactor`.  If this function tries to
    /// allocate a number of buckets larger than can be represented by this
    /// hash-table's `SizeType`, a `std::length_error` exception is thrown.
    /// This method requires that `ValueType` defined in the (template
    /// parameter) type `KEY_CONFIG` be `move-insertable` into this
    /// hash-table (see {Requirements on `KEY_CONFIG`}) and the (template
    /// parameter) type `SOURCE_TYPE` be implicitly convertible to
    /// `ValueType`.  Note that this method is deprecated and is provided
    /// only to ensure backward compatibility with existing clients; use the
    /// `emplaceWithHint` method instead.
    template <class SOURCE_TYPE>
    bslalg::BidirectionalLink *insert(
                          BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE) value,
                          bslalg::BidirectionalLink                     *hint);
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
    /// If a key equivalent to the specified `key` already exists in this
    /// hash-table, assign the specified `obj` to the value associated with
    /// that key, load `false` into the specified `isInsertedFlag` and
    /// return a pointer to the existing entry.  Otherwise, insert into this
    /// hash-table a newly-created `value_type` object, constructed from
    /// `key` and `obj`, load `true` into `isInsertedFlag`, and return a
    /// pointer to the newly-created entry.  Use the optionally specified
    /// `hint` as a starting place for the search for the existing key.
    template <class KEY_ARG, class BDE_OTHER_TYPE>
    bslalg::BidirectionalLink *insertOrAssign(
                    bool                                       *isInsertedFlag,
                    bslalg::BidirectionalLink                  *hint,
                    BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG)  key,
                    BDE_OTHER_TYPE&&                            obj);
#endif
 
    /// Re-organize this hash-table to have at least the specified
    /// `newNumBuckets`, preserving the invariant
    /// `loadFactor <= maxLoadFactor`.  If this function tries to allocate a
    /// number of buckets larger than can be represented by this hash
    /// table's `SizeType`, a `std::length_error` exception is thrown.  This
    /// operation provides the strong exception guarantee (see
    /// @ref bsldoc_glossary ) unless the `hasher` throws, in which case this
    /// operation provides the basic exception guarantee, leaving the
    /// hash-table in a valid, but otherwise unspecified (and potentially
    /// empty), state.  Note that more buckets than requested may be
    /// allocated in order to preserve the bucket allocation strategy of the
    /// hash table (but never fewer).
    void rehashForNumBuckets(SizeType newNumBuckets);
 
    /// Remove the specified `node` from this hash-table, and return the
    /// address of the node immediately after `node` in this hash-table
    /// (prior to its removal), or a null pointer value if `node` is the
    /// last node in the table.  This method invalidates only iterators and
    /// references to the removed node and previously saved values of the
    /// `end()` iterator, and preserves the relative order of the nodes not
    /// removed.  The behavior is undefined unless `node` refers to a node
    /// in this hash-table.
    bslalg::BidirectionalLink *remove(bslalg::BidirectionalLink *node);
 
    /// Remove all the elements from this hash-table.  Note that this
    /// hash-table is empty after this call, but allocated memory may be
    /// retained for future use.  The destructor of each (non-trivial)
    /// element that is remove shall be run.
    void removeAll();
 
    /// Re-organize this hash-table to have a sufficient number of buckets
    /// to accommodate at least the specified `numElements` without
    /// exceeding the `maxLoadFactor`, and ensure that there are sufficient
    /// nodes pre-allocated in this object's node pool.  If this function
    /// tries to allocate a number of buckets larger than can be represented
    /// by this hash table's `SizeType`, a `std::length_error` exception is
    /// thrown.  This operation provides the strong exception guarantee (see
    /// @ref bsldoc_glossary ) unless the `hasher` throws, in which case this
    /// operation provides the basic exception guarantee, leaving the
    /// hash-table in a valid, but otherwise unspecified (and potentially
    /// empty), state.
    void reserveForNumElements(SizeType numElements);
 
    /// Set the maximum load factor permitted by this hash table to the
    /// specified `newMaxLoadFactor`, where load factor is the statistical
    /// mean number of elements per bucket.  If 'newMaxLoadFactor <
    /// loadFactor', allocate at least enough buckets to re-establish the
    /// invariant `loadFactor <= maxLoadFactor`.  If this function tries to
    /// allocate a number of buckets larger than can be represented by this
    /// hash table's `SizeType`, a `std::length_error` exception is thrown.
    /// The behavior is undefined unless `0 < maxLoadFactor`.
    void setMaxLoadFactor(float newMaxLoadFactor);
 
    /// Exchange the value of this object, its `comparator` functor, its
    /// `hasher` functor, and its `maxLoadFactor` with those of the
    /// specified `other` object.  Additionally, if
    /// `bslstl::AllocatorTraits<ALLOCATOR>::propagate_on_container_swap` is
    /// `true`, then exchange the allocator of this object with that of the
    /// `other` object, and do not modify either allocator otherwise.  This
    /// method provides the no-throw exception-safety guarantee unless any
    /// of the `comparator` or `hasher` functors throw when swapped, leaving
    /// both objects in a safely destructible, but otherwise unusable,
    /// state.  The operation guarantees `O[1]` complexity.  The behavior is
    /// undefined unless either this object has an allocator that compares
    /// equal to the allocator of `other`, or the trait
    /// `bslstl::AllocatorTraits<ALLOCATOR>::propagate_on_container_swap` is
    /// `true`.
    void swap(HashTable& other);
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
    /// If a key equivalent to the specified `key` already exists in this
    /// hash-table, load `false` into the specified `isInsertedFlag` and
    /// return a pointer to the existing entry.  Otherwise, insert into this
    /// hash-table a newly-created `value_type` object, constructed from
    /// `key` and the specified `args`, load `true` into `isInsertedFlag`
    /// and return a pointer to the newly created entry.  Use the optionally
    /// specified `hint` as a starting place for the search for the existing
    /// key.
    template <class... ARGS>
    bslalg::BidirectionalLink *tryEmplace(
                    bool                                       *isInsertedFlag,
                    bslalg::BidirectionalLink                  *hint,
                    const KeyType&                              key,
                    ARGS&&...                                   args);
 
    /// If a key equivalent to the specified `key` already exists in this
    /// hash-table, load `false` into the specified `isInsertedFlag` and
    /// return a pointer to the existing entry.  Otherwise, insert into this
    /// hash-table a newly-created `value_type` object, constructed from
    /// `std::forward<KEY>(key)` and the specified `args`, load `true` into
    /// `isInsertedFlag` and return a pointer to the newly created entry.
    /// Use the optionally specified `hint` as a starting place for the
    /// search for the existing key.
    template <class... ARGS>
    bslalg::BidirectionalLink *tryEmplace(
                    bool                                       *isInsertedFlag,
                    bslalg::BidirectionalLink                  *hint,
                    bslmf::MovableRef<NonConstKeyType>          key,
                    ARGS&&...                                   args);
 
 
    /// If a key equivalent to the specified `key` already exists in this
    /// hash-table, load `false` into the specified `isInsertedFlag` and
    /// return a pointer to the existing entry.  Otherwise, insert into this
    /// hash-table a newly-created `value_type` object, constructed from
    /// `key` and the specified `args`, load `true` into `isInsertedFlag`
    /// and return a pointer to the newly created entry.  Use the optionally
    /// specified `hint` as a starting place for the search for the existing
    /// key.
    ///
    /// Note: implemented inline due to Sun CC compilation error.
    template <class LOOKUP_KEY, class... ARGS>
    typename bsl::enable_if<
      BloombergLP::bslmf::IsTransparentPredicate<HASHER,    LOOKUP_KEY>::value
   && BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,LOOKUP_KEY>::value,
    bslalg::BidirectionalLink *>::type tryEmplace(
                                    bool                       *isInsertedFlag,
                                    bslalg::BidirectionalLink  *hint,
                                    LOOKUP_KEY&&                key,
                                    ARGS&&...                   args)
    {
        typedef bslalg::HashTableImpUtil ImpUtil;
 
        const LOOKUP_KEY& lvalue = key;
        const std::size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
 
        // Use the hint, if we can
        if (!hint
            || !d_parameters.comparator()(
                                      lvalue,
                                      ImpUtil::extractKey<KEY_CONFIG>(hint))) {
 
                hint = bslalg::HashTableImpUtil::findTransparent<KEY_CONFIG>(
                                                 d_anchor,
                                                 lvalue,
                                                 d_parameters.comparator(),
                                                 hashCode);
        }
 
        // If the key exists, we're done
        if (hint) {
            *isInsertedFlag = false;
            return hint;                                              // RETURN
        }
 
        if (d_size >= d_capacity) {
            this->rehashForNumBuckets(numBuckets() * 2);
        }
 
        // Make a new node
    #if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
        hint = d_parameters.nodeFactory().emplaceIntoNewNode(
         std::piecewise_construct,
         std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(LOOKUP_KEY, key)),
         std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(ARGS, args)...));
    #else
        typedef typename ValueType::second_type MappedType;
 
        // TBD: make 'this->allocator()' return the allocator by reference with
        // modifiable access rather than by value.
 
        AllocatorType alloc = this->allocator();
 
        bsls::ObjectBuffer<MappedType> defaultMapped;
        AllocatorTraits::construct(alloc, defaultMapped.address(),
                                 BSLS_COMPILERFEATURES_FORWARD(ARGS, args)...);
        bslma::DestructorGuard<MappedType> mGuard(defaultMapped.address());
 
        hint = d_parameters.nodeFactory().emplaceIntoNewNode(
                         BSLS_COMPILERFEATURES_FORWARD(LOOKUP_KEY, key),
                         defaultMapped.object());
    #endif
 
        // Add it to the hash table
        HashTable_NodeProctor<typename ImplParameters::NodeFactory>
                                nodeProctor(&d_parameters.nodeFactory(), hint);
        ImpUtil::insertAtFrontOfBucket(&d_anchor, hint, hashCode);
        nodeProctor.release();
        ++d_size;
 
        *isInsertedFlag = true;
        return hint;
    }
#endif
 
    // ACCESSORS
 
    /// Return a copy of the allocator used to construct this hash table.
    /// Note that this is not the allocator used to allocate elements for
    /// this hash table, which is instead a copy of that allocator rebound
    /// to allocate the nodes used by the internal data structure of this
    /// hash table.
    ALLOCATOR allocator() const;
 
    /// Return a reference offering non-modifiable access to the
    /// `HashTableBucket` at the specified `index` position in the array of
    /// buckets of this table.  The behavior is undefined unless 'index <
    /// numBuckets()'.
    const bslalg::HashTableBucket& bucketAtIndex(SizeType index) const;
 
    /// Return the index of the bucket that would contain all the elements
    /// having the specified `key`.
    SizeType bucketIndexForKey(const KeyType& key) const;
 
    /// Return a reference providing non-modifiable access to the
    /// key-equality comparison functor used by this hash table.
    const COMPARATOR& comparator() const;
 
    /// Return the number elements contained in the bucket at the specified
    /// `index`.  Note that this operation has linear run-time complexity
    /// with respect to the number of elements in the indexed bucket.
    SizeType countElementsInBucket(SizeType index) const;
 
    /// Return the address of the first element in this hash table, or a
    /// null pointer value if this hash table is empty.
    bslalg::BidirectionalLink *elementListRoot() const;
 
    /// Return the address of a link whose key is equivalent to the
    /// specified `key` (according to this hash-table's `comparator`), and a
    /// null pointer value if no such link exists.  If this hash-table
    /// contains more than one element having the supplied `key`, return the
    /// first such element (from the contiguous sequence of elements having
    /// the same key).  The behavior is undefined unless `key` is equivalent
    /// to the elements of at most one equivalent-key group.
    template <class LOOKUP_KEY>
    typename bsl::enable_if<
      BloombergLP::bslmf::IsTransparentPredicate<HASHER,    LOOKUP_KEY>::value
   && BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,LOOKUP_KEY>::value,
                  bslalg::BidirectionalLink *>::type
    find(const LOOKUP_KEY& key) const
        {
            return bslalg::HashTableImpUtil::findTransparent<KEY_CONFIG>(
                                             d_anchor,
                                             key,
                                             d_parameters.comparator(),
                                             d_parameters.hashCodeForKey(key));
        }
 
    /// Return the address of a link whose key has the same value as the
    /// specified `key` (according to this hash-table's `comparator`), and a
    /// null pointer value if no such link exists.  If this hash-table
    /// contains more than one element having the supplied `key`, return the
    /// first such element (from the contiguous sequence of elements having
    /// the same key).
    bslalg::BidirectionalLink *find(const KeyType& key) const;
 
    /// Return the address of the first node after any nodes holding a value
    /// having the same key as the specified `first` node (according to this
    /// hash-table's `comparator`), and a null pointer value if all nodes
    /// following `first` hold values with the same key as `first`.  The
    /// behavior is undefined unless `first` is a link in this hash-table.
    /// Note that this hash-table ensures all elements having the same key
    /// form a contiguous sequence.
    bslalg::BidirectionalLink *findEndOfRange(
                                       bslalg::BidirectionalLink *first) const;
 
    /// Load into the specified `first` and `last` pointers the respective
    /// addresses of the first and last link (in the list of elements owned
    /// by this hash table) where the contained elements have a key that is
    /// equivalent to the specified `key` using the `comparator` of this
    /// hash-table, and null pointer values if there are no elements
    /// matching `key`.  The behavior is undefined unless `key` is
    /// equivalent to the elements of at most one equivalent-key group.
    /// Note that the output values will form a closed range, where both
    /// `first` and `last` point to links satisfying the predicate (rather
    /// than a semi-open range where `last` would point to the element
    /// following the range).  Also note that this hash-table ensures all
    /// elements having the same key form a contiguous sequence.
    ///
    /// Note: implemented inline due to Sun CC compilation error.
    template <class LOOKUP_KEY>
    typename bsl::enable_if<
      BloombergLP::bslmf::IsTransparentPredicate<HASHER,    LOOKUP_KEY>::value
   && BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,LOOKUP_KEY>::value,
                   void>::type
    findRange(bslalg::BidirectionalLink **first,
              bslalg::BidirectionalLink **last,
              const LOOKUP_KEY&           key) const
        {
            BSLS_ASSERT_SAFE(first);
            BSLS_ASSERT_SAFE(last);
 
            *first = this->find(key);
            *last  = *first ? this->findEndOfRange(*first) : 0;
        }
 
    /// Load into the specified `first` and `last` pointers the respective
    /// addresses of the first and last link (in the list of elements owned
    /// by this hash table) where the contained elements have a key that
    /// compares equal to the specified `key` using the `comparator` of this
    /// hash-table, and null pointer values if there are no elements
    /// matching `key`.  Note that the output values will form a closed
    /// range, where both `first` and `last` point to links satisfying the
    /// predicate (rather than a semi-open range where `last` would point to
    /// the element following the range).  Also note that this hash-table
    /// ensures all elements having the same key form a contiguous sequence.
    void findRange(bslalg::BidirectionalLink **first,
                   bslalg::BidirectionalLink **last,
                   const KeyType&              key) const;
 
    /// Return `true` if the specified `other` has the same value as this
    /// object, and `false` otherwise.  Two `HashTable` objects have the
    /// same value if they have the same number of elements, and for every
    /// subset of elements in this object having keys that compare equal
    /// (according to that hash table's `comparator`), a corresponding
    /// subset of elements exists in the `other` object, having the same
    /// number of elements, where, for some permutation of the subset in
    /// this object, every element in that subset compares equal (using
    /// `operator==`) to the corresponding element in the `other` subset.
    /// The behavior is undefined unless both the `hasher` and `comparator`
    /// of this object and the `other` return the same value for every valid
    /// input.  Note that this method requires that the `ValueType` of the
    /// parameterized `KEY_CONFIG` be "equality-comparable" (see
    /// {Requirements on `KEY_CONFIG`}).
    bool hasSameValue(const HashTable& other) const;
 
    /// Return a reference providing non-modifiable access to the hash
    /// functor used by this hash-table.
    const HASHER& hasher() const;
 
    /// Return the current load factor for this table.  The load factor is
    /// the statistical mean number of elements per bucket.
    float loadFactor() const;
 
    /// Return the maximum load factor permitted by this hash table object,
    /// where the load factor is the statistical mean number of elements per
    /// bucket.  Note that this hash table will enforce the maximum load
    /// factor by rehashing into a larger array of buckets on any any
    /// insertion operation where a successful insertion would exceed the
    /// maximum load factor.  The maximum load factor may actually be less
    /// than the current load factor if the maximum load factor has been
    /// reset, but no insert operations have yet occurred.
    float maxLoadFactor() const;
 
    /// Return a theoretical upper bound on the largest number of buckets
    /// that this hash-table could possibly have.  Note that there is no
    /// guarantee that the hash-table can successfully maintain that number
    /// of buckets, or even close to that number of buckets without running
    /// out of resources.
    SizeType maxNumBuckets() const;
 
    /// Return a theoretical upper bound on the largest number of elements
    /// that this hash-table could possibly hold.  Note that there is no
    /// guarantee that the hash-table can successfully grow to the returned
    /// size, or even close to that size without running out of resources.
    SizeType maxSize() const;
 
    /// Return the number of buckets contained in this hash table.
    SizeType numBuckets() const;
 
    /// Return the number of elements this hash table can hold without
    /// requiring a rehash operation in order to respect the
    /// `maxLoadFactor`.
    SizeType rehashThreshold() const;
 
    /// Return the number of elements in this hash table.
    SizeType size() const;
};
 
/// Swap both the value, the hasher, the comparator, and the `maxLoadFactor`
/// of the specified `x` object with the value, the hasher, the comparator,
/// and the `maxLoadFactor` of the specified `y` object.  Additionally, if
/// `bslstl::AllocatorTraits<ALLOCATOR>::propagate_on_container_swap` is
/// `true`, then exchange the allocator of `x` with that of `y`, and do not
/// modify either allocator otherwise.  This method guarantees `O[1]`
/// complexity if `x` and `y` have the same allocator or if the allocators
/// propagate on swap, otherwise this operation will typically pay the cost
/// of two copy constructors, which may in turn throw.  If the allocators
/// are the same or propagate, then this method provides the no-throw
/// exception-safety guarantee unless the `swap` function of the hasher or
/// comparator throw.  Otherwise this method offers only the basic exception
/// safety guarantee.
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
void swap(HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& x,
          HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& y);
 
/// Return `true` if the specified `lhs` and `rhs` objects have the same
/// value, and `false` otherwise.  Two `HashTable` objects have the same
/// value if they have the same number of elements, and for every subset of
/// elements in `lhs` having keys that compare equal (according to that hash
/// table's `comparator`), a corresponding subset of elements exists in
/// `rhs`, having the same number of elements, where, for some permutation
/// of the `lhs` subset, every element in that subset compares equal (using
/// `operator==`) to the corresponding element in the `rhs` subset.  The
/// behavior is undefined unless both the `hasher` and `comparator` of `lhs`
/// and `rhs` return the same value for every valid input.  Note that this
/// method requires that the `ValueType` of the parameterized `KEY_CONFIG`
/// be "equality-comparable" (see {Requirements on `KEY_CONFIG`}).
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bool operator==(
              const HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& lhs,
              const HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& rhs);
 
/// Return `true` if the specified `lhs` and `rhs` objects do not have the
/// same value, and `false` otherwise.  Two `HashTable` objects do not have
/// the same value if they do not have the same number of elements, or if,
/// for any key found in `lhs`, the subset of elements having that key
/// (according to the hash-table's `comparator`) in `lhs` either (1) does
/// not have the same number of elements as the subset of elements having
/// that key in `rhs`, or (2) there exists no permutation of the `lhs`
/// subset where each element compares equal (using `operator==`) to the
/// corresponding element in the `rhs` subset.  The behavior is undefined
/// unless both the `hasher` and `comparator` of `lhs` and `rhs` return the
/// same value for every valid input.  Note that this method requires that
/// the `ValueType` of the parameterized `KEY_CONFIG` be
/// "equality-comparable" (see {Requirements on `KEY_CONFIG`}).
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bool operator!=(
              const HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& lhs,
              const HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& rhs);
 
                    // ============================
                    // class HashTable_ArrayProctor
                    // ============================
 
/// This class probably already exists in `bslalg`
///
/// See @ref bslstl_hashtable 
template <class FACTORY>
class HashTable_ArrayProctor {
 
  private:
    // DATA
    FACTORY                 *d_factory_p;
    bslalg::HashTableAnchor *d_anchor_p;
 
  private:
    // NOT IMPLEMENTED
    HashTable_ArrayProctor(const HashTable_ArrayProctor&);
    HashTable_ArrayProctor& operator=(const HashTable_ArrayProctor&);
 
  public:
    // CREATORS
 
    /// Create a `HashTable_ArrayProctor` managing the hash-table data
    /// structure owned by the specified `anchor` that was created using the
    /// specified `factory`.
    HashTable_ArrayProctor(FACTORY                 *factory,
                           bslalg::HashTableAnchor *anchor);
 
    /// Destroy the hash-table data structure managed by this proctor and
    /// reclaim all of its resources, unless there was a call to `release`
    /// this proctor.
    ~HashTable_ArrayProctor();
 
    // MANIPULATORS
 
    /// Release from management the object currently managed by this
    /// proctor.  If no object is currently being managed, this method has
    /// no effect.
    void release();
};
 
                    // ===========================
                    // class HashTable_NodeProctor
                    // ===========================
 
/// This class implements a proctor that, unless its `release` method has
/// previously been invoked, automatically deallocates a managed list of
/// nodes upon destruction by recursively invoking the `deleteNode` method
/// of a supplied factory on each node.  The (template parameter) type
/// `FACTORY` shall be provide a member function that can be called as if it
/// had the following signature:
/// @code
/// void deleteNode(bslalg::BidirectionalLink *node);
/// @endcode
///
/// See @ref bslstl_hashtable 
template <class FACTORY>
class HashTable_NodeProctor {
 
  private:
    // DATA
    FACTORY                   *d_factory_p;
    bslalg::BidirectionalLink *d_node_p;
 
  private:
    // NOT IMPLEMENTED
    HashTable_NodeProctor(const HashTable_NodeProctor&);
    HashTable_NodeProctor& operator=(const HashTable_NodeProctor&);
 
  public:
    // CREATORS
 
    /// Create a new node-proctor that conditionally manages the specified
    /// `node` (if non-zero), and that uses the specified `factory` to
    /// destroy the node (unless released) upon its destruction.  The
    /// behavior is undefined unless `node` was created by the `factory`.
    HashTable_NodeProctor(FACTORY                   *factory,
                          bslalg::BidirectionalLink *node);
 
    /// Destroy this node proctor, and delete the node that it manages (if
    /// any) by invoking the `deleteNode` method of the factory supplied at
    /// construction.  If no node is currently being managed, this method
    /// has no effect.
    ~HashTable_NodeProctor();
 
    // MANIPULATORS
 
    /// Release from management the node currently managed by this proctor.
    /// If no object is currently being managed, this method has no effect.
    void release();
};
 
                    // ==========================
                    // class HashTable_ImpDetails
                    // ==========================
 
/// This utility `struct` provides a namespace for functions that are useful
/// when implementing a hash table.
struct HashTable_ImpDetails {
 
    // CLASS METHODS
 
    /// Return the address of a statically initialized empty bucket that can
    /// be shared as the (un-owned) bucket array by all empty hash tables.
    static bslalg::HashTableBucket *defaultBucketAddress();
 
    /// Return the suggested number of buckets to index a linked list that
    /// can hold as many as the specified `minElements` without exceeding
    /// the specified `maxLoadFactor`, and supporting at least the specified
    /// number of `requestedBuckets`.  Set the specified `*capacity` to the
    /// maximum length of linked list that the returned number of buckets
    /// could index without exceeding the `maxLoadFactor`.  The behavior is
    /// undefined unless `0 < maxLoadFactor`, `0 < minElements` and
    /// `0 < requestedBuckets`.
    static size_t growBucketsForLoadFactor(size_t *capacity,
                                           size_t  minElements,
                                           size_t  requestedBuckets,
                                           double  maxLoadFactor);
 
    /// Return that address of an allocator that can be used to allocate
    /// temporary storage, but that is neither the default nor global
    /// allocator.  Note that this function is intended to support detailed
    /// checks in `SAFE_2` builds, that may need additional storage for the
    /// evaluation of a validity check on a large data structure, but that
    /// should not change the expected values computed for regular allocator
    /// usage of the component as validated by the test driver.
    static bslma::Allocator *incidentalAllocator();
 
    /// Return the next prime number greater-than or equal to the specified
    /// `n` in the increasing sequence of primes chosen to disperse hash
    /// codes across buckets as uniformly as possible.  Throw a
    /// `std::length_error` exception if `n` is greater than the last prime
    /// number in the sequence.  Note that, typically, prime numbers in the
    /// sequence have increasing values that reflect a growth factor (e.g.,
    /// each value in the sequence may be, approximately, two times the
    /// preceding value).
    static size_t nextPrime(size_t n);
};
 
                    // ====================
                    // class HashTable_Util
                    // ====================
 
/// This utility `struct` provide utilities for initializing and destroying
/// bucket lists in anchors that are managed by a `HashTable`.  They cannot
/// migrate down to `bslalg::HashTableImpUtil` as they rely on the standard
/// library @ref bslma_allocatortraits  for their implementation.
struct HashTable_Util {
 
    // CLASS METHODS
 
    /// Assert that the passed argument (the specified `ptr`) is not a null
    /// pointer value.  Note that this utility is necessary as the
    /// `HashTable` class template may be instantiated with function
    /// pointers for the hasher or comparator policies, but there is no easy
    /// way to assert in general that the value of a generic type passed to
    /// a function is not a null pointer value.
    template <class TYPE>
    static void assertNotNullPointer(TYPE&);
    template <class TYPE>
    static void assertNotNullPointer(TYPE * const& ptr);
    template <class TYPE>
    static void assertNotNullPointer(TYPE * & ptr);
 
    /// Destroy the specified `data` array of the specified length
    /// `bucketArraySize`, that was allocated by the specified `allocator`.
    template<class ALLOCATOR>
    static void destroyBucketArray(bslalg::HashTableBucket *data,
                                   std::size_t              bucketArraySize,
                                   const ALLOCATOR&         allocator);
 
    /// Load into the specified `anchor` a (contiguous) array of buckets of
    /// the specified `bucketArraySize` using memory supplied by the
    /// specified `allocator`.  The behavior is undefined unless
    /// `0 < bucketArraySize` and `0 == anchor->bucketArraySize()`.  Note
    /// that this operation has no effect on `anchor->listRootAddress()`.
    template<class ALLOCATOR>
    static void initAnchor(bslalg::HashTableAnchor *anchor,
                           std::size_t              bucketArraySize,
                           const ALLOCATOR&         allocator);
};
 
                   // ==============================
                   // class HashTable_ImplParameters
                   // ==============================
 
    // It looks like the 'CallableVariable' adaptation would be more
    // appropriately addressed as part of the 'bslalg::FunctorAdapter' wrapper
    // than intrusively in this component, and in similar ways by any other
    // container trying to support the full range of standard conforming
    // functors.  Given that our intent is to support standard predicates, it
    // may be appropriate to handle calling non-'const' 'operator()' overloads
    // (via a 'mutable' member) too.
 
template <class HASHER>
struct HashTable_BaseHasher
     : bslalg::FunctorAdapter<HashTable_HashWrapper<
                                     typename CallableVariable<HASHER>::type> >
{
};
 
template <class COMPARATOR>
struct HashTable_Comparator
     : bslalg::FunctorAdapter<HashTable_ComparatorWrapper<
                                 typename CallableVariable<COMPARATOR>::type> >
{
};
 
/// This class holds all the parameterized parts of a `HashTable` class,
/// efficiently exploiting the empty base optimization without adding
/// unforeseen namespace associations to the `HashTable` class itself due to
/// the structural inheritance.
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
class HashTable_ImplParameters
    : private HashTable_BaseHasher<HASHER>::Type
    , private HashTable_Comparator<COMPARATOR>::Type
{
 
    // PRIVATE TYPES
    typedef typename HashTable_BaseHasher<HASHER>::Type        BaseHasher;
    typedef typename HashTable_Comparator<COMPARATOR>::Type    BaseComparator;
 
    /// This typedef is a convenient alias for the utility associated with
    /// movable references.
    typedef bslmf::MovableRefUtil                              MoveUtil;
 
    // typedefs stolen from HashTable
    typedef ALLOCATOR                                          AllocatorType;
    typedef ::bsl::allocator_traits<AllocatorType>             AllocatorTraits;
    typedef typename KEY_CONFIG::ValueType                     ValueType;
    typedef bslalg::BidirectionalNode<ValueType>               NodeType;
 
  public:
    // PUBLIC TYPES
    typedef HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR> HashTableType;
    typedef typename HashTableType::AllocatorTraits::
                              template rebind_traits<NodeType> ReboundTraits;
    typedef typename ReboundTraits::allocator_type             NodeAllocator;
 
    typedef
    BidirectionalNodePool<typename HashTableType::ValueType, NodeAllocator>
                                                               NodeFactory;
 
  private:
    // DATA
    NodeFactory  d_nodeFactory;     // nested 'struct's have public data by
                                    // convention, but should always be
                                    // accessed through the public methods.
 
  private:
    // NOT IMPLEMENTED
 
    /// = delete;
    HashTable_ImplParameters(const HashTable_ImplParameters&); // = delete;
    HashTable_ImplParameters& operator=(const HashTable_ImplParameters&);
 
  public:
    // CREATORS
 
    /// Create a `HashTable_ImplParameters` object having default
    /// constructed `HASHER` and `COMPARATOR` functors, and using the
    /// specified `allocator` to provide a `BidirectionalNodePool`.
    explicit HashTable_ImplParameters(const ALLOCATOR& allocator);
 
    /// Create a `HashTable_ImplParameters` object having the specified
    /// `hash` and `compare` functors, and using the specified `allocator`
    /// to provide a `BidirectionalNodePool`.
    HashTable_ImplParameters(const HASHER&     hash,
                             const COMPARATOR& compare,
                             const ALLOCATOR&  allocator);
 
    /// Create a `HashTable_ImplParameters` object having the same `hasher`
    /// and `comparator` attributes as the specified `original`, and
    /// providing a `BidirectionalNodePool` using the specified `allocator`.
    HashTable_ImplParameters(const HashTable_ImplParameters& original,
                             const ALLOCATOR&                allocator);
 
    /// Create a `HashTable_ImplParameters` object with a copy of the
    /// `hasher` and `comparator` attributes associated with the specified
    /// `original` parameters object, and adopting all outstanding memory
    /// allocations and the allocator associated with `original`.  Note that
    /// `original` is left in a valid but unspecified state.
    HashTable_ImplParameters(
                         bslmf::MovableRef<HashTable_ImplParameters> original);
 
    // MANIPULATORS
 
    /// Return a reference offering modifiable access to the `nodeFactory`
    /// owned by this object.
    NodeFactory& nodeFactory();
 
    /// Efficiently exchange the value, functor, and allocator of this
    /// object with those of the specified `other` object.  This method
    /// provides the no-throw exception-safety guarantee.
    void quickSwapExchangeAllocators(HashTable_ImplParameters *other);
 
    /// Efficiently exchange the value and functors this object with those
    /// of the specified `other` object.  This method provides the no-throw
    /// exception-safety guarantee.  The behavior is undefined unless this
    /// object was created with the same allocator as `other`.
    void quickSwapRetainAllocators(HashTable_ImplParameters *other);
 
    // ACCESSORS
 
    /// Return a reference offering non-modifiable access to the
    /// `comparator` functor owned by this object.
    const BaseComparator& comparator() const;
 
    /// Return the hash code for the specified `key` using a copy of the
    /// hash functor supplied at construction.  Note that this function is
    /// provided as a common way to resolve `const_cast` issues in the case
    /// that the stored hash functor has a function call operator that is
    /// not declared as `const`.
    template <class DEDUCED_KEY>
    std::size_t hashCodeForKey(DEDUCED_KEY& key) const;
 
    /// Return a reference offering non-modifiable access to the `hasher`
    /// functor owned by this object.
    const BaseHasher& hasher() const;
 
    /// Return a reference offering non-modifiable access to the
    /// `nodeFactory` owned by this object.
    const NodeFactory& nodeFactory() const;
 
    /// Return a reference offering non-modifiable access to the
    /// `comparator` functor owned by this object.
    const COMPARATOR& originalComparator() const;
 
    /// Return a reference offering non-modifiable access to the `hasher`
    /// functor owned by this object.
    const HASHER& originalHasher() const;
};
 
// ============================================================================
//                  TEMPLATE AND INLINE FUNCTION DEFINITIONS
// ============================================================================
 
                   // ---------------------------
                   // class HashTable_HashWrapper
                   // ---------------------------
 
template <class FUNCTOR>
inline
HashTable_HashWrapper<FUNCTOR>::HashTable_HashWrapper()
: d_functor()
{
}
 
template <class FUNCTOR>
inline
HashTable_HashWrapper<FUNCTOR>::HashTable_HashWrapper(const FUNCTOR& fn)
: d_functor(fn)
{
}
 
template <class FUNCTOR>
template <class ARG_TYPE>
inline
std::size_t
HashTable_HashWrapper<FUNCTOR>::operator()(ARG_TYPE& arg) const
{
    return d_functor(arg);
}
 
template <class FUNCTOR>
inline
const FUNCTOR& HashTable_HashWrapper<FUNCTOR>::functor() const
{
    return d_functor;
}
 
template <class FUNCTOR>
inline
void HashTable_HashWrapper<FUNCTOR>::swap(HashTable_HashWrapper &other)
{
    using std::swap;
    swap(d_functor, other.d_functor);
}
 
                 // 'const FUNCTOR' partial specialization
 
template <class FUNCTOR>
inline
HashTable_HashWrapper<const FUNCTOR>::HashTable_HashWrapper()
: d_functor()
{
}
 
template <class FUNCTOR>
inline
HashTable_HashWrapper<const FUNCTOR>::HashTable_HashWrapper(const FUNCTOR& fn)
: d_functor(fn)
{
}
 
template <class FUNCTOR>
template <class ARG_TYPE>
inline
std::size_t
HashTable_HashWrapper<const FUNCTOR>::operator()(ARG_TYPE& arg) const
{
    return d_functor(arg);
}
 
template <class FUNCTOR>
inline
const FUNCTOR& HashTable_HashWrapper<const FUNCTOR>::functor() const
{
    return d_functor;
}
 
                 // 'FUNCTOR &' partial specialization
 
template <class FUNCTOR>
inline
HashTable_HashWrapper<FUNCTOR &>::HashTable_HashWrapper(FUNCTOR& fn)
: d_functor(fn)
{
}
 
template <class FUNCTOR>
template <class ARG_TYPE>
inline
std::size_t
HashTable_HashWrapper<FUNCTOR &>::operator()(ARG_TYPE& arg) const
{
    return d_functor(arg);
}
 
template <class FUNCTOR>
inline
FUNCTOR& HashTable_HashWrapper<FUNCTOR &>::functor() const
{
    return d_functor;
}
 
                   // ---------------------------------
                   // class HashTable_ComparatorWrapper
                   // ---------------------------------
 
template <class FUNCTOR>
inline
HashTable_ComparatorWrapper<FUNCTOR>::HashTable_ComparatorWrapper()
: d_functor()
{
}
 
template <class FUNCTOR>
inline
HashTable_ComparatorWrapper<FUNCTOR>::
HashTable_ComparatorWrapper(const FUNCTOR& fn)
: d_functor(fn)
{
}
 
template <class FUNCTOR>
template <class ARG1_TYPE, class ARG2_TYPE>
inline
bool
HashTable_ComparatorWrapper<FUNCTOR>::operator()(ARG1_TYPE& arg1,
                                                 ARG2_TYPE& arg2) const
{
    return d_functor(arg1, arg2);
}
 
template <class FUNCTOR>
const FUNCTOR& HashTable_ComparatorWrapper<FUNCTOR>::functor() const
{
    return d_functor;
}
 
template <class FUNCTOR>
inline
void
HashTable_ComparatorWrapper<FUNCTOR>::swap(HashTable_ComparatorWrapper &other)
{
    using std::swap;
    swap(d_functor, other.d_functor);
}
 
                 // 'const FUNCTOR' partial specialization
 
template <class FUNCTOR>
inline
HashTable_ComparatorWrapper<const FUNCTOR>::HashTable_ComparatorWrapper()
: d_functor()
{
}
 
template <class FUNCTOR>
inline
HashTable_ComparatorWrapper<const FUNCTOR>::
HashTable_ComparatorWrapper(const FUNCTOR& fn)
: d_functor(fn)
{
}
 
template <class FUNCTOR>
template <class ARG1_TYPE, class ARG2_TYPE>
inline
bool
HashTable_ComparatorWrapper<const FUNCTOR>::operator()(ARG1_TYPE& arg1,
                                                       ARG2_TYPE& arg2) const
{
    return d_functor(arg1, arg2);
}
 
template <class FUNCTOR>
const FUNCTOR& HashTable_ComparatorWrapper<const FUNCTOR>::functor() const
{
    return d_functor;
}
 
                 // 'FUNCTOR &' partial specialization
 
template <class FUNCTOR>
inline
HashTable_ComparatorWrapper<FUNCTOR &>::
HashTable_ComparatorWrapper(FUNCTOR& fn)
: d_functor(fn)
{
}
 
template <class FUNCTOR>
template <class ARG1_TYPE, class ARG2_TYPE>
inline
bool
HashTable_ComparatorWrapper<FUNCTOR &>::operator()(ARG1_TYPE& arg1,
                                                   ARG2_TYPE& arg2) const
{
    return d_functor(arg1, arg2);
}
 
template <class FUNCTOR>
inline
FUNCTOR& HashTable_ComparatorWrapper<FUNCTOR &>::functor() const
{
    return d_functor;
}
 
                    // ---------------------------
                    // class HashTable_NodeProctor
                    // ---------------------------
 
// CREATORS
template <class FACTORY>
inline
HashTable_NodeProctor<FACTORY>::HashTable_NodeProctor(
                                            FACTORY                   *factory,
                                            bslalg::BidirectionalLink *node)
: d_factory_p(factory)
, d_node_p(node)
{
    BSLS_ASSERT_SAFE(factory);
}
 
template <class FACTORY>
inline
HashTable_NodeProctor<FACTORY>::~HashTable_NodeProctor()
{
    if (d_node_p) {
        d_factory_p->deleteNode(d_node_p);
    }
}
 
// MANIPULATORS
template <class FACTORY>
inline
void HashTable_NodeProctor<FACTORY>::release()
{
    d_node_p = 0;
}
 
                    // ----------------------------
                    // class HashTable_ArrayProctor
                    // ----------------------------
 
// CREATORS
template <class FACTORY>
inline
HashTable_ArrayProctor<FACTORY>::HashTable_ArrayProctor(
                                              FACTORY                 *factory,
                                              bslalg::HashTableAnchor *anchor)
: d_factory_p(factory)
, d_anchor_p(anchor)
{
    BSLS_ASSERT_SAFE(factory);
    BSLS_ASSERT_SAFE(anchor);
}
 
template <class FACTORY>
inline
HashTable_ArrayProctor<FACTORY>::~HashTable_ArrayProctor()
{
    if (d_anchor_p) {
        HashTable_Util::destroyBucketArray(d_anchor_p->bucketArrayAddress(),
                                           d_anchor_p->bucketArraySize(),
                                           d_factory_p->allocator());
 
        bslalg::BidirectionalLink *root = d_anchor_p->listRootAddress();
        while (root) {
            bslalg::BidirectionalLink *next = root->nextLink();
            d_factory_p->deleteNode(root);
            root = next;
        }
    }
}
 
// MANIPULATORS
template <class FACTORY>
inline
void HashTable_ArrayProctor<FACTORY>::release()
{
    d_anchor_p = 0;
}
 
                    // --------------------
                    // class HashTable_Util
                    // --------------------
 
template <class TYPE>
inline
void HashTable_Util::assertNotNullPointer(TYPE&)
{
}
 
template <class TYPE>
inline
void HashTable_Util::assertNotNullPointer(TYPE * const& ptr)
{
    // silence "unused parameter" warning in release builds:
    (void) ptr;
    BSLS_ASSERT(ptr);
}
 
template <class TYPE>
inline
void HashTable_Util::assertNotNullPointer(TYPE * & ptr)
{
    // silence "unused parameter" warning in release builds:
    (void) ptr;
    BSLS_ASSERT(ptr);
}
 
template <class ALLOCATOR>
inline
void HashTable_Util::destroyBucketArray(
                                     bslalg::HashTableBucket  *data,
                                     std::size_t               bucketArraySize,
                                     const ALLOCATOR&          allocator)
{
    BSLS_ASSERT_SAFE(data);
    BSLS_ASSERT_SAFE(
                  (1  < bucketArraySize
                     && HashTable_ImpDetails::defaultBucketAddress() != data)
               || (1 == bucketArraySize
                     && HashTable_ImpDetails::defaultBucketAddress() == data));
 
#ifdef BSLS_ASSERT_SAFE_IS_ACTIVE
    typedef typename bsl::allocator_traits<ALLOCATOR>::size_type AllocSizeType;
    BSLS_ASSERT_SAFE(
                 bucketArraySize <= std::numeric_limits<AllocSizeType>::max());
#endif
 
    if (HashTable_ImpDetails::defaultBucketAddress() != data) {
        bslma::AllocatorUtil::deallocateObject(allocator, data,
                                               bucketArraySize);
    }
}
 
template <class ALLOCATOR>
inline
void HashTable_Util::initAnchor(bslalg::HashTableAnchor *anchor,
                                std::size_t              bucketArraySize,
                                const ALLOCATOR&         allocator)
{
    BSLS_ASSERT_SAFE(anchor);
    BSLS_ASSERT_SAFE(0 != bucketArraySize);
 
#ifdef BSLS_ASSERT_SAFE_IS_ACTIVE
    typedef typename bsl::allocator_traits<ALLOCATOR>::size_type AllocSizeType;
    BSLS_ASSERT_SAFE(
                 bucketArraySize <= std::numeric_limits<AllocSizeType>::max());
#endif
 
    typedef bslalg::HashTableBucket Bucket;
    Bucket *data = bslma::AllocatorUtil::allocateObject<Bucket>(allocator,
                                                              bucketArraySize);
 
    std::fill_n(data, bucketArraySize, Bucket());
 
    anchor->setBucketArrayAddressAndSize(data, bucketArraySize);
}
 
                   //-------------------------------
                   // class HashTable_ImplParameters
                   //-------------------------------
 
// CREATORS
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
HashTable_ImplParameters(const ALLOCATOR& allocator)
: BaseHasher()
, BaseComparator()
, d_nodeFactory(allocator)
{
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
HashTable_ImplParameters(const HASHER&     hash,
                         const COMPARATOR& compare,
                         const ALLOCATOR&  allocator)
: BaseHasher(hash)
, BaseComparator(compare)
, d_nodeFactory(allocator)
{
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
HashTable_ImplParameters(const HashTable_ImplParameters& original,
                         const ALLOCATOR&                allocator)
: BaseHasher(static_cast<const BaseHasher&>(original))
, BaseComparator(static_cast<const BaseComparator&>(original))
, d_nodeFactory(allocator)
{
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
HashTable_ImplParameters(bslmf::MovableRef<HashTable_ImplParameters> original)
: BaseHasher(static_cast<const BaseHasher&>(original))
, BaseComparator(static_cast<const BaseComparator&>(original))
, d_nodeFactory(MoveUtil::move(MoveUtil::access(original).d_nodeFactory))
{
}
 
// MANIPULATORS
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
typename HashTable_ImplParameters<KEY_CONFIG,
                                  HASHER,
                                  COMPARATOR,
                                  ALLOCATOR>::NodeFactory &
HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
nodeFactory()
{
    return d_nodeFactory;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
void HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
quickSwapExchangeAllocators(HashTable_ImplParameters *other)
{
    BSLS_ASSERT_SAFE(other);
 
    using std::swap;
    swap(*static_cast<BaseHasher*>(this), *static_cast<BaseHasher*>(other));
 
    swap(*static_cast<BaseComparator*>(this),
         *static_cast<BaseComparator*>(other));
 
    nodeFactory().swapExchangeAllocators(other->nodeFactory());
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
void HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
quickSwapRetainAllocators(HashTable_ImplParameters *other)
{
    BSLS_ASSERT_SAFE(other);
 
    using std::swap;
    swap(*static_cast<BaseHasher*>(this), *static_cast<BaseHasher*>(other));
 
    swap(*static_cast<BaseComparator*>(this),
         *static_cast<BaseComparator*>(other));
 
    nodeFactory().swapRetainAllocators(other->nodeFactory());
}
 
// ACCESSORS
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
const typename HashTable_ImplParameters<KEY_CONFIG,
                                        HASHER,
                                        COMPARATOR,
                                        ALLOCATOR>::BaseComparator &
HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
comparator() const
{
    return *this;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class DEDUCED_KEY>
inline
std::size_t HashTable_ImplParameters<KEY_CONFIG,
                                     HASHER,
                                     COMPARATOR,
                                     ALLOCATOR>::
hashCodeForKey(DEDUCED_KEY& key) const
{
    return static_cast<const BaseHasher &>(*this)(key);
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
const typename HashTable_ImplParameters<KEY_CONFIG,
                                        HASHER,
                                        COMPARATOR,
                                        ALLOCATOR>::BaseHasher &
HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::hasher()
                                                                         const
{
    return *this;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
const typename HashTable_ImplParameters<KEY_CONFIG,
                                        HASHER,
                                        COMPARATOR,
                                        ALLOCATOR>::NodeFactory &
HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
nodeFactory() const
{
    return d_nodeFactory;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
const COMPARATOR&
HashTable_ImplParameters<KEY_CONFIG,
                         HASHER,
                         COMPARATOR,
                         ALLOCATOR>::originalComparator() const
{
    return static_cast<const BaseComparator *>(this)->functor();
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
const HASHER& HashTable_ImplParameters<KEY_CONFIG,
                                       HASHER,
                                       COMPARATOR,
                                       ALLOCATOR>::originalHasher() const
{
    return static_cast<const BaseHasher *>(this)->functor();
}
 
                        //----------------
                        // class HashTable
                        //----------------
 
// CREATORS
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
HashTable(const ALLOCATOR& basicAllocator)
: d_parameters(basicAllocator)
, d_anchor(HashTable_ImpDetails::defaultBucketAddress(), 1, 0)
, d_size()
, d_capacity()
, d_maxLoadFactor(1.0)
{
    BSLMF_ASSERT(!bsl::is_pointer<HASHER>::value &&
                 !bsl::is_pointer<COMPARATOR>::value);
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
HashTable(const HASHER&     hash,
          const COMPARATOR& compare,
          SizeType          initialNumBuckets,
          float             initialMaxLoadFactor,
          const ALLOCATOR&  basicAllocator)
: d_parameters(hash, compare, basicAllocator)
, d_anchor(HashTable_ImpDetails::defaultBucketAddress(), 1, 0)
, d_size()
, d_capacity(0)
, d_maxLoadFactor(initialMaxLoadFactor)
{
    BSLS_ASSERT_SAFE(0.0f < initialMaxLoadFactor);
 
    if (bsl::is_pointer<HASHER>::value) {
        HashTable_Util::assertNotNullPointer(hash);
    }
    if (bsl::is_pointer<COMPARATOR>::value) {
        HashTable_Util::assertNotNullPointer(compare);
    }
 
    if (0 != initialNumBuckets) {
        size_t capacity;  // This may be a different type than SizeType.
        size_t numBuckets = HashTable_ImpDetails::growBucketsForLoadFactor(
                                        &capacity,
                                        1,
                                        static_cast<size_t>(initialNumBuckets),
                                        d_maxLoadFactor);
        HashTable_Util::initAnchor(&d_anchor, numBuckets, basicAllocator);
        d_capacity = static_cast<SizeType>(capacity);
    }
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
HashTable(const HashTable& original)
: d_parameters(
  original.d_parameters,
  AllocatorTraits::select_on_container_copy_construction(original.allocator()))
, d_anchor(HashTable_ImpDetails::defaultBucketAddress(), 1, 0)
, d_size(original.d_size)
, d_capacity(0)
, d_maxLoadFactor(original.d_maxLoadFactor)
{
    if (0 < d_size) {
        d_parameters.nodeFactory().reserveNodes(original.d_size);
        this->copyDataStructure(original.d_anchor.listRootAddress());
    }
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::HashTable(
                            BloombergLP::bslmf::MovableRef<HashTable> original)
: d_parameters(MoveUtil::move(MoveUtil::access(original).d_parameters))
, d_anchor(HashTable_ImpDetails::defaultBucketAddress(), 1, 0)
, d_size()
, d_capacity()
, d_maxLoadFactor(1.0)
{
    HashTable& lvalue = original;
    using std::swap;
    swap(d_anchor,        lvalue.d_anchor);
    swap(d_size,          lvalue.d_size);
    swap(d_capacity,      lvalue.d_capacity);
    swap(d_maxLoadFactor, lvalue.d_maxLoadFactor);
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
HashTable(const HashTable& original, const ALLOCATOR& basicAllocator)
: d_parameters(original.d_parameters, basicAllocator)
, d_anchor(HashTable_ImpDetails::defaultBucketAddress(), 1, 0)
, d_size(original.d_size)
, d_capacity(0)
, d_maxLoadFactor(original.d_maxLoadFactor)
{
    if (0 < d_size) {
        d_parameters.nodeFactory().reserveNodes(original.d_size);
        this->copyDataStructure(original.d_anchor.listRootAddress());
    }
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
HashTable(bslmf::MovableRef<HashTable> original,
          const ALLOCATOR&             basicAllocator)
: d_parameters(MoveUtil::access(original).d_parameters.originalHasher(),
               MoveUtil::access(original).d_parameters.originalComparator(),
               basicAllocator)
, d_anchor(HashTable_ImpDetails::defaultBucketAddress(), 1, 0)
, d_size()
, d_capacity()
, d_maxLoadFactor(1.0)
{
    HashTable& lvalue = original;
    if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
                                    basicAllocator == lvalue.allocator())) {
        d_parameters.nodeFactory().adopt(
                            MoveUtil::move(lvalue.d_parameters.nodeFactory()));
        using std::swap;
        swap(d_anchor,        lvalue.d_anchor);
        swap(d_size,          lvalue.d_size);
        swap(d_capacity,      lvalue.d_capacity);
        swap(d_maxLoadFactor, lvalue.d_maxLoadFactor);
    }
    else {
        d_size = lvalue.d_size;
        d_maxLoadFactor = lvalue.d_maxLoadFactor;
        if (0 < d_size) {
            // 'original' left in the default state
            bslalg::HashTableAnchor anchor(
                           HashTable_ImpDetails::defaultBucketAddress(), 1, 0);
            using std::swap;
            swap(anchor, lvalue.d_anchor);
 
            lvalue.d_size = 0;
            lvalue.d_capacity = 0;
            lvalue.d_maxLoadFactor = 1.0f;
 
            HashTable_ArrayProctor<typename ImplParameters::NodeFactory>
                          arrayProctor(&lvalue.d_parameters.nodeFactory(),
                                       &anchor);
 
            d_parameters.nodeFactory().reserveNodes(d_size);
            this->moveDataStructure(anchor.listRootAddress());
 
            // 'arrayProctor' will care of deleting the nodes
        }
    }
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::~HashTable()
{
#if defined(BDE_BUILD_TARGET_SAFE_2)
    // ASSERT class invariant only in SAFE_2 builds.  Note that we specifically
    // use the MallocFree allocator, rather than allowing the default allocator
    // to supply memory to this state-checking function, in case the object
    // allocator *is* the default allocator, and so may be restricted during
    // testing.  This would cause the test below to fail by throwing a bad
    // allocation exception, and so result in a throwing destructor.  While the
    // MallocFree allocator might also run out of resources, that is not the
    // kind of catastrophic failure we are concerned with handling in an
    // invariant check that runs only in SAFE_2 builds from a destructor.
 
    BSLS_ASSERT_SAFE(bslalg::HashTableImpUtil::isWellFormed<KEY_CONFIG>(
                                 this->d_anchor,
                                 this->d_parameters.hasher(),
                                 HashTable_ImpDetails::incidentalAllocator()));
#endif
 
    this->removeAllAndDeallocate();
}
 
// PRIVATE MANIPULATORS
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::copyDataStructure(
                                             bslalg::BidirectionalLink *cursor)
{
    BSLS_ASSERT(0 != cursor);
    BSLS_ASSERT(0 < d_size);
 
    // This function will completely replace 'this->d_anchor's state.  It is
    // the caller's responsibility to ensure this will not leak resources owned
    // only by the previous state, such as the linked list.
 
    // Allocate an appropriate number of buckets
 
    size_t capacity;
    size_t numBuckets = HashTable_ImpDetails::growBucketsForLoadFactor(
                                                   &capacity,
                                                   static_cast<size_t>(d_size),
                                                   2,
                                                   d_maxLoadFactor);
 
    d_anchor.setListRootAddress(0);
    HashTable_Util::initAnchor(&d_anchor, numBuckets, this->allocator());
 
    // create a proctor for d_anchor's allocated array, and the list to follow.
 
    HashTable_ArrayProctor<typename ImplParameters::NodeFactory>
                          arrayProctor(&d_parameters.nodeFactory(), &d_anchor);
 
    d_capacity = static_cast<SizeType>(capacity);
 
    do {
        // Computing hash code depends on user-supplied code, and may throw.
        // Therefore, obtain the hash code from the node we are about to copy,
        // before any memory is allocated, so there is no risk of leaking an
        // object.  The hash code must be the same for both elements.
 
        size_t hashCode = this->hashCodeForNode(cursor);
        bslalg::BidirectionalLink *newNode =
                                 d_parameters.nodeFactory().cloneNode(*cursor);
 
        bslalg::HashTableImpUtil::insertAtBackOfBucket(&d_anchor,
                                                       newNode,
                                                       hashCode);
    }
    while (0 != (cursor = cursor->nextLink()));
 
    // release the proctor
 
    arrayProctor.release();
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::moveDataStructure(
                                             bslalg::BidirectionalLink *cursor)
{
    BSLS_ASSERT(0 != cursor);
    BSLS_ASSERT(0 < d_size);
 
    // This function will completely replace 'this->d_anchor's state.  It is
    // the caller's responsibility to ensure this will not leak resources owned
    // only by the previous state, such as the linked list.
 
    // Allocate an appropriate number of buckets
 
    size_t capacity;
    size_t numBuckets = HashTable_ImpDetails::growBucketsForLoadFactor(
                                                   &capacity,
                                                   static_cast<size_t>(d_size),
                                                   2,
                                                   d_maxLoadFactor);
 
    d_anchor.setListRootAddress(0);
    HashTable_Util::initAnchor(&d_anchor, numBuckets, this->allocator());
 
    d_capacity = static_cast<SizeType>(capacity);
 
    // create a proctor for d_anchor's allocated array, and the list to follow.
 
    HashTable_ArrayProctor<typename ImplParameters::NodeFactory>
                          arrayProctor(&d_parameters.nodeFactory(), &d_anchor);
 
    do {
        // Computing hash code depends on user-supplied code, and may throw.
        // Therefore, obtain the hash code from the node we are about to copy,
        // before any memory is allocated, so there is no risk of leaking an
        // object.  The hash code must be the same for both elements.
 
        size_t hashCode = this->hashCodeForNode(cursor);
        bslalg::BidirectionalLink *newNode =
                            d_parameters.nodeFactory().moveIntoNewNode(cursor);
 
        bslalg::HashTableImpUtil::insertAtBackOfBucket(&d_anchor,
                                                       newNode,
                                                       hashCode);
    }
    while (0 != (cursor = cursor->nextLink()));
 
    // release the proctor
 
    arrayProctor.release();
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
quickSwapExchangeAllocators(HashTable *other)
{
    BSLS_ASSERT_SAFE(other);
 
    d_parameters.quickSwapExchangeAllocators(&other->d_parameters);
 
    using std::swap;
    swap(d_anchor,        other->d_anchor);
    swap(d_size,          other->d_size);
    swap(d_capacity,      other->d_capacity);
    swap(d_maxLoadFactor, other->d_maxLoadFactor);
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
quickSwapRetainAllocators(HashTable *other)
{
    BSLS_ASSERT_SAFE(other);
    BSLS_ASSERT_SAFE(this->allocator() == other->allocator());
 
    d_parameters.quickSwapRetainAllocators(&other->d_parameters);
 
    using std::swap;
    swap(d_anchor,        other->d_anchor);
    swap(d_size,          other->d_size);
    swap(d_capacity,      other->d_capacity);
    swap(d_maxLoadFactor, other->d_maxLoadFactor);
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
rehashIntoExactlyNumBuckets(SizeType newNumBuckets, SizeType capacity)
{
    /// An object of this proctor class guarantees that, if an exception is
    /// thrown by a user-supplied hash functor, the container remains in a
    /// valid, usable (but unspecified) state.  In fact, that state will be
    /// empty, as there is no reliable way to re-index a bucket array if the
    /// hash functor is throwing, and the array is potentially corrupted
    /// following a failed ImpUtil::rehash call.
    ///
    /// See @ref bslstl_hashtable 
    class Proctor {
 
      private:
        HashTable               *d_table_p;
        bslalg::HashTableAnchor *d_originalAnchor_p;
        bslalg::HashTableAnchor *d_newAnchor_p;
 
#if !defined(BSLS_PLATFORM_CMP_MSVC)
        // Microsoft warns if these methods are declared private.
 
      private:
        // NOT IMPLEMENTED
        Proctor(const Proctor&); // = delete;
        Proctor& operator=(const Proctor&); // = delete;
#endif
 
      public:
        // CREATORS
        Proctor(HashTable               *table,
                bslalg::HashTableAnchor *originalAnchor,
                bslalg::HashTableAnchor *newAnchor)
        : d_table_p(table)
        , d_originalAnchor_p(originalAnchor)
        , d_newAnchor_p(newAnchor)
        {
            BSLS_ASSERT_SAFE(table);
            BSLS_ASSERT_SAFE(originalAnchor);
            BSLS_ASSERT_SAFE(newAnchor);
        }
 
        ~Proctor()
        {
            if (d_originalAnchor_p) {
                // Not dismissed, and the newAnchor now holds the correct
                // list-root.
 
                d_originalAnchor_p->setListRootAddress(
                                             d_newAnchor_p->listRootAddress());
                d_table_p->removeAll();
            }
 
            // Always destroy the spare anchor's bucket array at the end of
            // scope.  On a non-exceptional run, this will effectively be the
            // original bucket-array, as the anchors are swapped.
 
            HashTable_Util::destroyBucketArray(
                                           d_newAnchor_p->bucketArrayAddress(),
                                           d_newAnchor_p->bucketArraySize(),
                                           d_table_p->allocator());
        }
 
        // MANIPULATORS
        void dismiss()
        {
            d_originalAnchor_p = 0;
        }
    };
 
    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 
    // Now that 'anchor' is not default constructible, we take a copy of the
    // anchor in the table.  Would it be better for 'initAnchor' to be replaced
    // with a 'createArrayOfEmptyBuckets' function, and we use the result to
    // construct the 'newAnchor'?
 
    bslalg::HashTableAnchor newAnchor(0, 0, 0);
    HashTable_Util::initAnchor(&newAnchor,
                               static_cast<size_t>(newNumBuckets),
                               this->allocator());
 
    Proctor cleanUpIfUserHashThrows(this, &d_anchor, &newAnchor);
 
    if (d_anchor.listRootAddress()) {
        bslalg::HashTableImpUtil::rehash<KEY_CONFIG>(
                                          &newAnchor,
                                          this->d_anchor.listRootAddress(),
                                          this->d_parameters.hasher());
    }
 
    cleanUpIfUserHashThrows.dismiss();
 
    d_anchor.swap(newAnchor);
    d_capacity = capacity;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::removeAllAndDeallocate()
{
    this->removeAllImp();
    HashTable_Util::destroyBucketArray(d_anchor.bucketArrayAddress(),
                                       d_anchor.bucketArraySize(),
                                       this->allocator());
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::removeAllImp()
{
    typedef bslalg::BidirectionalLink BidirectionalLink;
 
    // Doing too much book-keeping of hash table - look for a more efficient
    // dispose-as-we-walk, that simply resets table.Anchor.next = 0, and
    // assigns the buckets index all null pointers
 
    if (BidirectionalLink *root = d_anchor.listRootAddress()) {
        BidirectionalLink *next;
        do {
            next = root->nextLink();
            d_parameters.nodeFactory().deleteNode(
                                                static_cast<NodeType *>(root));
        }
        while(0 != (root = next));
    }
}
 
// PRIVATE ACCESSORS
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class DEDUCED_KEY>
inline
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::find(
                                                  DEDUCED_KEY& key,
                                                  std::size_t  hashValue) const
{
    return bslalg::HashTableImpUtil::find<KEY_CONFIG>(
                                                     d_anchor,
                                                     key,
                                                     d_parameters.comparator(),
                                                     hashValue);
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
bslalg::HashTableBucket *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::getBucketAddress(
                                                    SizeType bucketIndex) const
{
    BSLS_ASSERT_SAFE(bucketIndex < this->numBuckets());
 
    return d_anchor.bucketArrayAddress() + bucketIndex;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
std::size_t
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::hashCodeForNode(
                                         bslalg::BidirectionalLink *node) const
{
    BSLS_ASSERT_SAFE(node);
 
    return d_parameters.hashCodeForKey(
                       bslalg::HashTableImpUtil::extractKey<KEY_CONFIG>(node));
}
 
// MANIPULATORS
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>&
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::operator=(
                                                          const HashTable& rhs)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(this != &rhs)) {
 
        if (AllocatorTraits::propagate_on_container_copy_assignment::value) {
            HashTable other(rhs, rhs.allocator());
            quickSwapExchangeAllocators(&other);
        }
        else {
            HashTable other(rhs, this->allocator());
            quickSwapRetainAllocators(&other);
        }
    }
    return *this;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>&
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::operator=(
                                              bslmf::MovableRef<HashTable> rhs)
{
    HashTable& lvalue = rhs;
    if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(this != &lvalue)) {
        if (allocator() == lvalue.allocator()) {
            HashTable other(MoveUtil::move(lvalue));
            quickSwapRetainAllocators(&other);
        }
        else if (
              AllocatorTraits::propagate_on_container_move_assignment::value) {
            HashTable other(MoveUtil::move(lvalue));
            quickSwapExchangeAllocators(&other);
        }
        else {
            HashTable other(MoveUtil::move(lvalue), allocator());
            quickSwapRetainAllocators(&other);
        }
    }
    return *this;
}
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class... ARGS>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
                                                           ARGS&&... arguments)
{
    typedef bslalg::HashTableImpUtil ImpUtil;
 
    // Rehash (if appropriate) first as it will reduce load factor and so
    // potentially improve the 'find' time.
 
    if (d_size >= d_capacity) {
        this->rehashForNumBuckets(numBuckets() * 2);
    }
 
    // Next we must create the node from the constructor arguments provided.
 
    bslalg::BidirectionalLink *newNode =
        d_parameters.nodeFactory().emplaceIntoNewNode(
                            BSLS_COMPILERFEATURES_FORWARD(ARGS, arguments)...);
 
    // This node needs wrapping in a proctor, in case either of the user-
    // supplied functors throws an exception.
 
    HashTable_NodeProctor<typename ImplParameters::NodeFactory>
                             nodeProctor(&d_parameters.nodeFactory(), newNode);
 
    // Now we can search for the node in the table, being careful to compute
    // the hash value only once.
 
    size_t hashCode = this->d_parameters.hashCodeForKey(
                                     ImpUtil::extractKey<KEY_CONFIG>(newNode));
    bslalg::BidirectionalLink *position = this->find(
                                      ImpUtil::extractKey<KEY_CONFIG>(newNode),
                                      hashCode);
 
    if (!position) {
        ImpUtil::insertAtFrontOfBucket(&d_anchor, newNode, hashCode);
    }
    else {
        ImpUtil::insertAtPosition(&d_anchor, newNode, hashCode, position);
    }
    nodeProctor.release();
 
    ++d_size;
 
    return newNode;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class... ARGS>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
                                          bslalg::BidirectionalLink *hint,
                                          ARGS&&...                  arguments)
{
    typedef bslalg::HashTableImpUtil ImpUtil;
 
    // Rehash (if appropriate) first as it will reduce load factor and so
    // potentially improve the potential 'find' time later.
 
    if (d_size >= d_capacity) {
        this->rehashForNumBuckets(numBuckets() * 2);
    }
 
    // Next we must create the node from the constructor arguments provided.
 
    bslalg::BidirectionalLink *newNode =
        d_parameters.nodeFactory().emplaceIntoNewNode(
                            BSLS_COMPILERFEATURES_FORWARD(ARGS, arguments)...);
 
    // There is potential for the user-supplied hasher and comparator to throw,
    // so now we need to manage our 'newNode' with a proctor.
 
    HashTable_NodeProctor<typename ImplParameters::NodeFactory>
                             nodeProctor(&d_parameters.nodeFactory(), newNode);
 
    // Insert logic, first test the hint
 
    size_t hashCode = this->d_parameters.hashCodeForKey(
                                     ImpUtil::extractKey<KEY_CONFIG>(newNode));
    if (!hint
     || !d_parameters.comparator()(ImpUtil::extractKey<KEY_CONFIG>(newNode),
                                   ImpUtil::extractKey<KEY_CONFIG>(hint))) {
        hint = this->find(ImpUtil::extractKey<KEY_CONFIG>(newNode), hashCode);
    }
 
    if (!hint) {
        ImpUtil::insertAtFrontOfBucket(&d_anchor, newNode, hashCode);
    }
    else {
        ImpUtil::insertAtPosition(&d_anchor, newNode, hashCode, hint);
    }
    nodeProctor.release();
 
    ++d_size;
 
    return newNode;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class... ARGS>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
                                              bool             *isInsertedFlag,
                                              ARGS&&...         arguments)
{
    BSLS_ASSERT(isInsertedFlag);
 
    typedef bslalg::HashTableImpUtil ImpUtil;
 
    // Rehash (if appropriate) first as it will reduce load factor and so
    // potentially improve the potential 'find' time later.
 
    if (d_size >= d_capacity) {
        this->rehashForNumBuckets(numBuckets() * 2);
    }
 
    // Next we must create the node from the constructor arguments provided.
 
    bslalg::BidirectionalLink *newNode =
        d_parameters.nodeFactory().emplaceIntoNewNode(
                            BSLS_COMPILERFEATURES_FORWARD(ARGS, arguments)...);
 
    // There is potential for the user-supplied hasher and comparator to throw,
    // so now we need to manage our 'newNode' with a proctor.
 
    HashTable_NodeProctor<typename ImplParameters::NodeFactory>
                             nodeProctor(&d_parameters.nodeFactory(), newNode);
 
    // Insert logic, first test the hint
 
    size_t hashCode = this->d_parameters.hashCodeForKey(
                                     ImpUtil::extractKey<KEY_CONFIG>(newNode));
    bslalg::BidirectionalLink *position = this->find(
                                      ImpUtil::extractKey<KEY_CONFIG>(newNode),
                                      hashCode);
 
    *isInsertedFlag = (!position);
 
    if(!position) {
        if (d_size >= d_capacity) {
            this->rehashForNumBuckets(numBuckets() * 2);
        }
 
        ImpUtil::insertAtFrontOfBucket(&d_anchor, newNode, hashCode);
        nodeProctor.release();
 
        ++d_size;
        position = newNode;
    }
 
    return position;
}
#endif
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::insertIfMissing(
                                                            const KeyType& key)
{
    bool dummy = false;
    return tryEmplace(&dummy, (bslalg::BidirectionalLink*)0, key);
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::insertIfMissing(
                                        bslmf::MovableRef<NonConstKeyType> key)
{
    bool dummy = false;
    return tryEmplace(&dummy,
                      (bslalg::BidirectionalLink *)0,
                       MoveUtil::move(key));
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::insertIfMissing(
                                              bool             *isInsertedFlag,
                                              const ValueType&  value)
{
    BSLS_ASSERT(isInsertedFlag);
 
    size_t hashCode = this->d_parameters.hashCodeForKey(
                                                KEY_CONFIG::extractKey(value));
    bslalg::BidirectionalLink *position = this->find(
                                                 KEY_CONFIG::extractKey(value),
                                                 hashCode);
 
    *isInsertedFlag = (!position);
 
    if(!position) {
        if (d_size >= d_capacity) {
            this->rehashForNumBuckets(numBuckets() * 2);
        }
 
        position = d_parameters.nodeFactory().emplaceIntoNewNode(value);
        bslalg::HashTableImpUtil::insertAtFrontOfBucket(&d_anchor,
                                                        position,
                                                        hashCode);
        ++d_size;
    }
 
    return position;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::insertIfMissing(
                                   bool                        *isInsertedFlag,
                                   bslmf::MovableRef<ValueType> value)
{
    ValueType& lvalue = value;
 
    BSLS_ASSERT(isInsertedFlag);
 
    size_t hashCode = this->d_parameters.hashCodeForKey(
                                               KEY_CONFIG::extractKey(lvalue));
    bslalg::BidirectionalLink *position = this->find(
                                                KEY_CONFIG::extractKey(lvalue),
                                                hashCode);
 
    *isInsertedFlag = (!position);
 
    if(!position) {
        if (d_size >= d_capacity) {
            this->rehashForNumBuckets(numBuckets() * 2);
        }
 
        position = d_parameters.nodeFactory().emplaceIntoNewNode(
                                                       MoveUtil::move(lvalue));
        bslalg::HashTableImpUtil::insertAtFrontOfBucket(&d_anchor,
                                                        position,
                                                        hashCode);
        ++d_size;
    }
 
    return position;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class SOURCE_TYPE>
inline
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::insertIfMissing(
                 bool                                          *isInsertedFlag,
                 BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE) value)
{
    BSLS_ASSERT(isInsertedFlag);
 
    return emplaceIfMissing(isInsertedFlag,
                            BSLS_COMPILERFEATURES_FORWARD(SOURCE_TYPE, value));
 
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class SOURCE_TYPE>
inline
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::insert(
                          BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE) value)
{
    return emplace(BSLS_COMPILERFEATURES_FORWARD(SOURCE_TYPE, value));
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class SOURCE_TYPE>
inline
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::insert(
                          BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE) value,
                          bslalg::BidirectionalLink                     *hint)
{
    return emplaceWithHint(hint,
                           BSLS_COMPILERFEATURES_FORWARD(SOURCE_TYPE, value));
}
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class BDE_OTHER_TYPE>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::insertOrAssign(
                    bool                                       *isInsertedFlag,
                    bslalg::BidirectionalLink                  *hint,
                    BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG)  key,
                    BDE_OTHER_TYPE&&                            obj)
{
    typedef bslalg::HashTableImpUtil ImpUtil;
 
    const KEY_ARG& lvalue = key;
    size_t         hashCode = this->d_parameters.hashCodeForKey(lvalue);
    // Use the hint, if we can
    if (!hint
        || !d_parameters.comparator()(lvalue,
                                      ImpUtil::extractKey<KEY_CONFIG>(hint))) {
        hint = this->find(lvalue, hashCode);
    }
 
    if (hint) { // assign
        static_cast<NodeType *>(hint)->value().second =
            BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj);
        *isInsertedFlag = false;
        return hint;                                                  // RETURN
    }
 
    // insert
    if (d_size >= d_capacity) {
        this->rehashForNumBuckets(numBuckets() * 2);
    }
 
    // Make a new node
    hint = d_parameters.nodeFactory().emplaceIntoNewNode(
        BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
        BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj));
 
    // Add it to the hash table
    HashTable_NodeProctor<typename ImplParameters::NodeFactory>
                            nodeProctor(&d_parameters.nodeFactory(), hint);
    ImpUtil::insertAtFrontOfBucket(&d_anchor, hint, hashCode);
    nodeProctor.release();
    ++d_size;
 
    *isInsertedFlag = true;
    return hint;
}
#endif
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::rehashForNumBuckets(
                                                        SizeType newNumBuckets)
{
    if (newNumBuckets > this->numBuckets()) {
        // Compute a "good" number of buckets, e.g., pick a prime number from a
        // sorted array of exponentially increasing primes.
 
        size_t capacity;
        SizeType numBuckets = static_cast<SizeType>(
                              HashTable_ImpDetails::growBucketsForLoadFactor(
                                            &capacity,
                                            d_size + 1u,
                                            static_cast<size_t>(newNumBuckets),
                                            d_maxLoadFactor));
 
        this->rehashIntoExactlyNumBuckets(numBuckets,
                                          static_cast<SizeType>(capacity));
    }
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::remove(
                                               bslalg::BidirectionalLink *node)
{
    BSLS_ASSERT_SAFE(node);
    BSLS_ASSERT_SAFE(node->previousLink()
                  || d_anchor.listRootAddress() == node);
 
    bslalg::BidirectionalLink *result = node->nextLink();
 
    bslalg::HashTableImpUtil::remove(&d_anchor,
                                     node,
                                     hashCodeForNode(node));
    --d_size;
 
    d_parameters.nodeFactory().deleteNode(static_cast<NodeType *>(node));
 
    return result;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::removeAll()
{
    this->removeAllImp();
    if (HashTable_ImpDetails::defaultBucketAddress() !=
        d_anchor.bucketArrayAddress()) {
        std::memset(d_anchor.bucketArrayAddress(),
                    0,
                    sizeof(bslalg::HashTableBucket) *
                    d_anchor.bucketArraySize());
    }
 
    d_anchor.setListRootAddress(0);
    d_size = 0;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::reserveForNumElements(
                                                          SizeType numElements)
{
    if (numElements < 1) { // Return avoids undefined behavior in node factory.
        return;                                                       // RETURN
    }
 
    if (numElements > d_capacity) {
        // Compute a "good" number of buckets, e.g., pick a prime number from a
        // sorted array of exponentially increasing primes.
 
        size_t capacity;
        SizeType numBuckets = static_cast<SizeType>(
                              HashTable_ImpDetails::growBucketsForLoadFactor(
                                       &capacity,
                                       numElements,
                                       static_cast<size_t>(this->numBuckets()),
                                       d_maxLoadFactor));
 
        this->rehashIntoExactlyNumBuckets(numBuckets,
                                          static_cast<SizeType>(capacity));
    }
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
void HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::setMaxLoadFactor(
                                                        float newMaxLoadFactor)
{
    BSLS_ASSERT_SAFE(0.0f < newMaxLoadFactor);
 
    size_t capacity;
    SizeType numBuckets = static_cast<SizeType>(
             HashTable_ImpDetails::growBucketsForLoadFactor(
                                       &capacity,
                                       std::max<SizeType>(d_size, 1u),
                                       static_cast<size_t>(this->numBuckets()),
                                       newMaxLoadFactor));
 
    this->rehashIntoExactlyNumBuckets(numBuckets,
                                      static_cast<SizeType>(capacity));
 
    // Always set this last, as there is potential to throw exceptions above.
 
    d_maxLoadFactor = newMaxLoadFactor;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::swap(HashTable& other)
{
    // This trait should perform 'if' at compile-time.
 
    if (AllocatorTraits::propagate_on_container_swap::value) {
        quickSwapExchangeAllocators(&other);
    }
    else {
        // C++11 behavior: undefined for unequal allocators
        // BSLS_ASSERT(allocator() == other.allocator());
 
        BSLS_ASSERT(d_parameters.nodeFactory().allocator() ==
                    other.d_parameters.nodeFactory().allocator());
        quickSwapRetainAllocators(&other);
    }
}
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class... ARGS>
inline
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
                    bool                                       *isInsertedFlag,
                    bslalg::BidirectionalLink                  *hint,
                    const KeyType&                              key,
                    ARGS&&...                                   args)
{
    typedef bslalg::HashTableImpUtil ImpUtil;
 
    const size_t   hashCode = this->d_parameters.hashCodeForKey(key);
 
    // Use the hint, if we can
    if (!hint
        || !d_parameters.comparator()(key,
                                      ImpUtil::extractKey<KEY_CONFIG>(hint))) {
         hint = this->find(key, hashCode);
    }
 
    // If the key exists, we're done
    if (hint) {
        *isInsertedFlag = false;
        return hint;                                                  // RETURN
    }
 
    if (d_size >= d_capacity) {
        this->rehashForNumBuckets(numBuckets() * 2);
    }
 
    // Make a new node
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
    hint = d_parameters.nodeFactory().emplaceIntoNewNode(
          std::piecewise_construct,
          std::forward_as_tuple(key),
          std::forward_as_tuple(std::forward<ARGS>(args)...));
#else
    typedef typename ValueType::second_type MappedType;
 
    // TBD: make 'this->allocator()' return the allocator by reference with
    // modifiable access rather than by value.
 
    AllocatorType alloc = this->allocator();
 
    bsls::ObjectBuffer<MappedType> defaultMapped;
    AllocatorTraits::construct(alloc, defaultMapped.address(),
                                                  std::forward<ARGS>(args)...);
    bslma::DestructorGuard<MappedType> mappedGuard(defaultMapped.address());
 
    hint = d_parameters.nodeFactory().emplaceIntoNewNode(
                     key,
                     defaultMapped.object());
#endif
 
    // Add it to the hash table
    HashTable_NodeProctor<typename ImplParameters::NodeFactory>
                            nodeProctor(&d_parameters.nodeFactory(), hint);
    ImpUtil::insertAtFrontOfBucket(&d_anchor, hint, hashCode);
    nodeProctor.release();
    ++d_size;
 
    *isInsertedFlag = true;
    return hint;
}
 
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class... ARGS>
inline
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
                    bool                                       *isInsertedFlag,
                    bslalg::BidirectionalLink                  *hint,
                    bslmf::MovableRef<NonConstKeyType>          key,
                    ARGS&&...                                   args)
{
    typedef bslalg::HashTableImpUtil ImpUtil;
 
    const KeyType& lvalue = key;
    const size_t   hashCode = this->d_parameters.hashCodeForKey(key);
 
    // Use the hint, if we can
    if (!hint
        || !d_parameters.comparator()(lvalue,
                                      ImpUtil::extractKey<KEY_CONFIG>(hint))) {
         hint = this->find(lvalue, hashCode);
    }
 
    // If the key exists, we're done
    if (hint) {
        *isInsertedFlag = false;
        return hint;                                                  // RETURN
    }
 
    if (d_size >= d_capacity) {
        this->rehashForNumBuckets(numBuckets() * 2);
    }
 
    // Make a new node
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
    hint = d_parameters.nodeFactory().emplaceIntoNewNode(
                           std::piecewise_construct,
                           std::forward_as_tuple(MoveUtil::move(key)),
                           std::forward_as_tuple(std::forward<ARGS>(args)...));
#else
    typedef typename ValueType::second_type MappedType;
 
    // TBD: make 'this->allocator()' return the allocator by reference with
    // modifiable access rather than by value.
 
    AllocatorType alloc = this->allocator();
 
    bsls::ObjectBuffer<MappedType> defaultMapped;
    AllocatorTraits::construct(alloc, defaultMapped.address(),
                                                  std::forward<ARGS>(args)...);
    bslma::DestructorGuard<MappedType> mappedGuard(defaultMapped.address());
 
    hint = d_parameters.nodeFactory().emplaceIntoNewNode(
                                                       MoveUtil::move(key),
                                                       defaultMapped.object());
#endif
 
    // Add it to the hash table
    HashTable_NodeProctor<typename ImplParameters::NodeFactory>
                            nodeProctor(&d_parameters.nodeFactory(), hint);
    ImpUtil::insertAtFrontOfBucket(&d_anchor, hint, hashCode);
    nodeProctor.release();
    ++d_size;
 
    *isInsertedFlag = true;
    return hint;
}
#endif
 
// ACCESSORS
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
ALLOCATOR HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::
                                                              allocator() const
{
    return d_parameters.nodeFactory().allocator();
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
const bslalg::HashTableBucket&
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::bucketAtIndex(
                                                          SizeType index) const
{
    BSLS_ASSERT_SAFE(index < this->numBuckets());
 
    return d_anchor.bucketArrayAddress()[index];
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
typename HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::SizeType
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::bucketIndexForKey(
                                                      const KeyType& key) const
{
    typedef typename
       HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::SizeType SizeType;
 
    // The following cast will not discard any useful bits, unless 'SizeType'
    // is larger than 'size_t', as the bucket computation takes a mod on the
    // supplied number of buckets.  We use the following 'BSLMF_ASSERT' to
    // assert that assumption at compile time.
 
    BSLMF_ASSERT(sizeof(SizeType) <= sizeof(size_t));
 
    size_t hashCode = this->d_parameters.hashCodeForKey(key);
    return static_cast<SizeType>(bslalg::HashTableImpUtil::computeBucketIndex(
                                                  hashCode,
                                                  d_anchor.bucketArraySize()));
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
const COMPARATOR&
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::comparator() const
{
    return d_parameters.originalComparator();
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
typename HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::SizeType
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::countElementsInBucket(
                                                          SizeType index) const
{
    BSLS_ASSERT_SAFE(index < this->numBuckets());
 
    return static_cast<SizeType>(bucketAtIndex(index).countElements());
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::elementListRoot() const
{
    return d_anchor.listRootAddress();
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::find(
                                                      const KeyType& key) const
{
    return bslalg::HashTableImpUtil::find<KEY_CONFIG>(
                                             d_anchor,
                                             key,
                                             d_parameters.comparator(),
                                             d_parameters.hashCodeForKey(key));
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::findEndOfRange(
                                        bslalg::BidirectionalLink *first) const
{
    BSLS_ASSERT_SAFE(first);
 
    typedef bslalg::HashTableImpUtil ImpUtil;
 
    // The reference to the Key passed to the functor is only optionally
    // const-qualified.  We must be sure to hold a reference with the correct
    // qualification.
 
    typedef
           typename bslalg::HashTableImpUtil_ExtractKeyResult<KEY_CONFIG>::Type
                                                                        KeyRef;
    KeyRef k = ImpUtil::extractKey<KEY_CONFIG>(first);
 
    while (0 != (first = first->nextLink()) &&
           d_parameters.comparator()(k,ImpUtil::extractKey<KEY_CONFIG>(first)))
    {
        // This loop body is intentionally left blank.
    }
    return first;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
void
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::findRange(
                                         bslalg::BidirectionalLink **first,
                                         bslalg::BidirectionalLink **last,
                                         const KeyType&              key) const
{
    BSLS_ASSERT_SAFE(first);
    BSLS_ASSERT_SAFE(last);
 
    *first = this->find(key);
    *last  = *first ? this->findEndOfRange(*first) : 0;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bool
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::hasSameValue(
                                                  const HashTable& other) const
{
    // TBD: The template bloat of this function can be significantly reduced.
    //..
    // What matters is that the two hash tables:
    // i/   are the same size
    // ii/  have lists that are permutations of each other according to the
    //      element's 'operator=='
    // This means that the implementation should be independent of all four
    // template parameters, but will depend on VALUE_TYPE deduced from the
    // KEY_CONFIG.  Otherwise, after the initial size comparison, the rest
    // depends only on the anchors.
    //..
 
    typedef typename KEY_CONFIG::ValueType ValueType;
    typedef typename ::bsl::allocator_traits<ALLOCATOR>::size_type SizeType;
    typedef bslalg::HashTableImpUtil ImpUtil;
 
    // First test - are the containers the same size?
 
    if (this->size() != other.size()) {
        return false;                                                 // RETURN
    }
    bslalg::BidirectionalLink *cursor = this->elementListRoot();
    if (!cursor) {  // containers are the same size, and empty.
        return true;                                                  // RETURN
    }
 
    while (cursor) {
        bslalg::BidirectionalLink *rhsFirst =
             ImpUtil::find<KEY_CONFIG>(other.d_anchor,
                                       ImpUtil::extractKey<KEY_CONFIG>(cursor),
                                       other.d_parameters.comparator(),
                                       other.d_parameters.hashCodeForKey(
                                     ImpUtil::extractKey<KEY_CONFIG>(cursor)));
        if (!rhsFirst) {
            return false;  // no matching key                         // RETURN
        }
 
        bslalg::BidirectionalLink *endRange = this->findEndOfRange(cursor);
        bslalg::BidirectionalLink *rhsLast  = other.findEndOfRange(rhsFirst);
 
        // Check the key-groups have the same length - a quick-fail test.
 
        bslalg::BidirectionalLink *endWalker = cursor->nextLink();
        bslalg::BidirectionalLink *rhsWalker = rhsFirst->nextLink();
 
        while (endWalker != endRange) {
 
            if (rhsWalker == rhsLast) {
                return false;   // different length subsequences      // RETURN
            }
            endWalker = endWalker->nextLink();
            rhsWalker = rhsWalker->nextLink();
        }
 
        if (rhsWalker != rhsLast) {
            return false;   // different length subsequences          // RETURN
        }
 
        // Efficiently compare identical prefixes: O[N] if sequences have the
        // same elements in the same order.  Note that comparison of values in
        // nodes is tested using 'operator==' and not the key-equality
        // comparator stored in the hash table.
 
        while (cursor != endRange &&
                 (ImpUtil::extractValue<KEY_CONFIG>(cursor) ==
                  ImpUtil::extractValue<KEY_CONFIG>(rhsFirst)))
        {
            cursor   = cursor->nextLink();
            rhsFirst = rhsFirst->nextLink();
        }
 
        if (cursor == endRange) {
            continue;                                               // CONTINUE
        }
 
        // Now comes the harder part of validating that one subsequence is a
        // permutation of another, by counting elements that compare equal
        // using the equality operator, 'operator=='.  Note that this code
        // could be simplified for hash-tables with unique keys, as we can omit
        // the counting-scan, and merely test for any match within the 'other'
        // range.  Trade off the ease of a single well-tested code path, vs.
        // the importance of an efficient 'operator==' for hash containers.
        // This is currently the only place the hash-table would care about
        // uniqueness, and risk different hash-table types for unique- vs.
        // multi-containers.  Note again that comparison of values in nodes is
        // tested using 'operator==' and not the key-equality comparator stored
        // in the hash tables.
 
        for (bslalg::BidirectionalLink *marker = cursor;
             marker != endRange;
             marker = marker->nextLink())
        {
            const ValueType& valueAtMarker =
                                    ImpUtil::extractValue<KEY_CONFIG>(marker);
 
            if (cursor != marker) {  // skip on first pass only
                // Check if the value at 'marker' has already be seen.
 
                bslalg::BidirectionalLink *scanner = cursor;
                while (scanner != marker &&
                 ImpUtil::extractValue<KEY_CONFIG>(scanner) != valueAtMarker) {
                    scanner = scanner->nextLink();
                }
                if (scanner != marker) {  // We have seen 'lhs' one before.
                    continue;                                       // CONTINUE
                }
            }
 
            SizeType matches = 0;
            for (bslalg::BidirectionalLink *scanner = rhsFirst;
                 scanner != rhsLast;
                 scanner = scanner->nextLink()) {
                if (ImpUtil::extractValue<KEY_CONFIG>(scanner) ==
                                                               valueAtMarker) {
                    ++matches;
                }
            }
            if (!matches) {
                return false;                                         // RETURN
            }
 
            // Remember, *scanner is by definition a good match
 
            for (bslalg::BidirectionalLink *scanner = marker->nextLink();
                 scanner != endRange;
                 scanner = scanner->nextLink()) {
 
                if (ImpUtil::extractValue<KEY_CONFIG>(scanner) ==
                                                               valueAtMarker) {
                    if (!--matches) {  // equal matches, but excluding initial
                        return false;                                 // RETURN
                    }
                }
            }
            if (1 != matches) {
                return false;                                         // RETURN
            }
        }
        cursor = endRange;
    }
    return true;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
const HASHER&
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::hasher() const
{
    return d_parameters.originalHasher();
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
float HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::loadFactor() const
{
    return static_cast<float>(static_cast<double>(this->size())
                                    / static_cast<double>(this->numBuckets()));
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
float
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::maxLoadFactor() const
{
    return d_maxLoadFactor;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
typename HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::SizeType
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::maxNumBuckets() const
{
    // This estimate is still on the high side, we should actually pick the
    // preceding entry from our table of prime numbers used for valid bucket
    // array sizes.  There is no easy way to find that value at the moment
    // though.
 
    typedef typename AllocatorTraits::
                                template rebind_traits<bslalg::HashTableBucket>
                                                         BucketAllocatorTraits;
    typedef typename BucketAllocatorTraits::allocator_type BucketAllocator;
 
    return BucketAllocatorTraits::max_size(BucketAllocator(this->allocator()));
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
typename HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::SizeType
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::maxSize() const
{
    return AllocatorTraits::max_size(this->allocator()) / sizeof(NodeType);
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
typename HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::SizeType
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::numBuckets() const
{
    return static_cast<SizeType>(d_anchor.bucketArraySize());
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
typename HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::SizeType
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::rehashThreshold() const
{
    return d_capacity;
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
typename HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::SizeType
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::size() const
{
    return d_size;
}
 
}  // close package namespace
 
//-----------------------------------------------------------------------------
//                      free functions and operators
//-----------------------------------------------------------------------------
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
void
bslstl::swap(bslstl::HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& a,
             bslstl::HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& b)
{
    typedef bslstl::HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>
                                                                     TableType;
 
    if (::bsl::allocator_traits<ALLOCATOR>::propagate_on_container_swap::value
        || a.allocator() == b.allocator()) {
        a.swap(b);
    }
    else {
        // C++11 behavior: undefined for unequal allocators
        // BSLS_ASSERT(allocator() == other.allocator());
 
        TableType aCopy(a, b.allocator());
        TableType bCopy(b, a.allocator());
 
        b.swap(aCopy);
        a.swap(bCopy);
    }
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
bool bslstl::operator==(
       const bslstl::HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& lhs,
       const bslstl::HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& rhs)
{
    return lhs.hasSameValue(rhs);
}
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
inline
bool bslstl::operator!=(
         const bslstl::HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& a,
         const bslstl::HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>& b)
{
    return !(a == b);
}
 
template <class FUNCTOR>
inline
void bslstl::swap(bslstl::HashTable_HashWrapper<FUNCTOR> &a,
                  bslstl::HashTable_HashWrapper<FUNCTOR> &b)
{
    a.swap(b);
}
 
template <class FUNCTOR>
inline
void bslstl::swap(bslstl::HashTable_ComparatorWrapper<FUNCTOR> &a,
                  bslstl::HashTable_ComparatorWrapper<FUNCTOR> &b)
{
    a.swap(b);
}
 
// ============================================================================
//                              TYPE TRAITS
// ============================================================================
 
// Type traits for HashTable:
//: o A HashTable is bitwise movable if the both functors and the allocator are
//:     bitwise movable.
//: o A HashTable uses 'bslma' allocators if the parameterized 'ALLOCATOR' is
//:     convertible from 'bslma::Allocator*'.
 
namespace bslma {
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
struct UsesBslmaAllocator<bslstl::HashTable<KEY_CONFIG,
                                            HASHER,
                                            COMPARATOR,
                                            ALLOCATOR> >
    : bsl::is_convertible<Allocator*, ALLOCATOR>::type {
};
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
struct UsesBslmaAllocator<bslstl::HashTable_ImplParameters<KEY_CONFIG,
                                                             HASHER,
                                                             COMPARATOR,
                                                             ALLOCATOR> >
    : bsl::is_convertible<Allocator*, ALLOCATOR>::type {
};
 
}  // close namespace bslma
 
namespace bslmf {
 
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
struct IsBitwiseMoveable<bslstl::HashTable<KEY_CONFIG,
                                           HASHER,
                                           COMPARATOR,
                                           ALLOCATOR> >
: bsl::integral_constant< bool, bslmf::IsBitwiseMoveable<HASHER>::value
                             && bslmf::IsBitwiseMoveable<COMPARATOR>::value
                             && bslmf::IsBitwiseMoveable<ALLOCATOR>::value>
{};
 
}  // close namespace bslmf
 
 
#endif // End C++11 code
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2013 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */