Add SingleMap_Leapfrog

[junction.git] / junction / SingleMap_Linear.h

diff --git a/junction/SingleMap_Linear.h b/junction/SingleMap_Linear.h
index 5ea2521fd70062761a32f3d09c596c9f53c171b8..ff1fd525ba63c72e8f39e71562062867988477b5 100644 (file)
--- a/junction/SingleMap_Linear.h
+++ b/junction/SingleMap_Linear.h
@@ -33,17 +33,19 @@ private:
     };
 
     Cell* m_cells;
-    u32 m_sizeMask;
-    u32 m_population;
+    ureg m_sizeMask;
+    ureg m_population;
 
     static Cell* createTable(ureg size) {
+        TURF_ASSERT(turf::util::isPowerOf2(size));
         Cell* cells = (Cell*) TURF_HEAP.alloc(sizeof(Cell) * size);
         for (ureg i = 0; i < size; i++)
-            new(cells + i) Cell(KeyTraits::NullHash, Value(ValueTraits::NullValue));
+            new (cells + i) Cell(KeyTraits::NullHash, Value(ValueTraits::NullValue));
         return cells;
     }
 
     static void destroyTable(Cell* cells, ureg size) {
+        TURF_ASSERT(turf::util::isPowerOf2(size));
         for (ureg i = 0; i < size; i++)
             cells[i].~Cell();
         TURF_HEAP.free(cells);
@@ -53,8 +55,7 @@ private:
         return (population * 4) >= (sizeMask * 3);
     }
 
-    void migrateToNewTable(size_t desiredSize) {
-        TURF_ASSERT(turf::util::isPowerOf2(desiredSize));
+    void migrateToNewTable(ureg desiredSize) {
         Cell* srcCells = m_cells;
         ureg srcSize = m_sizeMask + 1;
         m_cells = createTable(desiredSize);
@@ -75,38 +76,37 @@ private:
     }
 
 public:
-    SingleMap_Linear(size_t initialSize = 8) : m_cells(createTable(initialSize)), m_sizeMask(initialSize - 1), m_population(0) {
-        TURF_ASSERT(turf::util::isPowerOf2(initialSize));
+    SingleMap_Linear(ureg initialSize = 8) : m_cells(createTable(initialSize)), m_sizeMask(initialSize - 1), m_population(0) {
     }
 
     ~SingleMap_Linear() {
         destroyTable(m_cells, m_sizeMask + 1);
     }
 
-    class Iterator {
+    class Mutator {
     private:
         friend class SingleMap_Linear;
         SingleMap_Linear& m_map;
         Cell* m_cell;
 
         // Constructor: Find without insert
-        Iterator(SingleMap_Linear& map, Key key, bool) : m_map(map) {
+        Mutator(SingleMap_Linear& map, Key key, bool) : m_map(map) {
             Hash hash = KeyTraits::hash(key);
             TURF_ASSERT(hash != KeyTraits::NullHash);
             for (ureg idx = hash;; idx++) {
                 idx &= map.m_sizeMask;
                 m_cell = map.m_cells + idx;
                 if (m_cell->hash == hash)
-                    return;         // Key found in table.
+                    return; // Key found in table.
                 if (m_cell->hash != KeyTraits::NullHash)
-                    continue;       // Slot is taken by another key. Try next slot.
-                m_cell = NULL;  // Insert not allowed & key not found.
+                    continue;  // Slot is taken by another key. Try next slot.
+                m_cell = NULL; // Insert not allowed & key not found.
                 return;
             }
         }
 
         // Constructor: Find with insert
-        Iterator(SingleMap_Linear& map, Key key) : m_map(map) {
+        Mutator(SingleMap_Linear& map, Key key) : m_map(map) {
             Hash hash = KeyTraits::hash(key);
             TURF_ASSERT(hash != KeyTraits::NullHash);
             for (;;) {
@@ -114,24 +114,24 @@ public:
                     idx &= map.m_sizeMask;
                     m_cell = map.m_cells + idx;
                     if (m_cell->hash == hash)
-                        return;         // Key found in table.
+                        return; // Key found in table.
                     if (m_cell->hash != KeyTraits::NullHash)
-                        continue;       // Slot is taken by another key. Try next slot.
+                        continue; // Slot is taken by another key. Try next slot.
                     // Insert is allowed. Reserve this cell.
                     if (isOverpopulated(map.m_population, map.m_sizeMask)) {
                         map.migrateToNewTable((map.m_sizeMask + 1) * 2);
-                        break;          // Retry in new table.
+                        break; // Retry in new table.
                     }
                     map.m_population++;
                     m_cell->hash = hash;
-                    TURF_ASSERT(m_cell->value == NULL);
+                    TURF_ASSERT(m_cell->value == Value(ValueTraits::NullValue));
                     return;
                 }
             }
         }
 
-        ~Iterator() {
-            TURF_ASSERT(!m_cell || m_cell->value != NULL);  // Forbid leaving a cell half-inserted.
+        ~Mutator() {
+            TURF_ASSERT(!m_cell || m_cell->value != NULL); // In SingleMap_Linear, there are no deleted cells.
         }
 
     public:
@@ -146,7 +146,7 @@ public:
 
         Value exchangeValue(Value desired) {
             TURF_ASSERT(m_cell);
-            TURF_ASSERT(desired != NULL);  // Use eraseValue()
+            TURF_ASSERT(desired != NULL); // Use eraseValue()
             Value oldValue = m_cell->value;
             m_cell->value = desired;
             return oldValue;
@@ -154,17 +154,17 @@ public:
 
         Value erase() {
             TURF_ASSERT(m_cell);
-            TURF_ASSERT(m_cell->value != NULL);  // Forbid erasing a cell that's not actually used.
+            TURF_ASSERT(m_cell->value != Value(ValueTraits::NullValue)); // SingleMap_Linear never contains "deleted" cells.
             Value oldValue = m_cell->value;
             // Remove this cell by shuffling neighboring cells so there are no gaps in anyone's probe chain
-            ureg cellIdx = m_cell - m_map.m_cells; 
+            ureg cellIdx = m_cell - m_map.m_cells;
             for (ureg neighborIdx = cellIdx + 1;; neighborIdx++) {
                 neighborIdx &= m_map.m_sizeMask;
                 Cell* neighbor = m_map.m_cells + neighborIdx;
                 if (neighbor->hash == KeyTraits::NullHash) {
                     // Go ahead and clear this cell. It won't break anyone else's probe chain.
                     m_cell->hash = KeyTraits::NullHash;
-                    m_cell->value = NULL;
+                    m_cell->value = Value(ValueTraits::NullValue);
                     m_cell = NULL;
                     m_map.m_population--;
                     return oldValue;
@@ -180,22 +180,22 @@ public:
         }
     };
 
-    Iterator insertOrFindKey(const Key& key) {
-        return Iterator(*this, key);
+    Mutator insertOrFindKey(const Key& key) {
+        return Mutator(*this, key);
     }
 
     Value get(const Key& key) {
-        Iterator iter(*this, key, false);
+        Mutator iter(*this, key, false);
         return iter.isValid() ? iter.getValue() : NULL;
     }
 
-    Value insert(const Key& key, Value desired) {
-        Iterator iter(*this, key);
+    Value set(const Key& key, Value desired) {
+        Mutator iter(*this, key);
         return iter.exchangeValue(desired);
     }
 
     Value erase(const Key& key) {
-        Iterator iter(*this, key, false);
+        Mutator iter(*this, key, false);
         if (iter.isValid())
             return iter.erase();
         return NULL;