HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_Set.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_Set.h (UT Library, C++)
7  *
8  * COMMENTS: Wrapper for an unordered set data structure. Prefer to use
9  * this to std::set since hboost::unordered_set is more
10  * efficient when order is not needed.
11  */
12 
13 #ifndef __UT_Set__
14 #define __UT_Set__
15 
16 #include "UT_ContainerPrinter.h"
17 
18 #include <set>
19 #include <hboost/unordered_set.hpp>
20 
21 template<typename K, typename H, typename P>
22 int64
23 UTgetMemoryUsage(const hboost::unordered_set<K, H, P> &set, bool inclusive)
24 {
25  int64 mem = inclusive ? sizeof(set) : 0;
26  // Buckets only contain a pointer to the node
27  mem += set.bucket_count() * sizeof(void*);
28  // Nodes contain the hash value, a pointer to the next node,
29  // and the key.
30  mem += set.size() * (sizeof(size_t) + sizeof(void*) + sizeof(K));
31  return mem;
32 }
33 
34 template<typename K, typename C>
35 int64
36 UTgetMemoryUsage(const std::set<K, C> &set, bool inclusive)
37 {
38  int64 mem = inclusive ? sizeof(set) : 0;
39 
40  // NOTE: If the comparator object of type C owns any memory
41  // (i.e. apart from itself) when default constructed
42  // or copy constructed, that memory won't be counted.
43 
44  // NOTE: This count is for the VC++ 2010 implementation
45  // of std::map, but others should be in the ballpark.
46  // Nodes contain pointers to the left, parent, and right,
47  // the key, a colour in a char (red or black),
48  // and a flag in a char indicating if the node is the head,
49  // (in which case the key is ignored).
50  // Round up to a multiple of 4 on the size of each node.
51  mem += (set.size() + 1) * ((3*sizeof(void*) + sizeof(K)
52  + 2*sizeof(char) + 3) & ~3);
53  return mem;
54 }
55 
56 template<typename K,
57  typename H = hboost::hash<K>, typename P = std::equal_to<K> >
58 class UT_Set : public hboost::unordered_set<K, H, P>
59 {
60 public:
61  typedef hboost::unordered_set<K, H, P> Base;
62  typedef H Hasher;
63  typedef P Equal;
64 
65  explicit UT_Set(
66  const Hasher &hf = Hasher(),
67  const Equal &eql = Equal()) :
68  Base(hboost::unordered::detail::default_bucket_count, hf, eql) {}
69 
70  template <typename InputIt>
71  UT_Set(InputIt first, InputIt last,
72  const Hasher &hf = Hasher(),
73  const Equal &eql = Equal()) :
74  Base(first, last, hboost::unordered::detail::default_bucket_count,
75  hf, eql) {}
76 
77  // Note: This can be removed when C++11 support is enabled due to existence
78  // of initializer lists.
79  UT_Set(const K &k,
80  const Hasher &hf = Hasher(),
81  const Equal &eql = Equal())
82  : Base(hboost::unordered::detail::default_bucket_count, hf, eql)
83  {
84  this->insert(k);
85  }
86 
87  /// Constructs a set from an initializer list:
88  /// UT_Set<int> some_set({5,123,500});
89  UT_Set(std::initializer_list<K> init,
90  const Hasher &hf = Hasher(),
91  const Equal &eql = Equal())
92  : Base(hboost::unordered::detail::default_bucket_count, hf, eql)
93  {
94  for (auto &&p = init.begin(); p != init.end(); ++p) {
95  this->insert(*p);
96  }
97  }
98 
99  int64 getMemoryUsage(bool inclusive) const
100  {
101  int64 mem = inclusive ? sizeof(*this) : 0;
102  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
103  return mem;
104  }
105 
106  /// Determines membership in a set, a bit more semantically readable
107  /// than count() or find()
108  bool contains(const K &key) const
109  { return Base::count(key) > 0; }
110 
111  bool contains(const UT_Set<K> &src) const
112  { for (const_iterator it = src.begin(); it != src.end(); ++it)
113  if (!contains(*it))
114  return false;
115  return true; }
116 
117  /// The implementation of clear() is O(bucket_count()), not O(size()),
118  /// which can cause unexpected performance issues if the map has a large
119  /// capacity.
120  /// For std::unordered_map this was defect 2550
121  /// (http://cplusplus.github.io/LWG/lwg-defects.html#2550)
122  /// When updating or changing the underlying implemention, verify if this
123  /// is still necessary.
124  void clear()
125  {
126  // clear() is slightly faster than erase(begin(), end()) in typical
127  // scenarios, so only switch over to erase() once there are a lot of
128  // empty buckets.
129  if (Base::bucket_count() > 20 * Base::size())
130  Base::erase(Base::begin(), Base::end());
131  else
132  Base::clear();
133  }
134 
135  /// Set-wise boolean operations.
137  { for (const_iterator it = src.begin(); it != src.end(); ++it)
138  this->insert(*it);
139  return *this; }
142  for (const_iterator it = src.begin(); it != src.end(); ++it)
143  if (contains(*it))
144  result.insert(*it);
145  *this = std::move(result);
146  return *this; }
148  { for (const_iterator it = src.begin(); it != src.end(); ++it)
149  this->erase(*it);
150  return *this; }
151 
152 public:
153  // Lowering of base types
154  typedef typename Base::key_type key_type;
155  typedef typename Base::value_type value_type;
156  typedef typename Base::hasher hasher;
157  typedef typename Base::key_equal key_equal;
158  typedef typename Base::iterator iterator;
159  typedef typename Base::const_iterator const_iterator;
160 };
161 
162 
163 
164 template<typename K, typename C = std::less<K> >
165 class UT_SortedSet : public std::set<K, C>
166 {
167 public:
168  typedef std::set<K, C> Base;
169  typedef C LessThan;
170 
172 
173  explicit UT_SortedSet(const LessThan& lt) : Base(lt) {}
174 
175  template<typename InputIt>
176  UT_SortedSet(InputIt first, InputIt last) : Base(first, last) {}
177 
178  template<typename InputIt>
179  UT_SortedSet(InputIt first, InputIt last, const LessThan &lt) :
180  Base(first, last, lt) {}
181 
182  // Note: This can be removed when C++11 support is enabled due to existence
183  // of initializer lists.
184  UT_SortedSet(const K &k) : Base()
185  {
186  this->insert(k);
187  }
188 
189  int64 getMemoryUsage(bool inclusive) const
190  {
191  int64 mem = inclusive ? sizeof(*this) : 0;
192  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
193  return mem;
194  }
195 
196  /// Determines membership in a set, a bit more semantically readable
197  /// than count() or find()
198  bool contains(const K &key) const
199  { return this->count(key) > 0; }
200 
201  bool contains(const UT_SortedSet<K> &src) const
202  { for (const_iterator it = src.begin(); it != src.end(); ++it)
203  if (!contains(*it))
204  return false;
205  return true; }
206 
207  /// Set-wise boolean operations.
209  { for (const_iterator it = src.begin(); it != src.end(); ++it)
210  this->insert(*it);
211  return *this; }
214  for (const_iterator it = src.begin(); it != src.end(); ++it)
215  if (contains(*it))
216  result.insert(*it);
217  *this = std::move(result);
218  return *this; }
220  { for (const_iterator it = src.begin(); it != src.end(); ++it)
221  this->erase(*it);
222  return *this; }
223 
224 public:
225  // Lowering of base types.
226  typedef typename Base::key_type key_type;
227  typedef typename Base::value_type value_type;
228  typedef typename Base::key_compare key_compare;
229  typedef typename Base::iterator iterator;
230  typedef typename Base::const_iterator const_iterator;
231 };
232 
233 template<typename OS, typename S>
234 inline OS &
235 operator<<(OS &os, const UT_Set<S> &d)
236 {
237  os << "UT_Set" << UT_ContainerPrinter<UT_Set<S> >(d);
238  return os;
239 }
240 
241 template<typename OS, typename S>
242 inline OS &
243 operator<<(OS &os, const UT_SortedSet<S> &d)
244 {
245  os << "UT_SortedSet" << UT_ContainerPrinter<UT_SortedSet<S> >(d);
246  return os;
247 }
248 
249 
250 #endif
GLint first
Definition: glcorearb.h:405
UT_Set(InputIt first, InputIt last, const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:71
Definition: UT_Set.h:58
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Set.h:99
void clear()
Definition: UT_Set.h:124
Base::key_type key_type
Definition: UT_Set.h:154
UT_Set< K, H, P > & operator|=(const UT_Set< K, H, P > &src)
Set-wise boolean operations.
Definition: UT_Set.h:136
bool contains(const UT_SortedSet< K > &src) const
Definition: UT_Set.h:201
Base::const_iterator const_iterator
Definition: UT_Set.h:159
hboost::unordered_set< K, H, P > Base
Definition: UT_Set.h:61
UT_SortedSet< K, C > & operator&=(const UT_SortedSet< K, C > &src)
Definition: UT_Set.h:212
GA_API const UT_StringHolder P
**But if you need a result
Definition: thread.h:613
OIIO_FORCEINLINE vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
Definition: simd.h:3436
uint64 value_type
Definition: GA_PrimCompat.h:29
UT_SortedSet()
Definition: UT_Set.h:171
Base::key_compare key_compare
Definition: UT_Set.h:228
Base::value_type value_type
Definition: UT_Set.h:227
H Hasher
Definition: UT_Set.h:62
UT_SortedSet(const LessThan &lt)
Definition: UT_Set.h:173
UT_Set(const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:65
Base::iterator iterator
Definition: UT_Set.h:229
bool contains(const K &key) const
Definition: UT_Set.h:198
UT_SortedSet(InputIt first, InputIt last)
Definition: UT_Set.h:176
GLuint GLuint end
Definition: glcorearb.h:475
Base::value_type value_type
Definition: UT_Set.h:155
bool contains(const UT_Set< K > &src) const
Definition: UT_Set.h:111
UT_SortedSet(const K &k)
Definition: UT_Set.h:184
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Set.h:189
long long int64
Definition: SYS_Types.h:116
Base::const_iterator const_iterator
Definition: UT_Set.h:230
STATIC_INLINE uint64_t H(uint64_t x, uint64_t y, uint64_t mul, int r)
Definition: farmhash.h:701
int64 UTgetMemoryUsage(const hboost::unordered_set< K, H, P > &set, bool inclusive)
Definition: UT_Set.h:23
Base::key_equal key_equal
Definition: UT_Set.h:157
GLsizeiptr size
Definition: glcorearb.h:664
UT_Set< K, H, P > & operator&=(const UT_Set< K, H, P > &src)
Definition: UT_Set.h:140
Base::key_type key_type
Definition: UT_Set.h:226
UT_SortedSet< K, C > & operator|=(const UT_SortedSet< K, C > &src)
Set-wise boolean operations.
Definition: UT_Set.h:208
UT_Set< K, H, P > & operator-=(const UT_Set< K, H, P > &src)
Definition: UT_Set.h:147
std::set< K, C > Base
Definition: UT_Set.h:168
UT_SortedSet(InputIt first, InputIt last, const LessThan &lt)
Definition: UT_Set.h:179
UT_Set(std::initializer_list< K > init, const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:89
bool contains(const K &key) const
Definition: UT_Set.h:108
Base::hasher hasher
Definition: UT_Set.h:156
GLint GLsizei count
Definition: glcorearb.h:405
P Equal
Definition: UT_Set.h:63
UT_SortedSet< K, C > & operator-=(const UT_SortedSet< K, C > &src)
Definition: UT_Set.h:219
UT_Set(const K &k, const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:79
GLenum src
Definition: glcorearb.h:1793
Base::iterator iterator
Definition: UT_Set.h:158
PcpNodeRef_ChildrenIterator begin(const PcpNodeRef::child_const_range &r)
Support for range-based for loops for PcpNodeRef children ranges.
Definition: node.h:483