d064a4805b155a1b2702b1eeb5afeea8b9a751a8
[junction.git] / junction / ConcurrentMap_Crude.h
1 /*------------------------------------------------------------------------
2   Junction: Concurrent data structures in C++
3   Copyright (c) 2016 Jeff Preshing
4
5   Distributed under the Simplified BSD License.
6   Original location: https://github.com/preshing/junction
7
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 ------------------------------------------------------------------------*/
12
13 #ifndef JUNCTION_CONCURRENTMAP_CRUDE_H
14 #define JUNCTION_CONCURRENTMAP_CRUDE_H
15
16 #include <junction/Core.h>
17 #include <junction/MapTraits.h>
18
19 namespace junction {
20
21 template <typename K, typename V, class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V> >
22 class ConcurrentMap_Crude {
23 public:
24     typedef K Key;
25     typedef V Value;
26     typedef KT KeyTraits;
27     typedef VT ValueTraits;
28     
29     static const ureg DefaultCapacity = 256;
30
31 private:
32     struct Cell {
33         turf::Atomic<Key> key;
34         turf::Atomic<Value> value;
35     };
36
37     Cell* m_cells;
38     ureg m_sizeMask;
39
40 public:
41     ConcurrentMap_Crude(ureg capacity = DefaultCapacity) {
42         TURF_ASSERT(turf::util::isPowerOf2(capacity));
43         m_sizeMask = capacity - 1;
44         m_cells = new Cell[capacity];
45         clear();
46     }
47
48     ~ConcurrentMap_Crude() {
49         delete[] m_cells;
50     }
51
52     void set(Key key, Value value) {
53         TURF_ASSERT(key != KeyTraits::NullKey);
54         TURF_ASSERT(value != Value(ValueTraits::NullValue));
55
56         for (ureg idx = KeyTraits::hash(key);; idx++) {
57             idx &= m_sizeMask;
58             Cell* cell = m_cells + idx;
59
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.
66
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.
71
72                 // Either we just added the key, or another thread did.
73             }
74
75             // Store the value in this cell.
76             cell->value.store(value, turf::Relaxed);
77             return;
78         }
79     }
80
81     Value get(Key key) {
82         TURF_ASSERT(key != KeyTraits::NullKey);
83
84         for (ureg idx = KeyTraits::hash(key);; idx++) {
85             idx &= m_sizeMask;
86             Cell* cell = m_cells + idx;
87
88             Key probedKey = cell->key.load(turf::Relaxed);
89             if (probedKey == key)
90                 return cell->value.load(turf::Relaxed);
91             if (probedKey == KeyTraits::NullKey)
92                 return Value(ValueTraits::NullValue);
93         }
94     }
95
96     void clear() {
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));
102         }
103     }
104 };
105
106 } // namespace junction
107
108 #endif // JUNCTION_CONCURRENTMAP_CRUDE_H