X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FAtomicHashArray-inl.h;h=1125bb980f8964b4fdb924b24561cdc2067e23bf;hb=ffe26edc53bc90a14078c66e46764ea3e6a81df6;hp=d455bbce7919383525de2f54e6bed586b4fa0be3;hpb=e1c9764467c8c40c427c4b158342ba3642fe10a8;p=folly.git

diff --git a/folly/AtomicHashArray-inl.h b/folly/AtomicHashArray-inl.h
index d455bbce..1125bb98 100644
--- a/folly/AtomicHashArray-inl.h
+++ b/folly/AtomicHashArray-inl.h
@@ -25,8 +25,8 @@ namespace folly {
 
 // AtomicHashArray private constructor --
 template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+          class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
 AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
                 KeyT erasedKey, double _maxLoadFactor, size_t cacheSize)
     : capacity_(capacity),
@@ -44,17 +44,17 @@ AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
  *   ret.index is set to capacity_.
  */
 template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
+          class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
 typename AtomicHashArray<KeyT, ValueT,
-         HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+         HashFcn, EqualFcn, Allocator, ProbeFcn>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
 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;
        ;
-       idx = probeNext(idx, numProbes)) {
+       idx = ProbeFcn()(idx, numProbes, capacity_)) {
     const KeyT key = acquireLoadKey(cells_[idx]);
     if (LIKELY(EqualFcn()(key, key_in))) {
       return SimpleRetT(idx, true);
@@ -63,6 +63,8 @@ findInternal(const KeyT key_in) {
       // 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
@@ -82,12 +84,12 @@ findInternal(const KeyT key_in) {
  *   default.
  */
 template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-template <class T>
+          class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+template <typename... ArgTs>
 typename AtomicHashArray<KeyT, ValueT,
-         HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-insertInternal(KeyT key_in, T&& value) {
+         HashFcn, EqualFcn, Allocator, ProbeFcn>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+insertInternal(KeyT key_in, ArgTs&&... vCtorArgs) {
   const short NO_NEW_INSERTS = 1;
   const short NO_PENDING_INSERTS = 2;
   CHECK_NE(key_in, kEmptyKey_);
@@ -114,10 +116,11 @@ insertInternal(KeyT key_in, T&& value) {
         // another thread now does ++numPendingEntries_, we expect it
         // to pass the isFull_.load() test above. (It shouldn't insert
         // a new entry.)
-        FOLLY_SPIN_WAIT(
-          isFull_.load(std::memory_order_acquire) != NO_PENDING_INSERTS
-            && numPendingEntries_.readFull() != 0
-        );
+        detail::atomic_hash_spin_wait([&] {
+          return
+            (isFull_.load(std::memory_order_acquire) != NO_PENDING_INSERTS) &&
+            (numPendingEntries_.readFull() != 0);
+        });
         isFull_.store(NO_PENDING_INSERTS, std::memory_order_release);
 
         if (relaxedLoadKey(*cell) == kEmptyKey_) {
@@ -132,12 +135,7 @@ insertInternal(KeyT key_in, T&& value) {
           // Write the value - done before unlocking
           try {
             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));
+            new (&cell->second) ValueT(std::forward<ArgTs>(vCtorArgs)...);
             unlockCell(cell, key_in); // Sets the new key
           } catch (...) {
             // Transition back to empty key---requires handling
@@ -146,9 +144,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_in ||
+                 relaxedLoadKey(*cell) == kErasedKey_);
           --numPendingEntries_;
           ++numEntries_;  // This is a thread cached atomic increment :)
           if (numEntries_.readFast() >= maxEntries_) {
@@ -161,9 +161,9 @@ insertInternal(KeyT key_in, T&& value) {
     }
     DCHECK(relaxedLoadKey(*cell) != kEmptyKey_);
     if (kLockedKey_ == acquireLoadKey(*cell)) {
-      FOLLY_SPIN_WAIT(
-        kLockedKey_ == acquireLoadKey(*cell)
-      );
+      detail::atomic_hash_spin_wait([&] {
+        return kLockedKey_ == acquireLoadKey(*cell);
+      });
     }
 
     const KeyT thisKey = acquireLoadKey(*cell);
@@ -178,13 +178,16 @@ 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_);
   }
 }
 
@@ -200,15 +203,16 @@ insertInternal(KeyT key_in, T&& value) {
  *   touch it either.
  */
 template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+          class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
 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);
@@ -235,6 +239,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,16 +251,10 @@ 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>
+         class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
 typename AtomicHashArray<KeyT, ValueT,
-         HashFcn, EqualFcn, Allocator>::SmartPtr
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+         HashFcn, EqualFcn, Allocator, ProbeFcn>::SmartPtr
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
 create(size_t maxSize, const Config& c) {
   CHECK_LE(c.maxLoadFactor, 1.0);
   CHECK_GT(c.maxLoadFactor, 0.0);
@@ -292,8 +293,8 @@ create(size_t maxSize, const Config& c) {
 }
 
 template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
-void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+          class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
 destroy(AtomicHashArray* p) {
   assert(p);
 
@@ -311,8 +312,8 @@ 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>::
+          class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
 clear() {
   FOR_EACH_RANGE(i, 0, capacity_) {
     if (cells_[i].first != kEmptyKey_) {
@@ -331,9 +332,10 @@ clear() {
 // Iterator implementation
 
 template <class KeyT, class ValueT,
-          class HashFcn, class EqualFcn, class Allocator>
+          class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
 template <class ContT, class IterVal>
-struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::aha_iterator
+struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+    aha_iterator
     : boost::iterator_facade<aha_iterator<ContT,IterVal>,
                              IterVal,
                              boost::forward_traversal_tag>
@@ -397,5 +399,3 @@ struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::aha_iterator
 }; // aha_iterator
 
 } // namespace folly
-
-#undef FOLLY_SPIN_WAIT