X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FAtomicHashArray-inl.h;h=35a1927c53017de04822a04e9665252e94b1c9a2;hb=6896ff9de7e7e8d8db569b594e9b493d3e4f8122;hp=6ab54850beec6c5acec22d40679255e86abf4471;hpb=d383a1167cca0599b5ca9053f4f5ade55a7b50a5;p=folly.git

diff --git a/folly/AtomicHashArray-inl.h b/folly/AtomicHashArray-inl.h
index 6ab54850..35a1927c 100644
--- a/folly/AtomicHashArray-inl.h
+++ b/folly/AtomicHashArray-inl.h
@@ -18,15 +18,18 @@
 #error "This should only be included by AtomicHashArray.h"
 #endif
 
+#include <type_traits>
+
 #include <folly/Bits.h>
 #include <folly/detail/AtomicHashUtils.h>
 
 namespace folly {
 
 // AtomicHashArray private constructor --
-template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
+          class Allocator, class ProbeFcn, class KeyConvertFcn>
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                Allocator, ProbeFcn, KeyConvertFcn>::
 AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
                 KeyT erasedKey, double _maxLoadFactor, size_t cacheSize)
     : capacity_(capacity),
@@ -43,26 +46,30 @@ AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
  *   of key and returns true, or if key does not exist returns false and
  *   ret.index is set to capacity_.
  */
