denseHashMap.h

Go to the documentation of this file.

//
// Copyright 2016 Pixar
//
// Licensed under the terms set forth in the LICENSE.txt file available at
// https://openusd.org/license.
//
#ifndef PXR_BASE_TF_DENSE_HASH_MAP_H
#define PXR_BASE_TF_DENSE_HASH_MAP_H
 
 
#include "pxr/pxr.h"
#include "pxr/base/arch/attributes.h"
#include "pxr/base/tf/hashmap.h"
 
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>
 
PXR_NAMESPACE_OPEN_SCOPE
 
template <
    class    Key,
    class    Data,
    class    HashFn,
    class    EqualKey  = std::equal_to<Key>,
    unsigned Threshold = 128
>
 
class TfDenseHashMap
{
public:
 
    using key_type = Key;
    using mapped_type = Data;
    using value_type = std::pair<const Key, Data>;
    using pointer = value_type*;
    using const_pointer = const value_type*;
 
 
private:
 
    // This helper implements a std::pair with an assignment operator that
    // uses placement new instead of assignment.  The benefit here is that 
    // the two elements of the pair may be const.
    //
    struct _InternalValueType 
    {
        _InternalValueType() {}
 
        _InternalValueType(const Key &k, const Data &d)
        :   _value(k, d) {}
 
        _InternalValueType &operator=(const _InternalValueType &rhs) {
 
            if (this != &rhs) {
                // Since value_type's first member is const we need to 
                // use placement new to put the new element in place.  Just
                // make sure we destruct the element we are about to overwrite.
                _value.value_type::~value_type();
                new (&_value) value_type(rhs.GetValue());
            }
 
            return *this;
        }
 
        value_type &GetValue() {
            return _value;
        }
 
        const value_type &GetValue() const {
            return _value;
        }
 
        void swap(_InternalValueType &rhs) {
            using std::swap;
 
            // We do this in order to take advantage of a potentially fast
            // swap implementation.
            Key tmp = _value.first;
 
            _value.first.Key::~Key();
            new (const_cast<Key *>(&_value.first)) Key(rhs._value.first);
 
            rhs._value.first.Key::~Key();
            new (const_cast<Key *>(&rhs._value.first)) Key(tmp);
 
            swap(_value.second, rhs._value.second);
        }
 
    private:
 
        // Data hold by _InternalValueType.  Note that the key portion of
        // value_type maybe const.
        value_type _value;
    };
 
    // The vector type holding all data for this dense hash map.
    typedef std::vector<_InternalValueType> _Vector;
 
    // The hash map used when the map holds more than Threshold elements.
    typedef TfHashMap<Key, size_t, HashFn, EqualKey> _HashMap;
 
    // Note that we don't just use _Vector::iterator for accessing elements
    // of the TfDenseHashMap.  This is because the vector's iterator would
    // expose the _InternalValueType _including_ its assignment operator
    // that allows overwriting keys.
    //
    // Clearly not a good thing.
    //
    // Therefore we create an iterator that uses the map's value_type as
    // externally visible type.
    //
    template <class ElementType, class UnderlyingIterator>
    class _IteratorBase
    {
    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type = ElementType;
        using reference = ElementType&;
        using pointer = ElementType*;
        using difference_type = typename UnderlyingIterator::difference_type;
 
        // Empty ctor.
        _IteratorBase() = default;
 
        // Allow conversion of an iterator to a const_iterator.
        template<class OtherIteratorType>
        _IteratorBase(const OtherIteratorType &rhs)
        :   _iter(rhs._GetUnderlyingIterator()) {}
 
        reference operator*() const { return dereference(); }
        pointer operator->() const { return &(dereference()); }
 
        _IteratorBase& operator++() {
            increment();
            return *this;
        }
 
        _IteratorBase& operator--() {
            decrement();
            return *this;
        }
 
        _IteratorBase operator++(int) {
            _IteratorBase result(*this);
            increment();
            return result;
        }
 
