junction/ConcurrentMap_SimpleRelaxed.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_SIMPLERELAXED_H
  14 #define JUNCTION_CONCURRENTMAP_SIMPLERELAXED_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_SimpleRelaxed {
  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_SimpleRelaxed(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_SimpleRelaxed() {
  49         delete[] m_cells;
  50     }
  51
  52     void insert(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 = KeyTraits::NullKey;
 101             cell->value = Value(ValueTraits::NullValue);
 102         }
 103     }
 104 };
 105
 106 } // namespace junction
 107
 108 #endif // JUNCTION_CONCURRENTMAP_SIMPLERELAXED_H