diff options
Diffstat (limited to 'src/mongo/util/unordered_fast_key_table_internal.h')
| -rw-r--r-- | src/mongo/util/unordered_fast_key_table_internal.h | 335 |
1 files changed, 161 insertions, 174 deletions
diff --git a/src/mongo/util/unordered_fast_key_table_internal.h b/src/mongo/util/unordered_fast_key_table_internal.h index e9a31f8f469..bddca264a9f 100644 --- a/src/mongo/util/unordered_fast_key_table_internal.h +++ b/src/mongo/util/unordered_fast_key_table_internal.h @@ -31,205 +31,192 @@ #include "mongo/util/assert_util.h" namespace mongo { - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::Area(unsigned capacity, - double maxProbeRatio) - : _capacity( capacity ), - _maxProbe( static_cast<unsigned>( capacity * maxProbeRatio ) ), - _entries( new Entry[_capacity] ) { +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::Area(unsigned capacity, + double maxProbeRatio) + : _capacity(capacity), + _maxProbe(static_cast<unsigned>(capacity * maxProbeRatio)), + _entries(new Entry[_capacity]) {} + +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::Area(const Area& other) + : _capacity(other._capacity), _maxProbe(other._maxProbe), _entries(new Entry[_capacity]) { + for (unsigned i = 0; i < _capacity; i++) { + _entries[i] = other._entries[i]; } +} - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::Area(const Area& other ) - : _capacity( other._capacity ), - _maxProbe( other._maxProbe ), - _entries( new Entry[_capacity] ) { - for ( unsigned i = 0; i < _capacity; i++ ) { - _entries[i] = other._entries[i]; +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline int UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::find( + const K_L& key, size_t hash, int* firstEmpty, const UnorderedFastKeyTable& sm) const { + if (firstEmpty) + *firstEmpty = -1; + + for (unsigned probe = 0; probe < _maxProbe; probe++) { + unsigned pos = (hash + probe) % _capacity; + + if (!_entries[pos].used) { + // space is empty + if (firstEmpty && *firstEmpty == -1) + *firstEmpty = pos; + if (!_entries[pos].everUsed) + return -1; + continue; } - } - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline int UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::find( - const K_L& key, - size_t hash, - int* firstEmpty, - const UnorderedFastKeyTable& sm ) const { - if ( firstEmpty ) - *firstEmpty = -1; - - for ( unsigned probe = 0; probe < _maxProbe; probe++ ) { - unsigned pos = (hash + probe) % _capacity; - - if ( ! _entries[pos].used ) { - // space is empty - if ( firstEmpty && *firstEmpty == -1 ) - *firstEmpty = pos; - if ( ! _entries[pos].everUsed ) - return -1; - continue; - } - - if ( _entries[pos].curHash != hash ) { - // space has something else - continue; - } - - if ( ! sm._equals(key, sm._convertor( _entries[pos].data.first ) ) ) { - // hashes match - // strings are not equals - continue; - } - - // hashes and strings are equal - // yay! - return pos; + if (_entries[pos].curHash != hash) { + // space has something else + continue; } - return -1; - } - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline bool UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::transfer( - Area* newArea, - const UnorderedFastKeyTable& sm) const { - for ( unsigned i = 0; i < _capacity; i++ ) { - if ( ! _entries[i].used ) - continue; - - int firstEmpty = -1; - int loc = newArea->find( sm._convertor( _entries[i].data.first ), - _entries[i].curHash, - &firstEmpty, - sm ); - - verify( loc == -1 ); - if ( firstEmpty < 0 ) { - return false; - } - - newArea->_entries[firstEmpty] = _entries[i]; + if (!sm._equals(key, sm._convertor(_entries[pos].data.first))) { + // hashes match + // strings are not equals + continue; } - return true; - } - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::UnorderedFastKeyTable( - unsigned startingCapacity, - double maxProbeRatio) - : _maxProbeRatio( maxProbeRatio ), _area( startingCapacity, maxProbeRatio ) { - _size = 0; + // hashes and strings are equal + // yay! + return pos; } + return -1; +} - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::UnorderedFastKeyTable( - const UnorderedFastKeyTable& other ) - : _size( other._size ), - _maxProbeRatio( other._maxProbeRatio ), - _area( other._area ), - _hash( other._hash ), - _equals( other._equals ), - _convertor( other._convertor ), - _convertorOther( other._convertorOther ) { - } +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline bool UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::transfer( + Area* newArea, const UnorderedFastKeyTable& sm) const { + for (unsigned i = 0; i < _capacity; i++) { + if (!_entries[i].used) + continue; - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::copyTo( UnorderedFastKeyTable* out ) const { - out->_size = _size; - out->_maxProbeRatio = _maxProbeRatio; - Area x( _area ); - out->_area.swap( &x ); - } + int firstEmpty = -1; + int loc = newArea->find( + sm._convertor(_entries[i].data.first), _entries[i].curHash, &firstEmpty, sm); - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline V& UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::get( const K_L& key ) { - - const size_t hash = _hash( key ); - - for ( int numGrowTries = 0; numGrowTries < 5; numGrowTries++ ) { - int firstEmpty = -1; - int pos = _area.find( key, hash, &firstEmpty, *this ); - if ( pos >= 0 ) - return _area._entries[pos].data.second; - - // key not in map - // need to add - if ( firstEmpty >= 0 ) { - _size++; - _area._entries[firstEmpty].used = true; - _area._entries[firstEmpty].everUsed = true; - _area._entries[firstEmpty].curHash = hash; - _area._entries[firstEmpty].data.first = _convertorOther(key); - return _area._entries[firstEmpty].data.second; - } - - // no space left in map - _grow(); + verify(loc == -1); + if (firstEmpty < 0) { + return false; } - msgasserted( 16471, "UnorderedFastKeyTable couldn't add entry after growing many times" ); + + newArea->_entries[firstEmpty] = _entries[i]; } + return true; +} - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline size_t UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::erase( const K_L& key ) { +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::UnorderedFastKeyTable( + unsigned startingCapacity, double maxProbeRatio) + : _maxProbeRatio(maxProbeRatio), _area(startingCapacity, maxProbeRatio) { + _size = 0; +} - const size_t hash = _hash( key ); - int pos = _area.find( key, hash, NULL, *this ); +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::UnorderedFastKeyTable( + const UnorderedFastKeyTable& other) + : _size(other._size), + _maxProbeRatio(other._maxProbeRatio), + _area(other._area), + _hash(other._hash), + _equals(other._equals), + _convertor(other._convertor), + _convertorOther(other._convertorOther) {} + +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::copyTo( + UnorderedFastKeyTable* out) const { + out->_size = _size; + out->_maxProbeRatio = _maxProbeRatio; + Area x(_area); + out->_area.swap(&x); +} - if ( pos < 0 ) - return 0; +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline V& UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::get(const K_L& key) { + const size_t hash = _hash(key); + + for (int numGrowTries = 0; numGrowTries < 5; numGrowTries++) { + int firstEmpty = -1; + int pos = _area.find(key, hash, &firstEmpty, *this); + if (pos >= 0) + return _area._entries[pos].data.second; + + // key not in map + // need to add + if (firstEmpty >= 0) { + _size++; + _area._entries[firstEmpty].used = true; + _area._entries[firstEmpty].everUsed = true; + _area._entries[firstEmpty].curHash = hash; + _area._entries[firstEmpty].data.first = _convertorOther(key); + return _area._entries[firstEmpty].data.second; + } - --_size; - _area._entries[pos].used = false; - _area._entries[pos].data.second = V(); - return 1; + // no space left in map + _grow(); } + msgasserted(16471, "UnorderedFastKeyTable couldn't add entry after growing many times"); +} - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::erase( const_iterator it ) { - dassert(it._position >= 0); - dassert(it._area == &_area); +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline size_t UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::erase(const K_L& key) { + const size_t hash = _hash(key); + int pos = _area.find(key, hash, NULL, *this); - --_size; - _area._entries[it._position].used = false; - _area._entries[it._position].data.second = V(); - } + if (pos < 0) + return 0; - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::_grow() { - unsigned capacity = _area._capacity; - for ( int numGrowTries = 0; numGrowTries < 5; numGrowTries++ ) { - capacity *= 2; - Area newArea( capacity, _maxProbeRatio ); - bool success = _area.transfer( &newArea, *this ); - if ( !success ) { - continue; - } - _area.swap( &newArea ); - return; - } - msgasserted( 16845, - "UnorderedFastKeyTable::_grow couldn't add entry after growing many times" ); - } + --_size; + _area._entries[pos].used = false; + _area._entries[pos].data.second = V(); + return 1; +} - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator - UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::find( const K_L& key ) const { - if ( _size == 0 ) - return const_iterator(); - int pos = _area.find( key, _hash(key), 0, *this ); - if ( pos < 0 ) - return const_iterator(); - return const_iterator( &_area, pos ); +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::erase(const_iterator it) { + dassert(it._position >= 0); + dassert(it._area == &_area); + + --_size; + _area._entries[it._position].used = false; + _area._entries[it._position].data.second = V(); +} + +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::_grow() { + unsigned capacity = _area._capacity; + for (int numGrowTries = 0; numGrowTries < 5; numGrowTries++) { + capacity *= 2; + Area newArea(capacity, _maxProbeRatio); + bool success = _area.transfer(&newArea, *this); + if (!success) { + continue; + } + _area.swap(&newArea); + return; } + msgasserted(16845, "UnorderedFastKeyTable::_grow couldn't add entry after growing many times"); +} - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator - UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::end() const { +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator +UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::find(const K_L& key) const { + if (_size == 0) return const_iterator(); - } + int pos = _area.find(key, _hash(key), 0, *this); + if (pos < 0) + return const_iterator(); + return const_iterator(&_area, pos); +} - template< typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS > - inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator - UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::begin() const { - return const_iterator( &_area ); - } +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator +UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::end() const { + return const_iterator(); +} + +template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS> +inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator +UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::begin() const { + return const_iterator(&_area); +} } |