HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_Map.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_Map.h (UT Library, C++)
7  *
8  * COMMENTS: Wrapper for an unordered map data structure.
9  *
10  * UT_Map<key, entry> map;
11  * key id;
12  * entry item;
13  *
14  * map[id] = item; // insert or replace
15  *
16  * item = map[id]; // find or create new
17  *
18  * UT_Map<key,entry>::iterator map_item = map.find(id); // find only
19  * if(map_item != map.end())
20  * item = map_item->second;
21  *
22  * map.erase(id); // remove entry
23  *
24  * for(auto it = map.begin(); it != map.end(); ++it)
25  * {
26  * key = it->first; // traverse
27  * item = it->second;
28  * }
29  *
30  * int num = map.size(); // #entries
31  *
32  * map.clear(); // remove all entries
33  *
34  * RELATION TO THE STL:
35  *
36  * Use UT_Map (or UT_SortedMap) instead of std::map
37  *
38  * Reasoning to not use std::map:
39  *
40  * - Performance: std::map is an ordered map so is impossible to have
41  * reasonably fast implementations for it.
42  *
43  * - If you want a sorted map, we have wrapped std::map as UT_SortedMap. But
44  * you probably don’t.
45  *
46  * Use UT_Map instead of std::unordered_map:
47  *
48  * Reasoning to not use std::unordered_map:
49  *
50  * - There may are still be issues with std::unordered map (possibly platform
51  * specific hash functions?)
52  *
53  * - We also want to keep this wrapped so we can easily replace it with a
54  * faster version.
55  *
56  * - Consider UT_ArrayMap and UT_StringMap variants as well.
57  */
58 
59 #ifndef __UT_Map__
60 #define __UT_Map__
61 
62 #include "UT_ContainerPrinter.h"
63 #include "UT_IteratorRange.h"
64 #include <SYS/SYS_Types.h>
65 
66 #include <hboost/unordered_map.hpp>
67 #include <iterator>
68 #include <map>
69 
70 template<typename K, typename V, typename H, typename P>
71 int64
72 UTgetMemoryUsage(const hboost::unordered_map<K, V, H, P> &map, bool inclusive)
73 {
74  int64 mem = inclusive ? sizeof(map) : 0;
75  // Buckets only contain a pointer to the node
76  mem += map.bucket_count() * sizeof(void*);
77  // Nodes contain the hash value, a pointer to the next node,
78  // and the key-value pair.
79  mem += map.size() * (sizeof(size_t) + sizeof(void*) + sizeof(std::pair<K,V>));
80  return mem;
81 }
82 
83 template<typename K, typename V, typename C>
84 int64
85 UTgetMemoryUsage(const std::map<K, V, C> &map, bool inclusive)
86 {
87  int64 mem = inclusive ? sizeof(map) : 0;
88 
89  // NOTE: If the comparator object of type C owns any memory
90  // (i.e. apart from itself) when default constructed
91  // or copy constructed, that memory won't be counted.
92 
93  // NOTE: This count is for the VC++ 2010 implementation
94  // of std::map, but others should be in the ballpark.
95  // Nodes contain pointers to the left, parent, and right,
96  // the key-value pair, a colour in a char (red or black),
97  // and a flag in a char indicating if the node is the head.
98  // Round up to a multiple of 4 on the size of each node.
99  mem += (map.size() + 1) * ((3*sizeof(void*) + sizeof(std::pair<const K,V>)
100  + 2*sizeof(char) + 3) & ~3);
101  return mem;
102 }
103 
104 /// Unsorted map container.
105 template<typename K, typename V,
106  typename H = hboost::hash<K>, typename P = std::equal_to<K> >
107 class UT_Map : public hboost::unordered_map<K, V, H, P>
108 {
109 public:
110  // Hoisting of base types
111  typedef hboost::unordered_map<K, V, H, P> Base;
112  typedef typename Base::key_type key_type;
113  typedef typename Base::mapped_type mapped_type;
114  typedef typename Base::value_type value_type;
115  typedef typename Base::hasher hasher;
116  typedef typename Base::key_equal key_equal;
117  typedef typename Base::iterator iterator;
118  typedef typename Base::const_iterator const_iterator;
119  typedef H Hasher;
120  typedef P Equal;
121 
122  /// Initialize an empty map, and optionally a custom hasher and
123  /// equal compare functions.
124  explicit UT_Map(const Hasher &hf = Hasher(),
125  const Equal &eql = Equal()) :
126  Base(hboost::unordered::detail::default_bucket_count, hf, eql) {}
127 
128  /// Initialize the map from an iterator pair, and optionally a custom
129  /// hasher and equal compare functions.
130  template <typename InputIt>
131  UT_Map(InputIt first, InputIt last,
132  const Hasher &hf = Hasher(),
133  const Equal &eql = Equal()) :
134  Base(first, last, hboost::unordered::detail::default_bucket_count,
135  hf, eql) {}
136 
137  /// Initialize the map using an initializer list. The initializer list is a
138  /// list of pairs of items to add to the map. E.g:
139  /// @code
140  /// UT_Map<int, const char *> foo = {{1, "one"}, {2, "two"}};
141  /// @endcode
142  UT_Map(std::initializer_list<value_type> init_list)
143  {
144  // We can't thunk down to the hboost::unordered_map initializer_list
145  // constructor, since it seems disabled when building with clang.
146  this->insert(init_list.begin(), init_list.end());
147  }
148 
149  /// Returns the approximate size, in bytes, of the memory consumed by this map
150  /// or, optionally, only the data contained within.
151  int64 getMemoryUsage(bool inclusive) const
152  {
153  int64 mem = inclusive ? sizeof(*this) : 0;
154  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
155  return mem;
156  }
157 
158  /// Returns @c true if a value with the @c key is contained in the map.
159  bool contains(const key_type &key) const
160  {
161  return this->find(key) != this->end();
162  }
163 
164 protected:
165  template<typename VIT, typename VT>
167  {
168  VT &operator()(const VIT &v) const { return v->first; }
169  };
170  template<typename VIT, typename VT>
172  {
173  VT &operator()(const VIT &v) const { return v->second; }
174  };
175 
176  template<typename IT, typename T, typename DR>
178  public std::iterator<std::forward_iterator_tag, T>
179  {
180  public:
181  typedef T& reference;
182  typedef T* pointer;
183 
185 
186  template<typename EIT, typename EDR>
188  it(src.it) {}
189 
190  reference operator*() const { DR dr; return dr(it); }
191  pointer operator->() const { DR dr; return &dr(it); }
192 
194  { return it == o.it; }
195 
197  { return it != o.it; }
198 
200  {
201  ++it;
202  return *this;
203  }
204 
205  protected:
206  friend class UT_Map<K, V, H, P>;
207 
208  partial_iterator_base(IT it) : it(it) {}
209  private:
210  IT it;
211  };
212 
213 public:
214  using const_key_iterator = partial_iterator_base<const_iterator, const key_type,
215  deref_pair_first<const_iterator, const key_type>>;
216  using mapped_iterator = partial_iterator_base<iterator, mapped_type,
217  deref_pair_second<iterator, mapped_type>>;
218  using const_mapped_iterator = partial_iterator_base<const_iterator, const mapped_type,
219  deref_pair_second<const_iterator, const mapped_type>>;
220 
221  /// Returns a range object that iterates over the map but returns only
222  /// the key values.
223  /// Example:
224  /// @code
225  /// UT_Map<int, const char *> foo = {{1, "one"}, {2, "two"}};
226  /// for (int key : foo.key_range())
227  /// std::cout << key << "\n";
228  /// @endcode
230  { return UTmakeRange(const_key_iterator(this->begin()),
231  const_key_iterator(this->end())); }
232 
233  /// Returns a range object that iterates over the map but returns only
234  /// the mapped values.
236  { return UTmakeRange(mapped_iterator(this->begin()),
237  mapped_iterator(this->end())); }
238 
239  /// Returns a const range object that iterates over the map but returns
240  /// only the mapped values.
242  { return UTmakeRange(const_mapped_iterator(this->begin()),
243  const_mapped_iterator(this->end())); }
244 };
245 
246 /// Sorted map container.
247 template<typename K, typename V, typename C = std::less<K> >
248 class UT_SortedMap : public std::map<K, V, C>
249 {
250 public:
251  // Hoisting of base types.
252  typedef std::map<K, V, C> Base;
253  typedef typename Base::key_type key_type;
254  typedef typename Base::mapped_type mapped_type;
255  typedef typename Base::value_type value_type;
256  typedef typename Base::key_compare key_compare;
257  typedef typename Base::iterator iterator;
258  typedef typename Base::const_iterator const_iterator;
259 
260  typedef C LessThan;
261 
263 
264  explicit UT_SortedMap(const LessThan &lt) : Base(lt) {}
265 
266  template<typename InputIt>
267  UT_SortedMap(InputIt first, InputIt last) : Base(first, last) {}
268 
269  template<typename InputIt>
270  UT_SortedMap(InputIt first, InputIt last, const LessThan &lt) :
271  Base(first, last, lt) {}
272 
273  /// Initialize the map using an initializer list. The initializer list is a
274  /// list of pairs of items to add to the map. E.g:
275  /// @code
276  /// UT_Map<int, const char *> foo = {{1, "one"}, {2, "two"}};
277  /// @endcode
278  UT_SortedMap(std::initializer_list<value_type> init_list)
279  {
280  this->insert(init_list.begin(), init_list.end());
281  }
282 
283  int64 getMemoryUsage(bool inclusive) const
284  {
285  int64 mem = inclusive ? sizeof(*this) : 0;
286  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
287  return mem;
288  }
289 
290  bool contains(const key_type &key) const
291  {
292  return this->find(key) != this->end();
293  }
294 
295 protected:
296  template<typename VIT, typename VT>
298  {
299  VT &operator()(const VIT &v) const { return v->first; }
300  };
301  template<typename VIT, typename VT>
303  {
304  VT &operator()(const VIT &v) const { return v->second; }
305  };
306 
307  template<typename IT, typename T, typename DR>
309  public std::iterator<std::forward_iterator_tag, T>
310  {
311  public:
312  typedef T& reference;
313  typedef T* pointer;
314 
316 
317  template<typename EIT, typename EDR>
319  it(src.it) {}
320 
321  reference operator*() const { DR dr; return dr(it); }
322  pointer operator->() const { DR dr; return &dr(it); }
323 
325  { return it == o.it; }
326 
328  { return it != o.it; }
329 
331  {
332  ++it;
333  return *this;
334  }
335 
336  protected:
337  friend class UT_SortedMap<K, V, C>;
338 
339  partial_iterator_base(IT it) : it(it) {}
340  private:
341  IT it;
342  };
343 
344 public:
345  using key_iterator = partial_iterator_base<iterator, key_type,
346  deref_pair_first<iterator, key_type>>;
347  using const_key_iterator = partial_iterator_base<const_iterator, const key_type,
348  deref_pair_first<const_iterator, const key_type>>;
349  using mapped_iterator = partial_iterator_base<iterator, mapped_type,
350  deref_pair_second<iterator, mapped_type>>;
351  using const_mapped_iterator = partial_iterator_base<const_iterator, const mapped_type,
352  deref_pair_second<const_iterator, const mapped_type>>;
353 
354  /// Returns a range object that iterates over the map but returns only
355  /// the key values.
357  { return UTmakeRange(key_iterator(this->begin()),
358  key_iterator(this->end())); }
359 
360  /// Returns a const range object that iterates over the map but returns
361  /// only the key values.
363  { return UTmakeRange(const_key_iterator(this->begin()),
364  const_key_iterator(this->end())); }
365 
366  /// Returns a range object that iterates over the map but returns only
367  /// the mapped values.
369  { return UTmakeRange(mapped_iterator(this->begin()),
370  mapped_iterator(this->end())); }
371 
372  /// Returns a const range object that iterates over the map but returns
373  /// only the mapped values.
375  { return UTmakeRange(const_mapped_iterator(this->begin()),
376  const_mapped_iterator(this->end())); }
377 };
378 
379 namespace std
380 {
381  // This helper needs to live in the 'std' namespace for argument-dependent
382  // lookup to succeed.
383  template<typename OS, typename K, typename V>
384  inline OS &
385  operator<<(OS &os, const pair<K, V> &v)
386  {
387  os << "<" << v.first << ", " << v.second << ">";
388  return os;
389  }
390 }
391 
392 template<typename OS, typename K, typename V>
393 inline OS &
394 operator<<(OS &os, const UT_Map<K, V> &d)
395 {
396  os << "UT_Map" << UT_ContainerPrinter<UT_Map<K, V> >(d);
397  return os;
398 }
399 
400 template<typename OS, typename K, typename V>
401 inline OS &
402 operator<<(OS &os, const UT_SortedMap<K, V> &d)
403 {
404  os << "UT_SortedMap" << UT_ContainerPrinter<UT_SortedMap<K, V> >(d);
405  return os;
406 }
407 
408 #endif
partial_iterator_base< iterator, mapped_type, deref_pair_second< iterator, mapped_type >> mapped_iterator
Definition: UT_Map.h:217
Base::key_type key_type
Definition: UT_Map.h:112
UT_IteratorRange< const_key_iterator > key_range() const
Definition: UT_Map.h:229
Unsorted map container.
Definition: UT_Map.h:107
GLint first
Definition: glcorearb.h:405
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Map.h:283
P Equal
Definition: UT_Map.h:120
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Map.h:151
UT_IteratorRange< IterT > UTmakeRange(IterT &&b, IterT &&e)
partial_iterator_base(const partial_iterator_base< EIT, T, EDR > &src)
Definition: UT_Map.h:318
VT & operator()(const VIT &v) const
Definition: UT_Map.h:299
Base::key_type key_type
Definition: UT_Map.h:253
GLenum src
Definition: glcorearb.h:1793
reference operator*() const
Definition: UT_Map.h:190
OIIO_FORCEINLINE vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
Definition: simd.h:3436
H Hasher
Definition: UT_Map.h:119
uint64 value_type
Definition: GA_PrimCompat.h:29
partial_iterator_base & operator++()
Definition: UT_Map.h:199
bool operator!=(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:327
UT_SortedMap(std::initializer_list< value_type > init_list)
Definition: UT_Map.h:278
Base::value_type value_type
Definition: UT_Map.h:255
UT_SortedMap(InputIt first, InputIt last)
Definition: UT_Map.h:267
hboost::unordered_map< K, V, H, P > Base
Definition: UT_Map.h:111
Sorted map container.
Definition: UT_Map.h:248
VT & operator()(const VIT &v) const
Definition: UT_Map.h:173
partial_iterator_base< iterator, key_type, deref_pair_first< iterator, key_type >> key_iterator
Definition: UT_Map.h:346
std::map< K, V, C > Base
Definition: UT_Map.h:252
pointer operator->() const
Definition: UT_Map.h:191
bool operator!=(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:196
Base::mapped_type mapped_type
Definition: UT_Map.h:113
const GLdouble * v
Definition: glcorearb.h:837
GLuint GLuint end
Definition: glcorearb.h:475
partial_iterator_base< const_iterator, const key_type, deref_pair_first< const_iterator, const key_type >> const_key_iterator
Definition: UT_Map.h:215
UT_SortedMap(InputIt first, InputIt last, const LessThan &lt)
Definition: UT_Map.h:270
Base::iterator iterator
Definition: UT_Map.h:257
VT & operator()(const VIT &v) const
Definition: UT_Map.h:168
UT_IteratorRange< const_mapped_iterator > mapped_range() const
Definition: UT_Map.h:374
UT_Map(const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Map.h:124
UT_SortedMap()
Definition: UT_Map.h:262
partial_iterator_base< const_iterator, const mapped_type, deref_pair_second< const_iterator, const mapped_type >> const_mapped_iterator
Definition: UT_Map.h:219
UT_IteratorRange< mapped_iterator > mapped_range()
Definition: UT_Map.h:235
long long int64
Definition: SYS_Types.h:116
partial_iterator_base & operator++()
Definition: UT_Map.h:330
STATIC_INLINE uint64_t H(uint64_t x, uint64_t y, uint64_t mul, int r)
Definition: farmhash.h:701
Base::iterator iterator
Definition: UT_Map.h:117
Base::const_iterator const_iterator
Definition: UT_Map.h:258
int64 UTgetMemoryUsage(const hboost::unordered_map< K, V, H, P > &map, bool inclusive)
Definition: UT_Map.h:72
VT & operator()(const VIT &v) const
Definition: UT_Map.h:304
bool operator==(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:324
UT_SortedMap(const LessThan &lt)
Definition: UT_Map.h:264
Base::mapped_type mapped_type
Definition: UT_Map.h:254
Base::hasher hasher
Definition: UT_Map.h:115
UT_IteratorRange< const_mapped_iterator > mapped_range() const
Definition: UT_Map.h:241
UT_IteratorRange< key_iterator > key_range()
Definition: UT_Map.h:356
UT_Map(InputIt first, InputIt last, const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Map.h:131
UT_IteratorRange< mapped_iterator > mapped_range()
Definition: UT_Map.h:368
reference operator*() const
Definition: UT_Map.h:321
UT_Map(std::initializer_list< value_type > init_list)
Definition: UT_Map.h:142
UT_IteratorRange< const_key_iterator > key_range() const
Definition: UT_Map.h:362
Base::value_type value_type
Definition: UT_Map.h:114
bool contains(const key_type &key) const
Definition: UT_Map.h:290
Base::const_iterator const_iterator
Definition: UT_Map.h:118
partial_iterator_base< iterator, mapped_type, deref_pair_second< iterator, mapped_type >> mapped_iterator
Definition: UT_Map.h:350
Base::key_compare key_compare
Definition: UT_Map.h:256
partial_iterator_base< const_iterator, const key_type, deref_pair_first< const_iterator, const key_type >> const_key_iterator
Definition: UT_Map.h:348
Base::key_equal key_equal
Definition: UT_Map.h:116
partial_iterator_base< const_iterator, const mapped_type, deref_pair_second< const_iterator, const mapped_type >> const_mapped_iterator
Definition: UT_Map.h:352
bool operator==(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:193
partial_iterator_base(const partial_iterator_base< EIT, T, EDR > &src)
Definition: UT_Map.h:187
FMT_CONSTEXPR auto find(Ptr first, Ptr last, T value, Ptr &out) -> bool
Definition: core.h:2089
bool contains(const key_type &key) const
Returns true if a value with the key is contained in the map.
Definition: UT_Map.h:159
PcpNodeRef_ChildrenIterator begin(const PcpNodeRef::child_const_range &r)
Support for range-based for loops for PcpNodeRef children ranges.
Definition: node.h:450