-Junction is a library of concurrent data structures in C++. It contains three hash map implementations:
+Junction is a library of concurrent data structures in C++. It contains several hash map implementations:
+ junction::ConcurrentMap_Crude
junction::ConcurrentMap_Linear
junction::ConcurrentMap_LeapFrog
junction::ConcurrentMap_Grampa
## Rules and Behavior
-A Junction map is a lot like a big array of `std::atomic<>` variables, where the key is an index into the array, stores use `memory_order_release`, and loads use `memory_order_consume`.
+A Junction map is a lot like a big array of `std::atomic<>` variables, where the key is an index into the array. More precisely:
-More precisely, the following rules apply to Junction's Linear, LeapFrog and Grampa maps:
-
-* All of their member functions, together with their `Mutator` member functions, are atomic with respect to each other, so you can safely call them from any thread without mutual exclusion.
+* All of a Junction map's member functions, together with its `Mutator` member functions, are atomic with respect to each other, so you can safely call them from any thread without mutual exclusion.
* If an `insert` [happens before](http://preshing.com/20130702/the-happens-before-relation/) a `get` with the same key, the `get` will return the value it inserted, except if another operation changes the value in between. Any [synchronizing operation](http://preshing.com/20130823/the-synchronizes-with-relation/) will establish this relationship.
-* `insert` is a [release](http://preshing.com/20120913/acquire-and-release-semantics/) operation and `get` is a [consume](http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/) operation, so you can safely pass non-atomic information between threads using a pointer.
+* For Linear, LeapFrog and Grampa maps, `insert` is a [release](http://preshing.com/20120913/acquire-and-release-semantics/) operation and `get` is a [consume](http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/) operation, so you can safely pass non-atomic information between threads using a pointer. For Crude maps, all operations are relaxed.
* In the current version, you must not insert while concurrently using an `Iterator`.
## Feedback
--- /dev/null
+/*------------------------------------------------------------------------
+ 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 insert(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
+++ /dev/null
-/*------------------------------------------------------------------------
- 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_SIMPLERELAXED_H
-#define JUNCTION_CONCURRENTMAP_SIMPLERELAXED_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_SimpleRelaxed {
-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_SimpleRelaxed(ureg capacity = DefaultCapacity) {
- TURF_ASSERT(turf::util::isPowerOf2(capacity));
- m_sizeMask = capacity - 1;
- m_cells = new Cell[capacity];
- clear();
- }
-
- ~ConcurrentMap_SimpleRelaxed() {
- delete[] m_cells;
- }
-
- void insert(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_SIMPLERELAXED_H
--- /dev/null
+/*------------------------------------------------------------------------
+ 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_EXTRA_IMPL_MAPADAPTER_CRUDE_H
+#define JUNCTION_EXTRA_IMPL_MAPADAPTER_CRUDE_H
+
+#include <junction/Core.h>
+#include <junction/ConcurrentMap_Crude.h>
+#include <turf/Util.h>
+
+namespace junction {
+namespace extra {
+
+class MapAdapter {
+public:
+ static TURF_CONSTEXPR const char* MapName = "Junction Crude map";
+
+ MapAdapter(ureg) {
+ }
+
+ class ThreadContext {
+ public:
+ ThreadContext(MapAdapter&, ureg) {
+ }
+
+ void registerThread() {
+ }
+
+ void unregisterThread() {
+ }
+
+ void update() {
+ }
+ };
+
+ typedef ConcurrentMap_Crude<u32, void*> Map;
+
+ static ureg getInitialCapacity(ureg maxPopulation) {
+ return turf::util::roundUpPowerOf2(ureg(maxPopulation * 1.25f));
+ }
+};
+
+} // namespace extra
+} // namespace junction
+
+#endif // JUNCTION_EXTRA_IMPL_MAPADAPTER_CRUDE_H
+++ /dev/null
-/*------------------------------------------------------------------------
- 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_EXTRA_IMPL_MAPADAPTER_SIMPLERELAXED_H
-#define JUNCTION_EXTRA_IMPL_MAPADAPTER_SIMPLERELAXED_H
-
-#include <junction/Core.h>
-#include <junction/ConcurrentMap_SimpleRelaxed.h>
-#include <turf/Util.h>
-
-namespace junction {
-namespace extra {
-
-class MapAdapter {
-public:
- static TURF_CONSTEXPR const char* MapName = "Junction SimpleRelaxed map";
-
- MapAdapter(ureg) {
- }
-
- class ThreadContext {
- public:
- ThreadContext(MapAdapter&, ureg) {
- }
-
- void registerThread() {
- }
-
- void unregisterThread() {
- }
-
- void update() {
- }
- };
-
- typedef ConcurrentMap_SimpleRelaxed<u32, void*> Map;
-
- static ureg getInitialCapacity(ureg maxPopulation) {
- return turf::util::roundUpPowerOf2(ureg(maxPopulation * 1.25f));
- }
-};
-
-} // namespace extra
-} // namespace junction
-
-#endif // JUNCTION_EXTRA_IMPL_MAPADAPTER_SIMPLERELAXED_H
-#define JUNCTION_IMPL_MAPADAPTER_PATH "junction/extra/impl/MapAdapter_SimpleRelaxed.h"
+#define JUNCTION_IMPL_MAPADAPTER_PATH "junction/extra/impl/MapAdapter_Crude.h"