Prefer template aliases to classes in IntrusiveList

[folly.git] / folly / AtomicHashArray.h

diff --git a/folly/AtomicHashArray.h b/folly/AtomicHashArray.h
index f00e3074ea06e18cfbdc94d766a21f64d47f5930..71ef2c76ab5fe87ffba5b5679c7d64c5dc064963 100644 (file)
--- a/folly/AtomicHashArray.h
+++ b/folly/AtomicHashArray.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2014 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.
@@ -42,16 +42,38 @@
 
 namespace folly {
 
+struct AtomicHashArrayLinearProbeFcn
+{
+  inline size_t operator()(size_t idx, size_t numProbes, size_t capacity) const{
+    idx += 1; // linear probing
+
+    // Avoid modulus because it's slow
+    return LIKELY(idx < capacity) ? idx : (idx - capacity);
+  }
+};
+
+struct AtomicHashArrayQuadraticProbeFcn
+{
+  inline size_t operator()(size_t idx, size_t numProbes, size_t capacity) const{
+    idx += numProbes; // quadratic probing
+
+    // Avoid modulus because it's slow
+    return LIKELY(idx < capacity) ? idx : (idx - capacity);
+  }
+};
+
 template <class KeyT, class ValueT,
           class HashFcn = std::hash<KeyT>,
           class EqualFcn = std::equal_to<KeyT>,
-          class Allocator = std::allocator<char>>
+          class Allocator = std::allocator<char>,
+          class ProbeFcn = AtomicHashArrayLinearProbeFcn>
 class AtomicHashMap;
 
 template <class KeyT, class ValueT,
           class HashFcn = std::hash<KeyT>,
           class EqualFcn = std::equal_to<KeyT>,
-          class Allocator = std::allocator<char>>
+          class Allocator = std::allocator<char>,
+          class ProbeFcn = AtomicHashArrayLinearProbeFcn>
 class AtomicHashArray : boost::noncopyable {
   static_assert((std::is_convertible<KeyT,int32_t>::value ||
                  std::is_convertible<KeyT,int64_t>::value ||
@@ -128,17 +150,19 @@ class AtomicHashArray : boost::noncopyable {
     int    entryCountThreadCacheSize;
     size_t capacity; // if positive, overrides maxLoadFactor
 
-    constexpr Config() : emptyKey((KeyT)-1),
-                         lockedKey((KeyT)-2),
-                         erasedKey((KeyT)-3),
-                         maxLoadFactor(0.8),
-                         growthFactor(-1),
-                         entryCountThreadCacheSize(1000),
-                         capacity(0) {}
+  public:
+    //  Cannot have constexpr ctor because some compilers rightly complain.
+    Config() : emptyKey((KeyT)-1),
+               lockedKey((KeyT)-2),
+               erasedKey((KeyT)-3),
+               maxLoadFactor(0.8),
+               growthFactor(-1),
+               entryCountThreadCacheSize(1000),
+               capacity(0) {}
   };
 
-  static const Config defaultConfig;
-  static SmartPtr create(size_t maxSize, const Config& = defaultConfig);
+  //  Cannot have pre-instantiated const Config instance because of SIOF.
+  static SmartPtr create(size_t maxSize, const Config& c = Config());
 
   iterator find(KeyT k) {
     return iterator(this, findInternal(k).idx);
@@ -159,11 +183,21 @@ class AtomicHashArray : boost::noncopyable {
    *   iterator is set to the existing entry.
    */
   std::pair<iterator,bool> insert(const value_type& r) {
-    SimpleRetT ret = insertInternal(r.first, r.second);
-    return std::make_pair(iterator(this, ret.idx), ret.success);
+    return emplace(r.first, r.second);
   }
   std::pair<iterator,bool> insert(value_type&& r) {
-    SimpleRetT ret = insertInternal(r.first, std::move(r.second));
+    return emplace(r.first, std::move(r.second));
+  }
+
+  /*
+   * 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(KeyT key_in, ArgTs&&... vCtorArgs) {
+    SimpleRetT ret = insertInternal(key_in, std::forward<ArgTs>(vCtorArgs)...);
     return std::make_pair(iterator(this, ret.idx), ret.success);
   }
 
@@ -228,15 +262,22 @@ class AtomicHashArray : boost::noncopyable {
   /* Private data and helper functions... */
 
  private:
-  friend class AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>;
+friend class AtomicHashMap<KeyT,
+                           ValueT,
+                           HashFcn,
+                           EqualFcn,
+                           Allocator,
+                           ProbeFcn>;
 
   struct SimpleRetT { size_t idx; bool success;
     SimpleRetT(size_t i, bool s) : idx(i), success(s) {}
-    SimpleRetT() {}
+    SimpleRetT() = default;
   };
 
-  template <class T>
-  SimpleRetT insertInternal(KeyT key, T&& value);
+
+
+  template <typename... ArgTs>
+  SimpleRetT insertInternal(KeyT key, ArgTs&&... vCtorArgs);
 
   SimpleRetT findInternal(const KeyT key);
 
@@ -265,8 +306,8 @@ class AtomicHashArray : boost::noncopyable {
   // 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
 
@@ -277,7 +318,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);
@@ -295,12 +336,7 @@ class AtomicHashArray : boost::noncopyable {
     return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
   }
 
-  inline size_t probeNext(size_t idx, size_t numProbes) {
-    //idx += numProbes; // quadratic probing
-    idx += 1; // linear probing
-    // Avoid modulus because it's slow
-    return LIKELY(idx < capacity_) ? idx : (idx - capacity_);
-  }
+
 }; // AtomicHashArray
 
 } // namespace folly