1 /*------------------------------------------------------------------------
2 Junction: Concurrent data structures in C++
3 Copyright (c) 2016 Jeff Preshing
5 Distributed under the Simplified BSD License.
6 Original location: https://github.com/preshing/junction
8 This software is distributed WITHOUT ANY WARRANTY; without even the
9 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
10 See the LICENSE file for more information.
11 ------------------------------------------------------------------------*/
13 #ifndef JUNCTION_CONCURRENTMAP_CRUDE_H
14 #define JUNCTION_CONCURRENTMAP_CRUDE_H
16 #include <junction/Core.h>
17 #include <junction/MapTraits.h>
21 template <typename K, typename V, class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V> >
22 class ConcurrentMap_Crude {
27 typedef VT ValueTraits;
29 static const ureg DefaultCapacity = 256;
33 turf::Atomic<Key> key;
34 turf::Atomic<Value> value;
41 ConcurrentMap_Crude(ureg capacity = DefaultCapacity) {
42 TURF_ASSERT(turf::util::isPowerOf2(capacity));
43 m_sizeMask = capacity - 1;
44 m_cells = new Cell[capacity];
48 ~ConcurrentMap_Crude() {
52 void insert(Key key, Value value) {
53 TURF_ASSERT(key != KeyTraits::NullKey);
54 TURF_ASSERT(value != Value(ValueTraits::NullValue));
56 for (ureg idx = KeyTraits::hash(key);; idx++) {
58 Cell* cell = m_cells + idx;
60 // Load the key that was there.
61 Key probedKey = cell->key.load(turf::Relaxed);
62 if (probedKey != key) {
63 // The cell was either free, or contains another key.
64 if (probedKey != KeyTraits::NullKey)
65 continue; // Usually, it contains another key. Keep probing.
67 // The cell was free. Now let's try to take it using a CAS.
68 Key prevKey = cell->key.compareExchange(probedKey, key, turf::Relaxed);
69 if ((prevKey != KeyTraits::NullKey) && (prevKey != key))
70 continue; // Another thread just stole it from underneath us.
72 // Either we just added the key, or another thread did.
75 // Store the value in this cell.
76 cell->value.store(value, turf::Relaxed);
82 TURF_ASSERT(key != KeyTraits::NullKey);
84 for (ureg idx = KeyTraits::hash(key);; idx++) {
86 Cell* cell = m_cells + idx;
88 Key probedKey = cell->key.load(turf::Relaxed);
90 return cell->value.load(turf::Relaxed);
91 if (probedKey == KeyTraits::NullKey)
92 return Value(ValueTraits::NullValue);
97 // Must be called when there are no concurrent readers or writers
98 for (ureg idx = 0; idx <= m_sizeMask; idx++) {
99 Cell* cell = m_cells + idx;
100 cell->key.storeNonatomic(KeyTraits::NullKey);
101 cell->value.storeNonatomic(Value(ValueTraits::NullValue));
106 } // namespace junction
108 #endif // JUNCTION_CONCURRENTMAP_CRUDE_H