fast_map_noalloc.h

Go to the documentation of this file.

#pragma once

#include <deque>

#include "mongo/base/static_assert.h"
#include "mongo/util/assert_util.h"

namespace mongo {

template <class KeyType, class ValueType>
class FastMapNoAlloc {
private:
    struct PreallocEntry {
        bool inUse = false;

        KeyType key;
        ValueType value;
    };

    typedef typename std::deque<PreallocEntry> Container;

    typedef typename Container::size_type size_type;

    typedef typename Container::iterator map_iterator;

    typedef typename Container::const_iterator const_map_iterator;


    template <class MapType, class IteratorValueType, class IteratorType>
    class IteratorImpl {
    public:
        //
        // Operators
        //

        operator bool() const {
            return !finished();
        }

        IteratorValueType& operator*() const {
            return *objAddr();
        }

        IteratorValueType* operator->() const {
            return objAddr();
        }


        //
        // Other methods
        //

        bool finished() const {
            return (_it == _map._fastAccess.end());
        }

        IteratorValueType* objAddr() const {
            invariant(!finished());

            return &(_it->value);
        }

        const KeyType& key() const {
            invariant(!finished());

            return _it->key;
        }

        void next() {
            invariant(!finished());
            while (++_it != _map._fastAccess.end()) {
                if (_it->inUse) {
                    return;
                }
            }
        }

        void remove() {
            invariant(!finished());
            invariant(_it->inUse);

            _it->inUse = false;
            _map._fastAccessUsedSize--;

            next();
        }


    private:
        friend class FastMapNoAlloc<KeyType, ValueType>;

        // Used for iteration of the complete map
        IteratorImpl(MapType& map) : _map(map), _it(map._fastAccess.begin()) {
            while (_it != _map._fastAccess.end()) {
                if (_it->inUse) {
                    return;
                }
                ++_it;
            }
        }

        // Used for iterator starting at a position
        IteratorImpl(MapType& map, IteratorType it) : _map(map), _it(std::move(it)) {
            invariant(_it != _map._fastAccess.end());
        }

        // Used for iteration starting at a particular key
        IteratorImpl(MapType& map, const KeyType& key) : _map(map), _it(_map._fastAccess.begin()) {
            while (_it != _map._fastAccess.end()) {
                if (_it->inUse && _it->key == key) {
                    return;
                }

                ++_it;
            }
        }


        // The map being iterated on
        MapType& _map;

        // Iterator on the map
        IteratorType _it;
    };

public:
    typedef IteratorImpl<FastMapNoAlloc<KeyType, ValueType>, ValueType, map_iterator> Iterator;

    typedef IteratorImpl<const FastMapNoAlloc<KeyType, ValueType>,
                         const ValueType,
                         const_map_iterator>
        ConstIterator;

    FastMapNoAlloc() : _fastAccessUsedSize(0) {}

    Iterator insert(const KeyType& key) {
        if (_fastAccessUsedSize == _fastAccess.size()) {
            // Place the new entry in the front so the below map iteration is faster.
            _fastAccess.emplace_front();
        }

        map_iterator it = _fastAccess.begin();
        while (it != _fastAccess.end() && it->inUse) {
            ++it;
        }

        invariant(it != _fastAccess.end() && !(it->inUse));

        it->inUse = true;
        it->key = key;
        ++_fastAccessUsedSize;

        return Iterator(*this, it);
    }

    Iterator begin() {
        return Iterator(*this);
    }

    ConstIterator begin() const {
        return ConstIterator(*this);
    }

    Iterator find(const KeyType& key) {
        return Iterator(*this, key);
    }

    ConstIterator find(const KeyType& key) const {
        return ConstIterator(*this, key);
    }

    size_t size() const {
        return _fastAccessUsedSize;
    }
    bool empty() const {
        return (_fastAccessUsedSize == 0);
    }

private:
    // We chose a deque data structure because it maintains the validity of existing
    // pointers/references to its contents when it allocates more memory. Deque also gives us O(1)
    // emplace_front() in insert().
    std::deque<PreallocEntry> _fastAccess;

    size_type _fastAccessUsedSize;
};

}  // namespace mongo