diff options
Diffstat (limited to 'src/mongo/util/unordered_fast_key_table.h')
-rw-r--r-- | src/mongo/util/unordered_fast_key_table.h | 310 |
1 files changed, 161 insertions, 149 deletions
diff --git a/src/mongo/util/unordered_fast_key_table.h b/src/mongo/util/unordered_fast_key_table.h index 786747bcecb..781cc1e3fe1 100644 --- a/src/mongo/util/unordered_fast_key_table.h +++ b/src/mongo/util/unordered_fast_key_table.h @@ -35,193 +35,205 @@ namespace mongo { - template<typename K_L, typename K_S> - struct UnorderedFastKeyTable_LS_C { - K_S operator()( const K_L& a ) const { - return K_S(a); - } +template <typename K_L, typename K_S> +struct UnorderedFastKeyTable_LS_C { + K_S operator()(const K_L& a) const { + return K_S(a); + } +}; + +template <typename K_L, // key lookup + typename K_S, // key storage + typename V, // value + typename H, // hash of K_L + typename E, // equal of K_L + typename C, // convertor from K_S -> K_L + typename C_LS = UnorderedFastKeyTable_LS_C<K_L, K_S> // convertor from K_L -> K_S + > +class UnorderedFastKeyTable { +public: + typedef std::pair<K_S, V> value_type; + typedef K_L key_type; + typedef V mapped_type; + +private: + struct Entry { + Entry() : used(false), everUsed(false) {} + + bool used; + bool everUsed; + size_t curHash; + value_type data; }; - template< typename K_L, // key lookup - typename K_S, // key storage - typename V, // value - typename H , // hash of K_L - typename E, // equal of K_L - typename C, // convertor from K_S -> K_L - typename C_LS=UnorderedFastKeyTable_LS_C<K_L,K_S> // convertor from K_L -> K_S - > - class UnorderedFastKeyTable { - public: - typedef std::pair<K_S, V> value_type; - typedef K_L key_type; - typedef V mapped_type; + struct Area { + Area(unsigned capacity, double maxProbeRatio); + Area(const Area& other); - private: - struct Entry { - Entry() - : used( false ), everUsed( false ) { - } + int find(const K_L& key, + size_t hash, + int* firstEmpty, + const UnorderedFastKeyTable& sm) const; - bool used; - bool everUsed; - size_t curHash; - value_type data; - }; + bool transfer(Area* newArea, const UnorderedFastKeyTable& sm) const; - struct Area { - Area( unsigned capacity, double maxProbeRatio ); - Area( const Area& other ); + void swap(Area* other) { + using std::swap; + swap(_capacity, other->_capacity); + swap(_maxProbe, other->_maxProbe); + swap(_entries, other->_entries); + } - int find( const K_L& key, size_t hash, int* firstEmpty, const UnorderedFastKeyTable& sm ) const; + unsigned _capacity; + unsigned _maxProbe; + std::unique_ptr<Entry[]> _entries; + }; - bool transfer( Area* newArea, const UnorderedFastKeyTable& sm ) const; +public: + static const unsigned DEFAULT_STARTING_CAPACITY = 20; - void swap( Area* other ) { - using std::swap; - swap( _capacity, other->_capacity ); - swap( _maxProbe, other->_maxProbe ); - swap( _entries, other->_entries ); - } + /** + * @param startingCapacity how many buckets should exist on initial creation + * DEFAULT_STARTING_CAPACITY + * @param maxProbeRatio the percentage of buckets we're willing to probe + * no defined default as you can't have a static const double on windows + */ + UnorderedFastKeyTable(unsigned startingCapacity = DEFAULT_STARTING_CAPACITY, + double maxProbeRatio = 0.05); - unsigned _capacity; - unsigned _maxProbe; - std::unique_ptr<Entry[]> _entries; - }; + UnorderedFastKeyTable(const UnorderedFastKeyTable& other); - public: - static const unsigned DEFAULT_STARTING_CAPACITY = 20; + UnorderedFastKeyTable& operator=(const UnorderedFastKeyTable& other) { + other.copyTo(this); + return *this; + } - /** - * @param startingCapacity how many buckets should exist on initial creation - * DEFAULT_STARTING_CAPACITY - * @param maxProbeRatio the percentage of buckets we're willing to probe - * no defined default as you can't have a static const double on windows - */ - UnorderedFastKeyTable( unsigned startingCapacity = DEFAULT_STARTING_CAPACITY, - double maxProbeRatio = 0.05 ); + void copyTo(UnorderedFastKeyTable* out) const; - UnorderedFastKeyTable( const UnorderedFastKeyTable& other ); + /** + * @return number of elements in map + */ + size_t size() const { + return _size; + } - UnorderedFastKeyTable& operator=( const UnorderedFastKeyTable& other ) { - other.copyTo( this ); - return *this; - } + bool empty() const { + return _size == 0; + } - void copyTo( UnorderedFastKeyTable* out ) const; + /* + * @return storage space + */ + size_t capacity() const { + return _area._capacity; + } - /** - * @return number of elements in map - */ - size_t size() const { return _size; } + V& operator[](const K_L& key) { + return get(key); + } - bool empty() const { return _size == 0; } + V& get(const K_L& key); - /* - * @return storage space - */ - size_t capacity() const { return _area._capacity; } + /** + * @return number of elements removed + */ + size_t erase(const K_L& key); - V& operator[]( const K_L& key ) { return get( key ); } + class const_iterator { + friend class UnorderedFastKeyTable; - V& get( const K_L& key ); + public: + const_iterator() { + _position = -1; + } + const_iterator(const Area* area) { + _area = area; + _position = 0; + _max = _area->_capacity - 1; + _skip(); + } + const_iterator(const Area* area, int pos) { + _area = area; + _position = pos; + _max = pos; + } - /** - * @return number of elements removed - */ - size_t erase( const K_L& key ); + const value_type* operator->() const { + return &_area->_entries[_position].data; + } - class const_iterator { - friend class UnorderedFastKeyTable; + const value_type& operator*() const { + return _area->_entries[_position].data; + } - public: - const_iterator() { _position = -1; } - const_iterator( const Area* area ) { - _area = area; - _position = 0; - _max = _area->_capacity - 1; + const_iterator operator++() { + if (_position < 0) + return *this; + _position++; + if (_position > _max) + _position = -1; + else _skip(); - } - const_iterator( const Area* area, int pos ) { - _area = area; - _position = pos; - _max = pos; - } - - const value_type* operator->() const { return &_area->_entries[_position].data; } + return *this; + } - const value_type& operator*() const { return _area->_entries[_position].data; } + bool operator==(const const_iterator& other) const { + return _position == other._position; + } + bool operator!=(const const_iterator& other) const { + return _position != other._position; + } - const_iterator operator++() { - if ( _position < 0 ) - return *this; - _position++; - if ( _position > _max ) + private: + void _skip() { + while (true) { + if (_area->_entries[_position].used) + break; + if (_position >= _max) { _position = -1; - else - _skip(); - return *this; - } - - bool operator==( const const_iterator& other ) const { - return _position == other._position; - } - bool operator!=( const const_iterator& other ) const { - return _position != other._position; - } - - private: - - void _skip() { - while ( true ) { - if ( _area->_entries[_position].used ) - break; - if ( _position >= _max ) { - _position = -1; - break; - } - ++_position; + break; } + ++_position; } + } - const Area* _area; - int _position; - int _max; // inclusive - }; - - void erase( const_iterator it ); + const Area* _area; + int _position; + int _max; // inclusive + }; - /** - * @return either a one-shot iterator with the key, or end() - */ - const_iterator find( const K_L& key ) const; + void erase(const_iterator it); - const_iterator begin() const; + /** + * @return either a one-shot iterator with the key, or end() + */ + const_iterator find(const K_L& key) const; - const_iterator end() const; + const_iterator begin() const; - private: - /* - * @param firstEmpty, if we return -1, and firstEmpty != NULL, - * this will be set to the first empty bucket we found - * @retrun offset into _entries or -1 if not there - */ - int _find( const K_L& key, int hash, int* firstEmpty ) const; + const_iterator end() const; - void _grow(); +private: + /* + * @param firstEmpty, if we return -1, and firstEmpty != NULL, + * this will be set to the first empty bucket we found + * @retrun offset into _entries or -1 if not there + */ + int _find(const K_L& key, int hash, int* firstEmpty) const; - // ---- + void _grow(); - size_t _size; - double _maxProbeRatio; - Area _area; + // ---- - H _hash; - E _equals; - C _convertor; - C_LS _convertorOther; - }; + size_t _size; + double _maxProbeRatio; + Area _area; + H _hash; + E _equals; + C _convertor; + C_LS _convertorOther; +}; } #include "mongo/util/unordered_fast_key_table_internal.h" - |