/*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2014 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#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>
-const typename AtomicHashMap<KeyT, ValueT, HashFcn>::Config
-AtomicHashMap<KeyT, ValueT, HashFcn>::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>
-AtomicHashMap<KeyT, ValueT, HashFcn>::
+template <typename KeyT, typename ValueT,
+ typename HashFcn, typename EqualFcn, typename Allocator>
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
AtomicHashMap(size_t size, const Config& config)
- : kGrowthFrac_(1.0 - config.maxLoadFactor) {
+ : 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(),
std::memory_order_relaxed);
}
// insert --
-template <typename KeyT, typename ValueT, typename HashFcn>
-std::pair<typename AtomicHashMap<KeyT,ValueT,HashFcn>::iterator,bool>
-AtomicHashMap<KeyT, ValueT, HashFcn>::
-insert(const value_type& r) {
- SimpleRetT ret = insertInternal(r);
+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);
+ return std::make_pair(iterator(this, ret.i, subMap->makeIter(ret.j)),
+ ret.success);
+}
+
+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);
return std::make_pair(iterator(this, ret.i, subMap->makeIter(ret.j)),
ret.success);
}
// insertInternal -- Allocates new sub maps as existing ones fill up.
-template <typename KeyT, typename ValueT, typename HashFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn>::
-insertInternal(const value_type& r) {
+template <typename KeyT, typename ValueT,
+ typename HashFcn, typename EqualFcn, typename Allocator>
+template <class T>
+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
numMapsAllocated_.load(std::memory_order_acquire);
- uint32_t idx = 0;
typename SubMap::SimpleRetT ret;
FOR_EACH_RANGE(i, 0, nextMapIdx) {
// insert in each map successively. If one succeeds, we're done!
SubMap* subMap = subMaps_[i].load(std::memory_order_relaxed);
- ret = subMap->insertInternal(r);
+ ret = subMap->insertInternal(key, std::forward<T>(value));
if (ret.idx == subMap->capacity_) {
continue; //map is full, so try the next one
}
// just did a spin wait with an acquire load on numMapsAllocated_.
SubMap* loadedMap = subMaps_[nextMapIdx].load(std::memory_order_relaxed);
DCHECK(loadedMap && loadedMap != (SubMap*)kLockedPtr_);
- ret = loadedMap->insertInternal(r);
+ ret = loadedMap->insertInternal(key, std::forward<T>(value));
if (ret.idx != loadedMap->capacity_) {
return SimpleRetT(nextMapIdx, ret.idx, ret.success);
}
}
// find --
-template <typename KeyT, typename ValueT, typename HashFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn>::iterator
-AtomicHashMap<KeyT, ValueT, HashFcn>::
+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 AtomicHashMap<KeyT, ValueT, HashFcn>::const_iterator
-AtomicHashMap<KeyT, ValueT, HashFcn>::
+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 AtomicHashMap<KeyT, ValueT, HashFcn>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn>::
+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);
}
// findAtInternal -- see encodeIndex() for details.
-template <typename KeyT, typename ValueT, typename HashFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn>::
+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_) {
}
// erase --
-template <typename KeyT, typename ValueT, typename HashFcn>
-typename AtomicHashMap<KeyT, ValueT, HashFcn>::size_type
-AtomicHashMap<KeyT, ValueT, HashFcn>::
+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) {
}
// capacity -- summation of capacities of all submaps
-template <typename KeyT, typename ValueT, typename HashFcn>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn>::
+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);
// spaceRemaining --
// number of new insertions until current submaps are all at max load
-template <typename KeyT, typename ValueT, typename HashFcn>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn>::
+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);
// clear -- Wipes all keys and values from primary map and destroys
// all secondary maps. Not thread safe.
-template <typename KeyT, typename ValueT, typename HashFcn>
-void AtomicHashMap<KeyT, ValueT, HashFcn>::
+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_
}
// size --
-template <typename KeyT, typename ValueT, typename HashFcn>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn>::
+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);
// 31 1
// 27-30 which subMap
// 0-26 subMap offset (index_ret input)
-template <typename KeyT, typename ValueT, typename HashFcn>
-inline uint32_t AtomicHashMap<KeyT, ValueT, HashFcn>::
+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;
// Iterator implementation
-template <typename KeyT, typename ValueT, typename HashFcn>
+template <typename KeyT, typename ValueT,
+ typename HashFcn, typename EqualFcn, typename Allocator>
template<class ContT, class IterVal, class SubIt>
-struct AtomicHashMap<KeyT, ValueT, HashFcn>::ahm_iterator
+struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::ahm_iterator
: boost::iterator_facade<ahm_iterator<ContT,IterVal,SubIt>,
IterVal,
boost::forward_traversal_tag>