        _IteratorBase operator--(int) {
            _IteratorBase result(*this);
            decrement();
            return result;
        }
 
        template <class OtherIteratorType>
        bool operator==(const OtherIteratorType& other) const {
            return equal(other);
        }
 
        template <class OtherIteratorType>
        bool operator!=(const OtherIteratorType& other) const {
            return !equal(other);
        }
 
    private:
 
        friend class TfDenseHashMap;
 
        // Ctor from an underlying iterator.
        _IteratorBase(const UnderlyingIterator &iter)
        :   _iter(iter) {}
 
        template<class OtherIteratorType>
        bool equal(const OtherIteratorType &rhs) const {
            return _iter == rhs._iter;
        }
        
        void increment() {
            ++_iter;
        }
 
        void decrement() {
            --_iter;
        }
        
        ElementType &dereference() const {
            // The dereference() method accesses the correct value_type (ie.
            // the one with potentially const key_type.  This way, clients don't
            // see the assignment operator of _InternalValueType.
            return _iter->GetValue();
        }
 
        UnderlyingIterator _GetUnderlyingIterator() const {
            return _iter;
        }
 
    private:
        
        UnderlyingIterator _iter;
    };
 
 
public:
 
    typedef
        _IteratorBase<value_type, typename _Vector::iterator>
        iterator; 
 
    typedef
        _IteratorBase<const value_type, typename _Vector::const_iterator>
        const_iterator; 
 
    typedef std::pair<iterator, bool> insert_result;
 
public:
 
    explicit TfDenseHashMap(
        const HashFn   &hashFn   = HashFn(),
        const EqualKey &equalKey = EqualKey())
    {
        _hash() = hashFn;
        _equ()  = equalKey;
    }
 
    template <class Iterator>
    TfDenseHashMap(Iterator begin, Iterator end) {
        insert(begin, end);
    }
 
    TfDenseHashMap(std::initializer_list<value_type> l) {
        insert(l.begin(), l.end());
    }
 
    TfDenseHashMap(const TfDenseHashMap &rhs)
    :   _storage(rhs._storage) {
        if (rhs._h) {
            _h = std::make_unique<_HashMap>(*rhs._h);
        }
    }
    TfDenseHashMap(TfDenseHashMap &&rhs) = default;
 
    TfDenseHashMap &operator=(const TfDenseHashMap &rhs) {
        if (this != &rhs) {
            TfDenseHashMap temp(rhs);
            temp.swap(*this);
        }
        return *this;
    }
 
    TfDenseHashMap &operator=(TfDenseHashMap &&rhs) = default;
 
    TfDenseHashMap &operator=(std::initializer_list<value_type> l) {
        clear();
        insert(l.begin(), l.end());
        return *this;
    }
 
    bool operator==(const TfDenseHashMap &rhs) const {
 
        if (size() != rhs.size())
            return false;
 
        //XXX: Should we compare the HashFn and EqualKey too?
        const_iterator tend = end(), rend = rhs.end();
 
        for(const_iterator iter = begin(); iter != tend; ++iter) {
            const_iterator riter = rhs.find(iter->first);
            if (riter == rend)
                return false;
            if (iter->second != riter->second)
                return false;
        }
 
        return true;
    }
 
    bool operator!=(const TfDenseHashMap &rhs) const {
        return !(*this == rhs);
    }
 
    void clear() {
        _vec().clear();
        _h.reset();
    }
 
    void swap(TfDenseHashMap &rhs) {
        _storage.swap(rhs._storage);
        _h.swap(rhs._h);
    }
 
    bool empty() const {
        return _vec().empty();
    }
 
    size_t size() const {
        return _vec().size();
    }
 
    iterator begin() {
        return _vec().begin();
    }
 
    iterator end() {
        return _vec().end();
    }
 
    const_iterator begin() const {
        return _vec().begin();
    }
    
    const_iterator end() const {
        return _vec().end();
    }
 
