1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#pragma once
#include <initializer_list>
#include "WAVM/Inline/Assert.h"
#include "WAVM/Inline/BasicTypes.h"
#include "WAVM/Inline/Hash.h"
#include "WAVM/Inline/HashTable.h"
namespace WAVM {
template<typename Element> struct HashSetIterator
{
template<typename, typename> friend struct HashSet;
bool operator!=(const HashSetIterator& other) const;
bool operator==(const HashSetIterator& other) const;
operator bool() const;
void operator++();
const Element& operator*() const;
const Element* operator->() const;
private:
const HashTableBucket<Element>* bucket;
const HashTableBucket<Element>* endBucket;
HashSetIterator(const HashTableBucket<Element>* inBucket,
const HashTableBucket<Element>* inEndBucket);
};
template<typename Element, typename ElementHashPolicy = DefaultHashPolicy<Element>>
struct HashSet
{
HashSet(Uptr reserveNumElements = 0);
HashSet(const std::initializer_list<Element>& initializerList);
// If the set contains the element already, returns false.
// If the set didn't contain the element, adds it and returns true.
bool add(const Element& element);
// Assuming the set doesn't contain the element, add it. Asserts if the set contained the
// element, or silently does nothing if assertions are disabled.
void addOrFail(const Element& element);
// If the set contains the element, removes it and returns true.
// If the set doesn't contain the element, returns false.
bool remove(const Element& element);
// Assuming the set contains the element, remove it. Asserts if the set didn't contain the
// element, or silently does nothing if assertions are disabled.
void removeOrFail(const Element& element);
// Returns a reference to the element in the set matching the given element. Assumes that
// the map contains the key. This is useful if the hash policy allows distinct elements to
// compare as equal; e.g. for deduplicating equivalent values.
const Element& operator[](const Element& element) const;
// Returns true if the set contains the element.
bool contains(const Element& element) const;
// If the set contains the element, returns a pointer to it. This is useful if the hash
// policy allows distinct elements to compare as equal; e.g. for deduplicating equivalent
// values.
const Element* get(const Element& element) const;
// Removes all elements from the set.
void clear();
HashSetIterator<Element> begin() const;
HashSetIterator<Element> end() const;
Uptr size() const;
// Compute some statistics about the space usage of this set.
void analyzeSpaceUsage(Uptr& outTotalMemoryBytes,
Uptr& outMaxProbeCount,
F32& outOccupancy,
F32& outAverageProbeCount) const;
private:
struct HashTablePolicy
{
WAVM_FORCEINLINE static const Element& getKey(const Element& element)
{
return element;
}
WAVM_FORCEINLINE static bool areKeysEqual(const Element& left, const Element& right)
{
return ElementHashPolicy::areKeysEqual(left, right);
}
};
HashTable<Element, Element, HashTablePolicy> table;
};
// The implementation is defined in a separate file.
#include "Impl/HashSetImpl.h"
}
|
