// bslstl_hashtable_cpp03.h -*-C++-*-
// Automatically generated file. **DO NOT EDIT**
#ifndef INCLUDED_BSLSTL_HASHTABLE_CPP03
#define INCLUDED_BSLSTL_HASHTABLE_CPP03
//@PURPOSE: Provide C++03 implementation for bslstl_hashtable.h
//
//@CLASSES: See bslstl_hashtable.h for list of classes
//
//@SEE_ALSO: bslstl_hashtable
//
//@DESCRIPTION: This component is the C++03 translation of a C++11 component,
// generated by the 'sim_cpp11_features.pl' program. If the original header
// contains any specially delimited regions of C++11 code, then this generated
// file contains the C++03 equivalent, i.e., with variadic templates expanded
// and rvalue-references replaced by 'bslmf::MovableRef' objects. The header
// code in this file is designed to be '#include'd into the original header
// when compiling with a C++03 compiler. If there are no specially delimited
// regions of C++11 code, then this header contains no code and is not
// '#include'd in the original header.
//
// Generated on Mon Sep 19 08:58:18 2022
// Command line: sim_cpp11_features.pl bslstl_hashtable.h
#ifdef COMPILING_BSLSTL_HASHTABLE_H
namespace BloombergLP {
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
// ======================
template <class CALLABLE>
struct 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.
// TYPES
typedef typename bsl::conditional<
bsl::is_function<CALLABLE>::value,
typename bsl::add_lvalue_reference<CALLABLE>::type,
CALLABLE>::type type;
};
// ===========================
// class HashTable_HashWrapper
// ===========================
template <class FUNCTOR>
class HashTable_HashWrapper {
// This class provides a wrapper around a functor satisfying the 'Hash'
// requirements ({'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()'.
private:
mutable FUNCTOR d_functor;
public:
// CREATORS
HashTable_HashWrapper();
// Create a 'HashTable_HashWrapper' object wrapping a 'FUNCTOR' that
// has its default value.
explicit HashTable_HashWrapper(const FUNCTOR& fn);
// Create a 'HashTable_HashWrapper' object wrapping a 'FUNCTOR' that is
// a copy of the specified 'fn'.
// MANIPULATORS
void swap(HashTable_HashWrapper &other);
// Exchange the value of this object with the specified 'other' object.
// ACCESSORS
template <class ARG_TYPE>
std::size_t operator()(ARG_TYPE& arg) const;
// Call the wrapped 'functor' with the specified 'arg' and return the
// result. Note that 'ARG_TYPE' will typically be deduced as a 'const'
// type.
const FUNCTOR& functor() const;
// Return a reference providing non-modifiable access to the hash
// functor wrapped by this object.
};
template <class FUNCTOR>
class HashTable_HashWrapper<const FUNCTOR> {
// 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.
private:
const FUNCTOR d_functor;
public:
// CREATORS
HashTable_HashWrapper();
// Create a 'HashTable_HashWrapper' object wrapping a 'FUNCTOR' that
// has its default value.
explicit HashTable_HashWrapper(const FUNCTOR& fn);
// Create a 'HashTable_HashWrapper' object wrapping a 'FUNCTOR' that is
// a copy of the specified 'fn'.
// ACCESSORS
template <class ARG_TYPE>
std::size_t operator()(ARG_TYPE& arg) const;
// Call the wrapped 'functor' with the specified 'arg' and return the
// result. Note that 'ARG_TYPE' will typically be deduced as a 'const'
// type.
const FUNCTOR& functor() const;
// Return a reference providing non-modifiable access to the hash
// functor wrapped by this object.
};
template <class FUNCTOR>
class HashTable_HashWrapper<FUNCTOR &> {
// 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.
private:
FUNCTOR& d_functor;
public:
// CREATORS
explicit HashTable_HashWrapper(FUNCTOR& fn);
// Create a 'HashTable_HashWrapper' object wrapping a 'FUNCTOR' that is
// a copy of the specified 'fn'.
// ACCESSORS
template <class ARG_TYPE>
std::size_t operator()(ARG_TYPE& arg) const;
// Call the wrapped 'functor' with the specified 'arg' and return the
// result. Note that 'ARG_TYPE' will typically be deduced as a 'const'
// type.
FUNCTOR& functor() const;
// Return a reference providing non-modifiable access to the hash
// functor wrapped by this object.
};
template <class FUNCTOR>
void swap(HashTable_HashWrapper<FUNCTOR> &a,
HashTable_HashWrapper<FUNCTOR> &b);
// Swap the functor wrapped by the specified 'a' object with the functor
// wrapped by the specified 'b' object.
// =================================
// class HashTable_ComparatorWrapper
// =================================
template <class FUNCTOR>
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.
private:
mutable FUNCTOR d_functor;
public:
// CREATORS
HashTable_ComparatorWrapper();
// Create a 'HashTable_ComparatorWrapper' object wrapping a 'FUNCTOR'
// that has its default value.
explicit HashTable_ComparatorWrapper(const FUNCTOR& fn);
// Create a 'HashTable_ComparatorWrapper' object wrapping a 'FUNCTOR'
// that is a copy of the specified 'fn'.
// MANIPULATORS
void swap(HashTable_ComparatorWrapper &other);
// Exchange the value of this object with the specified 'other' object.
// ACCESSORS
template <class ARG1_TYPE, class ARG2_TYPE>
bool operator()(ARG1_TYPE& arg1, ARG2_TYPE& arg2) const;
// 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.
const FUNCTOR& functor() const;
// Return a reference providing non-modifiable access to the hash
// functor wrapped by this object.
};
template <class FUNCTOR>
class HashTable_ComparatorWrapper<const FUNCTOR> {
// 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.
private:
const FUNCTOR d_functor;
public:
// CREATORS
HashTable_ComparatorWrapper();
// Create a 'HashTable_ComparatorWrapper' object wrapping a 'FUNCTOR'
// that has its default value.
explicit HashTable_ComparatorWrapper(const FUNCTOR& fn);
// Create a 'HashTable_ComparatorWrapper' object wrapping a 'FUNCTOR'
// that is a copy of the specified 'fn'.
// ACCESSORS
template <class ARG1_TYPE, class ARG2_TYPE>
bool operator()(ARG1_TYPE& arg1, ARG2_TYPE& arg2) const;
// 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.
const FUNCTOR& functor() const;
// Return a reference providing non-modifiable access to the hash
// functor wrapped by this object.
};
template <class FUNCTOR>
class HashTable_ComparatorWrapper<FUNCTOR &> {
// 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.
private:
FUNCTOR& d_functor;
public:
// CREATORS
explicit HashTable_ComparatorWrapper(FUNCTOR& fn);
// Create a 'HashTable_ComparatorWrapper' object wrapping a 'FUNCTOR'
// that is a copy of the specified 'fn'.
// ACCESSORS
template <class ARG1_TYPE, class ARG2_TYPE>
bool operator()(ARG1_TYPE& arg1, ARG2_TYPE& arg2) const;
// 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.
FUNCTOR& functor() const;
// Return a reference providing non-modifiable access to the hash
// functor wrapped by this object.
};
template <class FUNCTOR>
void swap(HashTable_ComparatorWrapper<FUNCTOR> &lhs,
HashTable_ComparatorWrapper<FUNCTOR> &rhs);
// Swap the functor wrapped by the specified 'lhs' object with the functor
// wrapped by the specified 'rhs' object.
// ===============
// class HashTable
// ===============
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
class HashTable_ImplParameters;
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
class HashTable {
// 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:
//..
// HASHER hash;
// KEY_CONFIG::KeyType key;
// std::size_t result = hash(key);
//..
// where the definition of the called function meets the requirements of a
// hash function, as specified in {'bslstl_hash'}. 'COMPARATOR' shall
// support the a function call operator compatible with the following
// statements:
//..
// COMPARATOR compare;
// KEY_CONFIG::KeyType key1, key2;
// bool result = compare(key1, key2);
//..
// 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:
//: o supports a complete set of *value-semantic* operations
//: o except for 'bdex' serialization
//: o is *exception-neutral* (agnostic except for the 'at' method)
//: o is *alias-safe*
//: o is 'const' *thread-safe*
// For terminology see {'bsldoc_glossary'}.
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;
private:
// PRIVATE TYPES
typedef
HashTable_ImplParameters<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>
ImplParameters;
typedef bslmf::MovableRefUtil MoveUtil;
// This typedef is a convenient alias for the utility associated with
// movable references.
// 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
void copyDataStructure(bslalg::BidirectionalLink *cursor);
// 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 moveDataStructure(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 quickSwapExchangeAllocators(HashTable *other);
// 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 quickSwapRetainAllocators(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 rehashIntoExactlyNumBuckets(SizeType newNumBuckets,
SizeType capacity);
// 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
// {'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 removeAllAndDeallocate();
// 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 removeAllImp();
// 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.
// PRIVATE ACCESSORS
template <class DEDUCED_KEY>
bslalg::BidirectionalLink *find(DEDUCED_KEY& key,
std::size_t hashValue) const;
// 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.
bslalg::HashTableBucket *getBucketAddress(SizeType bucketIndex) 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()'.
std::size_t hashCodeForNode(bslalg::BidirectionalLink *node) 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>'.
public:
// CREATORS
explicit HashTable(const ALLOCATOR& basicAllocator = ALLOCATOR());
// 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).
HashTable(const HASHER& hash,
const COMPARATOR& compare,
SizeType initialNumBuckets,
float initialMaxLoadFactor,
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 HashTable& original);
// 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(BloombergLP::bslmf::MovableRef<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(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. 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(BloombergLP::bslmf::MovableRef<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();
// Destroy this object.
// MANIPULATORS
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_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=(BloombergLP::bslmf::MovableRef<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'}).
#if BSLS_COMPILERFEATURES_SIMULATE_VARIADIC_TEMPLATES
// {{{ BEGIN GENERATED CODE
// Command line: sim_cpp11_features.pl bslstl_hashtable.h
#ifndef BSLSTL_HASHTABLE_VARIADIC_LIMIT
#define BSLSTL_HASHTABLE_VARIADIC_LIMIT 10
#endif
#ifndef BSLSTL_HASHTABLE_VARIADIC_LIMIT_A
#define BSLSTL_HASHTABLE_VARIADIC_LIMIT_A BSLSTL_HASHTABLE_VARIADIC_LIMIT
#endif
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 0
bslalg::BidirectionalLink *emplace(
);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 0
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 1
template <class Args_01>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 1
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 2
template <class Args_01,
class Args_02>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 2
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 3
template <class Args_01,
class Args_02,
class Args_03>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 3
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 4
template <class Args_01,
class Args_02,
class Args_03,
class Args_04>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 4
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 5
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 5
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 6
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 6
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 7
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 7
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 8
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 8
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 9
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 9
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 10
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09,
class Args_10>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_10) arguments_10);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 10
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 0
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 0
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 1
template <class Args_01>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 1
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 2
template <class Args_01,
class Args_02>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 2
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 3
template <class Args_01,
class Args_02,
class Args_03>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 3
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 4
template <class Args_01,
class Args_02,
class Args_03,
class Args_04>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 4
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 5
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 5
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 6
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 6
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 7
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 7
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 8
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 8
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 9
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 9
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 10
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09,
class Args_10>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_10) arguments_10);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 10
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 0
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 0
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 1
template <class Args_01>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 1
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 2
template <class Args_01,
class Args_02>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 2
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 3
template <class Args_01,
class Args_02,
class Args_03>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 3
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 4
template <class Args_01,
class Args_02,
class Args_03,
class Args_04>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 4
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 5
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 5
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 6
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 6
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 7
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 7
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 8
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 8
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 9
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 9
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 10
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09,
class Args_10>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_10) arguments_10);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_A >= 10
#else
// The generated code below is a workaround for the absence of perfect
// forwarding in some compilers.
template <class... Args>
bslalg::BidirectionalLink *emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args)... arguments);
template <class... Args>
bslalg::BidirectionalLink *emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args)... arguments);
template <class... Args>
bslalg::BidirectionalLink *emplaceIfMissing(bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args)... arguments);
// }}} END GENERATED CODE
#endif
bslalg::BidirectionalLink *insertIfMissing(const KeyType& key);
// 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(
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'. 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,
bslmf::MovableRef<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'});
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' 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 *insert(
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,
bslalg::BidirectionalLink *hint);
// 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.
// {{{ BEGIN GENERATED CODE
// The generated code below is a workaround for the absence of perfect
// forwarding in some compilers.
template <class KEY_ARG, class BDE_OTHER_TYPE>
bslalg::BidirectionalLink *insertOrAssign(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(BDE_OTHER_TYPE) obj);
// }}} END GENERATED CODE
void rehashForNumBuckets(SizeType newNumBuckets);
// 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
// {'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).
bslalg::BidirectionalLink *remove(bslalg::BidirectionalLink *node);
// 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.
void removeAll();
// 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 reserveForNumElements(SizeType numElements);
// 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
// {'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 setMaxLoadFactor(float newMaxLoadFactor);
// 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 swap(HashTable& other);
// 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'.
#if BSLS_COMPILERFEATURES_SIMULATE_VARIADIC_TEMPLATES
// {{{ BEGIN GENERATED CODE
// Command line: sim_cpp11_features.pl bslstl_hashtable.h
#ifndef BSLSTL_HASHTABLE_VARIADIC_LIMIT
#define BSLSTL_HASHTABLE_VARIADIC_LIMIT 10
#endif
#ifndef BSLSTL_HASHTABLE_VARIADIC_LIMIT_C
#define BSLSTL_HASHTABLE_VARIADIC_LIMIT_C BSLSTL_HASHTABLE_VARIADIC_LIMIT
#endif
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 0
template <class KEY_ARG>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 0
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 1
template <class KEY_ARG, class Args_01>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 1
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 2
template <class KEY_ARG, class Args_01,
class Args_02>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 2
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 3
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 3
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 4
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 4
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 5
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 5
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 6
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) args_06);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 6
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 7
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) args_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) args_07);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 7
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 8
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) args_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) args_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) args_08);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 8
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 9
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) args_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) args_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) args_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) args_09);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 9
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 10
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09,
class Args_10>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) args_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) args_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) args_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) args_09,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_10) args_10);
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_C >= 10
#else
// The generated code below is a workaround for the absence of perfect
// forwarding in some compilers.
template <class KEY_ARG, class... Args>
bslalg::BidirectionalLink *tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args)... args);
// }}} END GENERATED CODE
#endif
// ACCESSORS
ALLOCATOR allocator() const;
// 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.
const bslalg::HashTableBucket& bucketAtIndex(SizeType index) 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()'.
SizeType bucketIndexForKey(const KeyType& key) const;
// Return the index of the bucket that would contain all the elements
// having the specified 'key'.
const COMPARATOR& comparator() const;
// Return a reference providing non-modifiable access to the
// key-equality comparison functor used by this hash table.
SizeType countElementsInBucket(SizeType index) 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.
bslalg::BidirectionalLink *elementListRoot() const;
// Return the address of the first element in this hash table, or a
// null pointer value if this hash table is empty.
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 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.
{
return bslalg::HashTableImpUtil::findTransparent<KEY_CONFIG>(
d_anchor,
key,
d_parameters.comparator(),
d_parameters.hashCodeForKey(key));
}
bslalg::BidirectionalLink *find(const KeyType& key) const;
// 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 *findEndOfRange(
bslalg::BidirectionalLink *first) 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.
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
// 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.
{
BSLS_ASSERT_SAFE(first);
BSLS_ASSERT_SAFE(last);
*first = this->find(key);
*last = *first ? this->findEndOfRange(*first) : 0;
}
void findRange(bslalg::BidirectionalLink **first,
bslalg::BidirectionalLink **last,
const KeyType& key) 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
// 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.
bool hasSameValue(const HashTable& other) 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'}).
const HASHER& hasher() const;
// Return a reference providing non-modifiable access to the hash
// functor used by this hash-table.
float loadFactor() const;
// Return the current load factor for this table. The load factor is
// the statistical mean number of elements per bucket.
float maxLoadFactor() 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.
SizeType maxNumBuckets() 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 maxSize() 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 numBuckets() const;
// Return the number of buckets contained in this hash table.
SizeType rehashThreshold() const;
// Return the number of elements this hash table can hold without
// requiring a rehash operation in order to respect the
// 'maxLoadFactor'.
SizeType size() const;
// Return the number of elements in this hash table.
};
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);
// 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>
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 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'}).
// ============================
// class HashTable_ArrayProctor
// ============================
template <class FACTORY>
class HashTable_ArrayProctor {
// This class probably already exists in 'bslalg'
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
HashTable_ArrayProctor(FACTORY *factory,
bslalg::HashTableAnchor *anchor);
// Create a 'HashTable_ArrayProctor' managing the hash-table data
// structure owned by the specified 'anchor' that was created using the
// specified 'factory'.
~HashTable_ArrayProctor();
// 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.
// MANIPULATORS
void release();
// Release from management the object currently managed by this
// proctor. If no object is currently being managed, this method has
// no effect.
};
// ===========================
// class HashTable_NodeProctor
// ===========================
template <class FACTORY>
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:
//..
// void deleteNode(bslalg::BidirectionalLink *node);
//..
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
HashTable_NodeProctor(FACTORY *factory,
bslalg::BidirectionalLink *node);
// 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();
// 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.
// MANIPULATORS
void release();
// Release from management the node currently managed by this proctor.
// If no object is currently being managed, this method has no effect.
};
// ==========================
// class HashTable_ImpDetails
// ==========================
struct HashTable_ImpDetails {
// This utility 'struct' provides a namespace for functions that are useful
// when implementing a hash table.
// CLASS METHODS
static bslalg::HashTableBucket *defaultBucketAddress();
// 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 size_t growBucketsForLoadFactor(size_t *capacity,
size_t minElements,
size_t requestedBuckets,
double maxLoadFactor);
// 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 bslma::Allocator *incidentalAllocator();
// 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 size_t nextPrime(size_t n);
// 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).
};
// ====================
// class HashTable_Util
// ====================
struct 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 'bslma_allocatortraits' for their implementation.
// CLASS METHODS
template <class TYPE>
static void assertNotNullPointer(TYPE&);
template <class TYPE>
static void assertNotNullPointer(TYPE * const& ptr);
template <class TYPE>
static void assertNotNullPointer(TYPE * & ptr);
// 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 ALLOCATOR>
static void destroyBucketArray(bslalg::HashTableBucket *data,
std::size_t bucketArraySize,
const ALLOCATOR& allocator);
// Destroy the specified 'data' array of the specified length
// 'bucketArraySize', that was allocated by the specified 'allocator'.
template<class ALLOCATOR>
static void initAnchor(bslalg::HashTableAnchor *anchor,
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()'.
};
// ==============================
// 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> >
{
};
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
class HashTable_ImplParameters
: private HashTable_BaseHasher<HASHER>::Type
, private HashTable_Comparator<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.
// PRIVATE TYPES
typedef typename HashTable_BaseHasher<HASHER>::Type BaseHasher;
typedef typename HashTable_Comparator<COMPARATOR>::Type BaseComparator;
typedef bslmf::MovableRefUtil MoveUtil;
// This typedef is a convenient alias for the utility associated with
// movable references.
// 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
HashTable_ImplParameters(const HashTable_ImplParameters&); // = delete;
HashTable_ImplParameters& operator=(const HashTable_ImplParameters&);
// = delete;
public:
// CREATORS
explicit HashTable_ImplParameters(const ALLOCATOR& allocator);
// Create a 'HashTable_ImplParameters' object having default
// constructed 'HASHER' and 'COMPARATOR' 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 specified
// 'hash' and 'compare' functors, and using the specified 'allocator'
// to provide a 'BidirectionalNodePool'.
HashTable_ImplParameters(const HashTable_ImplParameters& original,
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(
bslmf::MovableRef<HashTable_ImplParameters> original);
// 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.
// MANIPULATORS
NodeFactory& nodeFactory();
// Return a reference offering modifiable access to the 'nodeFactory'
// owned by this object.
void quickSwapExchangeAllocators(HashTable_ImplParameters *other);
// 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 quickSwapRetainAllocators(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'.
// ACCESSORS
const BaseComparator& comparator() const;
// Return a reference offering non-modifiable access to the
// 'comparator' functor owned by this object.
template <class DEDUCED_KEY>
std::size_t hashCodeForKey(DEDUCED_KEY& key) 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'.
const BaseHasher& hasher() const;
// Return a reference offering non-modifiable access to the 'hasher'
// functor owned by this object.
const NodeFactory& nodeFactory() const;
// Return a reference offering non-modifiable access to the
// 'nodeFactory' owned by this object.
const COMPARATOR& originalComparator() const;
// Return a reference offering non-modifiable access to the
// 'comparator' functor owned by this object.
const HASHER& originalHasher() const;
// Return a reference offering non-modifiable access to the 'hasher'
// functor owned by this object.
};
// ============================================================================
// 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));
typedef ::bsl::allocator_traits<ALLOCATOR> ParamAllocTraits;
typedef typename ParamAllocTraits::template
rebind_traits<bslalg::HashTableBucket> BucketAllocTraits;
typedef typename BucketAllocTraits::allocator_type ArrayAllocator;
typedef ::bsl::allocator_traits<ArrayAllocator> ArrayAllocatorTraits;
typedef typename ArrayAllocatorTraits::size_type SizeType;
BSLS_ASSERT_SAFE(bucketArraySize <= std::numeric_limits<SizeType>::max());
if (HashTable_ImpDetails::defaultBucketAddress() != data) {
ArrayAllocator reboundAllocator(allocator);
ArrayAllocatorTraits::deallocate(
reboundAllocator,
data,
static_cast<SizeType>(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);
typedef ::bsl::allocator_traits<ALLOCATOR> ParamAllocTraits;
typedef typename ParamAllocTraits::template
rebind_traits<bslalg::HashTableBucket> BucketAllocTraits;
typedef typename BucketAllocTraits::allocator_type ArrayAllocator;
typedef ::bsl::allocator_traits<ArrayAllocator> ArrayAllocatorTraits;
typedef typename ArrayAllocatorTraits::size_type SizeType;
BSLS_ASSERT_SAFE(bucketArraySize <= std::numeric_limits<SizeType>::max());
ArrayAllocator reboundAllocator(allocator);
// This test is necessary to avoid undefined behavior in the non-standard
// narrow contract of 'bsl::allocator', although it seems like a reasonable
// assumption to pre-empt other allocators too.
if (ArrayAllocatorTraits::max_size(reboundAllocator) < bucketArraySize) {
bsls::BslExceptionUtil::throwBadAlloc();
}
// Conversion to exactly the correct type resolves compiler warnings. The
// assertions above are a loose safety check that this conversion can never
// overflow - which would require an allocator using a 'size_type' larger
// than 'std::size_t', with the requirement that a standard conforming
// allocator must use a 'size_type' that is a built-in unsigned integer
// type.
const SizeType newArraySize = static_cast<SizeType>(bucketArraySize);
bslalg::HashTableBucket *data = ArrayAllocatorTraits::allocate(
reboundAllocator,
newArraySize);
std::fill_n(data, bucketArraySize, bslalg::HashTableBucket());
anchor->setBucketArrayAddressAndSize(data, newArraySize);
}
//-------------------------------
// 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)
{
class Proctor {
// 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.
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_VARIADIC_TEMPLATES
// {{{ BEGIN GENERATED CODE
// Command line: sim_cpp11_features.pl bslstl_hashtable.h
#ifndef BSLSTL_HASHTABLE_VARIADIC_LIMIT
#define BSLSTL_HASHTABLE_VARIADIC_LIMIT 10
#endif
#ifndef BSLSTL_HASHTABLE_VARIADIC_LIMIT_D
#define BSLSTL_HASHTABLE_VARIADIC_LIMIT_D BSLSTL_HASHTABLE_VARIADIC_LIMIT
#endif
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 0
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
);
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 0
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 1
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 1
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 2
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 2
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 3
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 3
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 4
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 4
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 5
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 5
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 6
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 6
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 7
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 7
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 8
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, arguments_08));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 8
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 9
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, arguments_08),
BSLS_COMPILERFEATURES_FORWARD(Args_09, arguments_09));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 9
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 10
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09,
class Args_10>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_10) arguments_10)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, arguments_08),
BSLS_COMPILERFEATURES_FORWARD(Args_09, arguments_09),
BSLS_COMPILERFEATURES_FORWARD(Args_10, arguments_10));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 10
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 0
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
);
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 0
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 1
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 1
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 2
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 2
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 3
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 3
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 4
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 4
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 5
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 5
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 6
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 6
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 7
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 7
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 8
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, arguments_08));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 8
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 9
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, arguments_08),
BSLS_COMPILERFEATURES_FORWARD(Args_09, arguments_09));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 9
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 10
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09,
class Args_10>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceWithHint(
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_10) arguments_10)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, arguments_08),
BSLS_COMPILERFEATURES_FORWARD(Args_09, arguments_09),
BSLS_COMPILERFEATURES_FORWARD(Args_10, arguments_10));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
#endif // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 10
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 0
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
);
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 0
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 1
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 1
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 2
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 2
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 3
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 3
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 4
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 4
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 5
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 5
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 6
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 6
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 7
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 7
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 8
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, arguments_08));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 8
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 9
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, arguments_08),
BSLS_COMPILERFEATURES_FORWARD(Args_09, arguments_09));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 9
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 10
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09,
class Args_10>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplaceIfMissing(
bool *isInsertedFlag,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) arguments_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) arguments_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) arguments_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) arguments_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) arguments_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) arguments_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) arguments_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) arguments_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) arguments_09,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_10) arguments_10)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args_01, arguments_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, arguments_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, arguments_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, arguments_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, arguments_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, arguments_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, arguments_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, arguments_08),
BSLS_COMPILERFEATURES_FORWARD(Args_09, arguments_09),
BSLS_COMPILERFEATURES_FORWARD(Args_10, arguments_10));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_D >= 10
#else
// The generated code below is a workaround for the absence of perfect
// forwarding in some compilers.
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class... Args>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::emplace(
BSLS_COMPILERFEATURES_FORWARD_REF(Args)... arguments)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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,
BSLS_COMPILERFEATURES_FORWARD_REF(Args)... arguments)
{
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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,
BSLS_COMPILERFEATURES_FORWARD_REF(Args)... arguments)
{
BSLS_ASSERT(isInsertedFlag);
typedef bslalg::HashTableImpUtil ImpUtil;
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
bslalg::BidirectionalLink *newNode =
d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), newNode);
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;
}
// }}} END GENERATED CODE
#endif
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::insertIfMissing(
const KeyType& key)
{
size_t hashCode = this->d_parameters.hashCodeForKey(key);
bslalg::BidirectionalLink *position = this->find(key, hashCode);
if (!position) {
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
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());
bslma::DestructorGuard<MappedType> mappedGuard(
defaultMapped.address());
#if defined(BSLMF_MOVABLEREF_USES_RVALUE_REFERENCES)
position = d_parameters.nodeFactory().emplaceIntoNewNode(
key,
MoveUtil::move(defaultMapped.object()));
#else
position = d_parameters.nodeFactory().emplaceIntoNewNode(
key,
defaultMapped.object());
#endif
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,
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));
}
// {{{ BEGIN GENERATED CODE
// The generated code below is a workaround for the absence of perfect
// forwarding in some compilers.
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,
BSLS_COMPILERFEATURES_FORWARD_REF(BDE_OTHER_TYPE) obj)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
static_cast<NodeType *>(hint)->value().second =
BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj);
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
BSLS_COMPILERFEATURES_FORWARD(BDE_OTHER_TYPE, obj));
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), hint);
ImpUtil::insertAtFrontOfBucket(&d_anchor, hint, hashCode);
nodeProctor.release();
++d_size;
*isInsertedFlag = true;
return hint;
}
// }}} END GENERATED CODE
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_VARIADIC_TEMPLATES
// {{{ BEGIN GENERATED CODE
// Command line: sim_cpp11_features.pl bslstl_hashtable.h
#ifndef BSLSTL_HASHTABLE_VARIADIC_LIMIT
#define BSLSTL_HASHTABLE_VARIADIC_LIMIT 10
#endif
#ifndef BSLSTL_HASHTABLE_VARIADIC_LIMIT_F
#define BSLSTL_HASHTABLE_VARIADIC_LIMIT_F BSLSTL_HASHTABLE_VARIADIC_LIMIT
#endif
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 0
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple());
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType());
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 0
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 1
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class Args_01>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01)));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01)));
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 1
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 2
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class Args_01,
class Args_02>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02)));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02)));
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 2
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 3
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03)));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03)));
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 3
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 4
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04)));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04)));
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 4
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 5
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05)));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05)));
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 5
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 6
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) args_06)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, args_06)));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, args_06)));
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 6
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 7
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) args_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) args_07)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, args_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, args_07)));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, args_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, args_07)));
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 7
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 8
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) args_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) args_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) args_08)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, args_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, args_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, args_08)));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, args_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, args_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, args_08)));
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 8
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 9
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) args_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) args_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) args_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) args_09)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, args_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, args_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, args_08),
BSLS_COMPILERFEATURES_FORWARD(Args_09, args_09)));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, args_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, args_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, args_08),
BSLS_COMPILERFEATURES_FORWARD(Args_09, args_09)));
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 9
#if BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 10
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class Args_01,
class Args_02,
class Args_03,
class Args_04,
class Args_05,
class Args_06,
class Args_07,
class Args_08,
class Args_09,
class Args_10>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_01) args_01,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_02) args_02,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_03) args_03,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_04) args_04,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_05) args_05,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_06) args_06,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_07) args_07,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_08) args_08,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_09) args_09,
BSLS_COMPILERFEATURES_FORWARD_REF(Args_10) args_10)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, args_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, args_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, args_08),
BSLS_COMPILERFEATURES_FORWARD(Args_09, args_09),
BSLS_COMPILERFEATURES_FORWARD(Args_10, args_10)));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(
BSLS_COMPILERFEATURES_FORWARD(Args_01, args_01),
BSLS_COMPILERFEATURES_FORWARD(Args_02, args_02),
BSLS_COMPILERFEATURES_FORWARD(Args_03, args_03),
BSLS_COMPILERFEATURES_FORWARD(Args_04, args_04),
BSLS_COMPILERFEATURES_FORWARD(Args_05, args_05),
BSLS_COMPILERFEATURES_FORWARD(Args_06, args_06),
BSLS_COMPILERFEATURES_FORWARD(Args_07, args_07),
BSLS_COMPILERFEATURES_FORWARD(Args_08, args_08),
BSLS_COMPILERFEATURES_FORWARD(Args_09, args_09),
BSLS_COMPILERFEATURES_FORWARD(Args_10, args_10)));
#endif
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 // BSLSTL_HASHTABLE_VARIADIC_LIMIT_F >= 10
#else
// The generated code below is a workaround for the absence of perfect
// forwarding in some compilers.
template <class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
template <class KEY_ARG, class... Args>
bslalg::BidirectionalLink *
HashTable<KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR>::tryEmplace(
bool *isInsertedFlag,
bslalg::BidirectionalLink *hint,
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key,
BSLS_COMPILERFEATURES_FORWARD_REF(Args)... args)
{
typedef bslalg::HashTableImpUtil ImpUtil;
const KEY_ARG& lvalue = key;
const size_t hashCode = this->d_parameters.hashCodeForKey(lvalue);
if (!hint
|| !d_parameters.comparator()(lvalue,
ImpUtil::extractKey<KEY_CONFIG>(hint))) {
hint = this->find(lvalue, hashCode);
}
if (hint) {
*isInsertedFlag = false;
return hint;
}
if (d_size >= d_capacity) {
this->rehashForNumBuckets(numBuckets() * 2);
}
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP11_PAIR_PIECEWISE_CONSTRUCTOR)
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
std::piecewise_construct,
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key)),
std::forward_as_tuple(BSLS_COMPILERFEATURES_FORWARD(Args, args)...));
#else
typedef typename ValueType::second_type MappedType;
hint = d_parameters.nodeFactory().emplaceIntoNewNode(
BSLS_COMPILERFEATURES_FORWARD(KEY_ARG, key),
MappedType(BSLS_COMPILERFEATURES_FORWARD(Args, args)...));
#endif
HashTable_NodeProctor<typename ImplParameters::NodeFactory>
nodeProctor(&d_parameters.nodeFactory(), hint);
ImpUtil::insertAtFrontOfBucket(&d_anchor, hint, hashCode);
nodeProctor.release();
++d_size;
*isInsertedFlag = true;
return hint;
}
// }}} END GENERATED CODE
#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;
}
// 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;
}
}
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
} // close enterprise namespace
#else // if ! defined(DEFINED_BSLSTL_HASHTABLE_H)
# error Not valid except when included from bslstl_hashtable.h
#endif // ! defined(COMPILING_BSLSTL_HASHTABLE_H)
#endif // ! defined(INCLUDED_BSLSTL_HASHTABLE_CPP03)
// ----------------------------------------------------------------------------
// Copyright 2022 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 ----------------------------------