    const_iterator cbegin() const {
        return _vec().cbegin();
    }
    
    const_iterator cend() const {
        return _vec().cbegin();
    }
 
    pointer data() {
        return _vec().empty() ? nullptr : &_vec().front().GetValue();
    }
 
    const_pointer data() const {
        return _vec().empty() ? nullptr : &_vec().front().GetValue();
    }
 
    const_pointer cdata() const {
        return _vec().empty() ? nullptr : &_vec().front().GetValue();
    }
 
    iterator find(const key_type &k) {
        if (_h) {
            typename _HashMap::const_iterator iter = _h->find(k);
            if (iter == _h->end())
                return end();
 
            return _vec().begin() + iter->second;
        } else {
            return _FindInVec(k);
        }
    }
 
    const_iterator find(const key_type &k) const {
        if (_h) {
            typename _HashMap::const_iterator iter = _h->find(k);
            if (iter == _h->end())
                return end();
 
            return _vec().begin() + iter->second;
        } else {
            return _FindInVec(k);
        }
    }
 
    size_t count(const key_type &k) const {
        return find(k) != end();
    }
 
    insert_result insert(const value_type &v) {
        if (_h) {
            // Attempt to insert the new index.  If this fails, we can't insert
            // v.
            std::pair<typename _HashMap::iterator, bool> res =
                _h->insert(std::make_pair(v.first, size()));
 
            if (!res.second)
                return insert_result(_vec().begin() + res.first->second, false);
        } else {
            // Bail if already inserted.
            iterator iter = _FindInVec(v.first);
            if (iter != end())
                return insert_result(iter, false);
        }
 
        // Insert at end and create table if necessary.
        _vec().push_back(_InternalValueType(v.first, v.second));
        _CreateTableIfNeeded();
 
        return insert_result(std::prev(end()), true);
    }
 
    template<class IteratorType>
    void insert(IteratorType i0, IteratorType i1) {
        // Assume elements are more often than not unique, so if the sum of the
        // current size and the size of the range is greater than or equal to
        // the threshold, we create the table immediately so we don't do m*n
        // work before creating the table.
        if (size() + std::distance(i0, i1) >= Threshold)
            _CreateTable();
 
        // Insert elements.
        for(IteratorType iter = i0; iter != i1; ++iter)
            insert(*iter);
    }
 
    template <class Iterator>
    void insert_unique(Iterator begin, Iterator end) {
        // Special-case empty container.
        if (empty()) {
            _vec().assign(begin, end);
            _CreateTableIfNeeded();
        } else {
            // Just insert, since duplicate checking will use the hash.
            insert(begin, end);
        }
    }
 
    Data &operator[](const key_type &key) {
        return insert(value_type(key, Data())).first->second;
    }
 
    size_t erase(const key_type &k) {
 
        iterator iter = find(k);
        if (iter != end()) {
            erase(iter);
            return 1;
        }
        return 0;
    }
 
    void erase(const iterator &iter) {
 
        // Erase key from hash table if applicable.
        if (_h)
            _h->erase(iter->first);
    
        // If we are not removing that last element...
        if (iter != std::prev(end())) {
    
            // Need to get the underlying vector iterator directly, because
            // we want to operate on the vector.
            typename _Vector::iterator vi = iter._GetUnderlyingIterator();
    
            // ... move the last element into the erased placed.
            vi->swap(_vec().back());
    
            // ... and update the moved element's index.
            if (_h)
                (*_h)[vi->GetValue().first] = vi - _vec().begin();
        }
    
        _vec().pop_back();
    }
 
    void erase(iterator i0, iterator i1) {
 
        if (_h) {
            for(iterator iter = i0; iter != i1; ++iter)
                _h->erase(iter->first);
        }
 
        typename _Vector::const_iterator vremain = _vec().erase(
            i0._GetUnderlyingIterator(), i1._GetUnderlyingIterator());
 
        if (_h) {
            for(; vremain != _vec().end(); ++vremain)
                (*_h)[vremain->GetValue().first] = vremain - _vec().begin();
        }
    }
 
