/*
- * 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.
};
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;
// The constructor takes a finalSizeEst which is the optimal
// number of elements to maximize space utilization and performance,
// and a Config object to specify more advanced options.
- static const Config defaultConfig;
- explicit AtomicHashMap(size_t finalSizeEst, const Config& = defaultConfig);
+ explicit AtomicHashMap(size_t finalSizeEst, const Config& c = Config());
~AtomicHashMap() {
const int numMaps = numMapsAllocated_.load(std::memory_order_relaxed);
key_equal key_eq() const { return key_equal(); }
hasher hash_function() const { return hasher(); }
- // TODO: emplace() support would be nice.
-
/*
* insert --
*
* 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 --
}
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 {
static const uint32_t kSubMapIndexShift_ = 32 - kNumSubMapBits_ - 1;
static const uint32_t kSubMapIndexMask_ = (1 << kSubMapIndexShift_) - 1;
static const uint32_t kNumSubMaps_ = 1 << kNumSubMapBits_;
- static const uintptr_t kLockedPtr_ = 0x88ul << 48; // invalid pointer
+ static const uintptr_t kLockedPtr_ = 0x88ULL << 48; // invalid pointer
struct SimpleRetT { uint32_t i; size_t j; bool success;
SimpleRetT(uint32_t ii, size_t jj, bool s) : i(ii), j(jj), success(s) {}
- SimpleRetT() {}
+ 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;
}; // 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>