src/cxx_supportlib/DataStructures/StringKeyTable.h in passenger-5.0.25 vs src/cxx_supportlib/DataStructures/StringKeyTable.h in passenger-5.0.26
- old
+ new
@@ -24,10 +24,11 @@
* THE SOFTWARE.
*/
#ifndef _PASSENGER_DATA_STRUCTURES_STRING_KEY_TABLE_H_
#define _PASSENGER_DATA_STRUCTURES_STRING_KEY_TABLE_H_
+#include <boost/move/move.hpp>
#include <boost/cstdint.hpp>
#include <limits>
#include <cstring>
#include <cassert>
#include <cstddef>
@@ -37,10 +38,15 @@
namespace Passenger {
using namespace std;
+
+struct SKT_EnableMoveSupport { };
+struct SKT_DisableMoveSupport { };
+
+
/**
* An optimized hash table that accepts string keys, optimized for the following workload:
*
* * Inserts happen in bulk, soon after hash table creation or clearing.
* * Once the bulk insertion phase is over, lookups are frequent, but modifications
@@ -61,11 +67,11 @@
* compact().
*
* This implementation is based on https://github.com/preshing/CompareIntegerMaps.
* See also http://preshing.com/20130107/this-hash-table-is-faster-than-a-judy-array
*/
-template<typename T>
+template<typename T, typename MoveSupport = SKT_DisableMoveSupport>
class StringKeyTable {
public:
#define SKT_FIRST_CELL(hash) (m_cells + ((hash) & (m_arraySize - 1)))
#define SKT_CIRCULAR_NEXT(c) ((c) + 1 != m_cells + m_arraySize ? (c) + 1 : m_cells)
#define SKT_CIRCULAR_OFFSET(a, b) ((b) >= (a) ? (b) - (a) : m_arraySize + (b) - (a))
@@ -86,10 +92,20 @@
T value;
Cell()
: keyOffset(EMPTY_CELL_KEY_OFFSET)
{ }
+
+ void move(Cell &target) {
+ target.keyOffset = keyOffset;
+ target.keyLength = keyLength;
+ target.hash = hash;
+ target.value = boost::move(value);
+ keyOffset = 0;
+ keyLength = 0;
+ hash = 0;
+ }
};
private:
Cell *m_cells;
unsigned short m_arraySize;
@@ -179,11 +195,11 @@
// Insert this element into new array
Cell *newCell = SKT_FIRST_CELL(oldCell->hash);
while (true) {
if (cellIsEmpty(newCell)) {
// Insert here
- *newCell = *oldCell;
+ copyOrMoveCell(*oldCell, *newCell, MoveSupport());
break;
} else {
newCell = SKT_CIRCULAR_NEXT(newCell);
}
}
@@ -192,11 +208,27 @@
// Delete old array
delete[] oldCells;
}
- void copyFrom(const StringKeyTable &other) {
+ void copyOrMoveCell(Cell &source, Cell &target, const SKT_EnableMoveSupport &t) {
+ source.move(target);
+ }
+
+ void copyOrMoveCell(Cell &source, Cell &target, const SKT_DisableMoveSupport &t) {
+ target = source;
+ }
+
+ void copyOrMoveValue(T &source, T &target, const SKT_EnableMoveSupport &t) {
+ target = boost::move(source);
+ }
+
+ void copyOrMoveValue(const T &source, T &target, const SKT_DisableMoveSupport &t) {
+ target = source;
+ }
+
+ void copyTableFrom(const StringKeyTable &other) {
m_arraySize = other.m_arraySize;
m_population = other.m_population;
m_cells = new Cell[other.m_arraySize];
for (unsigned int i = 0; i < m_arraySize; i++) {
m_cells[i] = other.m_cells[i];
@@ -210,33 +242,77 @@
} else {
m_storage = NULL;
}
}
+ template<typename ValueType, typename LocalMoveSupport>
+ void realInsert(const HashedStaticString &key, ValueType val, bool overwrite) {
+ assert(!key.empty());
+ assert(key.size() <= MAX_KEY_LENGTH);
+ assert(m_population < MAX_ITEMS);
+
+ if (OXT_UNLIKELY(m_cells == NULL)) {
+ init(DEFAULT_SIZE, DEFAULT_STORAGE_SIZE);
+ }
+
+ while (true) {
+ Cell *cell = SKT_FIRST_CELL(key.hash());
+ while (true) {
+ const char *cellKey = lookupCellKey(cell);
+ if (cellKey == NULL) {
+ // Cell is empty. Insert here.
+ if (shouldRepopulateOnInsert()) {
+ // Time to resize
+ repopulate(m_arraySize * 2);
+ break;
+ }
+ m_population++;
+ cell->keyOffset = appendToStorage(key);
+ cell->keyLength = key.size();
+ cell->hash = key.hash();
+ copyOrMoveValue(val, cell->value, LocalMoveSupport());
+ nonEmptyIndex = cell - &m_cells[0];
+ return;
+ } else if (compareKeys(cellKey, cell->keyLength, key)) {
+ // Cell matches.
+ if (overwrite) {
+ copyOrMoveValue(val, cell->value, LocalMoveSupport());
+ }
+ return;
+ } else {
+ cell = SKT_CIRCULAR_NEXT(cell);
+ }
+ }
+ }
+ }
+
public:
StringKeyTable(unsigned int initialSize = DEFAULT_SIZE, unsigned int initialStorageSize = DEFAULT_STORAGE_SIZE) {
init(initialSize, initialStorageSize);
}
StringKeyTable(const StringKeyTable &other) {
- copyFrom(other);
+ copyTableFrom(other);
}
~StringKeyTable() {
delete[] m_cells;
free(m_storage);
}
StringKeyTable &operator=(const StringKeyTable &other) {
- delete[] m_cells;
- free(m_storage);
- copyFrom(other);
+ if (this != &other) {
+ delete[] m_cells;
+ free(m_storage);
+ copyTableFrom(other);
+ }
return *this;
}
void init(unsigned int initialSize, unsigned int initialStorageSize) {
assert((initialSize & (initialSize - 1)) == 0); // Must be a power of 2
+ assert((initialSize == 0) == (initialStorageSize == 0));
nonEmptyIndex = NON_EMPTY_INDEX_NONE;
m_arraySize = initialSize;
if (initialSize == 0) {
@@ -312,11 +388,11 @@
}
}
OXT_FORCE_INLINE
bool lookup(const HashedStaticString &key, T **result) {
- return static_cast<const StringKeyTable<T> *>(this)->lookup(key,
+ return static_cast<const StringKeyTable<T, MoveSupport> *>(this)->lookup(key,
const_cast<const T **>(result));
}
const T lookupCopy(const HashedStaticString &key) const {
const T *result;
@@ -353,49 +429,25 @@
return false;
}
}
void insert(const HashedStaticString &key, const T &val, bool overwrite = true) {
- assert(!key.empty());
- assert(key.size() <= MAX_KEY_LENGTH);
- assert(m_population < MAX_ITEMS);
+ realInsert<const T &, SKT_DisableMoveSupport>(key, val, overwrite);
+ }
- while (true) {
- Cell *cell = SKT_FIRST_CELL(key.hash());
- while (true) {
- const char *cellKey = lookupCellKey(cell);
- if (cellKey == NULL) {
- // Cell is empty. Insert here.
- if (shouldRepopulateOnInsert()) {
- // Time to resize
- repopulate(m_arraySize * 2);
- break;
- }
- m_population++;
- cell->keyOffset = appendToStorage(key);
- cell->keyLength = key.size();
- cell->hash = key.hash();
- cell->value = val;
- nonEmptyIndex = cell - &m_cells[0];
- return;
- } else if (compareKeys(cellKey, cell->keyLength, key)) {
- // Cell matches.
- if (overwrite) {
- cell->value = val;
- }
- return;
- } else {
- cell = SKT_CIRCULAR_NEXT(cell);
- }
- }
- }
+ void insertByMoving(const HashedStaticString &key, BOOST_RV_REF(T) val, bool overwrite = true) {
+ realInsert<BOOST_RV_REF(T), SKT_EnableMoveSupport>(key, boost::move(val), overwrite);
}
void erase(Cell *cell) {
assert(cell >= m_cells && cell - m_cells < m_arraySize);
assert(!cellIsEmpty(cell));
+ if (OXT_UNLIKELY(m_cells == NULL)) {
+ return;
+ }
+
// Remove this cell by shuffling neighboring cells so there are no gaps in anyone's probe chain
Cell *neighbor = SKT_CIRCULAR_NEXT(cell);
while (true) {
if (cellIsEmpty(neighbor)) {
// There's nobody to swap with. Go ahead and clear this cell, then return.
@@ -431,9 +483,13 @@
}
}
/** Does not resize the array. */
void clear() {
+ if (OXT_UNLIKELY(m_cells == NULL)) {
+ return;
+ }
+
for (unsigned int i = 0; i < m_arraySize; i++) {
m_cells[i].keyOffset = EMPTY_CELL_KEY_OFFSET;
m_cells[i].value = T();
}
m_population = 0;