2 * Copyright 2012 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #ifndef FOLLY_ATOMICHASHARRAY_H_
18 #error "This should only be included by AtomicHashArray.h"
21 #include "folly/Bits.h"
22 #include "folly/detail/AtomicHashUtils.h"
26 // AtomicHashArray private constructor --
27 template <class KeyT, class ValueT, class HashFcn>
28 AtomicHashArray<KeyT, ValueT, HashFcn>::
29 AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
30 KeyT erasedKey, double maxLoadFactor, size_t cacheSize)
31 : capacity_(capacity), maxEntries_(size_t(maxLoadFactor * capacity_ + 0.5)),
32 kEmptyKey_(emptyKey), kLockedKey_(lockedKey), kErasedKey_(erasedKey),
33 kAnchorMask_(nextPowTwo(capacity_) - 1), numEntries_(0, cacheSize),
34 numPendingEntries_(0, cacheSize), isFull_(0), numErases_(0) {
40 * Sets ret.second to value found and ret.index to index
41 * of key and returns true, or if key does not exist returns false and
42 * ret.index is set to capacity_.
44 template <class KeyT, class ValueT, class HashFcn>
45 typename AtomicHashArray<KeyT, ValueT, HashFcn>::SimpleRetT
46 AtomicHashArray<KeyT, ValueT, HashFcn>::
47 findInternal(const KeyT key_in) {
48 DCHECK_NE(key_in, kEmptyKey_);
49 DCHECK_NE(key_in, kLockedKey_);
50 DCHECK_NE(key_in, kErasedKey_);
51 for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
53 idx = probeNext(idx, numProbes)) {
54 const KeyT key = relaxedLoadKey(cells_[idx]);
55 if (LIKELY(key == key_in)) {
56 return SimpleRetT(idx, true);
58 if (UNLIKELY(key == kEmptyKey_)) {
59 // if we hit an empty element, this key does not exist
60 return SimpleRetT(capacity_, false);
63 if (UNLIKELY(numProbes >= capacity_)) {
64 // probed every cell...fail
65 return SimpleRetT(capacity_, false);
73 * Returns false on failure due to key collision or full.
74 * Also sets ret.index to the index of the key. If the map is full, sets
75 * ret.index = capacity_. Also sets ret.second to cell value, thus if insert
76 * successful this will be what we just inserted, if there is a key collision
77 * this will be the previously inserted value, and if the map is full it is
80 template <class KeyT, class ValueT, class HashFcn>
81 typename AtomicHashArray<KeyT, ValueT, HashFcn>::SimpleRetT
82 AtomicHashArray<KeyT, ValueT, HashFcn>::
83 insertInternal(const value_type& record) {
84 const short NO_NEW_INSERTS = 1;
85 const short NO_PENDING_INSERTS = 2;
86 const KeyT key_in = record.first;
87 CHECK_NE(key_in, kEmptyKey_);
88 CHECK_NE(key_in, kLockedKey_);
89 CHECK_NE(key_in, kErasedKey_);
90 for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
92 idx = probeNext(idx, numProbes)) {
93 DCHECK_LT(idx, capacity_);
94 value_type* cell = &cells_[idx];
95 if (relaxedLoadKey(*cell) == kEmptyKey_) {
96 // NOTE: isFull_ is set based on numEntries_.readFast(), so it's
97 // possible to insert more than maxEntries_ entries. However, it's not
98 // possible to insert past capacity_.
100 if (isFull_.load(std::memory_order_acquire)) {
101 --numPendingEntries_;
103 // Before deciding whether this insert succeeded, this thread needs to
104 // wait until no other thread can add a new entry.
106 // Correctness assumes isFull_ is true at this point. If
107 // another thread now does ++numPendingEntries_, we expect it
108 // to pass the isFull_.load() test above. (It shouldn't insert
111 isFull_.load(std::memory_order_acquire) != NO_PENDING_INSERTS
112 && numPendingEntries_.readFull() != 0
114 isFull_.store(NO_PENDING_INSERTS, std::memory_order_release);
116 if (relaxedLoadKey(*cell) == kEmptyKey_) {
117 // Don't insert past max load factor
118 return SimpleRetT(capacity_, false);
121 // An unallocated cell. Try once to lock it. If we succeed, insert here.
122 // If we fail, fall through to comparison below; maybe the insert that
123 // just beat us was for this very key....
124 if (tryLockCell(cell)) {
125 // Write the value - done before unlocking
127 DCHECK(relaxedLoadKey(*cell) == kLockedKey_);
129 * This happens using the copy constructor because we won't have
130 * constructed a lhs to use an assignment operator on when
131 * values are being set.
133 new (&cell->second) ValueT(record.second);
134 unlockCell(cell, key_in); // Sets the new key
136 unlockCell(cell, kEmptyKey_);
137 --numPendingEntries_;
140 DCHECK(relaxedLoadKey(*cell) == key_in);
141 --numPendingEntries_;
142 ++numEntries_; // This is a thread cached atomic increment :)
143 if (numEntries_.readFast() >= maxEntries_) {
144 isFull_.store(NO_NEW_INSERTS, std::memory_order_relaxed);
146 return SimpleRetT(idx, true);
148 --numPendingEntries_;
151 DCHECK(relaxedLoadKey(*cell) != kEmptyKey_);
152 if (kLockedKey_ == cellKeyPtr(*cell)->load(std::memory_order_acquire)) {
154 kLockedKey_ == cellKeyPtr(*cell)->load(std::memory_order_acquire)
157 DCHECK(relaxedLoadKey(*cell) != kEmptyKey_);
158 DCHECK(relaxedLoadKey(*cell) != kLockedKey_);
159 if (key_in == relaxedLoadKey(*cell)) {
160 // Found an existing entry for our key, but we don't overwrite the
162 return SimpleRetT(idx, false);
165 if (UNLIKELY(numProbes >= capacity_)) {
166 // probed every cell...fail
167 return SimpleRetT(capacity_, false);
176 * This will attempt to erase the given key key_in if the key is found. It
177 * returns 1 iff the key was located and marked as erased, and 0 otherwise.
179 * Memory is not freed or reclaimed by erase, i.e. the cell containing the
180 * erased key will never be reused. If there's an associated value, we won't
183 template <class KeyT, class ValueT, class HashFcn>
184 size_t AtomicHashArray<KeyT, ValueT, HashFcn>::
186 CHECK_NE(key_in, kEmptyKey_);
187 CHECK_NE(key_in, kLockedKey_);
188 CHECK_NE(key_in, kErasedKey_);
189 for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
191 idx = probeNext(idx, numProbes)) {
192 DCHECK_LT(idx, capacity_);
193 value_type* cell = &cells_[idx];
194 if (relaxedLoadKey(*cell) == kEmptyKey_ ||
195 relaxedLoadKey(*cell) == kLockedKey_) {
196 // If we hit an empty (or locked) element, this key does not exist. This
197 // is similar to how it's handled in find().
200 if (key_in == relaxedLoadKey(*cell)) {
201 // Found an existing entry for our key, attempt to mark it erased.
202 // Some other thread may have erased our key, but this is ok.
203 KeyT expect = key_in;
204 if (cellKeyPtr(*cell)->compare_exchange_strong(expect, kErasedKey_)) {
205 numErases_.fetch_add(1, std::memory_order_relaxed);
207 // Even if there's a value in the cell, we won't delete (or even
208 // default construct) it because some other thread may be accessing it.
209 // Locking it meanwhile won't work either since another thread may be
210 // holding a pointer to it.
212 // We found the key and successfully erased it.
215 // If another thread succeeds in erasing our key, we'll stop our search.
219 if (UNLIKELY(numProbes >= capacity_)) {
220 // probed every cell...fail
226 template <class KeyT, class ValueT, class HashFcn>
227 const typename AtomicHashArray<KeyT, ValueT, HashFcn>::Config
228 AtomicHashArray<KeyT, ValueT, HashFcn>::defaultConfig;
230 template <class KeyT, class ValueT, class HashFcn>
231 typename AtomicHashArray<KeyT, ValueT, HashFcn>::SmartPtr
232 AtomicHashArray<KeyT, ValueT, HashFcn>::
233 create(size_t maxSize, const Config& c) {
234 CHECK_LE(c.maxLoadFactor, 1.0);
235 CHECK_GT(c.maxLoadFactor, 0.0);
236 CHECK_NE(c.emptyKey, c.lockedKey);
237 size_t capacity = size_t(maxSize / c.maxLoadFactor);
238 size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * capacity;
240 std::unique_ptr<void, void(*)(void*)> mem(malloc(sz), free);
241 new(mem.get()) AtomicHashArray(capacity, c.emptyKey, c.lockedKey, c.erasedKey,
242 c.maxLoadFactor, c.entryCountThreadCacheSize);
243 SmartPtr map(static_cast<AtomicHashArray*>(mem.release()));
246 * Mark all cells as empty.
248 * Note: we're bending the rules a little here accessing the key
249 * element in our cells even though the cell object has not been
250 * constructed, and casting them to atomic objects (see cellKeyPtr).
251 * (Also, in fact we never actually invoke the value_type
252 * constructor.) This is in order to avoid needing to default
253 * construct a bunch of value_type when we first start up: if you
254 * have an expensive default constructor for the value type this can
255 * noticeably speed construction time for an AHA.
257 FOR_EACH_RANGE(i, 0, map->capacity_) {
258 cellKeyPtr(map->cells_[i])->store(map->kEmptyKey_,
259 std::memory_order_relaxed);
264 template <class KeyT, class ValueT, class HashFcn>
265 void AtomicHashArray<KeyT, ValueT, HashFcn>::
266 destroy(AtomicHashArray* p) {
268 FOR_EACH_RANGE(i, 0, p->capacity_) {
269 if (p->cells_[i].first != p->kEmptyKey_) {
270 p->cells_[i].~value_type();
273 p->~AtomicHashArray();
277 // clear -- clears all keys and values in the map and resets all counters
278 template <class KeyT, class ValueT, class HashFcn>
279 void AtomicHashArray<KeyT, ValueT, HashFcn>::
281 FOR_EACH_RANGE(i, 0, capacity_) {
282 if (cells_[i].first != kEmptyKey_) {
283 cells_[i].~value_type();
284 *const_cast<KeyT*>(&cells_[i].first) = kEmptyKey_;
286 CHECK(cells_[i].first == kEmptyKey_);
289 numPendingEntries_.set(0);
290 isFull_.store(0, std::memory_order_relaxed);
291 numErases_.store(0, std::memory_order_relaxed);
295 // Iterator implementation
297 template <class KeyT, class ValueT, class HashFcn>
298 template <class ContT, class IterVal>
299 struct AtomicHashArray<KeyT, ValueT, HashFcn>::aha_iterator
300 : boost::iterator_facade<aha_iterator<ContT,IterVal>,
302 boost::forward_traversal_tag>
304 explicit aha_iterator() : aha_(0) {}
306 // Conversion ctor for interoperability between const_iterator and
307 // iterator. The enable_if<> magic keeps us well-behaved for
308 // is_convertible<> (v. the iterator_facade documentation).
309 template<class OtherContT, class OtherVal>
310 aha_iterator(const aha_iterator<OtherContT,OtherVal>& o,
311 typename std::enable_if<
312 std::is_convertible<OtherVal*,IterVal*>::value >::type* = 0)
317 explicit aha_iterator(ContT* array, size_t offset)
324 // Returns unique index that can be used with findAt().
325 // WARNING: The following function will fail silently for hashtable
326 // with capacity > 2^32
327 uint32_t getIndex() const { return offset_; }
330 friend class AtomicHashArray;
331 friend class boost::iterator_core_access;
338 bool equal(const aha_iterator& o) const {
339 return aha_ == o.aha_ && offset_ == o.offset_;
342 IterVal& dereference() const {
343 return aha_->cells_[offset_];
346 void advancePastEmpty() {
347 while (offset_ < aha_->capacity_ && !isValid()) {
352 bool isValid() const {
353 KeyT key = relaxedLoadKey(aha_->cells_[offset_]);
354 return key != aha_->kEmptyKey_ &&
355 key != aha_->kLockedKey_ &&
356 key != aha_->kErasedKey_;
366 #undef FOLLY_SPIN_WAIT