Line data Source code
1 : #ifdef __PLUMED_HAS_ASMJIT
2 : // This file is part of AsmJit project <https://asmjit.com>
3 : //
4 : // See asmjit.h or LICENSE.md for license and copyright information
5 : // SPDX-License-Identifier: Zlib
6 :
7 : #include "api-build_p.h"
8 : #include "support.h"
9 : #include "zone.h"
10 : #include "zonevector.h"
11 :
12 : ASMJIT_BEGIN_NAMESPACE
13 :
14 : // ZoneVectorBase - Helpers
15 : // ========================
16 :
17 885272 : Error ZoneVectorBase::_grow(ZoneAllocator* allocator, uint32_t sizeOfT, uint32_t n) noexcept {
18 885272 : uint32_t threshold = Globals::kGrowThreshold / sizeOfT;
19 885272 : uint32_t capacity = _capacity;
20 885272 : uint32_t after = _size;
21 :
22 885272 : if (ASMJIT_UNLIKELY(std::numeric_limits<uint32_t>::max() - n < after))
23 : return DebugUtils::errored(kErrorOutOfMemory);
24 :
25 885272 : after += n;
26 885272 : if (capacity >= after)
27 : return kErrorOk;
28 :
29 : // ZoneVector is used as an array to hold short-lived data structures used
30 : // during code generation. The growing strategy is simple - use small capacity
31 : // at the beginning (very good for ZoneAllocator) and then grow quicker to
32 : // prevent successive reallocations.
33 885272 : if (capacity < 4)
34 : capacity = 4;
35 87965 : else if (capacity < 8)
36 : capacity = 8;
37 29598 : else if (capacity < 16)
38 : capacity = 16;
39 7956 : else if (capacity < 64)
40 : capacity = 64;
41 1491 : else if (capacity < 256)
42 : capacity = 256;
43 :
44 997964 : while (capacity < after) {
45 112692 : if (capacity < threshold)
46 112692 : capacity *= 2;
47 : else
48 0 : capacity += threshold;
49 : }
50 :
51 885272 : return _reserve(allocator, sizeOfT, capacity);
52 : }
53 :
54 1704242 : Error ZoneVectorBase::_reserve(ZoneAllocator* allocator, uint32_t sizeOfT, uint32_t n) noexcept {
55 1704242 : uint32_t oldCapacity = _capacity;
56 1704242 : if (oldCapacity >= n) return kErrorOk;
57 :
58 1704242 : uint32_t nBytes = n * sizeOfT;
59 1704242 : if (ASMJIT_UNLIKELY(nBytes < n))
60 : return DebugUtils::errored(kErrorOutOfMemory);
61 :
62 : size_t allocatedBytes;
63 1704242 : uint8_t* newData = static_cast<uint8_t*>(allocator->alloc(nBytes, allocatedBytes));
64 :
65 1704242 : if (ASMJIT_UNLIKELY(!newData))
66 : return DebugUtils::errored(kErrorOutOfMemory);
67 :
68 1704242 : void* oldData = _data;
69 1704242 : if (_size)
70 173624 : memcpy(newData, oldData, size_t(_size) * sizeOfT);
71 :
72 1530618 : if (oldData)
73 173707 : allocator->release(oldData, size_t(oldCapacity) * sizeOfT);
74 :
75 1704242 : _capacity = uint32_t(allocatedBytes / sizeOfT);
76 : ASMJIT_ASSERT(_capacity >= n);
77 :
78 1704242 : _data = newData;
79 1704242 : return kErrorOk;
80 : }
81 :
82 164952 : Error ZoneVectorBase::_resize(ZoneAllocator* allocator, uint32_t sizeOfT, uint32_t n) noexcept {
83 164952 : uint32_t size = _size;
84 :
85 164952 : if (_capacity < n) {
86 109968 : ASMJIT_PROPAGATE(_grow(allocator, sizeOfT, n - size));
87 : ASMJIT_ASSERT(_capacity >= n);
88 : }
89 :
90 164952 : if (size < n)
91 164952 : memset(static_cast<uint8_t*>(_data) + size_t(size) * sizeOfT, 0, size_t(n - size) * sizeOfT);
92 :
93 164952 : _size = n;
94 164952 : return kErrorOk;
95 : }
96 :
97 : // ZoneBitVector - Operations
98 : // ==========================
99 :
100 0 : Error ZoneBitVector::copyFrom(ZoneAllocator* allocator, const ZoneBitVector& other) noexcept {
101 0 : BitWord* data = _data;
102 : uint32_t newSize = other.size();
103 :
104 0 : if (!newSize) {
105 0 : _size = 0;
106 0 : return kErrorOk;
107 : }
108 :
109 0 : if (newSize > _capacity) {
110 : // Realloc needed... Calculate the minimum capacity (in bytes) required.
111 : uint32_t minimumCapacityInBits = Support::alignUp<uint32_t>(newSize, kBitWordSizeInBits);
112 0 : if (ASMJIT_UNLIKELY(minimumCapacityInBits < newSize))
113 0 : return DebugUtils::errored(kErrorOutOfMemory);
114 :
115 : // Normalize to bytes.
116 0 : uint32_t minimumCapacity = minimumCapacityInBits / 8;
117 : size_t allocatedCapacity;
118 :
119 0 : BitWord* newData = static_cast<BitWord*>(allocator->alloc(minimumCapacity, allocatedCapacity));
120 0 : if (ASMJIT_UNLIKELY(!newData))
121 : return DebugUtils::errored(kErrorOutOfMemory);
122 :
123 : // `allocatedCapacity` now contains number in bytes, we need bits.
124 0 : size_t allocatedCapacityInBits = allocatedCapacity * 8;
125 :
126 : // Arithmetic overflow should normally not happen. If it happens we just
127 : // change the `allocatedCapacityInBits` to the `minimumCapacityInBits` as
128 : // this value is still safe to be used to call `_allocator->release(...)`.
129 0 : if (ASMJIT_UNLIKELY(allocatedCapacityInBits < allocatedCapacity))
130 0 : allocatedCapacityInBits = minimumCapacityInBits;
131 :
132 0 : if (data)
133 0 : allocator->release(data, _capacity / 8);
134 : data = newData;
135 :
136 0 : _data = data;
137 0 : _capacity = uint32_t(allocatedCapacityInBits);
138 : }
139 :
140 0 : _size = newSize;
141 : _copyBits(data, other.data(), _wordsPerBits(newSize));
142 :
143 : return kErrorOk;
144 : }
145 :
146 274920 : Error ZoneBitVector::_resize(ZoneAllocator* allocator, uint32_t newSize, uint32_t idealCapacity, bool newBitsValue) noexcept {
147 : ASMJIT_ASSERT(idealCapacity >= newSize);
148 :
149 274920 : if (newSize <= _size) {
150 : // The size after the resize is lesser than or equal to the current size.
151 0 : uint32_t idx = newSize / kBitWordSizeInBits;
152 0 : uint32_t bit = newSize % kBitWordSizeInBits;
153 :
154 : // Just set all bits outside of the new size in the last word to zero.
155 : // There is a case that there are not bits to set if `bit` is zero. This
156 : // happens when `newSize` is a multiply of `kBitWordSizeInBits` like 64, 128,
157 : // and so on. In that case don't change anything as that would mean settings
158 : // bits outside of the `_size`.
159 0 : if (bit)
160 0 : _data[idx] &= (BitWord(1) << bit) - 1u;
161 :
162 0 : _size = newSize;
163 0 : return kErrorOk;
164 : }
165 :
166 : uint32_t oldSize = _size;
167 274920 : BitWord* data = _data;
168 :
169 274920 : if (newSize > _capacity) {
170 : // Realloc needed, calculate the minimum capacity (in bytes) required.
171 : uint32_t minimumCapacityInBits = Support::alignUp<uint32_t>(idealCapacity, kBitWordSizeInBits);
172 :
173 274920 : if (ASMJIT_UNLIKELY(minimumCapacityInBits < newSize))
174 0 : return DebugUtils::errored(kErrorOutOfMemory);
175 :
176 : // Normalize to bytes.
177 274920 : uint32_t minimumCapacity = minimumCapacityInBits / 8;
178 : size_t allocatedCapacity;
179 :
180 274920 : BitWord* newData = static_cast<BitWord*>(allocator->alloc(minimumCapacity, allocatedCapacity));
181 274920 : if (ASMJIT_UNLIKELY(!newData))
182 : return DebugUtils::errored(kErrorOutOfMemory);
183 :
184 : // `allocatedCapacity` now contains number in bytes, we need bits.
185 274920 : size_t allocatedCapacityInBits = allocatedCapacity * 8;
186 :
187 : // Arithmetic overflow should normally not happen. If it happens we just
188 : // change the `allocatedCapacityInBits` to the `minimumCapacityInBits` as
189 : // this value is still safe to be used to call `_allocator->release(...)`.
190 274920 : if (ASMJIT_UNLIKELY(allocatedCapacityInBits < allocatedCapacity))
191 0 : allocatedCapacityInBits = minimumCapacityInBits;
192 :
193 : _copyBits(newData, data, _wordsPerBits(oldSize));
194 :
195 274920 : if (data)
196 0 : allocator->release(data, _capacity / 8);
197 : data = newData;
198 :
199 274920 : _data = data;
200 274920 : _capacity = uint32_t(allocatedCapacityInBits);
201 : }
202 :
203 : // Start (of the old size) and end (of the new size) bits
204 274920 : uint32_t idx = oldSize / kBitWordSizeInBits;
205 274920 : uint32_t startBit = oldSize % kBitWordSizeInBits;
206 274920 : uint32_t endBit = newSize % kBitWordSizeInBits;
207 :
208 : // Set new bits to either 0 or 1. The `pattern` is used to set multiple
209 : // bits per bit-word and contains either all zeros or all ones.
210 : BitWord pattern = Support::bitMaskFromBool<BitWord>(newBitsValue);
211 :
212 : // First initialize the last bit-word of the old size.
213 274920 : if (startBit) {
214 : uint32_t nBits = 0;
215 :
216 0 : if (idx == (newSize / kBitWordSizeInBits)) {
217 : // The number of bit-words is the same after the resize. In that case
218 : // we need to set only bits necessary in the current last bit-word.
219 : ASMJIT_ASSERT(startBit < endBit);
220 0 : nBits = endBit - startBit;
221 : }
222 : else {
223 : // There is be more bit-words after the resize. In that case we don't
224 : // have to be extra careful about the last bit-word of the old size.
225 0 : nBits = kBitWordSizeInBits - startBit;
226 : }
227 :
228 0 : data[idx++] |= pattern << nBits;
229 : }
230 :
231 : // Initialize all bit-words after the last bit-word of the old size.
232 : uint32_t endIdx = _wordsPerBits(newSize);
233 556184 : while (idx < endIdx) data[idx++] = pattern;
234 :
235 : // Clear unused bits of the last bit-word.
236 274920 : if (endBit)
237 274920 : data[endIdx - 1] = pattern & ((BitWord(1) << endBit) - 1);
238 :
239 274920 : _size = newSize;
240 274920 : return kErrorOk;
241 : }
242 :
243 0 : Error ZoneBitVector::_append(ZoneAllocator* allocator, bool value) noexcept {
244 : uint32_t kThreshold = Globals::kGrowThreshold * 8;
245 0 : uint32_t newSize = _size + 1;
246 0 : uint32_t idealCapacity = _capacity;
247 :
248 0 : if (idealCapacity < 128)
249 : idealCapacity = 128;
250 0 : else if (idealCapacity <= kThreshold)
251 0 : idealCapacity *= 2;
252 : else
253 0 : idealCapacity += kThreshold;
254 :
255 0 : if (ASMJIT_UNLIKELY(idealCapacity < _capacity)) {
256 0 : if (ASMJIT_UNLIKELY(_size == std::numeric_limits<uint32_t>::max()))
257 : return DebugUtils::errored(kErrorOutOfMemory);
258 : idealCapacity = newSize;
259 : }
260 :
261 0 : return _resize(allocator, newSize, idealCapacity, value);
262 : }
263 :
264 : // ZoneVector / ZoneBitVector - Tests
265 : // ==================================
266 :
267 : #if defined(ASMJIT_TEST)
268 : template<typename T>
269 : static void test_zone_vector(ZoneAllocator* allocator, const char* typeName) {
270 : int i;
271 : int kMax = 100000;
272 :
273 : ZoneVector<T> vec;
274 :
275 : INFO("ZoneVector<%s> basic tests", typeName);
276 : EXPECT(vec.append(allocator, 0) == kErrorOk);
277 : EXPECT(vec.empty() == false);
278 : EXPECT(vec.size() == 1);
279 : EXPECT(vec.capacity() >= 1);
280 : EXPECT(vec.indexOf(0) == 0);
281 : EXPECT(vec.indexOf(-11) == Globals::kNotFound);
282 :
283 : vec.clear();
284 : EXPECT(vec.empty());
285 : EXPECT(vec.size() == 0);
286 : EXPECT(vec.indexOf(0) == Globals::kNotFound);
287 :
288 : for (i = 0; i < kMax; i++) {
289 : EXPECT(vec.append(allocator, T(i)) == kErrorOk);
290 : }
291 : EXPECT(vec.empty() == false);
292 : EXPECT(vec.size() == uint32_t(kMax));
293 : EXPECT(vec.indexOf(T(kMax - 1)) == uint32_t(kMax - 1));
294 :
295 : EXPECT(vec.rbegin()[0] == kMax - 1);
296 :
297 : vec.release(allocator);
298 : }
299 :
300 : static void test_zone_bitvector(ZoneAllocator* allocator) {
301 : Zone zone(8096 - Zone::kBlockOverhead);
302 :
303 : uint32_t i, count;
304 : uint32_t kMaxCount = 100;
305 :
306 : ZoneBitVector vec;
307 : EXPECT(vec.empty());
308 : EXPECT(vec.size() == 0);
309 :
310 : INFO("ZoneBitVector::resize()");
311 : for (count = 1; count < kMaxCount; count++) {
312 : vec.clear();
313 : EXPECT(vec.resize(allocator, count, false) == kErrorOk);
314 : EXPECT(vec.size() == count);
315 :
316 : for (i = 0; i < count; i++)
317 : EXPECT(vec.bitAt(i) == false);
318 :
319 : vec.clear();
320 : EXPECT(vec.resize(allocator, count, true) == kErrorOk);
321 : EXPECT(vec.size() == count);
322 :
323 : for (i = 0; i < count; i++)
324 : EXPECT(vec.bitAt(i) == true);
325 : }
326 :
327 : INFO("ZoneBitVector::fillBits() / clearBits()");
328 : for (count = 1; count < kMaxCount; count += 2) {
329 : vec.clear();
330 : EXPECT(vec.resize(allocator, count) == kErrorOk);
331 : EXPECT(vec.size() == count);
332 :
333 : for (i = 0; i < (count + 1) / 2; i++) {
334 : bool value = bool(i & 1);
335 : if (value)
336 : vec.fillBits(i, count - i * 2);
337 : else
338 : vec.clearBits(i, count - i * 2);
339 : }
340 :
341 : for (i = 0; i < count; i++) {
342 : EXPECT(vec.bitAt(i) == bool(i & 1));
343 : }
344 : }
345 : }
346 :
347 : UNIT(zone_vector) {
348 : Zone zone(8096 - Zone::kBlockOverhead);
349 : ZoneAllocator allocator(&zone);
350 :
351 : test_zone_vector<int>(&allocator, "int");
352 : test_zone_vector<int64_t>(&allocator, "int64_t");
353 : test_zone_bitvector(&allocator);
354 : }
355 : #endif
356 :
357 : ASMJIT_END_NAMESPACE
358 :
359 : #endif // __PLUMED_HAS_ASMJIT
|
