X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FAtomicHashArray.h;h=3479572dc53488a1b8c0e1bfee105b18029eef23;hb=aa7aebf348c1b60d2ef2e81dd526aacd2f8d8769;hp=640605e49906265a7cf1d7ad82c9c0ededca38d6;hpb=27494a20393fa45072e7d526d358835f3abe312a;p=folly.git

diff --git a/folly/AtomicHashArray.h b/folly/AtomicHashArray.h
index 640605e4..3479572d 100644
--- a/folly/AtomicHashArray.h
+++ b/folly/AtomicHashArray.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2015 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -37,18 +37,25 @@
 #include <boost/iterator/iterator_facade.hpp>
 #include <boost/noncopyable.hpp>
 
-#include "folly/Hash.h"
-#include "folly/ThreadCachedInt.h"
+#include <folly/Hash.h>
+#include <folly/ThreadCachedInt.h>
 
 namespace folly {
 
-template <class KeyT, class ValueT, class HashFcn = std::hash<KeyT>>
+template <class KeyT, class ValueT,
+          class HashFcn = std::hash<KeyT>,
+          class EqualFcn = std::equal_to<KeyT>,
+          class Allocator = std::allocator<char>>
 class AtomicHashMap;
 
-template <class KeyT, class ValueT, class HashFcn = std::hash<KeyT>>
+template <class KeyT, class ValueT,
+          class HashFcn = std::hash<KeyT>,
+          class EqualFcn = std::equal_to<KeyT>,
+          class Allocator = std::allocator<char>>
 class AtomicHashArray : boost::noncopyable {
   static_assert((std::is_convertible<KeyT,int32_t>::value ||
-                 std::is_convertible<KeyT,int64_t>::value),
+                 std::is_convertible<KeyT,int64_t>::value ||
+                 std::is_convertible<KeyT,const void*>::value),
              "You are trying to use AtomicHashArray with disallowed key "
              "types.  You must use atomically compare-and-swappable integer "
              "keys, or a different container class.");
@@ -117,15 +124,23 @@ class AtomicHashArray : boost::noncopyable {
     KeyT   lockedKey;
     KeyT   erasedKey;
     double maxLoadFactor;
+    double growthFactor;
     int    entryCountThreadCacheSize;
     size_t capacity; // if positive, overrides maxLoadFactor
 
-    constexpr Config() : emptyKey(static_cast<KeyT>(-1ul)),
-                         lockedKey(static_cast<KeyT>(-2ul)),
-                         erasedKey(static_cast<KeyT>(-3ul)),
-                         maxLoadFactor(0.8),
-                         entryCountThreadCacheSize(1000),
-                         capacity(0) {}
+  private:
+    static const KeyT kEmptyKey;
+    static const KeyT kLockedKey;
+    static const KeyT kErasedKey;
+
+  public:
+    Config() : emptyKey(kEmptyKey),
+               lockedKey(kLockedKey),
+               erasedKey(kErasedKey),
+               maxLoadFactor(0.8),
+               growthFactor(-1),
+               entryCountThreadCacheSize(1000),
+               capacity(0) {}
   };
 
   static const Config defaultConfig;
@@ -150,7 +165,11 @@ class AtomicHashArray : boost::noncopyable {
    *   iterator is set to the existing entry.
    */
   std::pair<iterator,bool> insert(const value_type& r) {
-    SimpleRetT ret = insertInternal(r);
+    SimpleRetT ret = insertInternal(r.first, r.second);
+    return std::make_pair(iterator(this, ret.idx), ret.success);
+  }
+  std::pair<iterator,bool> insert(value_type&& r) {
+    SimpleRetT ret = insertInternal(r.first, std::move(r.second));
     return std::make_pair(iterator(this, ret.idx), ret.success);
   }
 
@@ -170,9 +189,18 @@ class AtomicHashArray : boost::noncopyable {
 
   bool empty() const { return size() == 0; }
 
-  iterator begin()             { return iterator(this, 0); }
+  iterator begin() {
+    iterator it(this, 0);
+    it.advancePastEmpty();
+    return it;
+  }
+  const_iterator begin() const {
+    const_iterator it(this, 0);
+    it.advancePastEmpty();
+    return it;
+  }
+
   iterator end()               { return iterator(this, capacity_); }
-  const_iterator begin() const { return const_iterator(this, 0); }
   const_iterator end() const   { return const_iterator(this, capacity_); }
 
   // See AtomicHashMap::findAt - access elements directly
@@ -206,14 +234,15 @@ class AtomicHashArray : boost::noncopyable {
   /* Private data and helper functions... */
 
  private:
-  friend class AtomicHashMap<KeyT,ValueT,HashFcn>;
+  friend class AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>;
 
   struct SimpleRetT { size_t idx; bool success;
     SimpleRetT(size_t i, bool s) : idx(i), success(s) {}
-    SimpleRetT() {}
+    SimpleRetT() = default;
   };
 
-  SimpleRetT insertInternal(const value_type& record);
+  template <class T>
+  SimpleRetT insertInternal(KeyT key, T&& value);
 
   SimpleRetT findInternal(const KeyT key);
 
@@ -232,14 +261,18 @@ class AtomicHashArray : boost::noncopyable {
     return cellKeyPtr(r)->load(std::memory_order_relaxed);
   }
 
+  static KeyT acquireLoadKey(const value_type& r) {
+    return cellKeyPtr(r)->load(std::memory_order_acquire);
+  }
+
   // Fun with thread local storage - atomic increment is expensive
   // (relatively), so we accumulate in the thread cache and periodically
   // flush to the actual variable, and walk through the unflushed counts when
   // reading the value, so be careful of calling size() too frequently.  This
   // increases insertion throughput several times over while keeping the count
   // accurate.
-  ThreadCachedInt<int64_t> numEntries_;  // Successful key inserts
-  ThreadCachedInt<int64_t> numPendingEntries_; // Used by insertInternal
+  ThreadCachedInt<uint64_t> numEntries_;  // Successful key inserts
+  ThreadCachedInt<uint64_t> numPendingEntries_; // Used by insertInternal
   std::atomic<int64_t> isFull_; // Used by insertInternal
   std::atomic<int64_t> numErases_;   // Successful key erases
 
@@ -250,7 +283,7 @@ class AtomicHashArray : boost::noncopyable {
   AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
                   KeyT erasedKey, double maxLoadFactor, size_t cacheSize);
 
-  ~AtomicHashArray() {}
+  ~AtomicHashArray() = default;
 
   inline void unlockCell(value_type* const cell, KeyT newKey) {
     cellKeyPtr(*cell)->store(newKey, std::memory_order_release);
@@ -259,7 +292,7 @@ class AtomicHashArray : boost::noncopyable {
   inline bool tryLockCell(value_type* const cell) {
     KeyT expect = kEmptyKey_;
     return cellKeyPtr(*cell)->compare_exchange_strong(expect, kLockedKey_,
-      std::memory_order_acquire);
+      std::memory_order_acq_rel);
   }
 
   inline size_t keyToAnchorIdx(const KeyT k) const {
@@ -268,7 +301,7 @@ class AtomicHashArray : boost::noncopyable {
     return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
   }
 
-  inline size_t probeNext(size_t idx, size_t numProbes) {
+  inline size_t probeNext(size_t idx, size_t /*numProbes*/) {
     //idx += numProbes; // quadratic probing
     idx += 1; // linear probing
     // Avoid modulus because it's slow
@@ -278,6 +311,6 @@ class AtomicHashArray : boost::noncopyable {
 
 } // namespace folly
 
-#include "AtomicHashArray-inl.h"
+#include <folly/AtomicHashArray-inl.h>
 
 #endif // FOLLY_ATOMICHASHARRAY_H_