add config to allow using quadratic probing

[folly.git] / folly / AtomicHashMap.h

diff --git a/folly/AtomicHashMap.h b/folly/AtomicHashMap.h
index 52d2fb0d86f1ab9da1e0a13c89edae9b2021aaa1..c6f06bd8f27016d0dcf5e371e94ece91af2508cd 100644 (file)
--- a/folly/AtomicHashMap.h
+++ b/folly/AtomicHashMap.h
@@ -156,9 +156,10 @@ struct AtomicHashMapFullError : std::runtime_error {
 };
 
 template<class KeyT, class ValueT,
-         class HashFcn, class EqualFcn, class Allocator>
+         class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
 class AtomicHashMap : boost::noncopyable {
-  typedef AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator> SubMap;
+typedef AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>
+    SubMap;
 
  public:
   typedef KeyT                key_type;
@@ -191,8 +192,7 @@ class AtomicHashMap : boost::noncopyable {
   // The constructor takes a finalSizeEst which is the optimal
   // number of elements to maximize space utilization and performance,
   // and a Config object to specify more advanced options.
-  static const Config defaultConfig;
-  explicit AtomicHashMap(size_t finalSizeEst, const Config& = defaultConfig);
+  explicit AtomicHashMap(size_t finalSizeEst, const Config& c = Config());
 
   ~AtomicHashMap() {
     const int numMaps = numMapsAllocated_.load(std::memory_order_relaxed);
@@ -206,8 +206,6 @@ class AtomicHashMap : boost::noncopyable {
   key_equal key_eq() const { return key_equal(); }
   hasher hash_function() const { return hasher(); }
 
-  // TODO: emplace() support would be nice.
-
   /*
    * insert --
    *
@@ -224,13 +222,26 @@ class AtomicHashMap : boost::noncopyable {
    *   AtomicHashMapFullError is thrown.
    */
   std::pair<iterator,bool> insert(const value_type& r) {
-    return insert(r.first, r.second);
+    return emplace(r.first, r.second);
+  }
+  std::pair<iterator,bool> insert(key_type k, const mapped_type& v) {
+    return emplace(k, v);
   }
-  std::pair<iterator,bool> insert(key_type k, const mapped_type& v);
   std::pair<iterator,bool> insert(value_type&& r) {
-    return insert(r.first, std::move(r.second));
+    return emplace(r.first, std::move(r.second));
   }
-  std::pair<iterator,bool> insert(key_type k, mapped_type&& v);
+  std::pair<iterator,bool> insert(key_type k, mapped_type&& v) {
+    return emplace(k, std::move(v));
+  }
+
+  /*
+   * emplace --
+   *
+   *   Same contract as insert(), but performs in-place construction
+   *   of the value type using the specified arguments.
+   */
+  template <typename... ArgTs>
+  std::pair<iterator,bool> emplace(key_type k, ArgTs&&... vCtorArg);
 
   /*
    * find --
@@ -392,8 +403,8 @@ class AtomicHashMap : boost::noncopyable {
     SimpleRetT() = default;
   };
 
-  template <class T>
-  SimpleRetT insertInternal(KeyT key, T&& value);
+  template <typename... ArgTs>
+  SimpleRetT insertInternal(KeyT key, ArgTs&&... value);
 
   SimpleRetT findInternal(const KeyT k) const;
 
@@ -412,6 +423,18 @@ class AtomicHashMap : boost::noncopyable {
 
 }; // AtomicHashMap
 
+template <class KeyT,
+          class ValueT,
+          class HashFcn = std::hash<KeyT>,
+          class EqualFcn = std::equal_to<KeyT>,
+          class Allocator = std::allocator<char>>
+using QuadraticProbingAtomicHashMap =
+    AtomicHashMap<KeyT,
+                  ValueT,
+                  HashFcn,
+                  EqualFcn,
+                  Allocator,
+                  AtomicHashArrayQuadraticProbeFcn>;
 } // namespace folly
 
 #include <folly/AtomicHashMap-inl.h>