junction/SingleMap_Linear.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_SINGLEMAP_LINEAR_H
  14 #define JUNCTION_SINGLEMAP_LINEAR_H
  15
  16 #include <junction/Core.h>
  17 #include <junction/MapTraits.h>
  18 #include <turf/Util.h>
  19 #include <turf/Heap.h>
  20
  21 namespace junction {
  22
  23 template <typename Key, typename Value, class KeyTraits = DefaultKeyTraits<Key>, class ValueTraits = DefaultValueTraits<Value>>
  24 class SingleMap_Linear {
  25 private:
  26     typedef typename KeyTraits::Hash Hash;
  27
  28     struct Cell {
  29         Hash hash;
  30         Value value;
  31         Cell(Hash hash, Value value) : hash(hash), value(value) {
  32         }
  33     };
  34
  35     Cell* m_cells;
  36     u32 m_sizeMask;
  37     u32 m_population;
  38
  39     static Cell* createTable(ureg size) {
  40         Cell* cells = (Cell*) TURF_HEAP.alloc(sizeof(Cell) * size);
  41         for (ureg i = 0; i < size; i++)
  42             new (cells + i) Cell(KeyTraits::NullHash, Value(ValueTraits::NullValue));
  43         return cells;
  44     }
  45
  46     static void destroyTable(Cell* cells, ureg size) {
  47         for (ureg i = 0; i < size; i++)
  48             cells[i].~Cell();
  49         TURF_HEAP.free(cells);
  50     }
  51
  52     static bool isOverpopulated(ureg population, ureg sizeMask) {
  53         return (population * 4) >= (sizeMask * 3);
  54     }
  55
  56     void migrateToNewTable(size_t desiredSize) {
  57         TURF_ASSERT(turf::util::isPowerOf2(desiredSize));
  58         Cell* srcCells = m_cells;
  59         ureg srcSize = m_sizeMask + 1;
  60         m_cells = createTable(desiredSize);
  61         m_sizeMask = desiredSize - 1;
  62         for (ureg srcIdx = 0; srcIdx < srcSize; srcIdx++) {
  63             Cell* srcCell = srcCells + srcIdx;
  64             if (srcCell->hash != KeyTraits::NullHash) {
  65                 for (ureg dstIdx = srcCell->hash;; dstIdx++) {
  66                     dstIdx &= m_sizeMask;
  67                     if (m_cells[dstIdx].hash == KeyTraits::NullHash) {
  68                         m_cells[dstIdx] = *srcCell;
  69                         break;
  70                     }
  71                 }
  72             }
  73         }
  74         destroyTable(srcCells, srcSize);
  75     }
  76
  77 public:
  78     SingleMap_Linear(size_t initialSize = 8) : m_cells(createTable(initialSize)), m_sizeMask(initialSize - 1), m_population(0) {
  79         TURF_ASSERT(turf::util::isPowerOf2(initialSize));
  80     }
  81
  82     ~SingleMap_Linear() {
  83         destroyTable(m_cells, m_sizeMask + 1);
  84     }
  85
  86     class Iterator {
  87     private:
  88         friend class SingleMap_Linear;
  89         SingleMap_Linear& m_map;
  90         Cell* m_cell;
  91
  92         // Constructor: Find without insert
  93         Iterator(SingleMap_Linear& map, Key key, bool) : m_map(map) {
  94             Hash hash = KeyTraits::hash(key);
  95             TURF_ASSERT(hash != KeyTraits::NullHash);
  96             for (ureg idx = hash;; idx++) {
  97                 idx &= map.m_sizeMask;
  98                 m_cell = map.m_cells + idx;
  99                 if (m_cell->hash == hash)
 100                     return; // Key found in table.
 101                 if (m_cell->hash != KeyTraits::NullHash)
 102                     continue;  // Slot is taken by another key. Try next slot.
 103                 m_cell = NULL; // Insert not allowed & key not found.
 104                 return;
 105             }
 106         }
 107
 108         // Constructor: Find with insert
 109         Iterator(SingleMap_Linear& map, Key key) : m_map(map) {
 110             Hash hash = KeyTraits::hash(key);
 111             TURF_ASSERT(hash != KeyTraits::NullHash);
 112             for (;;) {
 113                 for (ureg idx = hash;; idx++) {
 114                     idx &= map.m_sizeMask;
 115                     m_cell = map.m_cells + idx;
 116                     if (m_cell->hash == hash)
 117                         return; // Key found in table.
 118                     if (m_cell->hash != KeyTraits::NullHash)
 119                         continue; // Slot is taken by another key. Try next slot.
 120                     // Insert is allowed. Reserve this cell.
 121                     if (isOverpopulated(map.m_population, map.m_sizeMask)) {
 122                         map.migrateToNewTable((map.m_sizeMask + 1) * 2);
 123                         break; // Retry in new table.
 124                     }
 125                     map.m_population++;
 126                     m_cell->hash = hash;
 127                     TURF_ASSERT(m_cell->value == NULL);
 128                     return;
 129                 }
 130             }
 131         }
 132
 133         ~Iterator() {
 134             TURF_ASSERT(!m_cell || m_cell->value != NULL); // Forbid leaving a cell half-inserted.
 135         }
 136
 137     public:
 138         bool isValid() const {
 139             return !!m_cell;
 140         }
 141
 142         Value getValue() const {
 143             TURF_ASSERT(m_cell);
 144             return m_cell->value;
 145         }
 146
 147         Value exchangeValue(Value desired) {
 148             TURF_ASSERT(m_cell);
 149             TURF_ASSERT(desired != NULL); // Use eraseValue()
 150             Value oldValue = m_cell->value;
 151             m_cell->value = desired;
 152             return oldValue;
 153         }
 154
 155         Value erase() {
 156             TURF_ASSERT(m_cell);
 157             TURF_ASSERT(m_cell->value != NULL); // Forbid erasing a cell that's not actually used.
 158             Value oldValue = m_cell->value;
 159             // Remove this cell by shuffling neighboring cells so there are no gaps in anyone's probe chain
 160             ureg cellIdx = m_cell - m_map.m_cells;
 161             for (ureg neighborIdx = cellIdx + 1;; neighborIdx++) {
 162                 neighborIdx &= m_map.m_sizeMask;
 163                 Cell* neighbor = m_map.m_cells + neighborIdx;
 164                 if (neighbor->hash == KeyTraits::NullHash) {
 165                     // Go ahead and clear this cell. It won't break anyone else's probe chain.
 166                     m_cell->hash = KeyTraits::NullHash;
 167                     m_cell->value = NULL;
 168                     m_cell = NULL;
 169                     m_map.m_population--;
 170                     return oldValue;
 171                 }
 172                 ureg idealIdx = neighbor->hash & m_map.m_sizeMask;
 173                 if (((cellIdx - idealIdx) & m_map.m_sizeMask) < ((neighborIdx - idealIdx) & m_map.m_sizeMask)) {
 174                     // Swap with neighbor, then make neighbor the new cell to remove.
 175                     *m_cell = *neighbor;
 176                     m_cell = neighbor;
 177                     cellIdx = neighborIdx;
 178                 }
 179             }
 180         }
 181     };
 182
 183     Iterator insertOrFindKey(const Key& key) {
 184         return Iterator(*this, key);
 185     }
 186
 187     Value get(const Key& key) {
 188         Iterator iter(*this, key, false);
 189         return iter.isValid() ? iter.getValue() : NULL;
 190     }
 191
 192     Value insert(const Key& key, Value desired) {
 193         Iterator iter(*this, key);
 194         return iter.exchangeValue(desired);
 195     }
 196
 197     Value erase(const Key& key) {
 198         Iterator iter(*this, key, false);
 199         if (iter.isValid())
 200             return iter.erase();
 201         return NULL;
 202     }
 203 };
 204
 205 } // namespace junction
 206
 207 #endif // JUNCTION_SINGLEMAP_LINEAR_H