ts_hash_map.h

Go to the documentation of this file.

/* +------------------------------------------------------------------------+
   |                     Mobile Robot Programming Toolkit (MRPT)            |
   |                          http://www.mrpt.org/                          |
   |                                                                        |
   | Copyright (c) 2005-2017, Individual contributors, see AUTHORS file     |
   | See: http://www.mrpt.org/Authors - All rights reserved.                |
   | Released under BSD License. See details in http://www.mrpt.org/License |
   +------------------------------------------------------------------------+ */
#pragma once

#include <mrpt/utils/compiler_fixes.h>
#include <mrpt/utils/mrpt_macros.h>
#include <mrpt/utils/integer_select.h>

#include <array>

namespace mrpt
{
namespace utils
{
template <typename KEY, typename VALUE>
struct ts_map_entry
{
        bool used;
        KEY first;
        VALUE second;
        ts_map_entry() : used(false), first(KEY()), second() {}
};

/** hash function used by ts_hash_map. Uses dbj2 method */
void reduced_hash(const std::string& value, uint8_t& hash);
/** hash function used by ts_hash_map. Uses dbj2 method */
void reduced_hash(const std::string& value, uint16_t& hash);
/** hash function used by ts_hash_map. Uses dbj2 method */
void reduced_hash(const std::string& value, uint32_t& hash);
/** hash function used by ts_hash_map. Uses dbj2 method */
void reduced_hash(const std::string& value, uint64_t& hash);

/** A thread-safe (ts) container which minimally emulates a std::map<>'s [] and
 * find() methods but which is implemented as a linear vector indexed by a hash
 * of KEY.
  * Any custom hash function can be implemented, we don't rely by default on
 * C++11 std::hash<> due to its limitation in some implementations.
  *
  * This implementation is much more efficient than std::map<> when the most
 * common operation is accesing elements
  *  by KEY with find() or [], and is also thread-safe if different threads
 * create entries with different hash values.
  *
  * The default underlying non-associative container is a "memory-aligned
 * std::vector<>", but it can be changed to a
  *  standard vector<> or to a deque<> (to avoid memory reallocations) by
 * changing the template parameter \a VECTOR_T.
  *
  * \note Defined in #include <mrpt/utils/ts_hash_map.h>
  * \ingroup stlext_grp
  */
template <
        typename KEY, typename VALUE, unsigned int NUM_BYTES_HASH_TABLE = 1,
        unsigned int NUM_HAS_TABLE_COLLISIONS_ALLOWED = 5,
        typename VECTOR_T = std::array<
                std::array<ts_map_entry<KEY, VALUE>, NUM_HAS_TABLE_COLLISIONS_ALLOWED>,
                1u << (8 * NUM_BYTES_HASH_TABLE)>>
class ts_hash_map
{
   public:
        /** @name Types
                @{ */
        typedef ts_hash_map<KEY, VALUE, NUM_BYTES_HASH_TABLE,
                                                NUM_HAS_TABLE_COLLISIONS_ALLOWED, VECTOR_T>
                self_t;
        typedef KEY key_type;
        typedef ts_map_entry<KEY, VALUE> value_type;
        typedef VECTOR_T vec_t;

        struct iterator;
        struct const_iterator
        {
           public:
                const_iterator()
                        : m_vec(nullptr), m_parent(nullptr), m_idx_outer(0), m_idx_inner(0)
                {
                }
                const_iterator(
                        const VECTOR_T& vec, const self_t& parent, int idx_outer,
                        int idx_inner)
                        : m_vec(const_cast<VECTOR_T*>(&vec)),
                          m_parent(const_cast<self_t*>(&parent)),
                          m_idx_outer(idx_outer),
                          m_idx_inner(idx_inner)
                {
                }
                const_iterator& operator=(const const_iterator& o)
                {
                        m_vec = o.m_vec;
                        m_idx_outer = o.m_idx_outer;
                        m_idx_inner = o.m_idx_inner;
                        return *this;
                }
                bool operator==(const const_iterator& o) const
                {
                        return m_vec == o.m_vec && m_idx_outer == o.m_idx_outer &&
                                   m_idx_inner == o.m_idx_inner;
                }
                bool operator!=(const const_iterator& o) const { return !(*this == o); }
                const value_type& operator*() const
                {
                        return (*m_vec)[m_idx_outer][m_idx_inner];
                }
                const value_type* operator->() const
                {
                        return &(*m_vec)[m_idx_outer][m_idx_inner];
                }
                inline const_iterator operator++(int)
                { /* Post: it++ */
                        const_iterator aux = *this;
                        ++(*this);
                        return aux;
                }
                inline const_iterator& operator++()
                { /* pre: ++it */
                        incr();
                        return *this;
                }

