/*
- * Copyright 2013 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#error "This should only be included by AtomicHashMap.h"
#endif
-#include "folly/detail/AtomicHashUtils.h"
+#include <folly/detail/AtomicHashUtils.h>
namespace folly {
-template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-const typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::Config
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::defaultConfig;
-
// AtomicHashMap constructor -- Atomic wrapper that allows growth
// This class has a lot of overhead (184 Bytes) so only use for big maps
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-AtomicHashMap(size_t size, const Config& config)
- : kGrowthFrac_(config.growthFactor < 0 ?
- 1.0 - config.maxLoadFactor : config.growthFactor) {
- CHECK(config.maxLoadFactor > 0.0 && config.maxLoadFactor < 1.0);
- subMaps_[0].store(SubMap::create(size, config).release(),
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+AtomicHashMap<
+ KeyT,
+ ValueT,
+ HashFcn,
+ EqualFcn,
+ Allocator,
+ ProbeFcn,
+ KeyConvertFcn>::AtomicHashMap(size_t finalSizeEst, const Config& config)
+ : kGrowthFrac_(
+ config.growthFactor < 0 ? 1.0f - config.maxLoadFactor
+ : config.growthFactor) {
+ CHECK(config.maxLoadFactor > 0.0f && config.maxLoadFactor < 1.0f);
+ subMaps_[0].store(SubMap::create(finalSizeEst, config).release(),
std::memory_order_relaxed);
- auto numSubMaps = kNumSubMaps_;
- FOR_EACH_RANGE(i, 1, numSubMaps) {
+ auto subMapCount = kNumSubMaps_;
+ FOR_EACH_RANGE(i, 1, subMapCount) {
subMaps_[i].store(nullptr, std::memory_order_relaxed);
}
numMapsAllocated_.store(1, std::memory_order_relaxed);
}
-// insert --
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-std::pair<typename AtomicHashMap<KeyT, ValueT, HashFcn,
- EqualFcn, Allocator>::iterator, bool>
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-insert(key_type k, const mapped_type& v) {
- SimpleRetT ret = insertInternal(k,v);
- SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
- return std::make_pair(iterator(this, ret.i, subMap->makeIter(ret.j)),
- ret.success);
-}
-
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-std::pair<typename AtomicHashMap<KeyT, ValueT, HashFcn,
- EqualFcn, Allocator>::iterator, bool>
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-insert(key_type k, mapped_type&& v) {
- SimpleRetT ret = insertInternal(k, std::move(v));
+// emplace --
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+template <
+ typename LookupKeyT,
+ typename LookupHashFcn,
+ typename LookupEqualFcn,
+ typename LookupKeyToKeyFcn,
+ typename... ArgTs>
+std::pair<typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator,
+ ProbeFcn, KeyConvertFcn>::iterator, bool>
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+emplace(LookupKeyT k, ArgTs&&... vCtorArgs) {
+ SimpleRetT ret = insertInternal<LookupKeyT,
+ LookupHashFcn,
+ LookupEqualFcn,
+ LookupKeyToKeyFcn>(
+ k, std::forward<ArgTs>(vCtorArgs)...);
SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
return std::make_pair(iterator(this, ret.i, subMap->makeIter(ret.j)),
ret.success);
}
// insertInternal -- Allocates new sub maps as existing ones fill up.
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-template <class T>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-insertInternal(key_type key, T&& value) {
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+template <
+ typename LookupKeyT,
+ typename LookupHashFcn,
+ typename LookupEqualFcn,
+ typename LookupKeyToKeyFcn,
+ typename... ArgTs>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+ SimpleRetT
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+insertInternal(LookupKeyT key, ArgTs&&... vCtorArgs) {
beginInsertInternal:
- int nextMapIdx = // this maintains our state
+ auto nextMapIdx = // this maintains our state
numMapsAllocated_.load(std::memory_order_acquire);
typename SubMap::SimpleRetT ret;
FOR_EACH_RANGE(i, 0, nextMapIdx) {
// insert in each map successively. If one succeeds, we're done!
SubMap* subMap = subMaps_[i].load(std::memory_order_relaxed);
- ret = subMap->insertInternal(key, std::forward<T>(value));
+ ret = subMap->template insertInternal<LookupKeyT,
+ LookupHashFcn,
+ LookupEqualFcn,
+ LookupKeyToKeyFcn>(
+ key, std::forward<ArgTs>(vCtorArgs)...);
if (ret.idx == subMap->capacity_) {
continue; //map is full, so try the next one
}
size_t numCellsAllocated = (size_t)
(primarySubMap->capacity_ *
std::pow(1.0 + kGrowthFrac_, nextMapIdx - 1));
- size_t newSize = (int) (numCellsAllocated * kGrowthFrac_);
+ size_t newSize = size_t(numCellsAllocated * kGrowthFrac_);
DCHECK(subMaps_[nextMapIdx].load(std::memory_order_relaxed) ==
(SubMap*)kLockedPtr_);
// create a new map using the settings stored in the first map
} else {
// If we lost the race, we'll have to wait for the next map to get
// allocated before doing any insertion here.
- FOLLY_SPIN_WAIT(
- nextMapIdx >= numMapsAllocated_.load(std::memory_order_acquire)
- );
+ detail::atomic_hash_spin_wait([&] {
+ return nextMapIdx >= numMapsAllocated_.load(std::memory_order_acquire);
+ });
}
// Relaxed is ok here because either we just created this map, or we
// just did a spin wait with an acquire load on numMapsAllocated_.
SubMap* loadedMap = subMaps_[nextMapIdx].load(std::memory_order_relaxed);
DCHECK(loadedMap && loadedMap != (SubMap*)kLockedPtr_);
- ret = loadedMap->insertInternal(key, std::forward<T>(value));
+ ret = loadedMap->insertInternal(key, std::forward<ArgTs>(vCtorArgs)...);
if (ret.idx != loadedMap->capacity_) {
return SimpleRetT(nextMapIdx, ret.idx, ret.success);
}
}
// find --
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::iterator
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-find(KeyT k) {
- SimpleRetT ret = findInternal(k);
- if (ret.i >= numMapsAllocated_.load(std::memory_order_acquire)) {
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+template <class LookupKeyT, class LookupHashFcn, class LookupEqualFcn>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+ iterator
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::find(
+ LookupKeyT k) {
+ SimpleRetT ret = findInternal<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k);
+ if (!ret.success) {
return end();
}
SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
return iterator(this, ret.i, subMap->makeIter(ret.j));
}
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+template <class LookupKeyT, class LookupHashFcn, class LookupEqualFcn>
typename AtomicHashMap<KeyT, ValueT,
- HashFcn, EqualFcn, Allocator>::const_iterator
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-find(KeyT k) const {
- return const_cast<AtomicHashMap*>(this)->find(k);
+ HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn>::const_iterator
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+find(LookupKeyT k) const {
+ return const_cast<AtomicHashMap*>(this)->find<LookupKeyT,
+ LookupHashFcn,
+ LookupEqualFcn>(k);
}
// findInternal --
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-findInternal(const KeyT k) const {
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+template <class LookupKeyT, class LookupHashFcn, class LookupEqualFcn>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+ SimpleRetT
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+ findInternal(const LookupKeyT k) const {
SubMap* const primaryMap = subMaps_[0].load(std::memory_order_relaxed);
- typename SubMap::SimpleRetT ret = primaryMap->findInternal(k);
+ typename SubMap::SimpleRetT ret =
+ primaryMap->template findInternal<LookupKeyT,
+ LookupHashFcn,
+ LookupEqualFcn>(k);
if (LIKELY(ret.idx != primaryMap->capacity_)) {
return SimpleRetT(0, ret.idx, ret.success);
}
- int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
+ const unsigned int numMaps =
+ numMapsAllocated_.load(std::memory_order_acquire);
FOR_EACH_RANGE(i, 1, numMaps) {
// Check each map successively. If one succeeds, we're done!
SubMap* thisMap = subMaps_[i].load(std::memory_order_relaxed);
- ret = thisMap->findInternal(k);
+ ret = thisMap->template findInternal<LookupKeyT,
+ LookupHashFcn,
+ LookupEqualFcn>(k);
if (LIKELY(ret.idx != thisMap->capacity_)) {
return SimpleRetT(i, ret.idx, ret.success);
}
}
// findAtInternal -- see encodeIndex() for details.
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+ SimpleRetT
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
findAtInternal(uint32_t idx) const {
uint32_t subMapIdx, subMapOffset;
if (idx & kSecondaryMapBit_) {
}
// erase --
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::size_type
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+ size_type
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
erase(const KeyT k) {
int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
FOR_EACH_RANGE(i, 0, numMaps) {
}
// capacity -- summation of capacities of all submaps
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
capacity() const {
size_t totalCap(0);
int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
// spaceRemaining --
// number of new insertions until current submaps are all at max load
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
spaceRemaining() const {
size_t spaceRem(0);
int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
// clear -- Wipes all keys and values from primary map and destroys
// all secondary maps. Not thread safe.
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-void AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+void AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
clear() {
subMaps_[0].load(std::memory_order_relaxed)->clear();
int const numMaps = numMapsAllocated_
}
// size --
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
size() const {
size_t totalSize(0);
int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
// 31 1
// 27-30 which subMap
// 0-26 subMap offset (index_ret input)
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-inline uint32_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-encodeIndex(uint32_t subMap, uint32_t offset) {
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+inline uint32_t
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+ encodeIndex(uint32_t subMap, uint32_t offset) {
DCHECK_EQ(offset & kSecondaryMapBit_, 0); // offset can't be too big
- if (subMap == 0) return offset;
+ if (subMap == 0) {
+ return offset;
+ }
// Make sure subMap isn't too big
DCHECK_EQ(subMap >> kNumSubMapBits_, 0);
// Make sure subMap bits of offset are clear
// Iterator implementation
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-template<class ContT, class IterVal, class SubIt>
-struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::ahm_iterator
- : boost::iterator_facade<ahm_iterator<ContT,IterVal,SubIt>,
- IterVal,
- boost::forward_traversal_tag>
-{
- explicit ahm_iterator() : ahm_(0) {}
+template <
+ typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn,
+ typename KeyConvertFcn>
+template <class ContT, class IterVal, class SubIt>
+struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+ Allocator, ProbeFcn, KeyConvertFcn>::
+ ahm_iterator : boost::iterator_facade<ahm_iterator<ContT, IterVal, SubIt>,
+ IterVal,
+ boost::forward_traversal_tag> {
+ explicit ahm_iterator() : ahm_(nullptr) {}
// Conversion ctor for interoperability between const_iterator and
// iterator. The enable_if<> magic keeps us well-behaved for
// is_convertible<> (v. the iterator_facade documentation).
- template<class OtherContT, class OtherVal, class OtherSubIt>
- ahm_iterator(const ahm_iterator<OtherContT,OtherVal,OtherSubIt>& o,
- typename std::enable_if<
- std::is_convertible<OtherSubIt,SubIt>::value >::type* = 0)
- : ahm_(o.ahm_)
- , subMap_(o.subMap_)
- , subIt_(o.subIt_)
- {}
+ template <class OtherContT, class OtherVal, class OtherSubIt>
+ ahm_iterator(
+ const ahm_iterator<OtherContT, OtherVal, OtherSubIt>& o,
+ typename std::enable_if<
+ std::is_convertible<OtherSubIt, SubIt>::value>::type* = nullptr)
+ : ahm_(o.ahm_), subMap_(o.subMap_), subIt_(o.subIt_) {}
/*
* Returns the unique index that can be used for access directly
: ahm_(ahm)
, subMap_(subMap)
, subIt_(subIt)
- {
- checkAdvanceToNextSubmap();
- }
+ {}
friend class boost::iterator_core_access;
SubMap* thisMap = ahm_->subMaps_[subMap_].
load(std::memory_order_relaxed);
- if (subIt_ == thisMap->end()) {
+ while (subIt_ == thisMap->end()) {
// This sub iterator is done, advance to next one
if (subMap_ + 1 <
ahm_->numMapsAllocated_.load(std::memory_order_acquire)) {
subIt_ = thisMap->begin();
} else {
ahm_ = nullptr;
+ return;
}
}
}
}; // ahm_iterator
} // namespace folly
-
-#undef FOLLY_SPIN_WAIT
projects / folly.git / blobdiff