Viewing file:  StringKeyTable.h (17.04 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
/*
* Phusion Passenger - https://www.phusionpassenger.com/
* Copyright (c) 2014-2017 Phusion Holding B.V.
*
* "Passenger", "Phusion Passenger" and "Union Station" are registered
* trademarks of Phusion Holding B.V.
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* 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/config.hpp>
#include <boost/cstdint.hpp>
// for std::swap()
#if __cplusplus >= 201103L
#include <utility>
#else
#include <algorithm>
#endif
#include <limits>
#include <cstring>
#include <cassert>
#include <cstddef>
#include <DataStructures/HashedStaticString.h>
#include <StaticString.h>
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
* are not.
*
* The hash table uses open addressing and linear probing. It also stores key data
* in a single contiguous internal storage area, outside the cells. This reduces calls
* to malloc(), avoids a lot of malloc space overhead and improves cache locality.
* Because the table owns the key data, there's no need to allocate keys and to keep
* them alive outside the hash table.
*
* Keys may be at most 255 bytes long. The total sum of keys may not exceed
* 2^(24-1) bytes =~ 6 MB. This allows us to use compact indices in the Cell
* struct instead of pointers, significantly reducing memory usage on 64-bit platforms.
*
* The hash table automatically doubles in size when it becomes 75% full.
* The hash table never shrinks in size, even after clear(), unless you explicitly call
* 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, 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))
static const unsigned int DEFAULT_SIZE = 16;
// Fits in exactly 4 cache lines. The -16 is to account for malloc overhead.
static const unsigned int DEFAULT_STORAGE_SIZE = 4 * 64 - 16;
static const unsigned int MAX_KEY_LENGTH = 255;
static const unsigned int MAX_ITEMS = 65533; // 2^16-3
static const boost::uint32_t EMPTY_CELL_KEY_OFFSET = 16777215;
static const unsigned short NON_EMPTY_INDEX_NONE = 65535;
static const unsigned short NON_EMPTY_INDEX_UNKNOWN = 65534;
struct Cell {
boost::uint32_t keyOffset: 24;
boost::uint8_t keyLength;
boost::uint32_t hash;
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;
unsigned short m_population;
// Index of a random non-empty cell
unsigned short nonEmptyIndex;
char *m_storage;
unsigned int m_storageSize;
unsigned int m_storageUsed;
bool shouldRepopulateOnInsert() const {
return (m_population + 1) * 4 >= m_arraySize * 3;
}
const char *lookupCellKey(const Cell * const cell) const {
if (!cellIsEmpty(cell)) {
return &m_storage[cell->keyOffset];
} else {
return NULL;
}
}
OXT_FORCE_INLINE
bool cellIsEmpty(const Cell * const cell) const {
return cell->keyOffset == EMPTY_CELL_KEY_OFFSET;
}
static bool
compareKeys(const char *key1, unsigned int key1Length, const HashedStaticString &key2) {
return StaticString(key1, key1Length) == key2;
}
static boost::uint32_t upper_power_of_two(boost::uint32_t v) {
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
return v;
}
boost::uint32_t appendToStorage(const StaticString &key) {
const string::size_type keySize = key.size();
if (m_storageUsed + key.size() + 1 > m_storageSize) {
// Resize storage area when of insufficient size.
unsigned int newStorageSize = (m_storageSize + key.size() + 1) * 1.5;
char *newStorage = (char *) realloc(m_storage, newStorageSize);
if (OXT_UNLIKELY(newStorage == NULL)) {
throw std::bad_alloc();
} else {
m_storageSize = newStorageSize;
m_storage = newStorage;
}
}
// Append key to the end of the storage area, set NULL terminator.
boost::uint32_t old_storageUsed = m_storageUsed;
memcpy(m_storage + m_storageUsed, key.data(), keySize);
m_storage[m_storageUsed + key.size()] = '\0';
m_storageUsed += key.size() + 1;
return old_storageUsed;
}
void repopulate(unsigned int desiredSize) {
assert((desiredSize & (desiredSize - 1)) == 0); // Must be a power of 2
assert(m_population * 4 <= desiredSize * 3);
// Get start/end pointers of old array
Cell *oldCells = m_cells;
Cell *end = m_cells + m_arraySize;
// Allocate new array
m_arraySize = desiredSize;
m_cells = new Cell[m_arraySize];
if (oldCells == NULL) {
return;
}
// Iterate through old array
for (Cell *oldCell = oldCells; oldCell != end; oldCell++) {
if (!cellIsEmpty(oldCell)) {
// Insert this element into new array
Cell *newCell = SKT_FIRST_CELL(oldCell->hash);
while (true) {
if (cellIsEmpty(newCell)) {
// Insert here
copyOrMoveCell(*oldCell, *newCell, MoveSupport());
break;
} else {
newCell = SKT_CIRCULAR_NEXT(newCell);
}
}
}
}
// Delete old array
delete[] oldCells;
}
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];
}
m_storageSize = other.m_storageSize;
m_storageUsed = other.m_storageUsed;
if (other.m_storage != NULL) {
m_storage = (char *) malloc(m_storageSize);
memcpy(m_storage, other.m_storage, other.m_storageUsed);
} else {
m_storage = NULL;
}
}
template<typename ValueType, typename LocalMoveSupport>
Cell *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 cell;
} else if (compareKeys(cellKey, cell->keyLength, key)) {
// Cell matches.
if (overwrite) {
copyOrMoveValue(val, cell->value, LocalMoveSupport());
}
return cell;
} else {
cell = SKT_CIRCULAR_NEXT(cell);
}
}
}
return NULL; // Never reached
}
public:
StringKeyTable(unsigned int initialSize = DEFAULT_SIZE, unsigned int initialStorageSize = DEFAULT_STORAGE_SIZE) {
init(initialSize, initialStorageSize);
}
StringKeyTable(const StringKeyTable &other) {
copyTableFrom(other);
}
~StringKeyTable() {
delete[] m_cells;
free(m_storage);
}
StringKeyTable &operator=(const StringKeyTable &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) {
m_cells = NULL;
} else {
m_cells = new Cell[m_arraySize];
}
m_population = 0;
m_storageSize = initialStorageSize;
if (initialStorageSize == 0) {
m_storage = NULL;
} else {
m_storage = (char *) malloc(initialStorageSize);
}
m_storageUsed = 0;
}
Cell *lookupCell(const HashedStaticString &key) {
assert(!key.empty());
if (m_cells == NULL) {
return NULL;
}
Cell *cell = SKT_FIRST_CELL(key.hash());
while (true) {
const char *cellKey = lookupCellKey(cell);
if (cellKey == NULL) {
// Empty cell found.
return NULL;
} else if (compareKeys(cellKey, cell->keyLength, key)) {
// Non-empty cell found.
return cell;
} else {
// Keep probing.
cell = SKT_CIRCULAR_NEXT(cell);
}
}
}
const Cell *lookupCell(const HashedStaticString &key) const {
assert(!key.empty());
if (m_cells == NULL) {
return NULL;
}
const Cell *cell = SKT_FIRST_CELL(key.hash());
while (true) {
const char *cellKey = lookupCellKey(cell);
if (cellKey == NULL) {
// Empty cell found.
return NULL;
} else if (compareKeys(cellKey, cell->keyLength, key)) {
// Non-empty cell found.
return cell;
} else {
// Keep probing.
cell = SKT_CIRCULAR_NEXT(cell);
}
}
}
bool contains(const HashedStaticString &key) const {
return (lookupCell(key) != NULL);
}
bool lookup(const HashedStaticString &key, const T **result) const {
const Cell * const cell = lookupCell(key);
if (cell != NULL) {
*result = &cell->value;
return true;
} else {
*result = NULL;
return false;
}
}
OXT_FORCE_INLINE
bool lookup(const HashedStaticString &key, T **result) {
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;
if (lookup(key, &result)) {
return *result;
} else {
return T();
}
}
bool lookupRandom(HashedStaticString *key, T **result) {
if (nonEmptyIndex < MAX_ITEMS) {
assert(m_population > 0);
Cell *cell = &m_cells[nonEmptyIndex];
if (key != NULL) {
const char *cellKey = lookupCellKey(cell);
*key = HashedStaticString(cellKey, cell->keyLength, cell->hash);
}
*result = &cell->value;
return true;
} else if (nonEmptyIndex == NON_EMPTY_INDEX_UNKNOWN) {
assert(m_population > 0);
Iterator it(*this);
nonEmptyIndex = *it - &m_cells[0];
if (key != NULL) {
*key = it.getKey();
}
*result = &it.getValue();
return true;
} else {
assert(nonEmptyIndex == NON_EMPTY_INDEX_NONE);
assert(m_population == 0);
*result = NULL;
return false;
}
}
Cell *insert(const HashedStaticString &key, const T &val, bool overwrite = true) {
return realInsert<const T &, SKT_DisableMoveSupport>(key, val, overwrite);
}
Cell *insertByMoving(const HashedStaticString &key, BOOST_RV_REF(T) val, bool overwrite = true) {
return 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.
// Note that this doesn't erase the key from storage.
cell->keyOffset = EMPTY_CELL_KEY_OFFSET;
cell->value = T();
m_population--;
if (m_population == 0) {
nonEmptyIndex = NON_EMPTY_INDEX_NONE;
} else if (&m_cells[nonEmptyIndex] == cell) {
nonEmptyIndex = NON_EMPTY_INDEX_UNKNOWN;
}
return;
}
Cell *ideal = SKT_FIRST_CELL(neighbor->hash);
if (SKT_CIRCULAR_OFFSET(ideal, cell) < SKT_CIRCULAR_OFFSET(ideal, neighbor)) {
// Swap with neighbor, then make neighbor the new cell to remove.
*cell = *neighbor;
cell = neighbor;
}
neighbor = SKT_CIRCULAR_NEXT(neighbor);
}
}
bool erase(const HashedStaticString &key) {
Cell *cell = lookupCell(key);
if (cell != NULL) {
erase(cell);
return true;
} else {
return false;
}
}
/** 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;
m_storageUsed = 0;
nonEmptyIndex = NON_EMPTY_INDEX_NONE;
}
void freeMemory() {
delete[] m_cells;
m_cells = NULL;
m_arraySize = 0;
m_population = 0;
free(m_storage);
m_storage = NULL;
m_storageUsed = 0;
m_storageSize = 0;
nonEmptyIndex = NON_EMPTY_INDEX_NONE;
}
void compact() {
repopulate(upper_power_of_two((m_population * 4 + 3) / 3));
}
unsigned int size() const {
return m_population;
}
unsigned int arraySize() const {
return m_arraySize;
}
bool empty() const {
return m_population == 0;
}
void swap(StringKeyTable<T, MoveSupport> &other) BOOST_NOEXCEPT_OR_NOTHROW {
std::swap(m_cells, other.m_cells);
std::swap(m_arraySize, other.m_arraySize);
std::swap(m_population, other.m_population);
std::swap(nonEmptyIndex, other.nonEmptyIndex);
std::swap(m_storage, other.m_storage);
std::swap(m_storageSize, other.m_storageSize);
std::swap(m_storageUsed, other.m_storageUsed);
}
friend class Iterator;
class Iterator {
private:
StringKeyTable *m_table;
Cell *m_cur;
public:
Iterator(StringKeyTable &table)
: m_table(&table)
{
if (m_table->m_cells != NULL) {
m_cur = &m_table->m_cells[0];
if (m_table->cellIsEmpty(m_cur)) {
next();
}
} else {
m_cur = NULL;
}
}
Cell *next() {
if (m_cur == NULL) {
// Already finished.
return NULL;
}
Cell *end = m_table->m_cells + m_table->m_arraySize;
while (++m_cur != end) {
if (!m_table->cellIsEmpty(m_cur)) {
return m_cur;
}
}
// Finished
return m_cur = NULL;
}
inline Cell *operator*() const {
return m_cur;
}
inline Cell *operator->() const {
return m_cur;
}
HashedStaticString getKey() const {
const char *theKey = m_table->lookupCellKey(m_cur);
return HashedStaticString(theKey, m_cur->keyLength, m_cur->hash);
}
T &getValue() const {
return m_cur->value;
}
};
friend class ConstIterator;
class ConstIterator {
private:
const StringKeyTable *m_table;
const Cell *m_cur;
public:
ConstIterator(const StringKeyTable &table)
: m_table(&table)
{
if (m_table->m_cells != NULL) {
m_cur = &m_table->m_cells[0];
if (m_table->cellIsEmpty(m_cur)) {
next();
}
} else {
m_cur = NULL;
}
}
const Cell *next() {
if (m_cur == NULL) {
// Already finished.
return NULL;
}
const Cell *end = m_table->m_cells + m_table->m_arraySize;
while (++m_cur != end) {
if (!m_table->cellIsEmpty(m_cur)) {
return m_cur;
}
}
// Finished
return m_cur = NULL;
}
inline const Cell *operator*() const {
return m_cur;
}
inline const Cell *operator->() const {
return m_cur;
}
HashedStaticString getKey() const {
const char *theKey = m_table->lookupCellKey(m_cur);
return HashedStaticString(theKey, m_cur->keyLength, m_cur->hash);
}
const T &getValue() const {
return m_cur->value;
}
};
};
} // namespace Passenger
#endif /* _PASSENGER_DATA_STRUCTURES_STRING_KEY_TABLE_H_ */
|