diff options
Diffstat (limited to 'src/mongo/db/concurrency/fast_map_noalloc.h')
| -rw-r--r-- | src/mongo/db/concurrency/fast_map_noalloc.h | 357 |
1 files changed, 171 insertions, 186 deletions
diff --git a/src/mongo/db/concurrency/fast_map_noalloc.h b/src/mongo/db/concurrency/fast_map_noalloc.h index e7077a56222..cc2ccdb64ae 100644 --- a/src/mongo/db/concurrency/fast_map_noalloc.h +++ b/src/mongo/db/concurrency/fast_map_noalloc.h @@ -32,244 +32,229 @@ #include "mongo/util/assert_util.h" namespace mongo { - + +/** + * NOTE: This structure should not be used for anything other than the Lock Manager. + * + * This is a simple implementation of an unordered associative array with minimal + * functionality, used by the lock manager. It keeps a small number of memory entries to store + * values, in order to avoid memory allocations, which dominate the cost of the lock manager + * calls by a wide margin. + * + * This class is not thread-safe. + */ +template <class KeyType, class ValueType, int PreallocCount> +class FastMapNoAlloc { +public: /** - * NOTE: This structure should not be used for anything other than the Lock Manager. - * - * This is a simple implementation of an unordered associative array with minimal - * functionality, used by the lock manager. It keeps a small number of memory entries to store - * values, in order to avoid memory allocations, which dominate the cost of the lock manager - * calls by a wide margin. - * - * This class is not thread-safe. + * Forward-only iterator. Does not synchronize with the underlying collection in any way. + * In other words, do not modify the collection while there is an open iterator on it. */ - template <class KeyType, class ValueType, int PreallocCount> - class FastMapNoAlloc { + template <class MapType, class IteratorValueType> + class IteratorImpl { public: + IteratorImpl(const IteratorImpl& other) : _map(other._map), _idx(other._idx) {} - /** - * Forward-only iterator. Does not synchronize with the underlying collection in any way. - * In other words, do not modify the collection while there is an open iterator on it. - */ - template<class MapType, class IteratorValueType> - class IteratorImpl { - public: - - IteratorImpl(const IteratorImpl& other) - : _map(other._map), - _idx(other._idx) { - - } + // + // Operators + // - // - // Operators - // + bool operator!() const { + return finished(); + } - bool operator!() const { - return finished(); - } + IteratorValueType& operator*() const { + return *objAddr(); + } - IteratorValueType& operator*() const { - return *objAddr(); - } + IteratorValueType* operator->() const { + return objAddr(); + } - IteratorValueType* operator->() const { - return objAddr(); - } + // + // Other methods + // - // - // Other methods - // + /** + * Returns whether the iterator has been exhausted through calls to next. This value + * can be used to determine whether a previous call to find has found something. + */ + bool finished() const { + return (MONGO_unlikely(_idx == PreallocCount)); + } - /** - * Returns whether the iterator has been exhausted through calls to next. This value - * can be used to determine whether a previous call to find has found something. - */ - bool finished() const { - return (MONGO_unlikely(_idx == PreallocCount)); - } + /** + * Returns the address of the object at the current position. Cannot be called with an + * uninitialized iterator, or iterator which has reached the end. + */ + IteratorValueType* objAddr() const { + invariant(!finished()); - /** - * Returns the address of the object at the current position. Cannot be called with an - * uninitialized iterator, or iterator which has reached the end. - */ - IteratorValueType* objAddr() const { - invariant(!finished()); + return &_map._fastAccess[_idx].value; + } - return &_map._fastAccess[_idx].value; - } + /** + * Returns the key of the value at the current position. Cannot be called with an + * uninitialized iterator or iterator which has reached the end. + */ + const KeyType& key() const { + invariant(!finished()); - /** - * Returns the key of the value at the current position. Cannot be called with an - * uninitialized iterator or iterator which has reached the end. - */ - const KeyType& key() const { - invariant(!finished()); + return _map._fastAccess[_idx].key; + } - return _map._fastAccess[_idx].key; - } + /** + * Advances the iterator to the next entry. No particular order of iteration is + * guaranteed. + */ + void next() { + invariant(!finished()); - /** - * Advances the iterator to the next entry. No particular order of iteration is - * guaranteed. - */ - void next() { - invariant(!finished()); - - while (++_idx < PreallocCount) { - if (_map._fastAccess[_idx].inUse) { - return; - } + while (++_idx < PreallocCount) { + if (_map._fastAccess[_idx].inUse) { + return; } } + } - /** - * Removes the element at the current position and moves the iterator to the next, - * which might be the last entry on the map. - */ - void remove() { - invariant(!finished()); - invariant(_map._fastAccess[_idx].inUse); - - _map._fastAccess[_idx].inUse = false; - _map._fastAccessUsedSize--; - - next(); - } - - - private: - - friend class FastMapNoAlloc<KeyType, ValueType, PreallocCount>; + /** + * Removes the element at the current position and moves the iterator to the next, + * which might be the last entry on the map. + */ + void remove() { + invariant(!finished()); + invariant(_map._fastAccess[_idx].inUse); - // Used for iteration of the complete map - IteratorImpl(MapType& map) - : _map(map), - _idx(-1) { + _map._fastAccess[_idx].inUse = false; + _map._fastAccessUsedSize--; - next(); - } + next(); + } - // Used for iterator starting at a position - IteratorImpl(MapType& map, int idx) - : _map(map), - _idx(idx) { - invariant(_idx >= 0); - } + private: + friend class FastMapNoAlloc<KeyType, ValueType, PreallocCount>; - // Used for iteration starting at a particular key - IteratorImpl(MapType& map, const KeyType& key) - : _map(map), - _idx(0) { + // Used for iteration of the complete map + IteratorImpl(MapType& map) : _map(map), _idx(-1) { + next(); + } - while (_idx < PreallocCount) { - if (_map._fastAccess[_idx].inUse && (_map._fastAccess[_idx].key == key)) { - return; - } + // Used for iterator starting at a position + IteratorImpl(MapType& map, int idx) : _map(map), _idx(idx) { + invariant(_idx >= 0); + } - ++_idx; + // Used for iteration starting at a particular key + IteratorImpl(MapType& map, const KeyType& key) : _map(map), _idx(0) { + while (_idx < PreallocCount) { + if (_map._fastAccess[_idx].inUse && (_map._fastAccess[_idx].key == key)) { + return; } - } + ++_idx; + } + } - // The map being iterated on - MapType& _map; - - // Index to the current entry being iterated - int _idx; - }; + // The map being iterated on + MapType& _map; - typedef IteratorImpl<FastMapNoAlloc<KeyType, ValueType, PreallocCount>, - ValueType> Iterator; + // Index to the current entry being iterated + int _idx; + }; - typedef IteratorImpl<const FastMapNoAlloc<KeyType, ValueType, PreallocCount>, - const ValueType> ConstIterator; + typedef IteratorImpl<FastMapNoAlloc<KeyType, ValueType, PreallocCount>, ValueType> Iterator; - FastMapNoAlloc() : _fastAccess(), - _fastAccessUsedSize(0) { } + typedef IteratorImpl<const FastMapNoAlloc<KeyType, ValueType, PreallocCount>, const ValueType> + ConstIterator; - /** - * Inserts the specified entry in the map and returns a reference to the memory for the - * entry just inserted. - */ - Iterator insert(const KeyType& key) { - // Find the first unused slot. This could probably be even further optimized by adding - // a field pointing to the first unused location. - int idx = 0; - for (; _fastAccess[idx].inUse; idx++); - invariant(idx < PreallocCount); + FastMapNoAlloc() : _fastAccess(), _fastAccessUsedSize(0) {} - _fastAccess[idx].inUse = true; - _fastAccess[idx].key = key; - _fastAccessUsedSize++; + /** + * Inserts the specified entry in the map and returns a reference to the memory for the + * entry just inserted. + */ + Iterator insert(const KeyType& key) { + // Find the first unused slot. This could probably be even further optimized by adding + // a field pointing to the first unused location. + int idx = 0; + for (; _fastAccess[idx].inUse; idx++) + ; - return Iterator(*this, idx); - } + invariant(idx < PreallocCount); - /** - * Returns an iterator to the first element in the map. - */ - Iterator begin() { - return Iterator(*this); - } + _fastAccess[idx].inUse = true; + _fastAccess[idx].key = key; + _fastAccessUsedSize++; - ConstIterator begin() const { - return ConstIterator(*this); - } + return Iterator(*this, idx); + } - /** - * Returns an iterator pointing to the first position, which has entry with the specified - * key. Before dereferencing the returned iterator, it should be checked for validity using - * the finished() method or the ! operator. If no element was found, finished() will return - * false. - * - * While it is allowed to call next() on the returned iterator, this is not very useful, - * because the container is not ordered. - */ - Iterator find(const KeyType& key) { - return Iterator(*this, key); - } + /** + * Returns an iterator to the first element in the map. + */ + Iterator begin() { + return Iterator(*this); + } - ConstIterator find(const KeyType& key) const { - return ConstIterator(*this, key); - } + ConstIterator begin() const { + return ConstIterator(*this); + } - int size() const { return _fastAccessUsedSize; } - bool empty() const { return (_fastAccessUsedSize == 0); } + /** + * Returns an iterator pointing to the first position, which has entry with the specified + * key. Before dereferencing the returned iterator, it should be checked for validity using + * the finished() method or the ! operator. If no element was found, finished() will return + * false. + * + * While it is allowed to call next() on the returned iterator, this is not very useful, + * because the container is not ordered. + */ + Iterator find(const KeyType& key) { + return Iterator(*this, key); + } - private: + ConstIterator find(const KeyType& key) const { + return ConstIterator(*this, key); + } - // Empty and very large maps do not make sense since there will be no performance gain, so - // disallow them. - BOOST_STATIC_ASSERT(PreallocCount > 0); - BOOST_STATIC_ASSERT(PreallocCount < 32); + int size() const { + return _fastAccessUsedSize; + } + bool empty() const { + return (_fastAccessUsedSize == 0); + } - // Iterator accesses the map directly - friend class IteratorImpl<FastMapNoAlloc<KeyType, ValueType, PreallocCount>, - ValueType>; +private: + // Empty and very large maps do not make sense since there will be no performance gain, so + // disallow them. + BOOST_STATIC_ASSERT(PreallocCount > 0); + BOOST_STATIC_ASSERT(PreallocCount < 32); - friend class IteratorImpl<const FastMapNoAlloc<KeyType, ValueType, PreallocCount>, - const ValueType>; + // Iterator accesses the map directly + friend class IteratorImpl<FastMapNoAlloc<KeyType, ValueType, PreallocCount>, ValueType>; + friend class IteratorImpl<const FastMapNoAlloc<KeyType, ValueType, PreallocCount>, + const ValueType>; - struct PreallocEntry { - PreallocEntry() : inUse(false) { } - bool inUse; + struct PreallocEntry { + PreallocEntry() : inUse(false) {} - KeyType key; - ValueType value; - }; + bool inUse; - // Pre-allocated memory for entries - PreallocEntry _fastAccess[PreallocCount]; - int _fastAccessUsedSize; + KeyType key; + ValueType value; }; -} // namespace mongo + // Pre-allocated memory for entries + PreallocEntry _fastAccess[PreallocCount]; + int _fastAccessUsedSize; +}; + +} // namespace mongo |