projects / folly.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
folly: fix another test running under buck
[folly.git] / folly / AtomicHashMap-inl.h
diff --git a/folly/AtomicHashMap-inl.h b/folly/AtomicHashMap-inl.h
index 1548b7f06415c9a51254e45d651f64635232e875..4752cdd3aec69c345e36f12b8553e422ba421a30 100644 (file)
--- a/folly/AtomicHashMap-inl.h
+++ b/folly/AtomicHashMap-inl.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2013 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.
@@ -18,35 +18,39 @@
 #error "This should only be included by AtomicHashMap.h"
 #endif
 
-#include "folly/detail/AtomicHashUtils.h"
+#include <folly/detail/AtomicHashUtils.h>
 
 namespace folly {
 
-template <class KeyT, class ValueT, class HashFcn, class EqualFcn>
-const typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::Config
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::defaultConfig;
+template <class KeyT, class ValueT,
+          class HashFcn, class EqualFcn, class Allocator>
+const typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::Config
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::defaultConfig;
 
 // AtomicHashMap constructor -- Atomic wrapper that allows growth
 // This class has a lot of overhead (184 Bytes) so only use for big maps
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
-AtomicHashMap(size_t size, const Config& config)
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+AtomicHashMap(size_t finalSizeEst, const Config& config)
   : kGrowthFrac_(config.growthFactor < 0 ?
                  1.0 - config.maxLoadFactor : config.growthFactor) {
   CHECK(config.maxLoadFactor > 0.0 && config.maxLoadFactor < 1.0);
-  subMaps_[0].store(SubMap::create(size, config).release(),
+  subMaps_[0].store(SubMap::create(finalSizeEst, config).release(),
     std::memory_order_relaxed);
-  auto numSubMaps = kNumSubMaps_;
-  FOR_EACH_RANGE(i, 1, numSubMaps) {
+  auto subMapCount = kNumSubMaps_;
+  FOR_EACH_RANGE(i, 1, subMapCount) {
     subMaps_[i].store(nullptr, std::memory_order_relaxed);
   }
   numMapsAllocated_.store(1, std::memory_order_relaxed);
 }
 
 // insert --
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-std::pair<typename AtomicHashMap<KeyT,ValueT,HashFcn,EqualFcn>::iterator,bool>
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+std::pair<typename AtomicHashMap<KeyT, ValueT, HashFcn,
+                                 EqualFcn, Allocator>::iterator, bool>
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 insert(key_type k, const mapped_type& v) {
   SimpleRetT ret = insertInternal(k,v);
   SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
@@ -54,9 +58,11 @@ insert(key_type k, const mapped_type& v) {
                         ret.success);
 }
 
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-std::pair<typename AtomicHashMap<KeyT,ValueT,HashFcn,EqualFcn>::iterator,bool>
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+std::pair<typename AtomicHashMap<KeyT, ValueT, HashFcn,
+                                 EqualFcn, Allocator>::iterator, bool>
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 insert(key_type k, mapped_type&& v) {
   SimpleRetT ret = insertInternal(k, std::move(v));
   SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
@@ -65,13 +71,14 @@ insert(key_type k, mapped_type&& v) {
 }
 
 // insertInternal -- Allocates new sub maps as existing ones fill up.
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
 template <class T>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 insertInternal(key_type key, T&& value) {
  beginInsertInternal:
-  int nextMapIdx = // this maintains our state
+  auto nextMapIdx = // this maintains our state
     numMapsAllocated_.load(std::memory_order_acquire);
   typename SubMap::SimpleRetT ret;
   FOR_EACH_RANGE(i, 0, nextMapIdx) {
@@ -142,29 +149,33 @@ insertInternal(key_type key, T&& value) {
 }
 
 // find --
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::iterator
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::iterator
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 find(KeyT k) {
   SimpleRetT ret = findInternal(k);
-  if (ret.i >= numMapsAllocated_.load(std::memory_order_acquire)) {
+  if (!ret.success) {
     return end();
   }
   SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
   return iterator(this, ret.i, subMap->makeIter(ret.j));
 }
 
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::const_iterator
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+typename AtomicHashMap<KeyT, ValueT,
+         HashFcn, EqualFcn, Allocator>::const_iterator
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 find(KeyT k) const {
   return const_cast<AtomicHashMap*>(this)->find(k);
 }
 
 // findInternal --
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 findInternal(const KeyT k) const {
   SubMap* const primaryMap = subMaps_[0].load(std::memory_order_relaxed);
   typename SubMap::SimpleRetT ret = primaryMap->findInternal(k);
@@ -185,9 +196,10 @@ findInternal(const KeyT k) const {
 }
 
 // findAtInternal -- see encodeIndex() for details.
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 findAtInternal(uint32_t idx) const {
   uint32_t subMapIdx, subMapOffset;
   if (idx & kSecondaryMapBit_) {
@@ -205,9 +217,10 @@ findAtInternal(uint32_t idx) const {
 }
 
 // erase --
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::size_type
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::size_type
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 erase(const KeyT k) {
   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
   FOR_EACH_RANGE(i, 0, numMaps) {
@@ -221,8 +234,9 @@ erase(const KeyT k) {
 }
 
 // capacity -- summation of capacities of all submaps
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 capacity() const {
   size_t totalCap(0);
   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
@@ -234,8 +248,9 @@ capacity() const {
 
 // spaceRemaining --
 // number of new insertions until current submaps are all at max load
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 spaceRemaining() const {
   size_t spaceRem(0);
   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
@@ -251,8 +266,9 @@ spaceRemaining() const {
 
 // clear -- Wipes all keys and values from primary map and destroys
 // all secondary maps.  Not thread safe.
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-void AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+void AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 clear() {
   subMaps_[0].load(std::memory_order_relaxed)->clear();
   int const numMaps = numMapsAllocated_
@@ -267,8 +283,9 @@ clear() {
 }
 
 // size --
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 size() const {
   size_t totalSize(0);
   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
@@ -296,8 +313,9 @@ size() const {
 //         31              1
 //      27-30   which subMap
 //       0-26  subMap offset (index_ret input)
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
-inline uint32_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
+inline uint32_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 encodeIndex(uint32_t subMap, uint32_t offset) {
   DCHECK_EQ(offset & kSecondaryMapBit_, 0);  // offset can't be too big
   if (subMap == 0) return offset;
@@ -313,9 +331,10 @@ encodeIndex(uint32_t subMap, uint32_t offset) {
 
 // Iterator implementation
 
-template <typename KeyT, typename ValueT, typename HashFcn, typename EqualFcn>
+template <typename KeyT, typename ValueT,
+          typename HashFcn, typename EqualFcn, typename Allocator>
 template<class ContT, class IterVal, class SubIt>
-struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::ahm_iterator
+struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::ahm_iterator
     : boost::iterator_facade<ahm_iterator<ContT,IterVal,SubIt>,
                              IterVal,
                              boost::forward_traversal_tag>
@@ -351,9 +370,7 @@ struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::ahm_iterator
       : ahm_(ahm)
       , subMap_(subMap)
       , subIt_(subIt)
-  {
-    checkAdvanceToNextSubmap();
-  }
+  {}
 
   friend class boost::iterator_core_access;
 
@@ -389,7 +406,7 @@ struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::ahm_iterator
 
     SubMap* thisMap = ahm_->subMaps_[subMap_].
       load(std::memory_order_relaxed);
-    if (subIt_ == thisMap->end()) {
+    while (subIt_ == thisMap->end()) {
       // This sub iterator is done, advance to next one
       if (subMap_ + 1 <
           ahm_->numMapsAllocated_.load(std::memory_order_acquire)) {
@@ -398,6 +415,7 @@ struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn>::ahm_iterator
         subIt_ = thisMap->begin();
       } else {
         ahm_ = nullptr;
+        return;
       }
     }
   }
Unnamed repository; edit this file 'description' to name the repository.