Rename SimpleRelaxed to Crude

diff --git a/README.md b/README.md
index 5fd67b002860663423052dfd9abdddef99c5abfd..195a7475b86566f06df37675f6ebf37dd85de371 100644 (file)
--- a/README.md
+++ b/README.md
@@ -1,5 +1,6 @@
-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
     junction::ConcurrentMap_Linear
     junction::ConcurrentMap_LeapFrog
     junction::ConcurrentMap_Grampa


@@ -98,13 +99,11 @@ The `JUNCTION_USERCONFIG` variable works in a similar way. As an example, take a
 
 ## Rules and Behavior
 
 
 ## 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.
 * 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
 * In the current version, you must not insert while concurrently using an `Iterator`.
 
 ## Feedback

diff --git a/junction/ConcurrentMap_Crude.h b/junction/ConcurrentMap_Crude.h
new file mode 100644 (file)
index 0000000..c78e4cf
--- /dev/null
+++ b/junction/ConcurrentMap_Crude.h
@@ -0,0 +1,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 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

diff --git a/junction/ConcurrentMap_SimpleRelaxed.h b/junction/ConcurrentMap_SimpleRelaxed.h
deleted file mode 100644 (file)
index 269db9a..0000000
--- a/junction/ConcurrentMap_SimpleRelaxed.h
+++ /dev/null
@@ -1,108 +0,0 @@
-/*------------------------------------------------------------------------
-  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

diff --git a/junction/extra/impl/MapAdapter_Crude.h b/junction/extra/impl/MapAdapter_Crude.h
new file mode 100644 (file)
index 0000000..1548ff6
--- /dev/null
+++ b/junction/extra/impl/MapAdapter_Crude.h
@@ -0,0 +1,55 @@
+/*------------------------------------------------------------------------
+  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

diff --git a/junction/extra/impl/MapAdapter_SimpleRelaxed.h b/junction/extra/impl/MapAdapter_SimpleRelaxed.h
deleted file mode 100644 (file)
index 88a2e81..0000000
--- a/junction/extra/impl/MapAdapter_SimpleRelaxed.h
+++ /dev/null
@@ -1,55 +0,0 @@
-/*------------------------------------------------------------------------
-  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

diff --git a/samples/MapLinearizabilityTest/junction_userconfig.h.in b/samples/MapLinearizabilityTest/junction_userconfig.h.in
index 5c9739d6edbe2b4c7d8bc48997fef4ff32bbb376..738001309292d981ccc344097af3603723ae4734 100644 (file)
--- a/samples/MapLinearizabilityTest/junction_userconfig.h.in
+++ b/samples/MapLinearizabilityTest/junction_userconfig.h.in
@@ -1 +1 @@
-#define JUNCTION_IMPL_MAPADAPTER_PATH "junction/extra/impl/MapAdapter_SimpleRelaxed.h"
+#define JUNCTION_IMPL_MAPADAPTER_PATH "junction/extra/impl/MapAdapter_Crude.h"