Quick Links: |
#include <bdlcc_stripedunorderedmap.h>
Public Types | |
enum | { k_DEFAULT_NUM_BUCKETS = 16, k_DEFAULT_NUM_STRIPES = 4 } |
typedef bsl::pair< KEY, VALUE > | KVType |
typedef bsl::function< bool(VALUE *, const KEY &) | VisitorFunction ) |
typedef bsl::function< bool(const VALUE &, const KEY &)> | ReadOnlyVisitorFunction |
Public Member Functions | |
StripedUnorderedMap (bsl::size_t numInitialBuckets=k_DEFAULT_NUM_BUCKETS, bsl::size_t numStripes=k_DEFAULT_NUM_STRIPES, bslma::Allocator *basicAllocator=0) | |
StripedUnorderedMap (bslma::Allocator *basicAllocator) | |
~StripedUnorderedMap () | |
void | clear () |
void | disableRehash () |
void | enableRehash () |
bsl::size_t | erase (const KEY &key) |
template<class RANDOM_ITER > | |
bsl::size_t | eraseBulk (RANDOM_ITER first, RANDOM_ITER last) |
bsl::size_t | insert (const KEY &key, const VALUE &value) |
bsl::size_t | insert (const KEY &key, bslmf::MovableRef< VALUE > value) |
template<class RANDOM_ITER > | |
bsl::size_t | insertBulk (RANDOM_ITER first, RANDOM_ITER last) |
void | maxLoadFactor (float newMaxLoadFactor) |
void | rehash (bsl::size_t numBuckets) |
int | setComputedValue (const KEY &key, const VisitorFunction &visitor) |
bsl::size_t | setValue (const KEY &key, const VALUE &value) |
bsl::size_t | setValue (const KEY &key, bslmf::MovableRef< VALUE > value) |
int | update (const KEY &key, const VisitorFunction &visitor) |
int | visit (const VisitorFunction &visitor) |
int | visit (const KEY &key, const VisitorFunction &visitor) |
bsl::size_t | bucketCount () const |
bsl::size_t | bucketIndex (const KEY &key) const |
bsl::size_t | bucketSize (bsl::size_t index) const |
bool | empty () const |
EQUAL | equalFunction () const |
bsl::size_t | getValue (VALUE *value, const KEY &key) const |
HASH | hashFunction () const |
bool | isRehashEnabled () const |
float | loadFactor () const |
float | maxLoadFactor () const |
bsl::size_t | numStripes () const |
int | visitReadOnly (const ReadOnlyVisitorFunction &visitor) const |
int | visitReadOnly (const KEY &key, const ReadOnlyVisitorFunction &visitor) const |
bsl::size_t | size () const |
bslma::Allocator * | allocator () const |
This class template defines a fully thread-safe container that provides a mapping from keys (of template parameter type KEY
) to their associated mapped values (of template parameter type VALUE
).
The buckets of this hash map are guarded by numStripes
reader-writer locks, a value specified on construction. Partitioning the buckets among several locks allows greater overall concurrency than a bsl::unordered_map
object guarded by a single lock.
The interface is inspired by, but not identical to that of bsl::unordered_map
. Notably absent are iterators, which are of limited practicality in the typical use case because they are readily invalidated when the map population is open to modification by multiple threads.
See Component bdlcc_stripedunorderedmap
typedef bsl::pair<KEY, VALUE> bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::KVType |
typedef bsl::function<bool (VALUE *, const KEY&) bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::VisitorFunction) |
An alias to a function meeting the following contract:
bool visitorFunction(VALUE *value, const KEY& key); // Visit the specified 'value' attribute associated with the // specified 'key'. Return 'true' if this function may be // called on additional elements, and 'false' otherwise (i.e., // if no other elements should be visited). Note that this // functor can change the value associated with 'key'.
typedef bsl::function<bool (const VALUE&, const KEY&)> bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::ReadOnlyVisitorFunction |
An alias to a function meeting the following contract:
bool visitorFunction(const VALUE& value, const KEY& key); // Visit the specified 'value' attribute associated with the // specified 'key'. Return 'true' if this function may be // called on additional elements, and 'false' otherwise (i.e., // if no other elements should be visited). Note that this // functor can *not* change the value associated with 'key' // and 'value'.
anonymous enum |
bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::StripedUnorderedMap | ( | bsl::size_t | numInitialBuckets = k_DEFAULT_NUM_BUCKETS , |
|
bsl::size_t | numStripes = k_DEFAULT_NUM_STRIPES , |
|||
bslma::Allocator * | basicAllocator = 0 | |||
) | [explicit] |
bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::StripedUnorderedMap | ( | bslma::Allocator * | basicAllocator | ) | [explicit] |
Create an empty StripedUnorderedMap
object, a fully thread-safe hash map where access is partitioned into "stripes" (a group of buckets protected a reader-writer mutex). Optionally specify numInitialBuckets
and numStripes
which define the minimum number of buckets and the (fixed) number of stripes in this map. Optionally specify a basicAllocator
used to supply memory. If basicAllocator
is 0, the currently installed default allocator is used. The hash map has rehash enabled. Note that the number of stripes will not change after construction, but the number of buckets may (unless rehashing is disabled via disableRehash
).
bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::~StripedUnorderedMap | ( | ) |
Destroy this hash map.
void bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::clear | ( | ) |
Remove all elements from this hash map. If rehash is in progress, block until it completes.
void bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::disableRehash | ( | ) |
Prevent future rehash until enableRehash
is called.
void bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::enableRehash | ( | ) |
Allow rehash. If conditions warrant, rehash will be started by the next method call that observes the load factor is exceeded (see Concurrent Rehash). Note that calling maxLoadFactor(maxLoadFactor())
(i.e., setting the maximum load factor to its current value) will trigger a rehash if needed but otherwise does not change the hash map.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::erase | ( | const KEY & | key | ) |
Erase from this hash map the element having the specified key
. Return 1 on success and 0 if key
does not exist. Note that the returned value equals the number of elements removed.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::eraseBulk | ( | RANDOM_ITER | first, | |
RANDOM_ITER | last | |||
) |
Erase from this hash map elements in this hash map having any of the values in the keys contained between the specified first
(inclusive) and last
(exclusive) random-access iterators. The iterators provide read access to a sequence of KEY
objects. All erasures are done by the calling thread and the order of erasure is not specified. Return the number of elements removed. The behavior is undefined unless first <= last
. Note that the map may not have an element for every value in keys
.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::insert | ( | const KEY & | key, | |
const VALUE & | value | |||
) |
Insert into this hash map an element having the specified key
and value
. If key
already exists in this hash map, the value attribute of that element is set to value
. Return 1 if an element is inserted, and 0 if an existing element is updated. Note that the return value equals the number of elements inserted.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::insert | ( | const KEY & | key, | |
bslmf::MovableRef< VALUE > | value | |||
) |
Insert into this hash map an element having the specified key
and the specified move-insertable value
. If key
already exists in this hash map, the value attribute of that element is set to value
. Return 1 if an element is inserted, and 0 if an existing element is updated. The value
object is left in a valid but unspecified state. If value
is allocator-enabled and allocator() != value.allocator()
this operation may cost as much as a copy. Note that the return value equals the number of elements inserted.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::insertBulk | ( | RANDOM_ITER | first, | |
RANDOM_ITER | last | |||
) |
Insert into this hash map elements having the key-value pairs obtained between the specified first
(inclusive) and last
(exclusive) random-access iterators. The iterators provide read access to a sequence of bsl::pair<KEY, VALUE>
objects. If an element having one of the keys already exists in this hash map, set the value attribute to the corresponding value from data
. All insertions are done by the calling thread and the order of insertion is not specified. Return the number of elements inserted. The behavior is undefined unless first <= last
.
void bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::maxLoadFactor | ( | float | newMaxLoadFactor | ) |
Set the maximum load factor of this unordered map to the specified newMaxLoadFactor
. If newMaxLoadFactor < loadFactor()
, this operation will cause an immediate rehash; otherwise, this operation has a constant-time cost. The rehash will increase the number of buckets by a power of 2. The behavior is undefined unless 0 < newMaxLoadFactor
.
void bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::rehash | ( | bsl::size_t | numBuckets | ) |
Recreate this hash map to one having at least the specified numBuckets
. This operation is a no-op if any of the following are true: 1) rehash is disabled; 2) numBuckets
less or equals the current number of buckets. See Rehash.
int bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::setComputedValue | ( | const KEY & | key, | |
const VisitorFunction & | visitor | |||
) |
Invoke the specified visitor
on the value associated with the specified key
. The visitor
will be passed the address of the value, and key
. If key
is not in the map, value
will be default constructed. That is, visitor
must be invocable with the VisitorFunction
signature:
bool visitor(VALUE *value, const Key& key);
If no element in the map has key
, insert (key, VALUE())
and invoke visitor
with value
pointing to the default constructed value. Return 1 if key
was found and visitor
returned true
, 0 if key
was not found, and -1 if key
was found and visitor
returned false
. visitor
, when invoked, has exclusive access (i.e., write access) to the element. The behavior is undefined if hash map manipulators and getValue*
methods are invoked from within visitor
, as it may lead to a deadlock. Note that the return value equals the number of elements found having key
. Also note that a return value of 0
implies that an element was inserted.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::setValue | ( | const KEY & | key, | |
const VALUE & | value | |||
) |
Set the value attribute of the element in this hash map having the specified key
to the specified value
. If no such such element exists, insert (key, value)
. Return 1 if key
was found, and 0 otherwise. Note that the return value equals the number of elements found having key
.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::setValue | ( | const KEY & | key, | |
bslmf::MovableRef< VALUE > | value | |||
) |
Set the value attribute of the element in this hash map having the specified key
to the specified move-insertable value
. If no such such element exists, insert (key, value)
. Return 1 if key
was found, and 0 otherwise. The value
object is left in a valid but unspecified state. If value
is allocator-enabled and allocator() != value.allocator()
this operation may cost as much as a copy. Note that the return value equals the number of elements found having key
.
int bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::update | ( | const KEY & | key, | |
const VisitorFunction & | visitor | |||
) |
DEPRECATED: Use visit(key, visitor)
instead.
Call the specified visitor
with the element (if one exists) in this hash map having the specified key
. That is:
bool visitor(&value, key);
Return the number of elements updated or -1 if visitor
returned false
. visitor
has exclusive access (i.e., write access) the element for during its invocation. The behavior is undefined if hash map manipulators and getValue*
methods are invoked from within visitor
, as it may lead to a deadlock.
int bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::visit | ( | const VisitorFunction & | visitor | ) |
Call the specified visitor
(in an unspecified order) on all elements in this hash table until each such element has been visited or visitor
returns false
. That is, for (key, value)
, invoke:
bool visitor(&value, key);
Return the number of elements visited or the negation of that value if visitations stopped because visitor
returned false
. visitor
has exclusive access (i.e., write access) to each element for duration of each invocation. Every element present in this hash map at the time visit
is invoked will be visited unless it is removed before visitor
is called for that element. Each visitation is done by the calling thread and the order of visitation is not specified. Elements inserted during the execution of visit
may or may not be visited. The behavior is undefined if hash map manipulators and getValue*
methods are invoked from within visitor
, as it may lead to a deadlock. Note that visitor
can change the value of the visited elements.
int bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::visit | ( | const KEY & | key, | |
const VisitorFunction & | visitor | |||
) |
Call the specified visitor
with the element (if one exists) in this hash map having the specified key
. That is:
bool visitor(&value, key);
Return the number of elements updated or -1 if visitor
returned false
. visitor
has exclusive access (i.e., write access) the element for during its invocation. The behavior is undefined if hash map manipulators and getValue*
methods are invoked from within visitor
, as it may lead to a deadlock.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::bucketCount | ( | ) | const |
Return the number of buckets in the array of buckets maintained by this hash map. Note that unless rehash is disabled, the value returned may be obsolete by the time it is received.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::bucketIndex | ( | const KEY & | key | ) | const |
Return the index of the bucket, in the array of buckets maintained by this hash map, where elements having the specified key
are inserted. Note that unless rehash is disabled, the value returned may be obsolete at the time it is returned.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::bucketSize | ( | bsl::size_t | index | ) | const |
Return the number of elements contained in the bucket at the specified index
in the array of buckets maintained by this hash map. The behavior is undefined unless 0 <= index < bucketCount()
. Note that unless rehash is disabled the value returned may be obsolete by the time it is returned.
bool bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::empty | ( | ) | const |
Return true
if this hash map contains no elements, and false
otherwise.
EQUAL bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::equalFunction | ( | ) | const |
Return (a copy of) the key-equality functor used by this hash map. The returned function will return true
if two KEY
objects have the same value, and false
otherwise.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::getValue | ( | VALUE * | value, | |
const KEY & | key | |||
) | const |
Load, into the specified *value
, the value attribute of the element in this hash map having the specified key
. Return 1 on success and 0 if key
does not exist in this hash map. Note that the return value equals the number of values returned.
HASH bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::hashFunction | ( | ) | const |
Return (a copy of) the unary hash functor used by this hash map. The return function will generate a hash value (of type std::size_t
) for a KEY
object.
bool bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::isRehashEnabled | ( | ) | const |
Return true
if rehash is enabled, or false
otherwise.
float bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::loadFactor | ( | ) | const |
Return the current quotient of the size of this hash map and the number of buckets. Note that the load factor is a measure of container "fullness"; that is, a high load factor typically implies many collisions (many elements landing in the same bucket) and that decreases performance. See Rehash Control.
float bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::maxLoadFactor | ( | ) | const |
Return the maximum load factor allowed for this hash map. If an insert operation would cause the load factor to exceed the maxLoadFactor()
and rehashing is enabled, then that insert increases the number of buckets and rehashes the elements of the container into that larger set of buckets. See Rehash Control.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::numStripes | ( | ) | const |
Return the number of stripes in the hash.
int bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::visitReadOnly | ( | const ReadOnlyVisitorFunction & | visitor | ) | const |
Call the specified visitor
(in an unspecified order) on all elements in this hash table until each such element has been visited or visitor
returns false
. That is, for (key, value)
, invoke:
bool visitor(value, key);
Return the number of elements visited or the negation of that value if visitations stopped because visitor
returned false
. visitor
has read-only access to each element for duration of each invocation. Every element present in this hash map at the time visit
is invoked will be visited unless it is removed before visitor
is called for that element. Each visitation is done by the calling thread and the order of visitation is not specified. The behavior is undefined if hash map manipulators are invoked from within visitor
, as it may lead to a deadlock. Note that visitor
can not change the value of the visited elements.
int bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::visitReadOnly | ( | const KEY & | key, | |
const ReadOnlyVisitorFunction & | visitor | |||
) | const |
Call the specified visitor
on element (if one exists) in this hash map having the specified key
. That is, for (key, value)
, invoke:
bool visitor(value, key);
Return the number of elements visited or -1
if visitor
returned false
. visitor
has read-only access to each element for duration of each invocation. The behavior is undefined if hash map manipulators are invoked from within visitor
, as it may lead to a deadlock.
bsl::size_t bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::size | ( | ) | const |
Return the current number of elements in this hash map.
bslma::Allocator* bdlcc::StripedUnorderedMap< KEY, VALUE, HASH, EQUAL >::allocator | ( | ) | const |
Return the allocator used by this hash map to supply memory. Note that if no allocator was supplied at construction the default allocator installed at that time is used.