bslstl_hashtableiterator.h

Go to the documentation of this file.

/// @file bslstl_hashtableiterator.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslstl_hashtableiterator.h                                         -*-C++-*-
#ifndef INCLUDED_BSLSTL_HASHTABLEITERATOR
#define INCLUDED_BSLSTL_HASHTABLEITERATOR
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslstl_hashtableiterator bslstl_hashtableiterator
/// @brief  Provide an STL compliant iterator for hash tables.
/// @addtogroup bsl
/// @{
/// @addtogroup bslstl
/// @{
/// @addtogroup bslstl_hashtableiterator
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslstl_hashtableiterator-purpose"> Purpose</a>
/// * <a href="#bslstl_hashtableiterator-classes"> Classes </a>
/// * <a href="#bslstl_hashtableiterator-description"> Description </a>
///   * <a href="#bslstl_hashtableiterator-usage"> Usage </a>
///     * <a href="#bslstl_hashtableiterator-example-1-iterating-a-hash-table-using-hashtableiterator"> Example 1: Iterating a Hash Table Using HashTableIterator </a>
///
/// # Purpose {#bslstl_hashtableiterator-purpose}
/// Provide an STL compliant iterator for hash tables.
///
/// # Classes {#bslstl_hashtableiterator-classes}
///
/// -  bslstl::HashTableIterator: an STL compliant forward iterator
///
/// **Canonical header:**  bsl_unordered_map.h, bsl_unordered_set.h
///
/// @see  bslalg_bidirectionallink, bslstl_unorderedmap, bslstl_unorderedset
///
/// # Description {#bslstl_hashtableiterator-description}
/// This component provides a standard-conforming forward iterator,
/// `bslstl::HashTableIterator`, over a list of elements (of type
/// `bslalg::BidirectionalLink`) in a hashtable.  The requirements of a forward
/// iterator are outlined in the C++11 standard in section [24.2.5] under the
/// tag [forward.iterators].  The `bslstl::HashTableIterator` class template has
/// two template parameters: `VALUE_TYPE`, and `DIFFERENCE_TYPE`.  `VALUE_TYPE`
/// indicates the type of the value to which this iterator provides references,
/// and may be const-qualified for constant iterators.  `DIFFERENCE_TYPE`
/// determines the (standard mandated) @ref difference_type  for the iterator, and
/// will typically be supplied by the allocator used by the hash-table being
/// iterated over.
///
/// ## Usage {#bslstl_hashtableiterator-usage}
///
///
/// This section illustrates intended use of this component.
///
/// ### Example 1: Iterating a Hash Table Using HashTableIterator {#bslstl_hashtableiterator-example-1-iterating-a-hash-table-using-hashtableiterator}
///
///
/// In the following example we create a simple hashtable and then use a
/// `HashTableIterator` to iterate through its elements.
///
/// First, we define a typedef, `Node`, prepresenting a bidirectional node
/// holding an integer value:
/// @code
/// typedef bslalg::BidirectionalNode<int> Node;
/// @endcode
/// Then, we construct a test allocator, and we use it to allocate an array of
/// `Node` objects, each holding a unique integer value:
/// @code
/// bslma::TestAllocator scratch;
///
/// const int NUM_NODES = 5;
/// const int NUM_BUCKETS = 3;
///
/// Node *nodes[NUM_NODES];
/// for (int i = 0; i < NUM_NODES; ++i) {
///     nodes[i] = static_cast<Node *>(scratch.allocate(sizeof(Node)));
///     nodes[i]->value() = i;
/// }
/// @endcode
/// Next, we create an array of `HashTableBuckets` objects, and we use the array
/// to construct an empty hash table characterized by a `HashTableAnchor`
/// object:
/// @code
/// bslalg::HashTableBucket buckets[NUM_BUCKETS];
/// for (int i = 0; i < NUM_BUCKETS; ++i) {
///     buckets[i].reset();
/// }
/// bslalg::HashTableAnchor hashTable(buckets, NUM_BUCKETS, 0);
/// @endcode
/// Then, we insert each node in the array of nodes into the hash table using
/// `bslalg::HashTableImpUtil`, supplying the integer value held by each node as
/// its hash value:
/// @code
/// for (int i = 0; i < NUM_NODES; ++i) {
///     bslalg::HashTableImpUtil::insertAtFrontOfBucket(&hashTable,
///                                                     nodes[i],
///                                                     nodes[i]->value());
/// }
/// @endcode
/// Next, we define a `typedef` that is an alias an instance of
/// `HashTableIterator` that can traverse hash tables holding integer values.
/// @code
/// typedef bslstl::HashTableIterator<int, ptrdiff_t> Iter;
/// @endcode
/// Now, we create two iterators: one pointing to the start of the bidirectional
/// linked list held by the hash table, and the other representing the end
/// sentinel.  We use them to navigate and print the elements of the hash table:
/// @code
/// Iter iter(hashTable.listRootAddress());
/// Iter end;
/// for (;iter != end; ++iter) {
///     printf("%d\n", *iter);
/// }
/// @endcode
/// Then, we observe the following output:
/// @code
/// 2
/// 4
/// 1
/// 3
/// 0
/// @endcode
/// Finally, we deallocate the memory used by the hash table:
/// @code
/// for (int i = 0; i < NUM_NODES; ++i) {
///     scratch.deallocate(nodes[i]);
/// }
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslstl
 * @{
 */
/** @addtogroup bslstl_hashtableiterator
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bslstl_iterator.h>
 
#include <bslalg_bidirectionallink.h>
#include <bslalg_bidirectionalnode.h>
 
#include <bslmf_removecv.h>
 
#include <bsls_assert.h>
#include <bsls_compilerfeatures.h>
#include <bsls_libraryfeatures.h>
#include <bsls_util.h>
 
#ifndef BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
#include <bslmf_removecvq.h>
#include <bsls_nativestd.h>
#endif // BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
 
 
namespace bslstl {
 
                          // =======================
                          // class HashTableIterator
                          // =======================
 
/// This class template implements an in-core value-semantic type that is an
/// standard-conforming forward iterator (see section 24.2.5
/// [forward.iterators] of the C++11 standard) over a list of
/// `bslalg::BidirectionalLink` objects.  A `HashTableIterator` object
/// provides access to values of the (template parameter) `VALUE_TYPE`,
/// stored in a hash table composed of `bslalg::BidirectionalLink` nodes.
/// The (template parameter) `DIFFERENCE_TYPE` determines the standard
/// mandated @ref difference_type  of the iterator, without requiring access to
/// the allocator-traits for the node.
#if defined(BSLS_LIBRARYFEATURES_STDCPP_LIBCSTD)
/// On Solaris just to keep studio12-v4 happy, since algorithms take only
/// iterators inheriting from `std::iterator`.
///
/// See @ref bslstl_hashtableiterator 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
class HashTableIterator
: public std::iterator<std::forward_iterator_tag, VALUE_TYPE> {
#else
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
class HashTableIterator {
#endif
 
    // PRIVATE TYPES
    typedef typename bsl::remove_cv<VALUE_TYPE>::type   NcType;
    typedef HashTableIterator<NcType, DIFFERENCE_TYPE>  NcIter;
 
  public:
    // PUBLIC TYPES
    typedef NcType                      value_type;
    typedef DIFFERENCE_TYPE             difference_type;
    typedef VALUE_TYPE                 *pointer;
    typedef VALUE_TYPE&                 reference;
 
    /// Standard iterator defined types [24.4.2].
    typedef bsl::forward_iterator_tag   iterator_category;
 
  private:
    // DATA
    bslalg::BidirectionalLink *d_node_p;  // pointer to the node referred to by
                                          // this iterator
 
  private:
    // PRIVATE MANIPULATORS
 
    /// Move this iterator to refer to the next node in the list.
    void advance();
 
  public:
    // CREATORS
 
    /// Create a default-constructed iterator referring to an empty list of
    /// nodes.  All default-constructed iterators are non-dereferenceable
    /// and refer to the same empty list.
    HashTableIterator();
 
    /// Create an iterator referring to the specified `node`.  The behavior
    /// is undefined unless `node` is of the type
    /// `bslalg::BidirectionalNode<VALUE_TYPE>`, which is derived from
    /// `bslalg::BidirectionalLink`.  Note that this constructor is an
    /// implementation detail and is not part of the C++ standard.
    explicit HashTableIterator(bslalg::BidirectionalLink *node);
 
    /// Create an iterator at the same position as the specified `original`
    /// iterator.  Note that this constructor enables converting from
    /// modifiable to `const` iterator types.
    HashTableIterator(const NcIter& original);                      // IMPLICIT
 
    /// Create an iterator having the same value as the specified
    /// `original`.  Note that this operation is either defined by the
    /// constructor taking `NcIter` (if `NcType` is the same as
    /// `VALUE_TYPE`), or generated automatically by the compiler.  Also
    /// note that this constructor cannot be defined explicitly (without
    /// using `bsls::enableif`) to avoid a duplicate declaration when
    /// `NcType` is the same as `VALUE_TYPE`.
     HashTableIterator(const HashTableIterator& original) = default;
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_DEFAULTED_FUNCTIONS)
    /// Destroy this object.
    ~HashTableIterator() = default;
 
    // MANIPULATORS
 
    /// Assign to this object the value of the specified `rhs` object, and
    /// a return a reference providing modifiable access to this object.
    HashTableIterator& operator=(const HashTableIterator& rhs) = default;
#endif
 
    /// Move this iterator to the next node in the list and return a
    /// reference providing modifiable access to this iterator.  The
    /// behavior is undefined unless the iterator refers to a valid (not yet
    /// erased) node in the list.
    HashTableIterator& operator++();
 
    // ACCESSORS
 
    /// Return a reference providing modifiable access to the value (of the
    /// template parameter `VALUE_TYPE`) of the node at which this iterator
    /// is positioned.  The behavior is undefined unless the iterator refers
    /// to a valid (not yet erased) node the list.
    reference operator*() const;
 
    /// Return the address of the value (of the template parameter
    /// `VALUE_TYPE`) of the element at which this iterator is positioned.
    /// The behavior is undefined unless the iterator refers to a valid (not
    /// yet erased) node the list.
    pointer operator->() const;
 
    /// Return the address of the node at which this iterator is positioned
    /// in the list, or 0 if this iterator is positioned after the end of a
    /// list.  Note that this method is an implementation detail and is not
    /// part of the C++ standard.
    bslalg::BidirectionalLink *node() const;
};
 
// FREE OPERATORS
 
/// Return `true` if the specified `lhs` and the specified `rhs` iterators
/// have the same value and `false` otherwise.  Two iterators have the same
/// value if they refer to the same node in the same list, or if both
/// iterators are at the past-the-end position of the tree.
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
bool operator==(const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
                const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>& rhs);
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
bool operator==(
              const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>&       lhs,
              const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& rhs);
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
bool operator==(
              const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
              const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>&       rhs);
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
bool operator==(
              const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
              const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& rhs);
 
/// Return `true` if the specified `lhs` and the specified `rhs` iterators
/// do not have the same value and `false` otherwise.  Two iterators do not
/// have the same value if they refer to the different nodes in the same
/// list, or if either (but not both) of the iterators are at the
/// past-the-end position of the tree.
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
bool operator!=(const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
                const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>& rhs);
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
bool operator!=(
              const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>&       lhs,
              const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& rhs);
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
bool operator!=(
        const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
        const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>&       rhs);
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
bool operator!=(
              const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
              const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& rhs);
 
 
/// Move the specified `iter` to the next node in the list and return
/// value of `iter` prior to this call.  The behavior is undefined
/// unless `iter` refers to a valid (not yet erased) node a the list.
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>
operator++(HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>& iter, int);
 
 
// ============================================================================
//                  TEMPLATE AND INLINE FUNCTION DEFINITIONS
// ============================================================================
 
                     // -----------------------
                     // class HashTableIterator
                     // -----------------------
 
// CREATORS
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>::
HashTableIterator()
: d_node_p()
{
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>::
HashTableIterator(bslalg::BidirectionalLink *node)
: d_node_p(node)
{
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>::
HashTableIterator(const NcIter& original)
: d_node_p(original.node())
{
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
void HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>::advance()
{
    BSLS_ASSERT_SAFE(d_node_p);
 
    this->d_node_p = this->d_node_p->nextLink();
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>&
HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>::operator++()
{
    BSLS_ASSERT_SAFE(this->d_node_p);
 
    this->advance();
    return *this;
}
 
// ACCESSORS
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
typename HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>::reference
HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>::operator*() const
{
    BSLS_ASSERT_SAFE(this->d_node_p);
 
    return static_cast<bslalg::BidirectionalNode<VALUE_TYPE> *>(
                                                            d_node_p)->value();
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
typename HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>::pointer
HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>::operator->() const
{
    BSLS_ASSERT_SAFE(this->d_node_p);
 
    return bsls::Util::addressOf(
            static_cast<bslalg::BidirectionalNode<VALUE_TYPE> *>(
                                                           d_node_p)->value());
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
bslalg::BidirectionalLink *
HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>::node() const
{
    return d_node_p;
}
 
// FREE OPERATORS
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
bool operator==(const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
                const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>& rhs)
{
    return lhs.node() == rhs.node();
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
bool operator==(
               const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>&       lhs,
               const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& rhs)
{
    return lhs.node() == rhs.node();
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
bool operator==(
               const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
               const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>&       rhs)
{
    return lhs.node() == rhs.node();
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
bool operator==(
               const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
               const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& rhs)
{
    return lhs.node() == rhs.node();
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
bool operator!=(const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
                const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>& rhs)
{
    return lhs.node() != rhs.node();
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
bool operator!=(
               const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>&       lhs,
               const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& rhs)
{
    return lhs.node() != rhs.node();
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
bool operator!=(
               const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
               const HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>&       rhs)
{
    return lhs.node() != rhs.node();
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
bool operator!=(
               const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& lhs,
               const HashTableIterator<const VALUE_TYPE, DIFFERENCE_TYPE>& rhs)
{
    return lhs.node() != rhs.node();
}
 
template <class VALUE_TYPE, class DIFFERENCE_TYPE>
inline
HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>
operator++(HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE>& iter, int)
{
    BSLS_ASSERT_SAFE(iter.node());
 
    HashTableIterator<VALUE_TYPE, DIFFERENCE_TYPE> temp(iter);
    ++iter;
    return temp;
}
 
}  // close package namespace
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2019 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 ----------------------------------
 
/** @} */
/** @} */
/** @} */