(Wangle) unorderedReduce

[folly.git] / folly / AtomicHashMap.h

diff --git a/folly/AtomicHashMap.h b/folly/AtomicHashMap.h
index 86d01ecfc3e91f42c1b24b5524af57aa3bc4dd52..f0b04a56366c2b1a3dbf3cf9f6a458fa494e6787 100644 (file)
--- a/folly/AtomicHashMap.h
+++ b/folly/AtomicHashMap.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.
@@ -85,17 +85,16 @@
 #include <boost/iterator/iterator_facade.hpp>
 #include <boost/noncopyable.hpp>
 #include <boost/type_traits/is_convertible.hpp>
-#include <glog/logging.h>
 
 #include <stdexcept>
 #include <functional>
 #include <atomic>
 
-#include "folly/AtomicHashArray.h"
-#include "folly/Foreach.h"
-#include "folly/Hash.h"
-#include "folly/Likely.h"
-#include "folly/ThreadCachedInt.h"
+#include <folly/AtomicHashArray.h>
+#include <folly/Foreach.h>
+#include <folly/Hash.h>
+#include <folly/Likely.h>
+#include <folly/ThreadCachedInt.h>
 
 namespace folly {
 
@@ -136,7 +135,9 @@ namespace folly {
  *   make_pair everywhere), and providing both can lead to some gross
  *   template error messages.
  *
- * - Not Allocator-aware.
+ * - The Allocator must not be stateful (a new instance will be spun up for
+ *   each allocation), and its allocate() method must take a raw number of
+ *   bytes.
  *
  * - KeyT must be a 32 bit or 64 bit atomic integer type, and you must
  *   define special 'locked' and 'empty' key values in the ctor
@@ -144,10 +145,6 @@ namespace folly {
  * - We don't take the Hash function object as an instance in the
  *   constructor.
  *
- * - We don't take a Compare template parameter (since our keys must
- *   be integers, and the underlying hash array here uses atomic
- *   compare-and-swap instructions, we only allow normal integer
- *   comparisons).
  */
 
 // Thrown when insertion fails due to running out of space for
@@ -158,16 +155,17 @@ struct AtomicHashMapFullError : std::runtime_error {
   {}
 };
 
-template<class KeyT, class ValueT, class HashFcn>
+template<class KeyT, class ValueT,
+         class HashFcn, class EqualFcn, class Allocator>
 class AtomicHashMap : boost::noncopyable {
-  typedef AtomicHashArray<KeyT, ValueT, HashFcn> SubMap;
+  typedef AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator> SubMap;
 
  public:
   typedef KeyT                key_type;
   typedef ValueT              mapped_type;
   typedef std::pair<const KeyT, ValueT> value_type;
   typedef HashFcn             hasher;
-  typedef std::equal_to<KeyT> key_equal;
+  typedef EqualFcn            key_equal;
   typedef value_type*         pointer;
   typedef value_type&         reference;
   typedef const value_type&   const_reference;
@@ -205,7 +203,7 @@ class AtomicHashMap : boost::noncopyable {
     }
   }
 
-  key_equal key_eq() const { return key_eq(); }
+  key_equal key_eq() const { return key_equal(); }
   hasher hash_function() const { return hasher(); }
 
   // TODO: emplace() support would be nice.
@@ -320,17 +318,21 @@ class AtomicHashMap : boost::noncopyable {
   }
 
   iterator begin() {
-    return iterator(this, 0,
+    iterator it(this, 0,
       subMaps_[0].load(std::memory_order_relaxed)->begin());
-  }
-
-  iterator end() {
-    return iterator();
+    it.checkAdvanceToNextSubmap();
+    return it;
   }
 
   const_iterator begin() const {
-    return const_iterator(this, 0,
+    const_iterator it(this, 0,
       subMaps_[0].load(std::memory_order_relaxed)->begin());
+    it.checkAdvanceToNextSubmap();
+    return it;
+  }
+
+  iterator end() {
+    return iterator();
   }
 
   const_iterator end() const {
@@ -395,7 +397,7 @@ class AtomicHashMap : boost::noncopyable {
 
   SimpleRetT findInternal(const KeyT k) const;
 
-  SimpleRetT findAtInternal(const uint32_t idx) const;
+  SimpleRetT findAtInternal(uint32_t idx) const;
 
   std::atomic<SubMap*> subMaps_[kNumSubMaps_];
   std::atomic<uint32_t> numMapsAllocated_;
@@ -412,6 +414,6 @@ class AtomicHashMap : boost::noncopyable {
 
 } // namespace folly
 
-#include "AtomicHashMap-inl.h"
+#include <folly/AtomicHashMap-inl.h>
 
 #endif // FOLLY_ATOMICHASHMAP_H_