MRPT  1.9.9
ts_hash_map.h
Go to the documentation of this file.
1 /* +------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | https://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2020, Individual contributors, see AUTHORS file |
6  | See: https://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See: https://www.mrpt.org/License |
8  +------------------------------------------------------------------------+ */
9 #pragma once
10 
11 #include <mrpt/core/common.h> // remove MSVC warnings
13 #include <array>
14 #include <stdexcept>
15 #include <string_view>
16 
17 namespace mrpt::containers
18 {
19 template <typename KEY, typename VALUE>
21 {
22  bool used{false};
23  KEY first;
24  VALUE second;
25  ts_map_entry() = default;
26 };
27 
28 /** hash function used by ts_hash_map. Uses dbj2 method */
29 void reduced_hash(const std::string_view& value, uint8_t& hash);
30 void reduced_hash(const std::string_view& value, uint16_t& hash);
31 void reduced_hash(const std::string_view& value, uint32_t& hash);
32 void reduced_hash(const std::string_view& value, uint64_t& hash);
33 
34 /** A thread-safe (ts) container which minimally emulates a std::map<>'s [] and
35  * find() methods but which is implemented as a linear vector indexed by a hash
36  * of KEY.
37  * Any custom hash function can be implemented, we don't rely by default on
38  * C++11 std::hash<> due to its limitation in some implementations.
39  *
40  * This implementation is much more efficient than std::map<> when the most
41  * common operation is accesing elements
42  * by KEY with find() or [], and is also thread-safe if different threads
43  * create entries with different hash values.
44  *
45  * The default underlying non-associative container is a "memory-aligned
46  * std::vector<>", but it can be changed to a
47  * standard vector<> or to a deque<> (to avoid memory reallocations) by
48  * changing the template parameter \a VECTOR_T.
49  *
50  * \note Defined in #include <mrpt/containers/ts_hash_map.h>
51  * \ingroup mrpt_containers_grp
52  */
53 template <
54  typename KEY, typename VALUE, unsigned int NUM_BYTES_HASH_TABLE = 1,
55  unsigned int NUM_HAS_TABLE_COLLISIONS_ALLOWED = 5,
56  typename VECTOR_T = std::array<
57  std::array<ts_map_entry<KEY, VALUE>, NUM_HAS_TABLE_COLLISIONS_ALLOWED>,
58  1u << (8 * NUM_BYTES_HASH_TABLE)>>
59 class ts_hash_map
60 {
61  public:
62  /** @name Types
63  @{ */
64  using self_t = ts_hash_map<
65  KEY, VALUE, NUM_BYTES_HASH_TABLE, NUM_HAS_TABLE_COLLISIONS_ALLOWED,
66  VECTOR_T>;
67  using key_type = KEY;
68  using value_type = ts_map_entry<KEY, VALUE>;
69  using vec_t = VECTOR_T;
70 
71  struct iterator;
72  struct const_iterator
73  {
74  public:
75  const_iterator() : m_vec(nullptr), m_parent(nullptr) {}
76  const_iterator(
77  const VECTOR_T& vec, const self_t& parent, int idx_outer,
78  int idx_inner)
79  : m_vec(const_cast<VECTOR_T*>(&vec)),
80  m_parent(const_cast<self_t*>(&parent)),
81  m_idx_outer(idx_outer),
82  m_idx_inner(idx_inner)
83  {
84  }
85  const_iterator(const const_iterator& o) { *this = o; }
86  const_iterator& operator=(const const_iterator& o)
87  {
88  m_vec = o.m_vec;
89  m_idx_outer = o.m_idx_outer;
90  m_idx_inner = o.m_idx_inner;
91  return *this;
92  }
93  bool operator==(const const_iterator& o) const
94  {
95  return m_vec == o.m_vec && m_idx_outer == o.m_idx_outer &&
96  m_idx_inner == o.m_idx_inner;
97  }
98  bool operator!=(const const_iterator& o) const { return !(*this == o); }
99  const value_type& operator*() const
100  {
101  return (*m_vec)[m_idx_outer][m_idx_inner];
102  }
103  const value_type* operator->() const
104  {
105  return &(*m_vec)[m_idx_outer][m_idx_inner];
106  }
107  inline const_iterator operator++(int)
108  { /* Post: it++ */
109  const_iterator aux = *this;
110  ++(*this);
111  return aux;
112  }
113  inline const_iterator& operator++()
114  { /* pre: ++it */
115  incr();
116  return *this;
117  }
118 
119  protected:
120  VECTOR_T* m_vec;
121  self_t* m_parent;
122  int m_idx_outer{0}, m_idx_inner{0};
123  void incr()
124  {
125  // This loop ends with the first used entry in the nested arrays, or
126  // an iterator pointing to "end()".
127  do
128  {
129  if (++m_idx_inner >=
130  static_cast<int>(NUM_HAS_TABLE_COLLISIONS_ALLOWED))
131  {
132  m_idx_inner = 0;
133  m_idx_outer++;
134  }
135  } while (m_idx_outer < static_cast<int>(m_parent->m_vec.size()) &&
136  !(*m_vec)[m_idx_outer][m_idx_inner].used);
137  }
138  };
139 
140  struct iterator : public const_iterator
141  {
142  public:
143  iterator() : const_iterator() {}
144  iterator(VECTOR_T& vec, self_t& parent, int idx_outer, int idx_inner)
145  : const_iterator(vec, parent, idx_outer, idx_inner)
146  {
147  }
148  value_type& operator*()
149  {
150  return (*const_iterator::m_vec)[const_iterator::m_idx_outer]
151  [const_iterator::m_idx_inner];
152  }
153  value_type* operator->()
154  {
155  return &(*const_iterator::m_vec)[const_iterator::m_idx_outer]
156  [const_iterator::m_idx_inner];
157  }
158  inline iterator operator++(int)
159  { /* Post: it++ */
160  iterator aux = *this;
161  ++(*this);
162  return aux;
163  }
164  inline iterator& operator++()
165  { /* pre: ++it */
166  const_iterator::incr();
167  return *this;
168  }
169  };
170  /** @} */
171  private:
172  /** The actual container */
173  vec_t m_vec;
174  /** Number of elements accessed with write access so far */
175  size_t m_size{0};
176 
177  public:
178  /** @name Constructors, read/write access and other operations
179  @{ */
180  //!< Default constructor */
181  ts_hash_map() = default;
182  /** Clear the contents of this container */
183  void clear()
184  {
185  m_size = 0;
186  for (size_t oi = 0; oi < m_vec.size(); oi++)
187  for (size_t ii = 0; ii < NUM_HAS_TABLE_COLLISIONS_ALLOWED; ii++)
188  m_vec[oi][ii] = value_type();
189  }
190 
191  bool empty() const { return m_size == 0; }
192  /** noexcept version of operator[], returns nullptr upon failure */
193  VALUE* find_or_alloc(const KEY& key) noexcept
194  {
196  hash;
197  reduced_hash(key, hash);
198  std::array<ts_map_entry<KEY, VALUE>, NUM_HAS_TABLE_COLLISIONS_ALLOWED>&
199  match_arr = m_vec[hash];
200  for (unsigned int i = 0; i < NUM_HAS_TABLE_COLLISIONS_ALLOWED; i++)
201  {
202  if (!match_arr[i].used)
203  {
204  m_size++;
205  match_arr[i].used = true;
206  match_arr[i].first = key;
207  return &match_arr[i].second;
208  }
209  if (match_arr[i].first == key) return &match_arr[i].second;
210  }
211  return nullptr;
212  }
213 
214  /** Write/read via [i] operator, that creates an element if it didn't exist
215  * already. */
216  VALUE& operator[](const KEY& key)
217  {
218  VALUE* v = find_or_alloc(key);
219  if (!v)
220  throw std::runtime_error("ts_hash_map: too many hash collisions!");
221  return *v;
222  }
223 
224  const_iterator find(const KEY& key) const
225  {
227  hash;
228  reduced_hash(key, hash);
229  const std::array<
230  ts_map_entry<KEY, VALUE>, NUM_HAS_TABLE_COLLISIONS_ALLOWED>&
231  match_arr = m_vec[hash];
232  for (unsigned int i = 0; i < NUM_HAS_TABLE_COLLISIONS_ALLOWED; i++)
233  {
234  if (match_arr[i].used && match_arr[i].first == key)
235  return const_iterator(m_vec, *this, hash, i);
236  }
237  return this->end();
238  }
239 
240  const_iterator begin() const
241  {
242  const_iterator it(m_vec, *this, 0, -1);
243  ++it;
244  return it;
245  }
246  const_iterator end() const
247  {
248  return const_iterator(m_vec, *this, m_vec.size(), 0);
249  }
250  iterator begin()
251  {
252  iterator it(m_vec, *this, 0, -1);
253  ++it;
254  return it;
255  }
256  iterator end() { return iterator(m_vec, *this, m_vec.size(), 0); }
257  /** @} */
258 
259 }; // end class ts_hash_map
260 
261 } // namespace mrpt::containers
const_iterator find(const KEY &key) const
Definition: ts_hash_map.h:224
VALUE second
Definition: ts_hash_map.h:24
ts_map_entry()=default
VALUE & operator[](const KEY &key)
Write/read via [i] operator, that creates an element if it didn&#39;t exist already.
Definition: ts_hash_map.h:216
Usage: uint_select_by_bytecount<N>::type var; allows defining var as a unsigned integer with...
void reduced_hash(const std::string_view &value, uint8_t &hash)
hash function used by ts_hash_map.
Definition: ts_hash_map.cpp:25
KEY first
Definition: ts_hash_map.h:23
ts_hash_map()=default
< Default constructor */
bool operator==(const LUT_info &a, const LUT_info &o)
bool empty() const
Definition: ts_hash_map.h:191
const_iterator end() const
Definition: ts_hash_map.h:246
const_iterator begin() const
Definition: ts_hash_map.h:240
VALUE * find_or_alloc(const KEY &key) noexcept
noexcept version of operator[], returns nullptr upon failure
Definition: ts_hash_map.h:193
bool used
Definition: ts_hash_map.h:22
vec_t m_vec
The actual container.
Definition: ts_hash_map.h:169
iterator operator++(int)
A thread-safe (ts) container which minimally emulates a std::map<>&#39;s [] and find() methods but which ...
Definition: ts_hash_map.h:158
bool operator!=(const mrpt::img::TCamera &a, const mrpt::img::TCamera &b)
Definition: TCamera.cpp:238
void clear()
Clear the contents of this container.
Definition: ts_hash_map.h:183
size_t m_size
Number of elements accessed with write access so far.
Definition: ts_hash_map.h:175
Definition: ts_hash_map.h:20
std::vector< T1 > operator*(const std::vector< T1 > &a, const std::vector< T2 > &b)
a*b (element-wise multiplication)
Definition: ops_vectors.h:50



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: c7a3bec24 Sun Mar 29 18:33:13 2020 +0200 at dom mar 29 18:50:38 CEST 2020