Loading...
Searching...
No Matches
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 PXR_BASE_TF_DENSE_HASH_SET_H
25#define PXR_BASE_TF_DENSE_HASH_SET_H
26
28
29#include "pxr/pxr.h"
31#include "pxr/base/tf/hashmap.h"
32
33#include <memory>
34#include <vector>
35
36PXR_NAMESPACE_OPEN_SCOPE
37
49template <
50 class Element,
51 class HashFn,
52 class EqualElement = std::equal_to<Element>,
53 unsigned Threshold = 128
54>
56{
57public:
58
59 typedef Element value_type;
60
62
63private:
64
65 // The vector type holding all data for this dense hash set.
66 typedef std::vector<Element> _Vector;
67
68 // The hash map used when the map holds more than Threshold elements.
69 typedef TfHashMap<Element, size_t, HashFn, EqualElement> _HashMap;
70
72
73public:
74
78 typedef typename _Vector::const_iterator iterator;
79
81 typedef typename _Vector::const_iterator const_iterator;
82
84 typedef std::pair<const_iterator, bool> insert_result;
85
86public:
87
91 const HashFn &hashFn = HashFn(),
92 const EqualElement &equalElement = EqualElement())
93 {
94 _hash() = hashFn;
95 _equ() = equalElement;
96 }
97
101 : _storage(rhs._storage) {
102 if (rhs._h) {
103 _h = std::make_unique<_HashMap>(*rhs._h);
104 }
105 }
106
110
113 template <class Iterator>
114 TfDenseHashSet(Iterator begin, Iterator end) {
115 insert(begin, end);
116 }
117
120 TfDenseHashSet(std::initializer_list<Element> l) {
121 insert(l.begin(), l.end());
122 }
123
127 if (this != &rhs) {
128 TfDenseHashSet temp(rhs);
129 temp.swap(*this);
130 }
131 return *this;
132 }
133
137
140 TfDenseHashSet &operator=(std::initializer_list<Element> l) {
141 clear();
142 insert(l.begin(), l.end());
143 return *this;
144 }
145
148 bool operator==(const TfDenseHashSet &rhs) const {
149
150 if (size() != rhs.size())
151 return false;
152
153 //XXX: Should we compare the HashFn and EqualElement too?
154 const_iterator tend = end();
155
156 for(const_iterator iter = begin(); iter != tend; ++iter) {
157 if (!rhs.count(*iter))
158 return false;
159 }
160
161 return true;
162 }
163
164 bool operator!=(const TfDenseHashSet &rhs) const {
165 return !(*this == rhs);
166 }
167
170 void clear() {
171 _vec().clear();
172 _h.reset();
173 }
174
177 void swap(TfDenseHashSet &rhs) {
178 _storage.swap(rhs._storage);
179 _h.swap(rhs._h);
180 }
181
184 bool empty() const {
185 return _vec().empty();
186 }
187
190 size_t size() const {
191 return _vec().size();
192 }
193
197 return _vec().begin();
198 }
199
203 return _vec().end();
204 }
205
208 const_iterator find(const Element &k) const {
209
210 if (_h) {
211 typename _HashMap::const_iterator iter = _h->find(k);
212 if (iter == _h->end())
213 return end();
214
215 return _vec().begin() + iter->second;
216 }
217
218 typename _Vector::const_iterator iter, end = _vec().end();
219
220 for(iter = _vec().begin(); iter != end; ++iter)
221 if (_equ()(*iter, k))
222 break;
223
224 return iter;
225 }
226
229 size_t count(const Element &k) const {
230 return find(k) != end();
231 }
232
236 insert_result insert(const value_type &v) {
237
238 if (_h) {
239
240 // Attempt to insert the new index. If this fails, we can't
241 // insert v.
242
243 std::pair<typename _HashMap::iterator, bool> res =
244 _h->insert(std::make_pair(v, size()));
245
246 if (!res.second)
247 return insert_result(_vec().begin() + res.first->second, false);
248
249 } else {
250
251 // Bail if already inserted.
252 const_iterator iter = find(v);
253 if (iter != end())
254 return insert_result(iter, false);
255 }
256
257 // Insert at end and create table if necessary.
258 _vec().push_back(v);
259 _CreateTableIfNeeded();
260
261 return insert_result(std::prev(end()), true);
262 }
263
267 template<class IteratorType>
268 void insert(IteratorType i0, IteratorType i1) {
269 // Assume elements are more often than not unique, so if the sum of the
270 // current size and the size of the range is greater than or equal to
271 // the threshold, we create the table immediately so we don't do m*n
272 // work before creating the table.
273 if (size() + std::distance(i0, i1) >= Threshold)
274 _CreateTable();
275
276 // Insert elements.
277 for (IteratorType iter = i0; iter != i1; ++iter)
278 insert(*iter);
279 }
280
284 template <class Iterator>
285 void insert_unique(Iterator begin, Iterator end) {
286 // Special-case empty container.
287 if (empty()) {
288 _vec().assign(begin, end);
289 _CreateTableIfNeeded();
290 } else {
291 // Just insert, since duplicate checking will use the hash.
292 insert(begin, end);
293 }
294 }
295
298 size_t erase(const Element &k) {
299
300 const_iterator iter = find(k);
301 if (iter != end()) {
302 erase(iter);
303 return 1;
304 }
305 return 0;
306 }
307
310 void erase(const iterator &iter) {
311
312 // Erase key from hash table if applicable.
313 if (_h)
314 _h->erase(*iter);
315
316 // If we are not removing that last element...
317 if (iter != std::prev(end())) {
318 using std::swap;
319
320 // ... move the last element into the erased placed.
321 // Note that we can cast constness away because we explicitly update
322 // the TfHashMap _h below.
323 swap(*const_cast<Element *>(&(*iter)), _vec().back());
324
325 // ... and update the moved element's index.
326 if (_h)
327 (*_h)[*iter] = iter - _vec().begin();
328 }
329
330 _vec().pop_back();
331 }
332
335 void erase(const iterator &i0, const iterator &i1) {
336
337 if (_h) {
338 for(const_iterator iter = i0; iter != i1; ++iter)
339 _h->erase(iter->first);
340 }
341
342 const_iterator vremain = _vec().erase(i0, i1);
343
344 if (_h) {
345 for(; vremain != _vec().end(); ++vremain)
346 (*_h)[*vremain] = vremain - _vec().begin();
347 }
348 }
349
353
354 // Shrink the vector to best size.
355 _vec().shrink_to_fit();
356
357 if (!_h)
358 return;
359
360 size_t sz = size();
361
362 // If we have a hash map and are underneath the threshold, discard it.
363 if (sz < Threshold) {
364
365 _h.reset();
366
367 } else {
368
369 // Otherwise, allocate a new hash map with the optimal size.
370 _h.reset(new _HashMap(sz, _hash(), _equ()));
371 for(size_t i=0; i<sz; ++i)
372 (*_h)[_vec()[i]] = i;
373 }
374 }
375
378 const Element &operator[](size_t index) const {
379 TF_VERIFY(index < size());
380 return _vec()[index];
381 }
382
384
385private:
386
387 // Helper to access the storage vector.
388 _Vector &_vec() {
389 return _storage.vector;
390 }
391
392 // Helper to access the hash functor.
393 HashFn &_hash() {
394 return _storage;
395 }
396
397 // Helper to access the equality functor.
398 EqualElement &_equ() {
399 return _storage;
400 }
401
402 // Helper to access the storage vector.
403 const _Vector &_vec() const {
404 return _storage.vector;
405 }
406
407 // Helper to access the hash functor.
408 const HashFn &_hash() const {
409 return _storage;
410 }
411
412 // Helper to access the equality functor.
413 const EqualElement &_equ() const {
414 return _storage;
415 }
416
417 // Helper to create the acceleration table if size dictates.
418 inline void _CreateTableIfNeeded() {
419 if (size() >= Threshold) {
420 _CreateTable();
421 }
422 }
423
424 // Unconditionally create the acceleration table if it doesn't already
425 // exist.
426 inline void _CreateTable() {
427 if (!_h) {
428 _h.reset(new _HashMap(Threshold, _hash(), _equ()));
429 for(size_t i=0; i < size(); ++i)
430 (*_h)[_vec()[i]] = i;
431 }
432 }
433
434 // Since sizeof(EqualElement) == 0 and sizeof(HashFn) == 0 in many cases
435 // we use the empty base optimization to not pay a size penalty.
436 // In C++20, explore using [[no_unique_address]] as an alternative
437 // way to get this optimization.
438 struct ARCH_EMPTY_BASES _CompressedStorage :
439 private EqualElement, private HashFn {
440 static_assert(!std::is_same<EqualElement, HashFn>::value,
441 "EqualElement and HashFn must be distinct types.");
442 _CompressedStorage() = default;
443 _CompressedStorage(const EqualElement& equal, const HashFn& hashFn)
444 : EqualElement(equal), HashFn(hashFn) {}
445
446 void swap(_CompressedStorage& other) {
447 using std::swap;
448 vector.swap(other.vector);
449 swap(static_cast<EqualElement&>(*this),
450 static_cast<EqualElement&>(other));
451 swap(static_cast<HashFn&>(*this), static_cast<HashFn&>(other));
452 }
453 _Vector vector;
454 friend class TfDenseHashSet;
455 };
456 _CompressedStorage _storage;
457
458 // Optional hash map that maps from keys to vector indices.
459 std::unique_ptr<_HashMap> _h;
460};
461
462PXR_NAMESPACE_CLOSE_SCOPE
463
464#endif // PXR_BASE_TF_DENSE_HASH_SET_H
Define function attributes.
#define ARCH_EMPTY_BASES
Macro to begin the definition of a class that is using private inheritance to take advantage of the e...
Definition: attributes.h:170
This is a space efficient container that mimics the TfHashSet API that uses a vector for storage when...
Definition: denseHashSet.h:56
size_t erase(const Element &k)
Erase element with key k.
Definition: denseHashSet.h:298
size_t size() const
Returns the size of the set.
Definition: denseHashSet.h:190
const_iterator begin() const
Returns an const_iterator pointing to the beginning of the set.
Definition: denseHashSet.h:196
TfDenseHashSet(TfDenseHashSet &&rhs)=default
Move Ctor.
TfDenseHashSet(Iterator begin, Iterator end)
Construct from range.
Definition: denseHashSet.h:114
const Element & operator[](size_t index) const
Index into set via index.
Definition: denseHashSet.h:378
void insert(IteratorType i0, IteratorType i1)
Insert a range into the hash set.
Definition: denseHashSet.h:268
size_t count(const Element &k) const
Returns the number of elements with key k.
Definition: denseHashSet.h:229
TfDenseHashSet(const HashFn &hashFn=HashFn(), const EqualElement &equalElement=EqualElement())
Ctor.
Definition: denseHashSet.h:90
void shrink_to_fit()
Optimize storage space.
Definition: denseHashSet.h:352
bool empty() const
true if the set's size is 0.
Definition: denseHashSet.h:184
void erase(const iterator &i0, const iterator &i1)
Erases a range from the set.
Definition: denseHashSet.h:335
void erase(const iterator &iter)
Erases element pointed to by iter.
Definition: denseHashSet.h:310
TfDenseHashSet & operator=(TfDenseHashSet &&rhs)=default
Move assignment operator.
void swap(TfDenseHashSet &rhs)
Swaps the contents of two sets.
Definition: denseHashSet.h:177
std::pair< const_iterator, bool > insert_result
Return type for insert() method.
Definition: denseHashSet.h:84
const_iterator find(const Element &k) const
Finds the element with key k.
Definition: denseHashSet.h:208
TfDenseHashSet(std::initializer_list< Element > l)
Construct from an initializer_list.
Definition: denseHashSet.h:120
_Vector::const_iterator const_iterator
A const_iterator type for this set.
Definition: denseHashSet.h:81
bool operator==(const TfDenseHashSet &rhs) const
Equality operator.
Definition: denseHashSet.h:148
insert_result insert(const value_type &v)
Returns a pair of <iterator, bool> where iterator points to the element in the list and bool is true ...
Definition: denseHashSet.h:236
void clear()
Erases all of the elements.
Definition: denseHashSet.h:170
TfDenseHashSet & operator=(const TfDenseHashSet &rhs)
Copy assignment operator.
Definition: denseHashSet.h:126
void insert_unique(Iterator begin, Iterator end)
Insert a range of unique elements into the container.
Definition: denseHashSet.h:285
const_iterator end() const
Returns an const_iterator pointing to the end of the set.
Definition: denseHashSet.h:202
_Vector::const_iterator iterator
An iterator type for this set.
Definition: denseHashSet.h:78
TfDenseHashSet(const TfDenseHashSet &rhs)
Copy Ctor.
Definition: denseHashSet.h:100
TfDenseHashSet & operator=(std::initializer_list< Element > l)
Assignment from an initializer_list.
Definition: denseHashSet.h:140
#define TF_VERIFY(cond, format,...)
Checks a condition and reports an error if it evaluates false.
Definition: diagnostic.h:283