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



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: ad3a9d8ae Tue May 1 23:10:22 2018 -0700 at lun oct 28 00:14:14 CET 2019