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 
325  protected:
326  friend class UT_SortedMap<K, V, C>;
327 
328  partial_iterator_base(IT it) : it(it) {}
329  private:
330  IT it;
331  };
332 
333 public:
334  using key_iterator = partial_iterator_base<iterator, key_type,
335  deref_pair_first<iterator, key_type>>;
336  using const_key_iterator = partial_iterator_base<const_iterator, const key_type,
337  deref_pair_first<const_iterator, const key_type>>;
338  using mapped_iterator = partial_iterator_base<iterator, mapped_type,
339  deref_pair_second<iterator, mapped_type>>;
340  using const_mapped_iterator = partial_iterator_base<const_iterator, const mapped_type,
341  deref_pair_second<const_iterator, const mapped_type>>;
342 
343  /// Returns a range object that iterates over the map but returns only
344  /// the key values.
346  { return UTmakeRange(key_iterator(this->begin()),
347  key_iterator(this->end())); }
348 
349  /// Returns a const range object that iterates over the map but returns
350  /// only the key values.
352  { return UTmakeRange(const_key_iterator(this->begin()),
353  const_key_iterator(this->end())); }
354 
355  /// Returns a range object that iterates over the map but returns only
356  /// the mapped values.
358  { return UTmakeRange(mapped_iterator(this->begin()),
359  mapped_iterator(this->end())); }
360 
361  /// Returns a const range object that iterates over the map but returns
362  /// only the mapped values.
364  { return UTmakeRange(const_mapped_iterator(this->begin()),
365  const_mapped_iterator(this->end())); }
366 };
367 
368 namespace std
369 {
370  // This helper needs to live in the 'std' namespace for argument-dependent
371  // lookup to succeed.
372  template<typename OS, typename K, typename V>
373  inline OS &
374  operator<<(OS &os, const pair<K, V> &v)
375  {
376  os << "<" << v.first << ", " << v.second << ">";
377  return os;
378  }
379 }
380 
381 template<typename OS, typename K, typename V>
382 inline OS &
383 operator<<(OS &os, const UT_Map<K, V> &d)
384 {
385  os << "UT_Map" << UT_ContainerPrinter<UT_Map<K, V> >(d);
386  return os;
387 }
388 
389 template<typename OS, typename K, typename V>
390 inline OS &
391 operator<<(OS &os, const UT_SortedMap<K, V> &d)
392 {
393  os << "UT_SortedMap" << UT_ContainerPrinter<UT_SortedMap<K, V> >(d);
394  return os;
395 }
396 
397 #endif
vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
Definition: simd.h:3414
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
Unsorted map container.
Definition: UT_Map.h:83
GLint first
Definition: glcorearb.h:404
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Map.h:272
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
VT & operator()(const VIT &v) const
Definition: UT_Map.h:288
Base::key_type key_type
Definition: UT_Map.h:242
GLenum src
Definition: glcorearb.h:1792
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:335
FMT_CONSTEXPR bool find(Ptr first, Ptr last, T value, Ptr &out)
Definition: format.h:2929
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
const GLdouble * v
Definition: glcorearb.h:836
GLuint GLuint end
Definition: glcorearb.h:474
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
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:363
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
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: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:345
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:357
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:351
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:339
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:337
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:341
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