HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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  UT_Map(UT_Map const &other) : Base(other) {}
130 
131  /// Returns the approximate size, in bytes, of the memory consumed by this map
132  /// or, optionally, only the data contained within.
133  int64 getMemoryUsage(bool inclusive) const
134  {
135  int64 mem = inclusive ? sizeof(*this) : 0;
136  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
137  return mem;
138  }
139 
140  /// Returns @c true if a value with the @c key is contained in the map.
141  bool contains(const key_type &key) const
142  {
143  return this->find(key) != this->end();
144  }
145 
146 protected:
147  template<typename VIT, typename VT>
149  {
150  VT &operator()(const VIT &v) const { return v->first; }
151  };
152  template<typename VIT, typename VT>
154  {
155  VT &operator()(const VIT &v) const { return v->second; }
156  };
157 
158  template<typename IT, typename T, typename DR>
160  public std::iterator<std::forward_iterator_tag, T>
161  {
162  public:
163  typedef T& reference;
164  typedef T* pointer;
165 
167 
168  template<typename EIT, typename EDR>
170  it(src.it) {}
171 
172  reference operator*() const { DR dr; return dr(it); }
173  pointer operator->() const { DR dr; return &dr(it); }
174 
176  { return it == o.it; }
177 
179  { return it != o.it; }
180 
182  {
183  ++it;
184  return *this;
185  }
186 
188  {
189  it = src.it;
190  return *this;
191  }
192  protected:
193  friend class UT_Map<K, V, H, P>;
194 
195  partial_iterator_base(IT it) : it(it) {}
196  private:
197  IT it;
198  };
199 
200 public:
201  using key_iterator = partial_iterator_base<iterator, key_type,
202  deref_pair_first<iterator, key_type>>;
203  using const_key_iterator = partial_iterator_base<const_iterator, const key_type,
204  deref_pair_first<const_iterator, const key_type>>;
205  using mapped_iterator = partial_iterator_base<iterator, mapped_type,
206  deref_pair_second<iterator, mapped_type>>;
207  using const_mapped_iterator = partial_iterator_base<const_iterator, const mapped_type,
208  deref_pair_second<const_iterator, const mapped_type>>;
209 
210  /// Returns a range object that iterates over the map but returns only
211  /// the key values.
212  /// Example:
213  /// @code
214  /// UT_Map<int, const char *> foo = {{1, "one"}, {2, "two"}};
215  /// for (int key : foo.key_range())
216  /// std::cout << key << "\n";
217  /// @endcode
218 
220  { return UTmakeRange(key_iterator(this->begin()),
221  key_iterator(this->end())); }
222 
223  /// Returns a const range object that iterates over the map but returns
224  /// only the key values.
226  { return UTmakeRange(const_key_iterator(this->begin()),
227  const_key_iterator(this->end())); }
228 
229  /// Returns a range object that iterates over the map but returns only
230  /// the mapped values.
232  { return UTmakeRange(mapped_iterator(this->begin()),
233  mapped_iterator(this->end())); }
234 
235  /// Returns a const range object that iterates over the map but returns
236  /// only the mapped values.
238  { return UTmakeRange(const_mapped_iterator(this->begin()),
239  const_mapped_iterator(this->end())); }
240 };
241 
242 /// Sorted map container.
243 template<typename K, typename V, typename C = std::less<K> >
244 class UT_SortedMap : public std::map<K, V, C>
245 {
246 public:
247  // Hoisting of base types.
248  typedef std::map<K, V, C> Base;
249  typedef typename Base::key_type key_type;
250  typedef typename Base::mapped_type mapped_type;
251  typedef typename Base::value_type value_type;
252  typedef typename Base::key_compare key_compare;
253  typedef typename Base::iterator iterator;
254  typedef typename Base::const_iterator const_iterator;
255 
256  typedef C LessThan;
257 
259 
260  explicit UT_SortedMap(const LessThan &lt) : Base(lt) {}
261 
262  template<typename InputIt>
263  UT_SortedMap(InputIt first, InputIt last) : Base(first, last) {}
264 
265  template<typename InputIt>
266  UT_SortedMap(InputIt first, InputIt last, const LessThan &lt) :
267  Base(first, last, lt) {}
268 
269  UT_SortedMap(const UT_SortedMap &other) : Base(other) {}
270 
271  /// Initialize the map using an initializer list. The initializer list is a
272  /// list of pairs of items to add to the map. E.g:
273  /// @code
274  /// UT_Map<int, const char *> foo = {{1, "one"}, {2, "two"}};
275  /// @endcode
276  UT_SortedMap(std::initializer_list<value_type> init_list)
277  {
278  this->insert(init_list.begin(), init_list.end());
279  }
280 
281  int64 getMemoryUsage(bool inclusive) const
282  {
283  int64 mem = inclusive ? sizeof(*this) : 0;
284  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
285  return mem;
286  }
287 
288  bool contains(const key_type &key) const
289  {
290  return this->find(key) != this->end();
291  }
292 
293 protected:
294  template<typename VIT, typename VT>
296  {
297  VT &operator()(const VIT &v) const { return v->first; }
298  };
299  template<typename VIT, typename VT>
301  {
302  VT &operator()(const VIT &v) const { return v->second; }
303  };
304 
305  template<typename IT, typename T, typename DR>
307  public std::iterator<std::forward_iterator_tag, T>
308  {
309  public:
310  typedef T& reference;
311  typedef T* pointer;
312 
314 
315  template<typename EIT, typename EDR>
317  it(src.it) {}
318 
319  reference operator*() const { DR dr; return dr(it); }
320  pointer operator->() const { DR dr; return &dr(it); }
321 
323  { return it == o.it; }
324 
326  { return it != o.it; }
327 
329  {
330  ++it;
331  return *this;
332  }
333 
335  {
336  it = src.it;
337  return *this;
338  }
339  protected:
340  friend class UT_SortedMap<K, V, C>;
341 
342  partial_iterator_base(IT it) : it(it) {}
343  private:
344  IT it;
345  };
346 
347 public:
348  using key_iterator = partial_iterator_base<iterator, key_type,
349  deref_pair_first<iterator, key_type>>;
350  using const_key_iterator = partial_iterator_base<const_iterator, const key_type,
351  deref_pair_first<const_iterator, const key_type>>;
352  using mapped_iterator = partial_iterator_base<iterator, mapped_type,
353  deref_pair_second<iterator, mapped_type>>;
354  using const_mapped_iterator = partial_iterator_base<const_iterator, const mapped_type,
355  deref_pair_second<const_iterator, const mapped_type>>;
356 
357  /// Returns a range object that iterates over the map but returns only
358  /// the key values.
360  { return UTmakeRange(key_iterator(this->begin()),
361  key_iterator(this->end())); }
362 
363  /// Returns a const range object that iterates over the map but returns
364  /// only the key values.
366  { return UTmakeRange(const_key_iterator(this->begin()),
367  const_key_iterator(this->end())); }
368 
369  /// Returns a range object that iterates over the map but returns only
370  /// the mapped values.
372  { return UTmakeRange(mapped_iterator(this->begin()),
373  mapped_iterator(this->end())); }
374 
375  /// Returns a const range object that iterates over the map but returns
376  /// only the mapped values.
378  { return UTmakeRange(const_mapped_iterator(this->begin()),
379  const_mapped_iterator(this->end())); }
380 };
381 
382 namespace std
383 {
384  // This helper needs to live in the 'std' namespace for argument-dependent
385  // lookup to succeed.
386  template<typename OS, typename K, typename V>
387  inline OS &
388  operator<<(OS &os, const pair<K, V> &v)
389  {
390  os << "<" << v.first << ", " << v.second << ">";
391  return os;
392  }
393 }
394 
395 template<typename OS, typename K, typename V>
396 inline OS &
397 operator<<(OS &os, const UT_Map<K, V> &d)
398 {
399  os << "UT_Map" << UT_ContainerPrinter<UT_Map<K, V> >(d);
400  return os;
401 }
402 
403 template<typename OS, typename K, typename V>
404 inline OS &
405 operator<<(OS &os, const UT_SortedMap<K, V> &d)
406 {
407  os << "UT_SortedMap" << UT_ContainerPrinter<UT_SortedMap<K, V> >(d);
408  return os;
409 }
410 
411 #endif
partial_iterator_base< iterator, mapped_type, deref_pair_second< iterator, mapped_type >> mapped_iterator
Definition: UT_Map.h:206
GLint first
Definition: glcorearb.h:404
partial_iterator_base< iterator, key_type, deref_pair_first< iterator, key_type >> key_iterator
Definition: UT_Map.h:202
Base::key_type key_type
Definition: UT_Map.h:88
UT_IteratorRange< const_key_iterator > key_range() const
Definition: UT_Map.h:225
Unsorted map container.
Definition: UT_Map.h:83
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Map.h:281
const GLdouble * v
Definition: glcorearb.h:836
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:133
UT_IteratorRange< IterT > UTmakeRange(IterT &&b, IterT &&e)
partial_iterator_base(const partial_iterator_base< EIT, T, EDR > &src)
Definition: UT_Map.h:316
VT & operator()(const VIT &v) const
Definition: UT_Map.h:297
Base::key_type key_type
Definition: UT_Map.h:249
reference operator*() const
Definition: UT_Map.h:172
H Hasher
Definition: UT_Map.h:95
uint64 value_type
Definition: GA_PrimCompat.h:29
partial_iterator_base & operator++()
Definition: UT_Map.h:181
bool operator!=(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:325
UT_SortedMap(const UT_SortedMap &other)
Definition: UT_Map.h:269
UT_SortedMap(std::initializer_list< value_type > init_list)
Definition: UT_Map.h:276
Base::value_type value_type
Definition: UT_Map.h:251
long long int64
Definition: SYS_Types.h:100
UT_SortedMap(InputIt first, InputIt last)
Definition: UT_Map.h:263
hboost::unordered_map< K, V, H, P > Base
Definition: UT_Map.h:87
Sorted map container.
Definition: UT_Map.h:244
VT & operator()(const VIT &v) const
Definition: UT_Map.h:155
partial_iterator_base< iterator, key_type, deref_pair_first< iterator, key_type >> key_iterator
Definition: UT_Map.h:349
std::map< K, V, C > Base
Definition: UT_Map.h:248
pointer operator->() const
Definition: UT_Map.h:173
bool operator!=(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:178
Base::mapped_type mapped_type
Definition: UT_Map.h:89
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:204
UT_SortedMap(InputIt first, InputIt last, const LessThan &lt)
Definition: UT_Map.h:266
Base::iterator iterator
Definition: UT_Map.h:253
VT & operator()(const VIT &v) const
Definition: UT_Map.h:150
UT_IteratorRange< const_mapped_iterator > mapped_range() const
Definition: UT_Map.h:377
UT_Map(const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Map.h:100
UT_SortedMap()
Definition: UT_Map.h:258
partial_iterator_base< const_iterator, const mapped_type, deref_pair_second< const_iterator, const mapped_type >> const_mapped_iterator
Definition: UT_Map.h:208
UT_IteratorRange< mapped_iterator > mapped_range()
Definition: UT_Map.h:231
partial_iterator_base & operator++()
Definition: UT_Map.h:328
Base::iterator iterator
Definition: UT_Map.h:93
UT_Map(UT_Map const &other)
Definition: UT_Map.h:129
Base::const_iterator const_iterator
Definition: UT_Map.h:254
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:302
bool operator==(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:322
UT_SortedMap(const LessThan &lt)
Definition: UT_Map.h:260
Base::mapped_type mapped_type
Definition: UT_Map.h:250
Base::hasher hasher
Definition: UT_Map.h:91
UT_IteratorRange< const_mapped_iterator > mapped_range() const
Definition: UT_Map.h:237
partial_iterator_base & operator=(const partial_iterator_base< IT, T, DR > &src)
Definition: UT_Map.h:187
UT_IteratorRange< key_iterator > key_range()
Definition: UT_Map.h:359
partial_iterator_base & operator=(const partial_iterator_base< IT, T, DR > &src)
Definition: UT_Map.h:334
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:371
reference operator*() const
Definition: UT_Map.h:319
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:365
Base::value_type value_type
Definition: UT_Map.h:90
bool contains(const key_type &key) const
Definition: UT_Map.h:288
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:353
Base::key_compare key_compare
Definition: UT_Map.h:252
partial_iterator_base< const_iterator, const key_type, deref_pair_first< const_iterator, const key_type >> const_key_iterator
Definition: UT_Map.h:351
UT_IteratorRange< key_iterator > key_range()
Definition: UT_Map.h:219
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:355
bool operator==(const partial_iterator_base< IT, T, DR > &o) const
Definition: UT_Map.h:175
partial_iterator_base(const partial_iterator_base< EIT, T, EDR > &src)
Definition: UT_Map.h:169
bool contains(const key_type &key) const
Returns true if a value with the key is contained in the map.
Definition: UT_Map.h:141
GLenum src
Definition: glcorearb.h:1792