X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2FAtomicHashMap-inl.h;h=ee3da5da01f8b526d56636a11f24f097718b5891;hp=f2738649c8c62b04d9f9640778df00f61e9805ca;hb=df9c2e3e07c9a5ae2052304cfc368791d8bc3644;hpb=27494a20393fa45072e7d526d358835f3abe312a diff --git a/folly/AtomicHashMap-inl.h b/folly/AtomicHashMap-inl.h index f2738649..ee3da5da 100644 --- a/folly/AtomicHashMap-inl.h +++ b/folly/AtomicHashMap-inl.h @@ -1,5 +1,5 @@ /* - * Copyright 2012 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. @@ -18,55 +18,104 @@ #error "This should only be included by AtomicHashMap.h" #endif -#include "folly/detail/AtomicHashUtils.h" +#include namespace folly { -template -const typename AtomicHashMap::Config -AtomicHashMap::defaultConfig; - // AtomicHashMap constructor -- Atomic wrapper that allows growth // This class has a lot of overhead (184 Bytes) so only use for big maps -template -AtomicHashMap:: -AtomicHashMap(size_t size, const Config& config) - : kGrowthFrac_(1.0 - config.maxLoadFactor) { - 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 -std::pair::iterator,bool> -AtomicHashMap:: -insert(const value_type& r) { - SimpleRetT ret = insertInternal(r); +// 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::iterator, bool> +AtomicHashMap:: +emplace(LookupKeyT k, ArgTs&&... vCtorArgs) { + SimpleRetT ret = insertInternal( + k, std::forward(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 AtomicHashMap::SimpleRetT -AtomicHashMap:: -insertInternal(const value_type& r) { +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:: + SimpleRetT +AtomicHashMap:: +insertInternal(LookupKeyT key, ArgTs&&... vCtorArgs) { beginInsertInternal: - int nextMapIdx = // this maintains our state + auto nextMapIdx = // this maintains our state numMapsAllocated_.load(std::memory_order_acquire); - uint32_t idx = 0; 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(r); + ret = subMap->template insertInternal( + key, std::forward(vCtorArgs)...); if (ret.idx == subMap->capacity_) { continue; //map is full, so try the next one } @@ -90,7 +139,7 @@ insertInternal(const value_type& r) { 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 @@ -112,16 +161,16 @@ insertInternal(const value_type& r) { } 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(r); + ret = loadedMap->insertInternal(key, std::forward(vCtorArgs)...); if (ret.idx != loadedMap->capacity_) { return SimpleRetT(nextMapIdx, ret.idx, ret.success); } @@ -131,40 +180,80 @@ insertInternal(const value_type& r) { } // find -- -template -typename AtomicHashMap::iterator -AtomicHashMap:: -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 +typename AtomicHashMap:: + iterator +AtomicHashMap::find( + LookupKeyT k) { + SimpleRetT ret = findInternal(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 AtomicHashMap::const_iterator -AtomicHashMap:: -find(KeyT k) const { - return const_cast(this)->find(k); +template < + typename KeyT, + typename ValueT, + typename HashFcn, + typename EqualFcn, + typename Allocator, + typename ProbeFcn, + typename KeyConvertFcn> +template +typename AtomicHashMap::const_iterator +AtomicHashMap:: +find(LookupKeyT k) const { + return const_cast(this)->find(k); } // findInternal -- -template -typename AtomicHashMap::SimpleRetT -AtomicHashMap:: -findInternal(const KeyT k) const { +template < + typename KeyT, + typename ValueT, + typename HashFcn, + typename EqualFcn, + typename Allocator, + typename ProbeFcn, + typename KeyConvertFcn> +template +typename AtomicHashMap:: + SimpleRetT +AtomicHashMap:: + 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(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_release); - ret = thisMap->findInternal(k); + SubMap* thisMap = subMaps_[i].load(std::memory_order_relaxed); + ret = thisMap->template findInternal(k); if (LIKELY(ret.idx != thisMap->capacity_)) { return SimpleRetT(i, ret.idx, ret.success); } @@ -174,9 +263,19 @@ findInternal(const KeyT k) const { } // findAtInternal -- see encodeIndex() for details. -template -typename AtomicHashMap::SimpleRetT -AtomicHashMap:: +template < + typename KeyT, + typename ValueT, + typename HashFcn, + typename EqualFcn, + typename Allocator, + typename ProbeFcn, + typename KeyConvertFcn> +typename AtomicHashMap:: + SimpleRetT +AtomicHashMap:: findAtInternal(uint32_t idx) const { uint32_t subMapIdx, subMapOffset; if (idx & kSecondaryMapBit_) { @@ -194,9 +293,19 @@ findAtInternal(uint32_t idx) const { } // erase -- -template -typename AtomicHashMap::size_type -AtomicHashMap:: +template < + typename KeyT, + typename ValueT, + typename HashFcn, + typename EqualFcn, + typename Allocator, + typename ProbeFcn, + typename KeyConvertFcn> +typename AtomicHashMap:: + size_type +AtomicHashMap:: erase(const KeyT k) { int const numMaps = numMapsAllocated_.load(std::memory_order_acquire); FOR_EACH_RANGE(i, 0, numMaps) { @@ -210,8 +319,16 @@ erase(const KeyT k) { } // capacity -- summation of capacities of all submaps -template -size_t AtomicHashMap:: +template < + typename KeyT, + typename ValueT, + typename HashFcn, + typename EqualFcn, + typename Allocator, + typename ProbeFcn, + typename KeyConvertFcn> +size_t AtomicHashMap:: capacity() const { size_t totalCap(0); int const numMaps = numMapsAllocated_.load(std::memory_order_acquire); @@ -223,8 +340,16 @@ capacity() const { // spaceRemaining -- // number of new insertions until current submaps are all at max load -template -size_t AtomicHashMap:: +template < + typename KeyT, + typename ValueT, + typename HashFcn, + typename EqualFcn, + typename Allocator, + typename ProbeFcn, + typename KeyConvertFcn> +size_t AtomicHashMap:: spaceRemaining() const { size_t spaceRem(0); int const numMaps = numMapsAllocated_.load(std::memory_order_acquire); @@ -240,8 +365,16 @@ spaceRemaining() const { // clear -- Wipes all keys and values from primary map and destroys // all secondary maps. Not thread safe. -template -void AtomicHashMap:: +template < + typename KeyT, + typename ValueT, + typename HashFcn, + typename EqualFcn, + typename Allocator, + typename ProbeFcn, + typename KeyConvertFcn> +void AtomicHashMap:: clear() { subMaps_[0].load(std::memory_order_relaxed)->clear(); int const numMaps = numMapsAllocated_ @@ -256,8 +389,16 @@ clear() { } // size -- -template -size_t AtomicHashMap:: +template < + typename KeyT, + typename ValueT, + typename HashFcn, + typename EqualFcn, + typename Allocator, + typename ProbeFcn, + typename KeyConvertFcn> +size_t AtomicHashMap:: size() const { size_t totalSize(0); int const numMaps = numMapsAllocated_.load(std::memory_order_acquire); @@ -285,11 +426,22 @@ size() const { // 31 1 // 27-30 which subMap // 0-26 subMap offset (index_ret input) -template -inline uint32_t AtomicHashMap:: -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:: + 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 @@ -302,26 +454,31 @@ encodeIndex(uint32_t subMap, uint32_t offset) { // Iterator implementation -template -template -struct AtomicHashMap::ahm_iterator - : boost::iterator_facade, - 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 +struct AtomicHashMap:: + ahm_iterator : boost::iterator_facade, + 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 - ahm_iterator(const ahm_iterator& o, - typename std::enable_if< - std::is_convertible::value >::type* = 0) - : ahm_(o.ahm_) - , subMap_(o.subMap_) - , subIt_(o.subIt_) - {} + template + ahm_iterator( + const ahm_iterator& o, + typename std::enable_if< + std::is_convertible::value>::type* = nullptr) + : ahm_(o.ahm_), subMap_(o.subMap_), subIt_(o.subIt_) {} /* * Returns the unique index that can be used for access directly @@ -340,9 +497,7 @@ struct AtomicHashMap::ahm_iterator : ahm_(ahm) , subMap_(subMap) , subIt_(subIt) - { - checkAdvanceToNextSubmap(); - } + {} friend class boost::iterator_core_access; @@ -378,7 +533,7 @@ struct AtomicHashMap::ahm_iterator 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)) { @@ -387,6 +542,7 @@ struct AtomicHashMap::ahm_iterator subIt_ = thisMap->begin(); } else { ahm_ = nullptr; + return; } } } @@ -398,5 +554,3 @@ struct AtomicHashMap::ahm_iterator }; // ahm_iterator } // namespace folly - -#undef FOLLY_SPIN_WAIT