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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
// This file is part of AsmJit project <https://asmjit.com>
//
// See asmjit.h or LICENSE.md for license and copyright information
// SPDX-License-Identifier: Zlib
#ifndef ASMJIT_CORE_ZONEHASH_H_INCLUDED
#define ASMJIT_CORE_ZONEHASH_H_INCLUDED
#include "../core/zone.h"
ASMJIT_BEGIN_NAMESPACE
//! \addtogroup asmjit_zone
//! \{
//! Node used by \ref ZoneHash template.
//!
//! You must provide function `bool eq(const Key& key)` in order to make `ZoneHash::get()` working.
class ZoneHashNode {
public:
ASMJIT_NONCOPYABLE(ZoneHashNode)
inline ZoneHashNode(uint32_t hashCode = 0) noexcept
: _hashNext(nullptr),
_hashCode(hashCode),
_customData(0) {}
//! Next node in the chain, null if it terminates the chain.
ZoneHashNode* _hashNext;
//! Precalculated hash-code of key.
uint32_t _hashCode;
//! Padding, can be reused by any Node that inherits `ZoneHashNode`.
uint32_t _customData;
};
//! Base class used by \ref ZoneHash template
class ZoneHashBase {
public:
ASMJIT_NONCOPYABLE(ZoneHashBase)
//! Buckets data.
ZoneHashNode** _data;
//! Count of records inserted into the hash table.
size_t _size;
//! Count of hash buckets.
uint32_t _bucketsCount;
//! When buckets array should grow (only checked after insertion).
uint32_t _bucketsGrow;
//! Reciprocal value of `_bucketsCount`.
uint32_t _rcpValue;
//! How many bits to shift right when hash is multiplied with `_rcpValue`.
uint8_t _rcpShift;
//! Prime value index in internal prime array.
uint8_t _primeIndex;
//! Embedded data, used by empty hash tables.
ZoneHashNode* _embedded[1];
//! \name Construction & Destruction
//! \{
inline ZoneHashBase() noexcept {
reset();
}
inline ZoneHashBase(ZoneHashBase&& other) noexcept {
_data = other._data;
_size = other._size;
_bucketsCount = other._bucketsCount;
_bucketsGrow = other._bucketsGrow;
_rcpValue = other._rcpValue;
_rcpShift = other._rcpShift;
_primeIndex = other._primeIndex;
_embedded[0] = other._embedded[0];
if (_data == other._embedded) _data = _embedded;
}
inline void reset() noexcept {
_data = _embedded;
_size = 0;
_bucketsCount = 1;
_bucketsGrow = 1;
_rcpValue = 1;
_rcpShift = 0;
_primeIndex = 0;
_embedded[0] = nullptr;
}
inline void release(ZoneAllocator* allocator) noexcept {
ZoneHashNode** oldData = _data;
if (oldData != _embedded)
allocator->release(oldData, _bucketsCount * sizeof(ZoneHashNode*));
reset();
}
//! \}
//! \name Accessors
//! \{
inline bool empty() const noexcept { return _size == 0; }
inline size_t size() const noexcept { return _size; }
//! \}
//! \name Utilities
//! \{
inline void _swap(ZoneHashBase& other) noexcept {
std::swap(_data, other._data);
std::swap(_size, other._size);
std::swap(_bucketsCount, other._bucketsCount);
std::swap(_bucketsGrow, other._bucketsGrow);
std::swap(_rcpValue, other._rcpValue);
std::swap(_rcpShift, other._rcpShift);
std::swap(_primeIndex, other._primeIndex);
std::swap(_embedded[0], other._embedded[0]);
if (_data == other._embedded) _data = _embedded;
if (other._data == _embedded) other._data = other._embedded;
}
//! \cond INTERNAL
inline uint32_t _calcMod(uint32_t hash) const noexcept {
uint32_t x = uint32_t((uint64_t(hash) * _rcpValue) >> _rcpShift);
return hash - x * _bucketsCount;
}
ASMJIT_API void _rehash(ZoneAllocator* allocator, uint32_t newCount) noexcept;
ASMJIT_API ZoneHashNode* _insert(ZoneAllocator* allocator, ZoneHashNode* node) noexcept;
ASMJIT_API ZoneHashNode* _remove(ZoneAllocator* allocator, ZoneHashNode* node) noexcept;
//! \endcond
//! \}
};
//! Low-level hash table specialized for storing string keys and POD values.
//!
//! This hash table allows duplicates to be inserted (the API is so low level that it's up to you if you allow it or
//! not, as you should first `get()` the node and then modify it or insert a new node by using `insert()`, depending
//! on the intention).
template<typename NodeT>
class ZoneHash : public ZoneHashBase {
public:
ASMJIT_NONCOPYABLE(ZoneHash)
typedef NodeT Node;
//! \name Construction & Destruction
//! \{
inline ZoneHash() noexcept
: ZoneHashBase() {}
inline ZoneHash(ZoneHash&& other) noexcept
: ZoneHash(other) {}
//! \}
//! \name Utilities
//! \{
inline void swap(ZoneHash& other) noexcept { ZoneHashBase::_swap(other); }
template<typename KeyT>
inline NodeT* get(const KeyT& key) const noexcept {
uint32_t hashMod = _calcMod(key.hashCode());
NodeT* node = static_cast<NodeT*>(_data[hashMod]);
while (node && !key.matches(node))
node = static_cast<NodeT*>(node->_hashNext);
return node;
}
inline NodeT* insert(ZoneAllocator* allocator, NodeT* node) noexcept { return static_cast<NodeT*>(_insert(allocator, node)); }
inline NodeT* remove(ZoneAllocator* allocator, NodeT* node) noexcept { return static_cast<NodeT*>(_remove(allocator, node)); }
//! \}
};
//! \}
ASMJIT_END_NAMESPACE
#endif // ASMJIT_CORE_ZONEHASH_H_INCLUDED
|
