/*
- * 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 AtomicHashArray.h"
#endif
-#include "folly/Bits.h"
-#include "folly/detail/AtomicHashUtils.h"
+#include <folly/Bits.h>
+#include <folly/detail/AtomicHashUtils.h>
namespace folly {
// AtomicHashArray private constructor --
-template <class KeyT, class ValueT, class HashFcn>
-AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+ class HashFcn, class EqualFcn, class Allocator>
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
KeyT erasedKey, double maxLoadFactor, size_t cacheSize)
: capacity_(capacity), maxEntries_(size_t(maxLoadFactor * capacity_ + 0.5)),
* of key and returns true, or if key does not exist returns false and
* ret.index is set to capacity_.
*/
-template <class KeyT, class ValueT, class HashFcn>
-typename AtomicHashArray<KeyT, ValueT, HashFcn>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+ class HashFcn, class EqualFcn, class Allocator>
+typename AtomicHashArray<KeyT, ValueT,
+ HashFcn, EqualFcn, Allocator>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
findInternal(const KeyT key_in) {
DCHECK_NE(key_in, kEmptyKey_);
DCHECK_NE(key_in, kLockedKey_);
for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
;
idx = probeNext(idx, numProbes)) {
- const KeyT key = relaxedLoadKey(cells_[idx]);
- if (LIKELY(key == key_in)) {
+ const KeyT key = acquireLoadKey(cells_[idx]);
+ if (LIKELY(EqualFcn()(key, key_in))) {
return SimpleRetT(idx, true);
}
if (UNLIKELY(key == kEmptyKey_)) {
* this will be the previously inserted value, and if the map is full it is
* default.
*/
-template <class KeyT, class ValueT, class HashFcn>
-typename AtomicHashArray<KeyT, ValueT, HashFcn>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn>::
-insertInternal(const value_type& record) {
+template <class KeyT, class ValueT,
+ class HashFcn, class EqualFcn, class Allocator>
+template <class T>
+typename AtomicHashArray<KeyT, ValueT,
+ HashFcn, EqualFcn, Allocator>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+insertInternal(KeyT key_in, T&& value) {
const short NO_NEW_INSERTS = 1;
const short NO_PENDING_INSERTS = 2;
- const KeyT key_in = record.first;
CHECK_NE(key_in, kEmptyKey_);
CHECK_NE(key_in, kLockedKey_);
CHECK_NE(key_in, kErasedKey_);
- for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
- ;
- idx = probeNext(idx, numProbes)) {
+
+ size_t idx = keyToAnchorIdx(key_in);
+ size_t numProbes = 0;
+ for (;;) {
DCHECK_LT(idx, capacity_);
value_type* cell = &cells_[idx];
if (relaxedLoadKey(*cell) == kEmptyKey_) {
* constructed a lhs to use an assignment operator on when
* values are being set.
*/
- new (&cell->second) ValueT(record.second);
+ new (&cell->second) ValueT(std::forward<T>(value));
unlockCell(cell, key_in); // Sets the new key
} catch (...) {
+ // Transition back to empty key---requires handling
+ // locked->empty below.
unlockCell(cell, kEmptyKey_);
--numPendingEntries_;
throw;
}
+ // Direct comparison rather than EqualFcn ok here
+ // (we just inserted it)
DCHECK(relaxedLoadKey(*cell) == key_in);
--numPendingEntries_;
++numEntries_; // This is a thread cached atomic increment :)
}
}
DCHECK(relaxedLoadKey(*cell) != kEmptyKey_);
- if (kLockedKey_ == cellKeyPtr(*cell)->load(std::memory_order_acquire)) {
+ if (kLockedKey_ == acquireLoadKey(*cell)) {
FOLLY_SPIN_WAIT(
- kLockedKey_ == cellKeyPtr(*cell)->load(std::memory_order_acquire)
+ kLockedKey_ == acquireLoadKey(*cell)
);
}
- DCHECK(relaxedLoadKey(*cell) != kEmptyKey_);
- DCHECK(relaxedLoadKey(*cell) != kLockedKey_);
- if (key_in == relaxedLoadKey(*cell)) {
+
+ const KeyT thisKey = acquireLoadKey(*cell);
+ if (EqualFcn()(thisKey, key_in)) {
// Found an existing entry for our key, but we don't overwrite the
// previous value.
return SimpleRetT(idx, false);
+ } else if (thisKey == kEmptyKey_ || thisKey == kLockedKey_) {
+ // We need to try again (i.e., don't increment numProbes or
+ // advance idx): this case can happen if the constructor for
+ // ValueT threw for this very cell (the rethrow block above).
+ continue;
}
+
++numProbes;
if (UNLIKELY(numProbes >= capacity_)) {
// probed every cell...fail
return SimpleRetT(capacity_, false);
}
+
+ idx = probeNext(idx, numProbes);
}
}
* erased key will never be reused. If there's an associated value, we won't
* touch it either.
*/
-template <class KeyT, class ValueT, class HashFcn>
-size_t AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+ class HashFcn, class EqualFcn, class Allocator>
+size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
erase(KeyT key_in) {
CHECK_NE(key_in, kEmptyKey_);
CHECK_NE(key_in, kLockedKey_);
idx = probeNext(idx, numProbes)) {
DCHECK_LT(idx, capacity_);
value_type* cell = &cells_[idx];
- if (relaxedLoadKey(*cell) == kEmptyKey_ ||
- relaxedLoadKey(*cell) == kLockedKey_) {
+ KeyT currentKey = acquireLoadKey(*cell);
+ if (currentKey == kEmptyKey_ || currentKey == kLockedKey_) {
// If we hit an empty (or locked) element, this key does not exist. This
// is similar to how it's handled in find().
return 0;
}
- if (key_in == relaxedLoadKey(*cell)) {
+ if (EqualFcn()(currentKey, key_in)) {
// Found an existing entry for our key, attempt to mark it erased.
// Some other thread may have erased our key, but this is ok.
- KeyT expect = key_in;
+ KeyT expect = currentKey;
if (cellKeyPtr(*cell)->compare_exchange_strong(expect, kErasedKey_)) {
numErases_.fetch_add(1, std::memory_order_relaxed);
}
}
-template <class KeyT, class ValueT, class HashFcn>
-const typename AtomicHashArray<KeyT, ValueT, HashFcn>::Config
-AtomicHashArray<KeyT, ValueT, HashFcn>::defaultConfig;
-
-template <class KeyT, class ValueT, class HashFcn>
-typename AtomicHashArray<KeyT, ValueT, HashFcn>::SmartPtr
-AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+ class HashFcn, class EqualFcn, class Allocator>
+const typename AtomicHashArray<KeyT, ValueT,
+ HashFcn, EqualFcn, Allocator>::Config
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::defaultConfig;
+
+template <class KeyT, class ValueT,
+ class HashFcn, class EqualFcn, class Allocator>
+typename AtomicHashArray<KeyT, ValueT,
+ HashFcn, EqualFcn, Allocator>::SmartPtr
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
create(size_t maxSize, const Config& c) {
CHECK_LE(c.maxLoadFactor, 1.0);
CHECK_GT(c.maxLoadFactor, 0.0);
size_t capacity = size_t(maxSize / c.maxLoadFactor);
size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * capacity;
- std::unique_ptr<void, void(*)(void*)> mem(malloc(sz), free);
- new(mem.get()) AtomicHashArray(capacity, c.emptyKey, c.lockedKey, c.erasedKey,
- c.maxLoadFactor, c.entryCountThreadCacheSize);
- SmartPtr map(static_cast<AtomicHashArray*>(mem.release()));
+ auto const mem = Allocator().allocate(sz);
+ try {
+ new (mem) AtomicHashArray(capacity, c.emptyKey, c.lockedKey, c.erasedKey,
+ c.maxLoadFactor, c.entryCountThreadCacheSize);
+ } catch (...) {
+ Allocator().deallocate(mem, sz);
+ throw;
+ }
+
+ SmartPtr map(static_cast<AtomicHashArray*>((void *)mem));
/*
* Mark all cells as empty.
* constructor.) This is in order to avoid needing to default
* construct a bunch of value_type when we first start up: if you
* have an expensive default constructor for the value type this can
- * noticably speed construction time for an AHA.
+ * noticeably speed construction time for an AHA.
*/
FOR_EACH_RANGE(i, 0, map->capacity_) {
cellKeyPtr(map->cells_[i])->store(map->kEmptyKey_,
return map;
}
-template <class KeyT, class ValueT, class HashFcn>
-void AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+ class HashFcn, class EqualFcn, class Allocator>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
destroy(AtomicHashArray* p) {
assert(p);
+
+ size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * p->capacity_;
+
FOR_EACH_RANGE(i, 0, p->capacity_) {
if (p->cells_[i].first != p->kEmptyKey_) {
p->cells_[i].~value_type();
}
}
p->~AtomicHashArray();
- free(p);
+
+ Allocator().deallocate((char *)p, sz);
}
// clear -- clears all keys and values in the map and resets all counters
-template <class KeyT, class ValueT, class HashFcn>
-void AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+ class HashFcn, class EqualFcn, class Allocator>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
clear() {
FOR_EACH_RANGE(i, 0, capacity_) {
if (cells_[i].first != kEmptyKey_) {
// Iterator implementation
-template <class KeyT, class ValueT, class HashFcn>
+template <class KeyT, class ValueT,
+ class HashFcn, class EqualFcn, class Allocator>
template <class ContT, class IterVal>
-struct AtomicHashArray<KeyT, ValueT, HashFcn>::aha_iterator
+struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::aha_iterator
: boost::iterator_facade<aha_iterator<ContT,IterVal>,
IterVal,
boost::forward_traversal_tag>
}
bool isValid() const {
- KeyT key = relaxedLoadKey(aha_->cells_[offset_]);
+ KeyT key = acquireLoadKey(aha_->cells_[offset_]);
return key != aha_->kEmptyKey_ &&
key != aha_->kLockedKey_ &&
key != aha_->kErasedKey_;
projects / folly.git / blobdiff