add config to allow using quadratic probing

[folly.git] / folly / AtomicHashMap.h

diff --git a/folly/AtomicHashMap.h b/folly/AtomicHashMap.h
index fb35388732e85740377aa47102bfe17929fb8d4b..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;
@@ -205,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 --
    *
@@ -223,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 --
@@ -391,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;
 
@@ -411,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>