X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2FAtomicHashMap-inl.h;h=ee3da5da01f8b526d56636a11f24f097718b5891;hp=6d8bb917ee2dac266e2db52dd677959cabcccb36;hb=3764b633f977129f8ee3bca60db7c5d1bb969eec;hpb=800a6af06f7ad195a8e63d484b2f5cd7c19655fd diff --git a/folly/AtomicHashMap-inl.h b/folly/AtomicHashMap-inl.h index 6d8bb917..ee3da5da 100644 --- a/folly/AtomicHashMap-inl.h +++ b/folly/AtomicHashMap-inl.h @@ -1,5 +1,5 @@ /* - * Copyright 2015 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. @@ -24,13 +24,26 @@ namespace folly { // 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 finalSizeEst, const Config& config) - : kGrowthFrac_(config.growthFactor < 0 ? - 1.0 - config.maxLoadFactor : config.growthFactor) { - CHECK(config.maxLoadFactor > 0.0 && config.maxLoadFactor < 1.0); +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 subMapCount = kNumSubMaps_; @@ -41,26 +54,56 @@ AtomicHashMap(size_t finalSizeEst, const Config& config) } // emplace -- -template -template -std::pair::iterator, bool> -AtomicHashMap:: -emplace(key_type k, ArgTs&&... vCtorArgs) { - SimpleRetT ret = insertInternal(k, std::forward(vCtorArgs)...); +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 -template -typename AtomicHashMap::SimpleRetT -AtomicHashMap:: -insertInternal(key_type key, ArgTs&&... vCtorArgs) { +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: auto nextMapIdx = // this maintains our state numMapsAllocated_.load(std::memory_order_acquire); @@ -68,7 +111,11 @@ insertInternal(key_type key, ArgTs&&... vCtorArgs) { 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(vCtorArgs)...); + ret = subMap->template insertInternal( + key, std::forward(vCtorArgs)...); if (ret.idx == subMap->capacity_) { continue; //map is full, so try the next one } @@ -92,7 +139,7 @@ insertInternal(key_type key, ArgTs&&... vCtorArgs) { 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 @@ -133,12 +180,22 @@ insertInternal(key_type key, ArgTs&&... vCtorArgs) { } // find -- -template -typename AtomicHashMap::iterator -AtomicHashMap:: -find(KeyT k) { - SimpleRetT ret = findInternal(k); +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(); } @@ -146,31 +203,57 @@ find(KeyT k) { return iterator(this, ret.i, subMap->makeIter(ret.j)); } -template +template < + typename KeyT, + typename ValueT, + typename HashFcn, + typename EqualFcn, + typename Allocator, + typename ProbeFcn, + typename KeyConvertFcn> +template typename AtomicHashMap::const_iterator -AtomicHashMap:: -find(KeyT k) const { - return const_cast(this)->find(k); + HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn>::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_relaxed); - ret = thisMap->findInternal(k); + ret = thisMap->template findInternal(k); if (LIKELY(ret.idx != thisMap->capacity_)) { return SimpleRetT(i, ret.idx, ret.success); } @@ -180,10 +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_) { @@ -201,10 +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) { @@ -218,9 +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); @@ -232,9 +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); @@ -250,9 +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_ @@ -267,9 +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); @@ -297,12 +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 @@ -315,27 +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