summaryrefslogtreecommitdiff
path: root/src/mongo/util/unordered_fast_key_table.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/mongo/util/unordered_fast_key_table.h')
-rw-r--r--src/mongo/util/unordered_fast_key_table.h310
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"
-
View Lorry Controller Status