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 
35 #ifndef __UT_Map__
36 #define __UT_Map__
37 
38 #include "UT_ContainerPrinter.h"
39 #include "UT_IteratorRange.h"
40 #include <SYS/SYS_Types.h>
41 
42 #include <hboost/unordered_map.hpp>
43 #include <iterator>
44 #include <map>
45 
46 template<typename K, typename V, typename H, typename P>
47 int64
48 UTgetMemoryUsage(const hboost::unordered_map<K, V, H, P> &map, bool inclusive)
49 {
50  int64 mem = inclusive ? sizeof(map) : 0;
51  // Buckets only contain a pointer to the node
52  mem += map.bucket_count() * sizeof(void*);
53  // Nodes contain the hash value, a pointer to the next node,
54  // and the key-value pair.
55  mem += map.size() * (sizeof(size_t) + sizeof(void*) + sizeof(std::pair<K,V>));
56  return mem;
57 }
58 
59 template<typename K, typename V, typename C>
60 int64
61 UTgetMemoryUsage(const std::map<K, V, C> &map, bool inclusive)
62 {
63  int64 mem = inclusive ? sizeof(map) : 0;
64 
65  // NOTE: If the comparator object of type C owns any memory
66  // (i.e. apart from itself) when default constructed
67  // or copy constructed, that memory won't be counted.
68 
69  // NOTE: This count is for the VC++ 2010 implementation
70  // of std::map, but others should be in the ballpark.
71  // Nodes contain pointers to the left, parent, and right,
72  // the key-value pair, a colour in a char (red or black),
73  // and a flag in a char indicating if the node is the head.
74  // Round up to a multiple of 4 on the size of each node.
75  mem += (map.size() + 1) * ((3*sizeof(void*) + sizeof(std::pair<const K,V>)
76  + 2*sizeof(char) + 3) & ~3);
77  return mem;
78 }
79 
80 /// Unsorted map container.
81 template<typename K, typename V,
82  typename H = hboost::hash<K>, typename P = std::equal_to<K> >
83 class UT_Map : public hboost::unordered_map<K, V, H, P>
84 {
85 public:
86  // Hoisting of base types
87  typedef hboost::unordered_map<K, V, H, P> Base;
88  typedef typename Base::key_type key_type;
89  typedef typename Base::mapped_type mapped_type;
90  typedef typename Base::value_type value_type;
91  typedef typename Base::hasher hasher;
92  typedef typename Base::key_equal key_equal;
93  typedef typename Base::iterator iterator;
94  typedef typename Base::const_iterator const_iterator;
95  typedef H Hasher;
96  typedef P Equal;
97 
98  /// Initialize an empty map, and optionally a custom hasher and
99  /// equal compare functions.
100  explicit UT_Map(const Hasher &hf = Hasher(),
101  const Equal &eql = Equal()) :
102  Base(hboost::unordered::detail::default_bucket_count, hf, eql) {}
103 
104  /// Initialize the map from an iterator pair.
105  template <typename InputIt>
106  UT_Map(InputIt first, InputIt last) : Base(first, last) {}
107 
108  /// Initialize the map from an iterator pair, and optionally a custom
109  /// hasher and equal compare functions.
110  template <typename InputIt>
111  UT_Map(InputIt first, InputIt last,
112  const Hasher &hf = Hasher(),
113  const Equal &eql = Equal()) :
114  Base(first, last, hboost::unordered::detail::default_bucket_count,
115  hf, eql) {}
116 
117  /// Initialize the map using an initializer list. The initializer list is a
118  /// list of pairs of items to add to the map. E.g:
119  /// @code
120  /// UT_Map<int, const char *> foo = {{1, "one"}, {2, "two"}};
121  /// @endcode
122  UT_Map(std::initializer_list<value_type> init_list)
123  {
124  // We can't thunk down to the hboost::unordered_map initializer_list
125  // constructor, since it seems disabled when building with clang.
126  this->insert(init_list.begin(), init_list.end());
127  }
128 
129  /// Returns the approximate size, in bytes, of the memory consumed by this map
130  /// or, optionally, only the data contained within.
131  int64 getMemoryUsage(bool inclusive) const
132  {
133  int64 mem = inclusive ? sizeof(*this) : 0;
134  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
135  return mem;
136  }
137 
138  /// Returns @c true if a value with the @c key is contained in the map.
139  bool contains(const key_type &key) const
140  {
141  return this->find(key) != this->end();
142  }
143 
144 protected:
145  template<typename VIT, typename VT>
147  {
148  VT &operator()(const VIT &v) const { return v->first; }
149  };
150  template<typename VIT, typename VT>
152  {
153  VT &operator()(const VIT &v) const { return v->second; }
154  };
155 
156  template<typename IT, typename T, typename DR>
158  public std::iterator<std::forward_iterator_tag, T>
159  {
160  public:
161  typedef T& reference;
162  typedef T* pointer;
163 
165 
166  template<typename EIT, typename EDR>
168  it(src.it) {}
169 
170  reference operator*() const { DR dr; return dr(it); }
171  pointer operator->() const { DR dr; return &dr(it); }
172 
174  { return it == o.it; }
175 
177  { return it != o.it; }
178 
180  {
181  ++it;
182  return *this;
183  }
184 
185  protected:
186  friend class UT_Map<K, V, H, P>;
187 
188  partial_iterator_base(IT it) : it(it) {}
189  private:
190  IT it;
191  };
192 
193 public:
194  using key_iterator = partial_iterator_base<iterator, key_type,
195  deref_pair_first<iterator, key_type>>;
196  using const_key_iterator = partial_iterator_base<const_iterator, const key_type,
197  deref_pair_first<const_iterator, const key_type>>;
198  using mapped_iterator = partial_iterator_base<iterator, mapped_type,
199  deref_pair_second<iterator, mapped_type>>;
200  using const_mapped_iterator = partial_iterator_base<const_iterator, const mapped_type,
201  deref_pair_second<const_iterator, const mapped_type>>;
202 
203  /// Returns a range object that iterates over the map but returns only
204  /// the key values.
205  /// Example:
206  /// @code
207  /// UT_Map<int, const char *> foo = {{1, "one"}, {2, "two"}};
208  /// for (int key : foo.key_range())
209  /// std::cout << key << "\n";
210  /// @endcode
211 
213  { return UTmakeRange(key_iterator(this->begin()),
214  key_iterator(this->end())); }
215 
216  /// Returns a const range object that iterates over the map but returns
217  /// only the key values.
219  { return UTmakeRange(const_key_iterator(this->begin()),
220  const_key_iterator(this->end())); }
221 
222  /// Returns a range object that iterates over the map but returns only
223  /// the mapped values.
225  { return UTmakeRange(mapped_iterator(this->begin()),
226  mapped_iterator(this->end())); }
227 
228  /// Returns a const range object that iterates over the map but returns
229  /// only the mapped values.
231  { return UTmakeRange(const_mapped_iterator(this->begin()),
232  const_mapped_iterator(this->end())); }
233 };
234 
235 /// Sorted map container.
236 template<typename K, typename V, typename C = std::less<K> >
237 class UT_SortedMap : public std::map<K, V, C>
238 {
239 public:
240  // Hoisting of base types.
241  typedef std::map<K, V, C> Base;
242  typedef typename Base::key_type key_type;
243  typedef typename Base::mapped_type mapped_type;
244  typedef typename Base::value_type value_type;
245  typedef typename Base::key_compare key_compare;
246  typedef typename Base::iterator iterator;
247  typedef typename Base::const_iterator const_iterator;
248 
249  typedef C LessThan;
250 
252 
253  explicit UT_SortedMap(const LessThan &lt) : Base(lt) {}
254 
255  template<typename InputIt>
256  UT_SortedMap(InputIt first, InputIt last) : Base(first, last) {}
257 
258  template<typename InputIt>
259  UT_SortedMap(InputIt first, InputIt last, const LessThan &lt) :
260  Base(first, last, lt) {}
261 
262  /// Initialize the map using an initializer list. The initializer list is a
263  /// list of pairs of items to add to the map. E.g:
264  /// @code
265  /// UT_Map<int, const char *> foo = {{1, "one"}, {2, "two"}};
266  /// @endcode
267  UT_SortedMap(std::initializer_list<value_type> init_list)
268  {
269  this->insert(init_list.begin(), init_list.end());
270  }
271 
272  int64 getMemoryUsage(bool inclusive) const
273  {
274  int64 mem = inclusive ? sizeof(*this) : 0;
275  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
276  return mem;
277  }
278 
279  bool contains(const key_type &key) const
280  {
281  return this->find(key) != this->end();
282  }
283 
284 protected:
285  template<typename VIT, typename VT>
287  {
288  VT &operator()(const VIT &v) const { return v->first; }
289  };
290  template<typename VIT, typename VT>
292  {
293  VT &operator()(const VIT &v) const { return v->second; }
294  };
295 
296  template<typename IT, typename T, typename DR>
298  public std::iterator<std::forward_iterator_tag, T>
299  {
300  public:
301  typedef T& reference;
302  typedef T* pointer;
303 
305 
306  template<typename EIT, typename EDR>
308  it(src.it) {}
309 
310  reference operator*() const { DR dr; return dr(it); }
311  pointer operator->() const { DR dr; return &dr(it); }
312 
314  { return it == o.it; }
315 
317  { return it != o.it; }
318 
320  {
321  ++it;
322  return *this;
323  }
324 
326  {
327  it = src.it;
328  return *this;
329  }
330  protected:
331  friend class UT_SortedMap<K, V, C>;
332 
333  partial_iterator_base(IT it) : it(it) {}
334  private:
335  IT it;
336  };
337 
338 public:
339  using key_iterator = partial_iterator_base<iterator, key_type,
340  deref_pair_first<iterator, key_type>>;
341  using const_key_iterator = partial_iterator_base<const_iterator, const key_type,
342  deref_pair_first<const_iterator, const key_type>>;
343  using mapped_iterator = partial_iterator_base<iterator, mapped_type,
344  deref_pair_second<iterator, mapped_type>>;
345  using const_mapped_iterator = partial_iterator_base<const_iterator, const mapped_type,
346  deref_pair_second<const_iterator, const mapped_type>>;
347 
348  /// Returns a range object that iterates over the map but returns only
349  /// the key values.
351  { return UTmakeRange(key_iterator(this->begin()),
352  key_iterator(this->end())); }
353 
354  /// Returns a const range object that iterates over the map but returns
355  /// only the key values.
357  { return UTmakeRange(const_key_iterator(this->begin()),
358  const_key_iterator(this->end())); }
359 
360  /// Returns a range object that iterates over the map but returns only
361  /// the mapped values.
363  { return UTmakeRange(mapped_iterator(this->begin()),
364  mapped_iterator(this->end())); }
365 
366  /// Returns a const range object that iterates over the map but returns
367  /// only the mapped values.
369  { return UTmakeRange(const_mapped_iterator(this->begin()),
370  const_mapped_iterator(this->end())); }
371 };
372 
373 namespace std
374 {
375  // This helper needs to live in the 'std' namespace for argument-dependent
376  // lookup to succeed.
377  template<typename OS, typename K, typename V>
378  inline OS &
379  operator<<(OS &os, const pair<K, V> &v)
380  {
381  os << "<" << v.first << ", " << v.second << ">";
382  return os;
383  }
384 }
385 
386 template<typename OS, typename K, typename V>
387 inline OS &
388 operator<<(OS &os, const UT_Map<K, V> &d)
389 {
390  os << "UT_Map" << UT_ContainerPrinter<UT_Map<K, V> >(d);
391  return os;
392 }
393 
394 template<typename OS, typename K, typename V>
395 inline OS &
396 operator<<(OS &os, const UT_SortedMap<K, V> &d)
397 {
398  os << "UT_SortedMap" << UT_ContainerPrinter<UT_SortedMap<K, V> >(d);
399  return os;
400 }
401 
402 #endif
vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
Definition: simd.h:3340
partial_iterator_base< iterator, mapped_type, deref_pair_second< iterator, mapped_type >> mapped_iterator
Definition: UT_Map.h:199
partial_iterator_base< iterator, key_type, deref_pair_first< iterator, key_type >> key_iterator
Definition: UT_Map.h:195
Base::key_type key_type
Definition: UT_Map.h:88
UT_IteratorRange< const_key_iterator > key_range() const
Definition: UT_Map.h:218
GLenum src
Definition: glew.h:2410
Unsorted map container.
Definition: UT_Map.h:83
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Map.h:272
FMT_CONSTEXPR auto begin(const C &c) -> decltype(c.begin())
Definition: format.h:251
P Equal
Definition: UT_Map.h:96
UT_Map(InputIt first, InputIt last)
Initialize the map from an iterator pair.
Definition: UT_Map.h:106
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Map.h:131
UT_IteratorRange< IterT > UTmakeRange(IterT &&b, IterT &&e)
partial_iterator_base(const partial_iterator_base< EIT, T, EDR > &src)
Definition: UT_Map.h:307
const GLint * first
Definition: glew.h:1528
const GLdouble * v
Definition: glew.h:1391
VT & operator()(const VIT &v) const
Definition: UT_Map.h:288
Base::key_type key_type
Definition: UT_Map.h:242
reference operator*() const
Definition: UT_Map.h:170
H Hasher
Definition: UT_Map.h:95
uint64 value_type
Definition: GA_PrimCompat.h:29
partial_iterator_base & operator++()
Definition: UT_Map.h:179
bool operator!=(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:316
UT_SortedMap(std::initializer_list< value_type > init_list)
Definition: UT_Map.h:267
Base::value_type value_type
Definition: UT_Map.h:244
UT_SortedMap(InputIt first, InputIt last)
Definition: UT_Map.h:256
hboost::unordered_map< K, V, H, P > Base
Definition: UT_Map.h:87
Sorted map container.
Definition: UT_Map.h:237
VT & operator()(const VIT &v) const
Definition: UT_Map.h:153
partial_iterator_base< iterator, key_type, deref_pair_first< iterator, key_type >> key_iterator
Definition: UT_Map.h:340
std::map< K, V, C > Base
Definition: UT_Map.h:241
pointer operator->() const
Definition: UT_Map.h:171
bool operator!=(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:176
Base::mapped_type mapped_type
Definition: UT_Map.h:89
partial_iterator_base< const_iterator, const key_type, deref_pair_first< const_iterator, const key_type >> const_key_iterator
Definition: UT_Map.h:197
UT_SortedMap(InputIt first, InputIt last, const LessThan &lt)
Definition: UT_Map.h:259
GLuint GLuint end
Definition: glew.h:1253
Base::iterator iterator
Definition: UT_Map.h:246
VT & operator()(const VIT &v) const
Definition: UT_Map.h:148
UT_IteratorRange< const_mapped_iterator > mapped_range() const
Definition: UT_Map.h:368
UT_Map(const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Map.h:100
UT_SortedMap()
Definition: UT_Map.h:251
partial_iterator_base< const_iterator, const mapped_type, deref_pair_second< const_iterator, const mapped_type >> const_mapped_iterator
Definition: UT_Map.h:201
UT_IteratorRange< mapped_iterator > mapped_range()
Definition: UT_Map.h:224
long long int64
Definition: SYS_Types.h:116
partial_iterator_base & operator++()
Definition: UT_Map.h:319
Base::iterator iterator
Definition: UT_Map.h:93
Base::const_iterator const_iterator
Definition: UT_Map.h:247
int64 UTgetMemoryUsage(const hboost::unordered_map< K, V, H, P > &map, bool inclusive)
Definition: UT_Map.h:48
VT & operator()(const VIT &v) const
Definition: UT_Map.h:293
bool operator==(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:313
UT_SortedMap(const LessThan &lt)
Definition: UT_Map.h:253
Base::mapped_type mapped_type
Definition: UT_Map.h:243
Base::hasher hasher
Definition: UT_Map.h:91
UT_IteratorRange< const_mapped_iterator > mapped_range() const
Definition: UT_Map.h:230
UT_IteratorRange< key_iterator > key_range()
Definition: UT_Map.h:350
partial_iterator_base & operator=(const partial_iterator_base< IT, T, DR > &src)
Definition: UT_Map.h:325
FMT_CONSTEXPR bool find(Ptr first, Ptr last, T value, Ptr &out)
Definition: format.h:2104
UT_Map(InputIt first, InputIt last, const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Map.h:111
UT_IteratorRange< mapped_iterator > mapped_range()
Definition: UT_Map.h:362
reference operator*() const
Definition: UT_Map.h:310
UT_Map(std::initializer_list< value_type > init_list)
Definition: UT_Map.h:122
UT_IteratorRange< const_key_iterator > key_range() const
Definition: UT_Map.h:356
Base::value_type value_type
Definition: UT_Map.h:90
bool contains(const key_type &key) const
Definition: UT_Map.h:279
Base::const_iterator const_iterator
Definition: UT_Map.h:94
partial_iterator_base< iterator, mapped_type, deref_pair_second< iterator, mapped_type >> mapped_iterator
Definition: UT_Map.h:344
Base::key_compare key_compare
Definition: UT_Map.h:245
partial_iterator_base< const_iterator, const key_type, deref_pair_first< const_iterator, const key_type >> const_key_iterator
Definition: UT_Map.h:342
UT_IteratorRange< key_iterator > key_range()
Definition: UT_Map.h:212
Base::key_equal key_equal
Definition: UT_Map.h:92
partial_iterator_base< const_iterator, const mapped_type, deref_pair_second< const_iterator, const mapped_type >> const_mapped_iterator
Definition: UT_Map.h:346
bool operator==(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:173
partial_iterator_base(const partial_iterator_base< EIT, T, EDR > &src)
Definition: UT_Map.h:167
bool contains(const key_type &key) const
Returns true if a value with the key is contained in the map.
Definition: UT_Map.h:139