1 /*------------------------------------------------------------------------
2 Junction: Concurrent data structures in C++
3 Copyright (c) 2016 Jeff Preshing
5 Distributed under the Simplified BSD License.
6 Original location: https://github.com/preshing/junction
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 ------------------------------------------------------------------------*/
13 #ifndef JUNCTION_SINGLEMAP_LINEAR_H
14 #define JUNCTION_SINGLEMAP_LINEAR_H
16 #include <junction/Core.h>
17 #include <junction/MapTraits.h>
18 #include <turf/Util.h>
19 #include <turf/Heap.h>
23 template <typename Key, typename Value, class KeyTraits = DefaultKeyTraits<Key>, class ValueTraits = DefaultValueTraits<Value>>
24 class SingleMap_Linear {
26 typedef typename KeyTraits::Hash Hash;
31 Cell(Hash hash, Value value) : hash(hash), value(value) {
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));
46 static void destroyTable(Cell* cells, ureg size) {
47 for (ureg i = 0; i < size; i++)
49 TURF_HEAP.free(cells);
52 static bool isOverpopulated(ureg population, ureg sizeMask) {
53 return (population * 4) >= (sizeMask * 3);
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++) {
67 if (m_cells[dstIdx].hash == KeyTraits::NullHash) {
68 m_cells[dstIdx] = *srcCell;
74 destroyTable(srcCells, srcSize);
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));
83 destroyTable(m_cells, m_sizeMask + 1);
88 friend class SingleMap_Linear;
89 SingleMap_Linear& m_map;
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.
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);
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.
127 TURF_ASSERT(m_cell->value == NULL);
134 TURF_ASSERT(!m_cell || m_cell->value != NULL); // Forbid leaving a cell half-inserted.
138 bool isValid() const {
142 Value getValue() const {
144 return m_cell->value;
147 Value exchangeValue(Value desired) {
149 TURF_ASSERT(desired != NULL); // Use eraseValue()
150 Value oldValue = m_cell->value;
151 m_cell->value = desired;
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;
169 m_map.m_population--;
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.
177 cellIdx = neighborIdx;
183 Iterator insertOrFindKey(const Key& key) {
184 return Iterator(*this, key);
187 Value get(const Key& key) {
188 Iterator iter(*this, key, false);
189 return iter.isValid() ? iter.getValue() : NULL;
192 Value insert(const Key& key, Value desired) {
193 Iterator iter(*this, key);
194 return iter.exchangeValue(desired);
197 Value erase(const Key& key) {
198 Iterator iter(*this, key, false);
205 } // namespace junction
207 #endif // JUNCTION_SINGLEMAP_LINEAR_H