From: Jeff Preshing <filter-github@preshing.com>
Date: Tue, 16 Feb 2016 14:42:32 +0000 (-0500)
Subject: Add ConcurrentMap_SimpleRelaxed
X-Git-Url: http://plrg.eecs.uci.edu/git/?p=junction.git;a=commitdiff_plain;h=3ef92edd2bdb5084e12483b746a925ddc7e5fcc8

Add ConcurrentMap_SimpleRelaxed

Nearly identical to http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table/
---

diff --git a/junction/ConcurrentMap_SimpleRelaxed.h b/junction/ConcurrentMap_SimpleRelaxed.h
new file mode 100644
index 0000000..d0f9a1a
--- /dev/null
+++ b/junction/ConcurrentMap_SimpleRelaxed.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_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 = KeyTraits::NullKey;
+            cell->value = Value(ValueTraits::NullValue);
+        }
+    }
+};
+
+} // namespace junction
+
+#endif // JUNCTION_CONCURRENTMAP_SIMPLERELAXED_H
diff --git a/junction/MapTraits.h b/junction/MapTraits.h
index de83d27..a34a4bc 100644
--- a/junction/MapTraits.h
+++ b/junction/MapTraits.h
@@ -22,6 +22,7 @@ template <class T>
 struct DefaultKeyTraits {
     typedef T Key;
     typedef typename turf::util::BestFit<T>::Unsigned Hash;
+    static const Key NullKey = Key(0);
     static const Hash NullHash = Hash(0);
     static Hash hash(T key) {
         return turf::util::avalanche(Hash(key));
diff --git a/junction/details/Linear.h b/junction/details/Linear.h
index 590d390..3e11a0e 100644
--- a/junction/details/Linear.h
+++ b/junction/details/Linear.h
@@ -262,7 +262,6 @@ template <class Map>
 bool Linear<Map>::TableMigration::migrateRange(Table* srcTable, ureg startIdx) {
     ureg srcSizeMask = srcTable->sizeMask;
     ureg endIdx = turf::util::min(startIdx + TableMigrationUnitSize, srcSizeMask + 1);
-    sreg valuesMigrated = 0;
     // Iterate over source range.
     for (ureg srcIdx = startIdx; srcIdx < endIdx; srcIdx++) {
         Cell* srcCell = srcTable->getCells() + (srcIdx & srcSizeMask);
diff --git a/junction/extra/impl/MapAdapter_SimpleRelaxed.h b/junction/extra/impl/MapAdapter_SimpleRelaxed.h
new file mode 100644
index 0000000..88a2e81
--- /dev/null
+++ b/junction/extra/impl/MapAdapter_SimpleRelaxed.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_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