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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#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 Key, typename Value> struct HashMapPair
{
Key key;
Value value;
template<typename... ValueArgs> HashMapPair(const Key& inKey, ValueArgs&&... valueArgs);
template<typename... ValueArgs> HashMapPair(Key&& inKey, ValueArgs&&... valueArgs);
};
template<typename Key, typename Value> struct HashMapIterator
{
template<typename, typename, typename> friend struct HashMap;
typedef HashMapPair<Key, Value> Pair;
bool operator!=(const HashMapIterator& other) const;
bool operator==(const HashMapIterator& other) const;
operator bool() const;
void operator++();
const Pair& operator*() const;
const Pair* operator->() const;
private:
const HashTableBucket<Pair>* bucket;
const HashTableBucket<Pair>* endBucket;
HashMapIterator(const HashTableBucket<Pair>* inBucket,
const HashTableBucket<Pair>* inEndBucket);
};
template<typename Key, typename Value, typename KeyHashPolicy = DefaultHashPolicy<Key>>
struct HashMap
{
typedef HashMapPair<Key, Value> Pair;
typedef HashMapIterator<Key, Value> Iterator;
HashMap(Uptr reserveNumPairs = 0);
HashMap(const std::initializer_list<Pair>& initializerList);
// If the map contains the key already, returns the value bound to that key.
// If the map doesn't contain the key, adds it to the map bound to a value constructed from
// the provided arguments.
template<typename... ValueArgs> Value& getOrAdd(const Key& key, ValueArgs&&... valueArgs);
// If the map contains the key already, returns false.
// If the map doesn't contain the key, adds it to the map bound to a value constructed from
// the provided arguments, and returns true.
template<typename... ValueArgs> bool add(const Key& key, ValueArgs&&... valueArgs);
// Assuming the map doesn't contain the key, add it. Asserts if the map contained the key,
// or silently does nothing if assertions are disabled.
template<typename... ValueArgs> void addOrFail(const Key& key, ValueArgs&&... valueArgs);
// If the map contains the key already, replaces the value bound to it with a value
// constructed from the provided arguments. If the map doesn't contain the key, adds it to
// the map bound to a value constructed from the provided arguments. In both cases, a
// reference to the value bound to the key is returned.
template<typename... ValueArgs> Value& set(const Key& key, ValueArgs&&... valueArgs);
// If the map contains the key, removes it and returns true.
// If the map doesn't contain the key, returns false.
bool remove(const Key& key);
// Assuming the map contains the key, remove it. Asserts if the map didn't contain the key,
// or silently does nothing if assertions are disabled.
void removeOrFail(const Key& key);
// Returns true if the map contains the key.
bool contains(const Key& key) const;
// Returns a reference to the value bound to the key. Assumes that the map contains the key.
const Value& operator[](const Key& key) const;
Value& operator[](const Key& key);
// Returns a pointer to the value bound to the key, or null if the map doesn't contain the
// key.
const Value* get(const Key& key) const;
Value* get(const Key& key);
// Returns a pointer to the key-value pair for a key, or null if the map doesn't contain the
// key.
const Pair* getPair(const Key& key) const;
// Removes all pairs from the map.
void clear();
Iterator begin() const;
Iterator end() const;
Uptr size() const;
// Compute some statistics about the space usage of this map.
void analyzeSpaceUsage(Uptr& outTotalMemoryBytes,
Uptr& outMaxProbeCount,
F32& outOccupancy,
F32& outAverageProbeCount) const;
private:
struct HashTablePolicy
{
WAVM_FORCEINLINE static const Key& getKey(const Pair& pair) { return pair.key; }
WAVM_FORCEINLINE static bool areKeysEqual(const Key& left, const Key& right)
{
return KeyHashPolicy::areKeysEqual(left, right);
}
};
HashTable<Key, Pair, HashTablePolicy> table;
};
// The implementation is defined in a separate file.
#include "Impl/HashMapImpl.h"
}
|
