/*
- * 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.
#include <boost/iterator/iterator_facade.hpp>
#include <boost/noncopyable.hpp>
-#include "folly/Hash.h"
-#include "folly/ThreadCachedInt.h"
+#include <folly/Hash.h>
+#include <folly/ThreadCachedInt.h>
namespace folly {
-template <class KeyT, class ValueT, class HashFcn = std::hash<KeyT>>
+template <class KeyT, class ValueT,
+ class HashFcn = std::hash<KeyT>,
+ class EqualFcn = std::equal_to<KeyT>,
+ class Allocator = std::allocator<char>>
class AtomicHashMap;
-template <class KeyT, class ValueT, class HashFcn = std::hash<KeyT>>
+template <class KeyT, class ValueT,
+ class HashFcn = std::hash<KeyT>,
+ class EqualFcn = std::equal_to<KeyT>,
+ class Allocator = std::allocator<char>>
class AtomicHashArray : boost::noncopyable {
static_assert((std::is_convertible<KeyT,int32_t>::value ||
- std::is_convertible<KeyT,int64_t>::value),
+ std::is_convertible<KeyT,int64_t>::value ||
+ std::is_convertible<KeyT,const void*>::value),
"You are trying to use AtomicHashArray with disallowed key "
"types. You must use atomically compare-and-swappable integer "
"keys, or a different container class.");
KeyT lockedKey;
KeyT erasedKey;
double maxLoadFactor;
+ double growthFactor;
int entryCountThreadCacheSize;
size_t capacity; // if positive, overrides maxLoadFactor
- constexpr Config() : emptyKey(static_cast<KeyT>(-1ul)),
- lockedKey(static_cast<KeyT>(-2ul)),
- erasedKey(static_cast<KeyT>(-3ul)),
- maxLoadFactor(0.8),
- entryCountThreadCacheSize(1000),
- capacity(0) {}
+ private:
+ static const KeyT kEmptyKey;
+ static const KeyT kLockedKey;
+ static const KeyT kErasedKey;
+
+ public:
+ Config() : emptyKey(kEmptyKey),
+ lockedKey(kLockedKey),
+ erasedKey(kErasedKey),
+ maxLoadFactor(0.8),
+ growthFactor(-1),
+ entryCountThreadCacheSize(1000),
+ capacity(0) {}
};
static const Config defaultConfig;
* iterator is set to the existing entry.
*/
std::pair<iterator,bool> insert(const value_type& r) {
- SimpleRetT ret = insertInternal(r);
+ SimpleRetT ret = insertInternal(r.first, r.second);
+ return std::make_pair(iterator(this, ret.idx), ret.success);
+ }
+ std::pair<iterator,bool> insert(value_type&& r) {
+ SimpleRetT ret = insertInternal(r.first, std::move(r.second));
return std::make_pair(iterator(this, ret.idx), ret.success);
}
bool empty() const { return size() == 0; }
- iterator begin() { return iterator(this, 0); }
+ iterator begin() {
+ iterator it(this, 0);
+ it.advancePastEmpty();
+ return it;
+ }
+ const_iterator begin() const {
+ const_iterator it(this, 0);
+ it.advancePastEmpty();
+ return it;
+ }
+
iterator end() { return iterator(this, capacity_); }
- const_iterator begin() const { return const_iterator(this, 0); }
const_iterator end() const { return const_iterator(this, capacity_); }
// See AtomicHashMap::findAt - access elements directly
/* Private data and helper functions... */
private:
- friend class AtomicHashMap<KeyT,ValueT,HashFcn>;
+ friend class AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>;
struct SimpleRetT { size_t idx; bool success;
SimpleRetT(size_t i, bool s) : idx(i), success(s) {}
- SimpleRetT() {}
+ SimpleRetT() = default;
};
- SimpleRetT insertInternal(const value_type& record);
+ template <class T>
+ SimpleRetT insertInternal(KeyT key, T&& value);
SimpleRetT findInternal(const KeyT key);
return cellKeyPtr(r)->load(std::memory_order_relaxed);
}
+ static KeyT acquireLoadKey(const value_type& r) {
+ return cellKeyPtr(r)->load(std::memory_order_acquire);
+ }
+
// Fun with thread local storage - atomic increment is expensive
// (relatively), so we accumulate in the thread cache and periodically
// flush to the actual variable, and walk through the unflushed counts when
// 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
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);
inline bool tryLockCell(value_type* const cell) {
KeyT expect = kEmptyKey_;
return cellKeyPtr(*cell)->compare_exchange_strong(expect, kLockedKey_,
- std::memory_order_acquire);
+ std::memory_order_acq_rel);
}
inline size_t keyToAnchorIdx(const KeyT k) const {
return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
}
- inline size_t probeNext(size_t idx, size_t numProbes) {
+ inline size_t probeNext(size_t idx, size_t /*numProbes*/) {
//idx += numProbes; // quadratic probing
idx += 1; // linear probing
// Avoid modulus because it's slow
} // namespace folly
-#include "AtomicHashArray-inl.h"
+#include <folly/AtomicHashArray-inl.h>
#endif // FOLLY_ATOMICHASHARRAY_H_
projects / folly.git / blobdiff