All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
denseHashSet.h
Go to the documentation of this file.
1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 #ifndef TF_DENSE_HASH_SET_H
25 #define TF_DENSE_HASH_SET_H
26 
28 
29 #include "pxr/pxr.h"
30 #include "pxr/base/tf/hashmap.h"
31 
32 #include <memory>
33 #include <vector>
34 
35 #include <boost/compressed_pair.hpp>
36 #include <boost/operators.hpp>
37 #include <boost/iterator/iterator_facade.hpp>
38 #include <boost/utility.hpp>
39 
40 #include <cstdio>
41 
42 PXR_NAMESPACE_OPEN_SCOPE
43 
55 template <
56  class Element,
57  class HashFn,
58  class EqualElement = std::equal_to<Element>,
59  unsigned Threshold = 128
60 >
62  private boost::equality_comparable<
63  TfDenseHashSet<Element, HashFn, EqualElement, Threshold>
64  >
65 {
66 public:
67 
68  typedef Element value_type;
69 
71 
72 private:
73 
74  // The vector type holding all data for this dense hash set.
75  typedef std::vector<Element> _Vector;
76 
77  // The hash map used when the map holds more than Threshold elements.
78  typedef TfHashMap<Element, size_t, HashFn, EqualElement> _HashMap;
79 
81 
82 public:
83 
87  typedef typename _Vector::const_iterator iterator;
88 
90  typedef typename _Vector::const_iterator const_iterator;
91 
93  typedef std::pair<const_iterator, bool> insert_result;
94 
95 public:
96 
99  explicit TfDenseHashSet(
100  const HashFn &hashFn = HashFn(),
101  const EqualElement &equalElement = EqualElement())
102  {
103  _hash() = hashFn;
104  _equ() = equalElement;
105  }
106 
110  : _vectorHashFnEqualFn(rhs._vectorHashFnEqualFn) {
111  if (rhs._h)
112  _h.reset(new _HashMap(*rhs._h));
113  }
114 
117  template <class Iterator>
118  TfDenseHashSet(Iterator begin, Iterator end) {
119  insert(begin, end);
120  }
121 
124  TfDenseHashSet(std::initializer_list<Element> l) {
125  insert(l.begin(), l.end());
126  }
127 
131  swap(rhs);
132  return *this;
133  }
134 
137  TfDenseHashSet &operator=(std::initializer_list<Element> l) {
138  clear();
139  insert(l.begin(), l.end());
140  return *this;
141  }
142 
145  bool operator==(const TfDenseHashSet &rhs) const {
146 
147  if (size() != rhs.size())
148  return false;
149 
150  //XXX: Should we compare the HashFn and EqualElement too?
151  const_iterator tend = end();
152 
153  for(const_iterator iter = begin(); iter != tend; ++iter) {
154  if (!rhs.count(*iter))
155  return false;
156  }
157 
158  return true;
159  }
160 
163  void clear() {
164  _vec().clear();
165  _h.reset();
166  }
167 
170  void swap(TfDenseHashSet &rhs) {
171  _vectorHashFnEqualFn.swap(rhs._vectorHashFnEqualFn);
172  _h.swap(rhs._h);
173  }
174 
177  bool empty() const {
178  return _vec().empty();
179  }
180 
183  size_t size() const {
184  return _vec().size();
185  }
186 
190  return _vec().begin();
191  }
192 
195  const_iterator end() const {
196  return _vec().end();
197  }
198 
201  const_iterator find(const Element &k) const {
202 
203  if (_h) {
204  typename _HashMap::const_iterator iter = _h->find(k);
205  if (iter == _h->end())
206  return end();
207 
208  return _vec().begin() + iter->second;
209  }
210 
211  typename _Vector::const_iterator iter, end = _vec().end();
212 
213  for(iter = _vec().begin(); iter != end; ++iter)
214  if (_equ()(*iter, k))
215  break;
216 
217  return iter;
218  }
219 
222  size_t count(const Element &k) const {
223  return find(k) != end();
224  }
225 
229  insert_result insert(const value_type &v) {
230 
231  if (_h) {
232 
233  // Attempt to insert the new index. If this fails, we can't
234  // insert v.
235 
236  std::pair<typename _HashMap::iterator, bool> res =
237  _h->insert(std::make_pair(v, size()));
238 
239  if (!res.second)
240  return insert_result(_vec().begin() + res.first->second, false);
241 
242  } else {
243 
244  // Bail if already inserted.
245  const_iterator iter = find(v);
246  if (iter != end())
247  return insert_result(iter, false);
248  }
249 
250  // Insert at end and create table if necessary.
251  _vec().push_back(v);
252  _CreateTableIfNeeded();
253 
254  return insert_result(std::prev(end()), true);
255  }
256 
260  template<class IteratorType>
261  void insert(IteratorType i0, IteratorType i1) {
262  // Assume elements are more often than not unique, so if the sum of the
263  // current size and the size of the range is greater than or equal to
264  // the threshold, we create the table immediately so we don't do m*n
265  // work before creating the table.
266  if (size() + std::distance(i0, i1) >= Threshold)
267  _CreateTable();
268 
269  // Insert elements.
270  for (IteratorType iter = i0; iter != i1; ++iter)
271  insert(*iter);
272  }
273 
277  template <class Iterator>
278  void insert_unique(Iterator begin, Iterator end) {
279  // Special-case empty container.
280  if (empty()) {
281  _vec().assign(begin, end);
282  _CreateTableIfNeeded();
283  } else {
284  // Just insert, since duplicate checking will use the hash.
285  insert(begin, end);
286  }
287  }
288 
291  size_t erase(const Element &k) {
292 
293  const_iterator iter = find(k);
294  if (iter != end()) {
295  erase(iter);
296  return 1;
297  }
298  return 0;
299  }
300 
303  void erase(const iterator &iter) {
304 
305  // Erase key from hash table if applicable.
306  if (_h)
307  _h->erase(*iter);
308 
309  // If we are not removing that last element...
310  if (iter != std::prev(end())) {
311  using std::swap;
312 
313  // ... move the last element into the erased placed.
314  // Note that we can cast constness away because we explicitly update
315  // the TfHashMap _h below.
316  swap(*const_cast<Element *>(&(*iter)), _vec().back());
317 
318  // ... and update the moved element's index.
319  if (_h)
320  (*_h)[*iter] = iter - _vec().begin();
321  }
322 
323  _vec().pop_back();
324  }
325 
328  void erase(const iterator &i0, const iterator &i1) {
329 
330  if (_h) {
331  for(const_iterator iter = i0; iter != i1; ++iter)
332  _h->erase(iter->first);
333  }
334 
335  const_iterator vremain = _vec().erase(i0, i1);
336 
337  if (_h) {
338  for(; vremain != _vec().end(); ++vremain)
339  (*_h)[*vremain] = vremain - _vec().begin();
340  }
341  }
342 
345  void shrink_to_fit() {
346 
347  // Shrink the vector to best size.
348  //XXX: When switching to c++0x we should call _vec().shrink_to_fit().
349  _Vector(_vec()).swap(_vec());
350 
351  if (!_h)
352  return;
353 
354  size_t sz = size();
355 
356  // If we have a hash map and are underneath the threshold, discard it.
357  if (sz < Threshold) {
358 
359  _h.reset();
360 
361  } else {
362 
363  // Otherwise, allocate a new hash map with the optimal size.
364  _h.reset(new _HashMap(sz, _hash(), _equ()));
365  for(size_t i=0; i<sz; ++i)
366  (*_h)[_vec()[i]] = i;
367  }
368  }
369 
372  const Element &operator[](size_t index) const {
373  TF_VERIFY(index < size());
374  return _vec()[index];
375  }
376 
378 
379 private:
380 
381  // Helper to access the storage vector.
382  _Vector &_vec() {
383  return _vectorHashFnEqualFn.first().first();
384  }
385 
386  // Helper to access the hash functor.
387  HashFn &_hash() {
388  return _vectorHashFnEqualFn.first().second();
389  }
390 
391  // Helper to access the equality functor.
392  EqualElement &_equ() {
393  return _vectorHashFnEqualFn.second();
394  }
395 
396  // Helper to access the storage vector.
397  const _Vector &_vec() const {
398  return _vectorHashFnEqualFn.first().first();
399  }
400 
401  // Helper to access the hash functor.
402  const HashFn &_hash() const {
403  return _vectorHashFnEqualFn.first().second();
404  }
405 
406  // Helper to access the equality functor.
407  const EqualElement &_equ() const {
408  return _vectorHashFnEqualFn.second();
409  }
410 
411  // Helper to create the acceleration table if size dictates.
412  inline void _CreateTableIfNeeded() {
413  if (size() >= Threshold) {
414  _CreateTable();
415  }
416  }
417 
418  // Unconditionally create the acceleration table if it doesn't already
419  // exist.
420  inline void _CreateTable() {
421  if (!_h) {
422  _h.reset(new _HashMap(Threshold, _hash(), _equ()));
423  for(size_t i=0; i < size(); ++i)
424  (*_h)[_vec()[i]] = i;
425  }
426  }
427 
428  // Vector holding all elements along with the EqualElement functor. Since
429  // sizeof(EqualElement) == 0 in many cases we use a compressed_pair to not
430  // pay a size penalty.
431 
432  typedef
433  boost::compressed_pair<
434  boost::compressed_pair<_Vector, HashFn>,
435  EqualElement>
436  _VectorHashFnEqualFn;
437 
438  _VectorHashFnEqualFn _vectorHashFnEqualFn;
439 
440  // Optional hash map that maps from keys to vector indices.
441  std::unique_ptr<_HashMap> _h;
442 };
443 
444 PXR_NAMESPACE_CLOSE_SCOPE
445 
446 #endif // TF_DENSE_HASH_SET_H
_Vector::const_iterator const_iterator
A const_iterator type for this set.
Definition: denseHashSet.h:90
void insert_unique(Iterator begin, Iterator end)
Insert a range of unique elements into the container.
Definition: denseHashSet.h:278
TfDenseHashSet(const HashFn &hashFn=HashFn(), const EqualElement &equalElement=EqualElement())
Ctor.
Definition: denseHashSet.h:99
std::pair< const_iterator, bool > insert_result
Return type for insert() method.
Definition: denseHashSet.h:93
size_t size() const
Returns the size of the set.
Definition: denseHashSet.h:183
const_iterator begin() const
Returns an const_iterator pointing to the beginning of the set.
Definition: denseHashSet.h:189
size_t count(const Element &k) const
Returns the number of elements with key k.
Definition: denseHashSet.h:222
const_iterator find(const Element &k) const
Finds the element with key k.
Definition: denseHashSet.h:201
insert_result insert(const value_type &v)
Returns a pair of &lt;iterator, bool&gt; where iterator points to the element in the list and bool is true ...
Definition: denseHashSet.h:229
void swap(UsdStageLoadRules &l, UsdStageLoadRules &r)
Swap the contents of rules l and r.
#define TF_VERIFY(cond, format,...)
Checks a condition and reports an error if it evaluates false.
Definition: diagnostic.h:289
void swap(TfDenseHashSet &rhs)
Swaps the contents of two sets.
Definition: denseHashSet.h:170
void erase(const iterator &i0, const iterator &i1)
Erases a range from the set.
Definition: denseHashSet.h:328
size_t erase(const Element &k)
Erase element with key k.
Definition: denseHashSet.h:291
TfDenseHashSet & operator=(std::initializer_list< Element > l)
Assignment from an initializer_list.
Definition: denseHashSet.h:137
TfDenseHashSet(std::initializer_list< Element > l)
Construct from an initializer_list.
Definition: denseHashSet.h:124
_Vector::const_iterator iterator
An iterator type for this set.
Definition: denseHashSet.h:87
const_iterator end() const
Returns an const_iterator pointing to the end of the set.
Definition: denseHashSet.h:195
void shrink_to_fit()
Optimize storage space.
Definition: denseHashSet.h:345
TfDenseHashSet(Iterator begin, Iterator end)
Construct from range.
Definition: denseHashSet.h:118
TfDenseHashSet(const TfDenseHashSet &rhs)
Copy Ctor.
Definition: denseHashSet.h:109
const Element & operator[](size_t index) const
Index into set via index.
Definition: denseHashSet.h:372
void insert(IteratorType i0, IteratorType i1)
Insert a range into the hash set.
Definition: denseHashSet.h:261
void clear()
Erases all of the elements.
Definition: denseHashSet.h:163
bool empty() const
true if the set&#39;s size is 0.
Definition: denseHashSet.h:177
TfDenseHashSet & operator=(TfDenseHashSet rhs)
Assignment operator.
Definition: denseHashSet.h:130
This is a space efficient container that mimics the TfHashSet API that uses a vector for storage when...
Definition: denseHashSet.h:61
bool operator==(const TfDenseHashSet &rhs) const
Equality operator.
Definition: denseHashSet.h:145
void erase(const iterator &iter)
Erases element pointed to by iter.
Definition: denseHashSet.h:303