-template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-typename AtomicHashArray<KeyT, ValueT,
-         HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-findInternal(const KeyT key_in) {
-  DCHECK_NE(key_in, kEmptyKey_);
-  DCHECK_NE(key_in, kLockedKey_);
-  DCHECK_NE(key_in, kErasedKey_);
-  for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
+template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
+          class Allocator, class ProbeFcn, class KeyConvertFcn>
+template <class LookupKeyT, class LookupHashFcn, class LookupEqualFcn>
+typename AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                         Allocator, ProbeFcn, KeyConvertFcn>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                Allocator, ProbeFcn, KeyConvertFcn>::
+findInternal(const LookupKeyT key_in) {
+  checkLegalKeyIfKey<LookupKeyT>(key_in);
+
+  for (size_t idx = keyToAnchorIdx<LookupKeyT, LookupHashFcn>(key_in),
+       numProbes = 0;
        ;
-       idx = probeNext(idx, numProbes)) {
+       idx = ProbeFcn()(idx, numProbes, capacity_)) {
     const KeyT key = acquireLoadKey(cells_[idx]);
-    if (LIKELY(EqualFcn()(key, key_in))) {
+    if (LIKELY(LookupEqualFcn()(key, key_in))) {
       return SimpleRetT(idx, true);
     }
     if (UNLIKELY(key == kEmptyKey_)) {
       // if we hit an empty element, this key does not exist
       return SimpleRetT(capacity_, false);
     }
+    // NOTE: the way we count numProbes must be same in find(), insert(),
+    // and erase(). Otherwise it may break probing.
     ++numProbes;
     if (UNLIKELY(numProbes >= capacity_)) {
       // probed every cell...fail
@@ -81,20 +88,23 @@ findInternal(const KeyT key_in) {
  *   this will be the previously inserted value, and if the map is full it is
  *   default.
  */
-template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-template <class T>
-typename AtomicHashArray<KeyT, ValueT,
-         HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-insertInternal(KeyT key_in, T&& value) {
+template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
+          class Allocator, class ProbeFcn, class KeyConvertFcn>
+template <typename LookupKeyT,
+          typename LookupHashFcn,
+          typename LookupEqualFcn,
+          typename LookupKeyToKeyFcn,
+          typename... ArgTs>
+typename AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                         Allocator, ProbeFcn, KeyConvertFcn>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                Allocator, ProbeFcn, KeyConvertFcn>::
+insertInternal(LookupKeyT key_in, ArgTs&&... vCtorArgs) {
   const short NO_NEW_INSERTS = 1;
   const short NO_PENDING_INSERTS = 2;
-  CHECK_NE(key_in, kEmptyKey_);
-  CHECK_NE(key_in, kLockedKey_);
-  CHECK_NE(key_in, kErasedKey_);
+  checkLegalKeyIfKey<LookupKeyT>(key_in);
 
-  size_t idx = keyToAnchorIdx(key_in);
+  size_t idx = keyToAnchorIdx<LookupKeyT, LookupHashFcn>(key_in);
   size_t numProbes = 0;
   for (;;) {
     DCHECK_LT(idx, capacity_);
@@ -130,16 +140,20 @@ insertInternal(KeyT key_in, T&& value) {
         // If we fail, fall through to comparison below; maybe the insert that
         // just beat us was for this very key....
         if (tryLockCell(cell)) {
+          KeyT key_new;
           // Write the value - done before unlocking
           try {
+            key_new = LookupKeyToKeyFcn()(key_in);
+            typedef typename std::remove_const<LookupKeyT>::type
+              LookupKeyTNoConst;
+            constexpr bool kAlreadyChecked =
+              std::is_same<KeyT, LookupKeyTNoConst>::value;
+            if (!kAlreadyChecked) {
+              checkLegalKeyIfKey(key_new);
+            }
             DCHECK(relaxedLoadKey(*cell) == kLockedKey_);
-            /*
-             * This happens using the copy constructor because we won't have
-             * constructed a lhs to use an assignment operator on when
-             * values are being set.
-             */
-            new (&cell->second) ValueT(std::forward<T>(value));
-            unlockCell(cell, key_in); // Sets the new key
+            new (&cell->second) ValueT(std::forward<ArgTs>(vCtorArgs)...);
+            unlockCell(cell, key_new); // Sets the new key
           } catch (...) {
             // Transition back to empty key---requires handling
             // locked->empty below.
@@ -147,9 +161,11 @@ insertInternal(KeyT key_in, T&& value) {
             --numPendingEntries_;
             throw;
           }
+          // An erase() can race here and delete right after our insertion
           // Direct comparison rather than EqualFcn ok here
           // (we just inserted it)
-          DCHECK(relaxedLoadKey(*cell) == key_in);
+          DCHECK(relaxedLoadKey(*cell) == key_new ||
+                 relaxedLoadKey(*cell) == kErasedKey_);
           --numPendingEntries_;
           ++numEntries_;  // This is a thread cached atomic increment :)
           if (numEntries_.readFast() >= maxEntries_) {
@@ -168,7 +184,7 @@ insertInternal(KeyT key_in, T&& value) {
     }
 
     const KeyT thisKey = acquireLoadKey(*cell);
-    if (EqualFcn()(thisKey, key_in)) {
+    if (LookupEqualFcn()(thisKey, key_in)) {
       // Found an existing entry for our key, but we don't overwrite the
       // previous value.
       return SimpleRetT(idx, false);
@@ -179,17 +195,19 @@ insertInternal(KeyT key_in, T&& value) {
       continue;
     }
 
+
+    // NOTE: the way we count numProbes must be same in find(),
+    // insert(), and erase(). Otherwise it may break probing.
     ++numProbes;
     if (UNLIKELY(numProbes >= capacity_)) {
       // probed every cell...fail
       return SimpleRetT(capacity_, false);
     }
 
-    idx = probeNext(idx, numProbes);
+    idx = ProbeFcn()(idx, numProbes, capacity_);
   }
 }
 
-
 /*
  * erase --
  *
@@ -200,16 +218,18 @@ insertInternal(KeyT key_in, T&& value) {
  *   erased key will never be reused. If there's an associated value, we won't
  *   touch it either.
  */
-template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
+          class Allocator, class ProbeFcn, class KeyConvertFcn>
+size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                       Allocator, ProbeFcn, KeyConvertFcn>::
 erase(KeyT key_in) {
   CHECK_NE(key_in, kEmptyKey_);
   CHECK_NE(key_in, kLockedKey_);
   CHECK_NE(key_in, kErasedKey_);
+
   for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
        ;
-       idx = probeNext(idx, numProbes)) {
+       idx = ProbeFcn()(idx, numProbes, capacity_)) {
     DCHECK_LT(idx, capacity_);
     value_type* cell = &cells_[idx];
     KeyT currentKey = acquireLoadKey(*cell);
@@ -236,6 +256,9 @@ erase(KeyT key_in) {
       // If another thread succeeds in erasing our key, we'll stop our search.
       return 0;
     }
+
+    // NOTE: the way we count numProbes must be same in find(), insert(),
+    // and erase(). Otherwise it may break probing.
     ++numProbes;
     if (UNLIKELY(numProbes >= capacity_)) {
       // probed every cell...fail
@@ -244,17 +267,12 @@ erase(KeyT key_in) {
   }
 }
 
-template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-const typename AtomicHashArray<KeyT, ValueT,
-      HashFcn, EqualFcn, Allocator>::Config
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::defaultConfig;
-
-template <class KeyT, class ValueT,
-         class HashFcn, class EqualFcn, class Allocator>
-typename AtomicHashArray<KeyT, ValueT,
-         HashFcn, EqualFcn, Allocator>::SmartPtr
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
+         class Allocator, class ProbeFcn, class KeyConvertFcn>
+typename AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                         Allocator, ProbeFcn, KeyConvertFcn>::SmartPtr
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                Allocator, ProbeFcn, KeyConvertFcn>::
 create(size_t maxSize, const Config& c) {
   CHECK_LE(c.maxLoadFactor, 1.0);
   CHECK_GT(c.maxLoadFactor, 0.0);
@@ -292,9 +310,10 @@ create(size_t maxSize, const Config& c) {
   return map;
 }
 
-template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
+          class Allocator, class ProbeFcn, class KeyConvertFcn>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                     Allocator, ProbeFcn, KeyConvertFcn>::
 destroy(AtomicHashArray* p) {
   assert(p);
 
@@ -311,9 +330,10 @@ destroy(AtomicHashArray* p) {
 }
 
 // clear -- clears all keys and values in the map and resets all counters
-template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
+          class Allocator, class ProbeFcn, class KeyConvertFcn>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                     Allocator, ProbeFcn, KeyConvertFcn>::
 clear() {
   FOR_EACH_RANGE(i, 0, capacity_) {
     if (cells_[i].first != kEmptyKey_) {
@@ -331,10 +351,12 @@ clear() {
 
 // Iterator implementation
 
-template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
+template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
+          class Allocator, class ProbeFcn, class KeyConvertFcn>
 template <class ContT, class IterVal>
-struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::aha_iterator
+struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
+                       Allocator, ProbeFcn, KeyConvertFcn>::
+    aha_iterator
     : boost::iterator_facade<aha_iterator<ContT,IterVal>,
                              IterVal,
                              boost::forward_traversal_tag>