           protected:
                VECTOR_T* m_vec;
                self_t* m_parent;
                int m_idx_outer, m_idx_inner;
                void incr()
                {
                        // This loop ends with the first used entry in the nested arrays, or
                        // an iterator pointing to "end()".
                        do
                        {
                                if (++m_idx_inner >= (int)NUM_HAS_TABLE_COLLISIONS_ALLOWED)
                                {
                                        m_idx_inner = 0;
                                        m_idx_outer++;
                                }
                        } while (m_idx_outer < (int)m_parent->m_vec.size() &&
                                         !(*m_vec)[m_idx_outer][m_idx_inner].used);
                }
        };

        struct iterator : public const_iterator
        {
           public:
                iterator() : const_iterator() {}
                iterator(VECTOR_T& vec, self_t& parent, int idx_outer, int idx_inner)
                        : const_iterator(vec, parent, idx_outer, idx_inner)
                {
                }
                value_type& operator*()
                {
                        return (*const_iterator::m_vec)[const_iterator::m_idx_outer]
                                                                                   [const_iterator::m_idx_inner];
                }
                value_type* operator->()
                {
                        return &(*const_iterator::m_vec)[const_iterator::m_idx_outer]
                                                                                        [const_iterator::m_idx_inner];
                }
                inline iterator operator++(int)
                { /* Post: it++ */
                        iterator aux = *this;
                        ++(*this);
                        return aux;
                }
                inline iterator& operator++()
                { /* pre: ++it */
                        const_iterator::incr();
                        return *this;
                }
        };
        /** @} */
   private:
        /** The actual container */
        vec_t m_vec;
        /** Number of elements accessed with write access so far */
        size_t m_size;

   public:
        /** @name Constructors, read/write access and other operations
                @{ */
        //!< Default constructor */
        ts_hash_map() : m_size(0) {}
        /** Clear the contents of this container */
        void clear()
        {
                m_size = 0;
                for (size_t oi = 0; oi < m_vec.size(); oi++)
                        for (size_t ii = 0; ii < NUM_HAS_TABLE_COLLISIONS_ALLOWED; ii++)
                                m_vec[oi][ii] = value_type();
        }

        bool empty() const { return m_size == 0; }
        /** Write/read via [i] operator, that creates an element if it didn't exist
         * already. */
        VALUE& operator[](const KEY& key)
        {
                typename mrpt::utils::uint_select_by_bytecount<
                        NUM_BYTES_HASH_TABLE>::type hash;
                reduced_hash(key, hash);
                std::array<ts_map_entry<KEY, VALUE>, NUM_HAS_TABLE_COLLISIONS_ALLOWED>&
                        match_arr = m_vec[hash];
                for (unsigned int i = 0; i < NUM_HAS_TABLE_COLLISIONS_ALLOWED; i++)
                {
                        if (!match_arr[i].used)
                        {
                                m_size++;
                                match_arr[i].used = true;
                                match_arr[i].first = key;
                                return match_arr[i].second;
                        }
                        if (match_arr[i].first == key) return match_arr[i].second;
                }
                THROW_EXCEPTION("ts_hash_map: too many hash collisions!");
        }
        const_iterator find(const KEY& key) const
        {
                typename mrpt::utils::uint_select_by_bytecount<
                        NUM_BYTES_HASH_TABLE>::type hash;
                reduced_hash(key, hash);
                const std::array<ts_map_entry<KEY, VALUE>,
                                                 NUM_HAS_TABLE_COLLISIONS_ALLOWED>& match_arr =
                        m_vec[hash];
                for (unsigned int i = 0; i < NUM_HAS_TABLE_COLLISIONS_ALLOWED; i++)
                {
                        if (match_arr[i].used && match_arr[i].first == key)
                                return const_iterator(m_vec, *this, hash, i);
                }
                return this->end();
        }

        const_iterator begin() const
        {
                const_iterator it(m_vec, *this, 0, -1);
                ++it;
                return it;
        }
        const_iterator end() const
        {
                return const_iterator(m_vec, *this, m_vec.size(), 0);
        }
        iterator begin()
        {
                iterator it(m_vec, *this, 0, -1);
                ++it;
                return it;
        }
        iterator end() { return iterator(m_vec, *this, m_vec.size(), 0); }
        /** @} */

};  // end class ts_hash_map

}  // End of namespace
}  // End of namespace