    void shrink_to_fit() {
 
        // Shrink the vector to best size.
        _vec().shrink_to_fit();
 
        if (!_h)
            return;
 
        size_t sz = size();
 
        // If we have a hash map and are underneath the threshold, discard it.
        if (sz < Threshold) {
 
            _h.reset();
 
        } else {
 
            // Otherwise, allocate a new hash map with the optimal size.
            _h.reset(new _HashMap(sz, _hash(), _equ()));
            for(size_t i=0; i<sz; ++i)
                _h->insert(std::make_pair(_vec()[i].GetValue().first, i));
        }
    }
 
    void reserve(size_t n) {
        _vec().reserve(n);
    }
 
 
private:
 
    // Helper to access the storage vector.
    _Vector &_vec() {
        return _storage.vector;
    }
 
    // Helper to access the hash functor.
    HashFn &_hash() {
        return _storage;
    }
 
    // Helper to access the equality functor.
    EqualKey &_equ() {
        return _storage;
    }
 
    // Helper to access the storage vector.
    const _Vector &_vec() const {
        return _storage.vector;
    }
 
    // Helper to access the hash functor.
    const HashFn &_hash() const {
        return _storage;
    }
 
    // Helper to access the equality functor.
    const EqualKey &_equ() const {
        return _storage;
    }
 
    // Helper to linear-search the vector for a key.
    inline iterator _FindInVec(const key_type &k) {
        _Vector &vec = _vec();
        EqualKey &equ = _equ();
        typename _Vector::iterator iter = vec.begin(), end = vec.end();
        for (; iter != end; ++iter) {
            if (equ(iter->GetValue().first, k))
                break;
        }
        return iter;
    }
 
    // Helper to linear-search the vector for a key.
    inline const_iterator _FindInVec(const key_type &k) const {
        _Vector const &vec = _vec();
        EqualKey const &equ = _equ();
        typename _Vector::const_iterator iter = vec.begin(), end = vec.end();
        for (; iter != end; ++iter) {
            if (equ(iter->GetValue().first, k))
                break;
        }
        return iter;
    }
 
    // Helper to create the acceleration table if size dictates.
    inline void _CreateTableIfNeeded() {
        if (size() >= Threshold) {
            _CreateTable();
        }
    }
 
    // Unconditionally create the acceleration table if it doesn't already
    // exist.
    inline void _CreateTable() {
        if (!_h) {
            _h.reset(new _HashMap(Threshold, _hash(), _equ()));
            for(size_t i=0; i < size(); ++i)
                _h->insert(std::make_pair(_vec()[i].GetValue().first, i));
        }
    }
 
    // Since sizeof(EqualKey) == 0 and sizeof(HashFn) == 0 in many cases
    // we use the empty base optimization to not pay a size penalty.
    // In C++20, explore using [[no_unique_address]] as an alternative
    // way to get this optimization.
    struct ARCH_EMPTY_BASES _CompressedStorage :
        private EqualKey, private HashFn {
        static_assert(!std::is_same<EqualKey, HashFn>::value,
                      "EqualKey and HashFn must be distinct types.");
        _CompressedStorage() = default;
        _CompressedStorage(const EqualKey& equalKey, const HashFn& hashFn)
            : EqualKey(equalKey), HashFn(hashFn) {}
 
        void swap(_CompressedStorage& other) {
            using std::swap;
            vector.swap(other.vector);
            swap(static_cast<EqualKey&>(*this), static_cast<EqualKey&>(other));
            swap(static_cast<HashFn&>(*this), static_cast<HashFn&>(other));
        }
        _Vector vector;
        friend class TfDenseHashMap;
    };
    _CompressedStorage _storage;
 
    // Optional hash map that maps from keys to vector indices.
    std::unique_ptr<_HashMap> _h;
};
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif // PXR_BASE_TF_DENSE_HASH_MAP_H