Repository navigation
Expand file tree
/
Copy pathConcurrentMap_Crude.h
More file actions
108 lines (85 loc) · 3.35 KB
/
Copy pathConcurrentMap_Crude.h
File metadata and controls
108 lines (85 loc) · 3.35 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*------------------------------------------------------------------------
Junction: Concurrent data structures in C++
Copyright (c) 2016 Jeff Preshing
Distributed under the Simplified BSD License.
Original location: https://github.com/preshing/junction
This software is distributed WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
See the LICENSE file for more information.
------------------------------------------------------------------------*/
#ifndef JUNCTION_CONCURRENTMAP_CRUDE_H
#define JUNCTION_CONCURRENTMAP_CRUDE_H
#include <junction/Core.h>
#include <junction/MapTraits.h>
namespace junction {
template <typename K, typename V, class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V> >
class ConcurrentMap_Crude {
public:
typedef K Key;
typedef V Value;
typedef KT KeyTraits;
typedef VT ValueTraits;
static const ureg DefaultCapacity = 256;
private:
struct Cell {
turf::Atomic<Key> key;
turf::Atomic<Value> value;
};
Cell* m_cells;
ureg m_sizeMask;
public:
ConcurrentMap_Crude(ureg capacity = DefaultCapacity) {
TURF_ASSERT(turf::util::isPowerOf2(capacity));
m_sizeMask = capacity - 1;
m_cells = new Cell[capacity];
clear();
}
~ConcurrentMap_Crude() {
delete[] m_cells;
}
void assign(Key key, Value value) {
TURF_ASSERT(key != KeyTraits::NullKey);
TURF_ASSERT(value != Value(ValueTraits::NullValue));
for (ureg idx = KeyTraits::hash(key);; idx++) {
idx &= m_sizeMask;
Cell* cell = m_cells + idx;
// Load the key that was there.
Key probedKey = cell->key.load(turf::Relaxed);
if (probedKey != key) {
// The cell was either free, or contains another key.
if (probedKey != KeyTraits::NullKey)
continue; // Usually, it contains another key. Keep probing.
// The cell was free. Now let's try to take it using a CAS.
Key prevKey = cell->key.compareExchange(probedKey, key, turf::Relaxed);
if ((prevKey != KeyTraits::NullKey) && (prevKey != key))
continue; // Another thread just stole it from underneath us.
// Either we just added the key, or another thread did.
}
// Store the value in this cell.
cell->value.store(value, turf::Relaxed);
return;
}
}
Value get(Key key) {
TURF_ASSERT(key != KeyTraits::NullKey);
for (ureg idx = KeyTraits::hash(key);; idx++) {
idx &= m_sizeMask;
Cell* cell = m_cells + idx;
Key probedKey = cell->key.load(turf::Relaxed);
if (probedKey == key)
return cell->value.load(turf::Relaxed);
if (probedKey == KeyTraits::NullKey)
return Value(ValueTraits::NullValue);
}
}
void clear() {
// Must be called when there are no concurrent readers or writers
for (ureg idx = 0; idx <= m_sizeMask; idx++) {
Cell* cell = m_cells + idx;
cell->key.storeNonatomic(KeyTraits::NullKey);
cell->value.storeNonatomic(Value(ValueTraits::NullValue));
}
}
};
} // namespace junction
#endif // JUNCTION_CONCURRENTMAP_CRUDE_H