X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FAtomicHashMap-inl.h;h=e00312662e942b6d6c65eb6287d7191f2f6e4638;hb=49399f7cf36dfdda58e1bc01f2c9a1bc7a4ed400;hp=61c23b14cfdd1f24698620e63b13cd75ec8da016;hpb=99de4c5fde6fce17ac9dab77b2b99ceffce999dc;p=folly.git

diff --git a/folly/AtomicHashMap-inl.h b/folly/AtomicHashMap-inl.h
index 61c23b14..e0031266 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,17 +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 <typename KeyT,
-          typename ValueT,
-          typename HashFcn,
-          typename EqualFcn,
-          typename Allocator,
-          typename ProbeFcn>
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
-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_;
@@ -50,13 +59,23 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
-template <typename... ArgTs>
-std::pair<typename AtomicHashMap<KeyT, ValueT, HashFcn,
-                                 EqualFcn, Allocator, ProbeFcn>::iterator, bool>
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
-emplace(key_type k, ArgTs&&... vCtorArgs) {
-  SimpleRetT ret = insertInternal(k, std::forward<ArgTs>(vCtorArgs)...);
+          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);
@@ -68,12 +87,19 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
-template <typename... ArgTs>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+          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>::
-insertInternal(key_type key, ArgTs&&... vCtorArgs) {
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+              Allocator, ProbeFcn, KeyConvertFcn>::
+insertInternal(LookupKeyT key, ArgTs&&... vCtorArgs) {
  beginInsertInternal:
   auto nextMapIdx = // this maintains our state
     numMapsAllocated_.load(std::memory_order_acquire);
@@ -81,7 +107,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<ArgTs>(vCtorArgs)...);
+    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
     }
@@ -105,7 +135,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
@@ -151,12 +181,16 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+          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>::find(
-    KeyT k) {
-  SimpleRetT ret = findInternal(k);
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+              Allocator, ProbeFcn, KeyConvertFcn>::find(
+    LookupKeyT k) {
+  SimpleRetT ret = findInternal<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k);
   if (!ret.success) {
     return end();
   }
@@ -169,12 +203,17 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
+          typename ProbeFcn,
+          typename KeyConvertFcn>
+template <class LookupKeyT, class LookupHashFcn, class LookupEqualFcn>
 typename AtomicHashMap<KeyT, ValueT,
-         HashFcn, EqualFcn, Allocator, ProbeFcn>::const_iterator
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
-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 --
@@ -183,21 +222,31 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+          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>::
-    findInternal(const KeyT k) const {
+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);
     }
@@ -212,10 +261,13 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+          typename ProbeFcn,
+          typename KeyConvertFcn>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+                       Allocator, ProbeFcn, KeyConvertFcn>::
     SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+              Allocator, ProbeFcn, KeyConvertFcn>::
 findAtInternal(uint32_t idx) const {
   uint32_t subMapIdx, subMapOffset;
   if (idx & kSecondaryMapBit_) {
@@ -238,10 +290,13 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+          typename ProbeFcn,
+          typename KeyConvertFcn>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+                       Allocator, ProbeFcn, KeyConvertFcn>::
     size_type
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+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) {
@@ -260,8 +315,10 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+          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);
@@ -278,8 +335,10 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+          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);
@@ -300,8 +359,10 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
-void AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+          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_
@@ -321,8 +382,10 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+          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);
@@ -355,9 +418,11 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
+          typename ProbeFcn,
+          typename KeyConvertFcn>
 inline uint32_t
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+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;
@@ -378,9 +443,11 @@ template <typename KeyT,
           typename HashFcn,
           typename EqualFcn,
           typename Allocator,
-          typename ProbeFcn>
+          typename ProbeFcn,
+          typename KeyConvertFcn>
 template <class ContT, class IterVal, class SubIt>
-struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn,
+                     Allocator, ProbeFcn, KeyConvertFcn>::
     ahm_iterator : boost::iterator_facade<ahm_iterator<ContT, IterVal, SubIt>,
                                           IterVal,
                                           boost::forward_traversal_tag> {