1 | // [Blend2D] |
2 | // 2D Vector Graphics Powered by a JIT Compiler. |
3 | // |
4 | // [License] |
5 | // Zlib - See LICENSE.md file in the package. |
6 | |
7 | #include "./blapi-build_p.h" |
8 | #include "./blarray.h" |
9 | #include "./blarray_p.h" |
10 | #include "./blruntime_p.h" |
11 | #include "./blsupport_p.h" |
12 | #include "./bltables_p.h" |
13 | #include "./blvariant_p.h" |
14 | |
15 | // ============================================================================ |
16 | // [BLArray - Global] |
17 | // ============================================================================ |
18 | |
19 | enum : uint32_t { |
20 | BL_IMPL_TYPE_ARRAY_FIRST = BL_IMPL_TYPE_ARRAY_VAR, |
21 | BL_IMPL_TYPE_ARRAY_LAST = BL_IMPL_TYPE_ARRAY_STRUCT_32 |
22 | }; |
23 | |
24 | static BLWrap<BLArrayImpl> blNullArrayImpl[BL_IMPL_TYPE_ARRAY_LAST + 1]; |
25 | static const uint8_t blNullArrayBuffer[64] = { 0 }; |
26 | |
27 | // ============================================================================ |
28 | // [BLArray - Capacity] |
29 | // ============================================================================ |
30 | |
31 | static constexpr size_t blArrayImplSizeOf() noexcept { |
32 | return sizeof(BLArrayImpl); |
33 | } |
34 | |
35 | static constexpr size_t blArrayImplSizeOf(size_t itemSize, size_t n) noexcept { |
36 | return blContainerSizeOf(sizeof(BLArrayImpl), itemSize, n); |
37 | } |
38 | |
39 | static constexpr size_t blArrayCapacityOf(size_t itemSize, size_t implSize) noexcept { |
40 | return blContainerCapacityOf(blArrayImplSizeOf(), itemSize, implSize); |
41 | } |
42 | |
43 | static constexpr size_t blArrayInitialCapacity(size_t itemSize) noexcept { |
44 | return blArrayCapacityOf(itemSize, BL_ALLOC_HINT_ARRAY); |
45 | } |
46 | |
47 | static BL_INLINE size_t blArrayFittingCapacity(size_t itemSize, size_t n) noexcept { |
48 | return blContainerFittingCapacity(blArrayImplSizeOf(), itemSize, n); |
49 | } |
50 | |
51 | static BL_INLINE size_t blArrayGrowingCapacity(size_t itemSize, size_t n) noexcept { |
52 | return blContainerGrowingCapacity(blArrayImplSizeOf(), itemSize, n, BL_ALLOC_HINT_ARRAY); |
53 | } |
54 | |
55 | // ============================================================================ |
56 | // [BLArray - Tables] |
57 | // ============================================================================ |
58 | |
59 | struct BLArrayItemSizeGen { |
60 | static constexpr uint8_t value(size_t implType) noexcept { |
61 | return implType == BL_IMPL_TYPE_ARRAY_VAR ? uint8_t(sizeof(void*)) : |
62 | implType == BL_IMPL_TYPE_ARRAY_I8 ? uint8_t(1) : |
63 | implType == BL_IMPL_TYPE_ARRAY_U8 ? uint8_t(1) : |
64 | implType == BL_IMPL_TYPE_ARRAY_I16 ? uint8_t(2) : |
65 | implType == BL_IMPL_TYPE_ARRAY_U16 ? uint8_t(2) : |
66 | implType == BL_IMPL_TYPE_ARRAY_I32 ? uint8_t(4) : |
67 | implType == BL_IMPL_TYPE_ARRAY_U32 ? uint8_t(4) : |
68 | implType == BL_IMPL_TYPE_ARRAY_I64 ? uint8_t(8) : |
69 | implType == BL_IMPL_TYPE_ARRAY_U64 ? uint8_t(8) : |
70 | implType == BL_IMPL_TYPE_ARRAY_F32 ? uint8_t(4) : |
71 | implType == BL_IMPL_TYPE_ARRAY_F64 ? uint8_t(8) : |
72 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_1 ? uint8_t(1) : |
73 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_2 ? uint8_t(2) : |
74 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_3 ? uint8_t(3) : |
75 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_4 ? uint8_t(4) : |
76 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_6 ? uint8_t(6) : |
77 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_8 ? uint8_t(8) : |
78 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_10 ? uint8_t(10) : |
79 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_12 ? uint8_t(12) : |
80 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_16 ? uint8_t(16) : |
81 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_20 ? uint8_t(20) : |
82 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_24 ? uint8_t(24) : |
83 | implType == BL_IMPL_TYPE_ARRAY_STRUCT_32 ? uint8_t(32) : uint8_t(0); |
84 | } |
85 | }; |
86 | |
87 | struct BLArrayMaximumCapacityGen { |
88 | static constexpr size_t value(size_t implType) noexcept { |
89 | return BLArrayItemSizeGen::value(implType) == 0 |
90 | ? size_t(0) |
91 | : blArrayCapacityOf(BLArrayItemSizeGen::value(implType), SIZE_MAX); |
92 | } |
93 | }; |
94 | |
95 | static constexpr const auto blArrayItemSizeTable = blLookupTable<uint8_t, BL_IMPL_TYPE_COUNT, BLArrayItemSizeGen>(); |
96 | static constexpr const auto blArrayMaximumCapacityTable = blLookupTable<size_t, BL_IMPL_TYPE_COUNT, BLArrayMaximumCapacityGen>(); |
97 | |
98 | // ============================================================================ |
99 | // [BLArray - Dispatch Funcs] |
100 | // ============================================================================ |
101 | |
102 | static constexpr bool blArrayDispatchTypeByImplType(uint32_t implType) noexcept { |
103 | return implType == BL_IMPL_TYPE_ARRAY_VAR; |
104 | } |
105 | |
106 | static constexpr bool blIsVarArrayImplType(uint32_t implType) noexcept { |
107 | return implType == BL_IMPL_TYPE_ARRAY_VAR; |
108 | } |
109 | |
110 | // Only used as a filler |
111 | template<size_t N> |
112 | struct BLUInt32xN { uint32_t data[N]; }; |
113 | |
114 | template<typename T> |
115 | static BL_INLINE void blArrayFillPattern(T* dst, T src, size_t n) noexcept { |
116 | for (size_t i = 0; i < n; i++) |
117 | dst[i] = src; |
118 | } |
119 | |
120 | static BLResult BL_CDECL blArrayDestroySimpleData(void* dst, size_t nBytes) noexcept { |
121 | BL_UNUSED(dst); |
122 | BL_UNUSED(nBytes); |
123 | return BL_SUCCESS; |
124 | } |
125 | |
126 | static void* BL_CDECL blArrayCopyVariantData(void* dst_, const void* src_, size_t nBytes) noexcept { |
127 | BL_ASSUME((nBytes % sizeof(BLVariant)) == 0); |
128 | |
129 | BLVariant* dst = static_cast<BLVariant*>(dst_); |
130 | const BLVariant* src = static_cast<const BLVariant*>(src_); |
131 | |
132 | void* end = blOffsetPtr(dst, nBytes); |
133 | while (dst != end) { |
134 | dst->impl = blImplIncRef(src->impl); |
135 | |
136 | dst = blOffsetPtr(dst, sizeof(BLVariant)); |
137 | src = blOffsetPtr(dst, sizeof(BLVariant)); |
138 | } |
139 | |
140 | return dst_; |
141 | } |
142 | |
143 | static void* BL_CDECL blArrayReplaceVariantData(void* dst_, const void* src_, size_t nBytes) noexcept { |
144 | BL_ASSUME((nBytes % sizeof(BLVariant)) == 0); |
145 | |
146 | BLVariant* dst = static_cast<BLVariant*>(dst_); |
147 | const BLVariant* src = static_cast<const BLVariant*>(src_); |
148 | |
149 | void* end = blOffsetPtr(dst, nBytes); |
150 | while (dst != end) { |
151 | BLVariantImpl* replacedImpl = dst->impl; |
152 | dst->impl = blImplIncRef(src->impl); |
153 | blVariantImplRelease(replacedImpl); |
154 | |
155 | dst = blOffsetPtr(dst, sizeof(BLVariant)); |
156 | src = blOffsetPtr(dst, sizeof(BLVariant)); |
157 | } |
158 | |
159 | return dst_; |
160 | } |
161 | |
162 | static BLResult BL_CDECL blArrayDestroyVariantData(void* data, size_t nBytes) noexcept { |
163 | BL_ASSUME((nBytes % sizeof(BLVariant)) == 0); |
164 | for (size_t i = 0; i < nBytes; i += sizeof(BLVariant)) |
165 | blVariantImplRelease(blOffsetPtr<BLVariant>(data, i)->impl); |
166 | return BL_SUCCESS; |
167 | } |
168 | |
169 | struct BLArrayFuncs { |
170 | typedef void* (BL_CDECL* CopyData)(void* dst, const void* src, size_t nBytes) BL_NOEXCEPT; |
171 | typedef void* (BL_CDECL* ReplaceData)(void* dst, const void* src, size_t nBytes) BL_NOEXCEPT; |
172 | typedef BLResult (BL_CDECL* DestroyData)(void* dst, size_t nBytes) BL_NOEXCEPT; |
173 | |
174 | CopyData copyData; |
175 | ReplaceData replaceData; |
176 | DestroyData destroyData; |
177 | }; |
178 | |
179 | static const BLArrayFuncs blArrayFuncs[2] = { |
180 | // DispatchType #0: Arrays that store simple data. |
181 | { |
182 | (BLArrayFuncs::CopyData)memcpy, |
183 | (BLArrayFuncs::ReplaceData)memcpy, |
184 | blArrayDestroySimpleData |
185 | }, |
186 | |
187 | // DispatchType #1:Arrays that store BLVariant or { BLVariant, ... } items. |
188 | { |
189 | blArrayCopyVariantData, |
190 | blArrayReplaceVariantData, |
191 | blArrayDestroyVariantData |
192 | } |
193 | }; |
194 | |
195 | static const BLArrayFuncs& blArrayFuncsByDispatchType(uint32_t dispatchType) noexcept { |
196 | BL_ASSERT(dispatchType < BL_ARRAY_SIZE(blArrayFuncs)); |
197 | return blArrayFuncs[dispatchType]; |
198 | } |
199 | |
200 | // ============================================================================ |
201 | // [BLArray - Internals] |
202 | // ============================================================================ |
203 | |
204 | static BL_INLINE BLArrayImpl* blArrayImplNew(uint32_t implType, size_t capacity) noexcept { |
205 | uint32_t itemSize = blArrayItemSizeTable[implType]; |
206 | uint16_t memPoolData; |
207 | BLArrayImpl* impl = blRuntimeAllocImplT<BLArrayImpl>(blArrayImplSizeOf(itemSize, capacity), &memPoolData); |
208 | |
209 | if (BL_UNLIKELY(!impl)) |
210 | return impl; |
211 | |
212 | blImplInit(impl, implType, BL_IMPL_TRAIT_MUTABLE, memPoolData); |
213 | impl->data = blOffsetPtr<void>(impl, sizeof(BLArrayImpl)); |
214 | impl->size = 0; |
215 | impl->capacity = capacity; |
216 | impl->itemSize = uint8_t(itemSize); |
217 | impl->dispatchType = uint8_t(blArrayDispatchTypeByImplType(implType)); |
218 | impl->reserved[0] = 0; |
219 | impl->reserved[1] = 0; |
220 | |
221 | return impl; |
222 | } |
223 | |
224 | static BL_INLINE BLArrayImpl* blArrayImplNewExternal(uint32_t implType, void* data, size_t size, size_t capacity, uint32_t dataAccessFlags, BLDestroyImplFunc destroyFunc, void* destroyData) noexcept { |
225 | size_t implSize = sizeof(BLExternalImplPreface) + sizeof(BLArrayImpl); |
226 | uint16_t memPoolData; |
227 | |
228 | void* p = blRuntimeAllocImpl(implSize, &memPoolData); |
229 | if (BL_UNLIKELY(!p)) |
230 | return nullptr; |
231 | |
232 | BLExternalImplPreface* preface = static_cast<BLExternalImplPreface*>(p); |
233 | BLArrayImpl* impl = blOffsetPtr<BLArrayImpl>(p, sizeof(BLExternalImplPreface)); |
234 | |
235 | preface->destroyFunc = destroyFunc ? destroyFunc : blRuntimeDummyDestroyImplFunc; |
236 | preface->destroyData = destroyFunc ? destroyData : nullptr; |
237 | |
238 | uint32_t itemSize = blArrayItemSizeTable[implType]; |
239 | uint32_t implTraits = blImplTraitsFromDataAccessFlags(dataAccessFlags) | BL_IMPL_TRAIT_EXTERNAL; |
240 | |
241 | blImplInit(impl, implType, implTraits, memPoolData); |
242 | impl->data = data; |
243 | impl->size = size; |
244 | impl->capacity = capacity; |
245 | impl->itemSize = uint8_t(itemSize); |
246 | impl->dispatchType = uint8_t(blArrayDispatchTypeByImplType(implType)); |
247 | impl->reserved[0] = 0; |
248 | impl->reserved[1] = 0; |
249 | |
250 | return impl; |
251 | } |
252 | |
253 | // Cannot be static, called by `BLVariant` implementation. |
254 | BLResult blArrayImplDelete(BLArrayImpl* impl) noexcept { |
255 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(impl->dispatchType); |
256 | funcs.destroyData(impl->data, impl->size * impl->itemSize); |
257 | |
258 | uint8_t* implBase = reinterpret_cast<uint8_t*>(impl); |
259 | size_t implSize = blArrayImplSizeOf(impl->implType, impl->capacity); |
260 | uint32_t implTraits = impl->implTraits; |
261 | uint32_t memPoolData = impl->memPoolData; |
262 | |
263 | if (implTraits & BL_IMPL_TRAIT_EXTERNAL) { |
264 | implSize = blArrayImplSizeOf() + sizeof(BLExternalImplPreface); |
265 | implBase -= sizeof(BLExternalImplPreface); |
266 | blImplDestroyExternal(impl); |
267 | } |
268 | |
269 | if (implTraits & BL_IMPL_TRAIT_FOREIGN) |
270 | return BL_SUCCESS; |
271 | else |
272 | return blRuntimeFreeImpl(implBase, implSize, memPoolData); |
273 | } |
274 | |
275 | static BL_NOINLINE BLResult blArrayRealloc(BLArrayCore* self, size_t capacity) noexcept { |
276 | BLArrayImpl* oldI = self->impl; |
277 | BLArrayImpl* newI = blArrayImplNew(oldI->implType, capacity); |
278 | |
279 | if (BL_UNLIKELY(!newI)) |
280 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
281 | |
282 | BL_ASSERT(newI->itemSize == oldI->itemSize); |
283 | |
284 | size_t size = oldI->size; |
285 | size_t itemSize = oldI->itemSize; |
286 | |
287 | self->impl = newI; |
288 | newI->size = size; |
289 | |
290 | if (oldI->refCount == 1) { |
291 | // Zero the old size and fall through to memcpy(). This is much better as |
292 | // we don't have to IncRef/DecRef the same BLVariant[]. |
293 | oldI->size = 0; |
294 | memcpy(newI->data, oldI->data, size * itemSize); |
295 | return blArrayImplRelease(oldI); |
296 | } |
297 | else { |
298 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(oldI->dispatchType); |
299 | funcs.copyData(newI->data, oldI->data, size * itemSize); |
300 | return blArrayImplRelease(oldI); |
301 | } |
302 | } |
303 | |
304 | // ============================================================================ |
305 | // [BLArray - Init / Reset] |
306 | // ============================================================================ |
307 | |
308 | BLResult blArrayInit(BLArrayCore* self, uint32_t arrayTypeId) noexcept { |
309 | if (BL_UNLIKELY(arrayTypeId >= BL_IMPL_TYPE_COUNT || !blArrayItemSizeTable[arrayTypeId])) { |
310 | self->impl = &blNullArrayImpl[0]; |
311 | return blTraceError(BL_ERROR_INVALID_VALUE); |
312 | } |
313 | |
314 | self->impl = &blNullArrayImpl[arrayTypeId]; |
315 | return BL_SUCCESS; |
316 | } |
317 | |
318 | BLResult blArrayReset(BLArrayCore* self) noexcept { |
319 | BLArrayImpl* selfI = self->impl; |
320 | self->impl = &blNullArrayImpl[selfI->implType]; |
321 | |
322 | if (blImplDecRefAndTest(selfI)) |
323 | return blArrayImplDelete(selfI); |
324 | return BL_SUCCESS; |
325 | } |
326 | |
327 | // ============================================================================ |
328 | // [BLArray - Create] |
329 | // ============================================================================ |
330 | |
331 | BLResult blArrayCreateFromData(BLArrayCore* self, void* data, size_t size, size_t capacity, uint32_t dataAccessFlags, BLDestroyImplFunc destroyFunc, void* destroyData) noexcept { |
332 | BLArrayImpl* selfI = self->impl; |
333 | uint32_t implType = selfI->implType; |
334 | size_t itemSize = selfI->itemSize; |
335 | |
336 | if (BL_UNLIKELY(!itemSize)) |
337 | return blTraceError(BL_ERROR_INVALID_STATE); |
338 | |
339 | BLOverflowFlag of = 0; |
340 | |
341 | size_t dataSizeInBytes = blMulOverflow(capacity, itemSize, &of); |
342 | BL_UNUSED(dataSizeInBytes); // We just want to know whether it has overflown. |
343 | |
344 | if (BL_UNLIKELY(!capacity || capacity < size || !blDataAccessFlagsIsValid(dataAccessFlags) || of)) |
345 | return blTraceError(BL_ERROR_INVALID_VALUE); |
346 | |
347 | BLArrayImpl* newI = blArrayImplNewExternal(implType, data, size, capacity, dataAccessFlags, destroyFunc, destroyData); |
348 | if (BL_UNLIKELY(!newI)) |
349 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
350 | |
351 | self->impl = newI; |
352 | return blArrayImplRelease(selfI); |
353 | } |
354 | |
355 | // ============================================================================ |
356 | // [BLArray - Storage] |
357 | // ============================================================================ |
358 | |
359 | size_t blArrayGetSize(const BLArrayCore* self) noexcept { |
360 | return self->impl->size; |
361 | } |
362 | |
363 | size_t blArrayGetCapacity(const BLArrayCore* self) noexcept { |
364 | return self->impl->capacity; |
365 | } |
366 | |
367 | const void* blArrayGetData(const BLArrayCore* self) noexcept { |
368 | return self->impl->data; |
369 | } |
370 | |
371 | BLResult blArrayClear(BLArrayCore* self) noexcept { |
372 | BLArrayImpl* selfI = self->impl; |
373 | size_t size = selfI->size; |
374 | if (!size) |
375 | return BL_SUCCESS; |
376 | |
377 | if (!blImplIsMutable(selfI)) { |
378 | self->impl = &blNullArrayImpl[selfI->implType]; |
379 | return blArrayImplRelease(selfI); |
380 | } |
381 | |
382 | selfI->size = 0; |
383 | |
384 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(selfI->dispatchType); |
385 | return funcs.destroyData(selfI->data, size * selfI->itemSize); |
386 | } |
387 | |
388 | BLResult blArrayShrink(BLArrayCore* self) noexcept { |
389 | BLArrayImpl* selfI = self->impl; |
390 | |
391 | size_t size = selfI->size; |
392 | if (size == 0) { |
393 | self->impl = &blNullArrayImpl[selfI->implType]; |
394 | return blArrayImplRelease(selfI); |
395 | } |
396 | |
397 | size_t capacity = blArrayFittingCapacity(selfI->itemSize, size); |
398 | if (capacity < selfI->capacity) |
399 | BL_PROPAGATE(blArrayRealloc(self, capacity)); |
400 | |
401 | return BL_SUCCESS; |
402 | } |
403 | |
404 | BLResult blArrayResize(BLArrayCore* self, size_t n, const void* fill) noexcept { |
405 | BLArrayImpl* selfI = self->impl; |
406 | size_t size = selfI->size; |
407 | size_t itemSize = selfI->itemSize; |
408 | |
409 | // If `n` is smaller than the current `size` then this is a truncation. We |
410 | // only have to cover the BLVariant[] case, which means to destroy all |
411 | // variants beyond `n`. |
412 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(selfI->dispatchType); |
413 | if (n <= size) { |
414 | if (!blImplIsMutable(selfI)) { |
415 | if (n == size) |
416 | return BL_SUCCESS; |
417 | |
418 | size_t capacity = blArrayFittingCapacity(itemSize, n); |
419 | BLArrayImpl* newI = blArrayImplNew(selfI->implType, capacity); |
420 | |
421 | if (BL_UNLIKELY(!newI)) |
422 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
423 | |
424 | newI->size = n; |
425 | self->impl = newI; |
426 | funcs.copyData(newI->data, selfI->data, n * itemSize); |
427 | return blArrayImplRelease(selfI); |
428 | } |
429 | else { |
430 | selfI->size = n; |
431 | return funcs.destroyData(selfI->data, (size - n) * itemSize); |
432 | } |
433 | } |
434 | |
435 | // `n` becames the number of items to add to the array. |
436 | n -= size; |
437 | |
438 | void* dst; |
439 | BL_PROPAGATE(blArrayModifyOp(self, BL_MODIFY_OP_APPEND_FIT, n, &dst)); |
440 | |
441 | if (BL_UNLIKELY(!fill)) { |
442 | memset(dst, 0, n * itemSize); |
443 | return BL_SUCCESS; |
444 | } |
445 | |
446 | if (selfI->dispatchType) { |
447 | BLVariant* dstPtr = static_cast<BLVariant*>(dst); |
448 | const BLVariant* fillPtr = static_cast<const BLVariant*>(fill); |
449 | |
450 | size_t tupleSize = itemSize / sizeof(BLVariant); |
451 | size_t i, j; |
452 | |
453 | for (j = 0; j < tupleSize; j++) { |
454 | BLVariantImpl* impl = fillPtr[j].impl; |
455 | if (impl->refCount != 0) |
456 | blAtomicFetchAdd(&impl->refCount, n); |
457 | } |
458 | |
459 | for (i = 0; i < n; i++) { |
460 | for (j = 0; j < tupleSize; j++) { |
461 | dstPtr->impl = fillPtr[j].impl; |
462 | dstPtr++; |
463 | } |
464 | } |
465 | return BL_SUCCESS; |
466 | } |
467 | |
468 | switch (itemSize) { |
469 | case 1: blArrayFillPattern(static_cast<uint8_t *>(dst), *static_cast<const uint8_t *>(fill), n); break; |
470 | case 2: blArrayFillPattern(static_cast<uint16_t *>(dst), *static_cast<const uint16_t *>(fill), n); break; |
471 | case 4: blArrayFillPattern(static_cast<uint32_t *>(dst), *static_cast<const uint32_t *>(fill), n); break; |
472 | case 8: blArrayFillPattern(static_cast<BLUInt32xN<2>*>(dst), *static_cast<const BLUInt32xN<2>*>(fill), n); break; |
473 | case 12: blArrayFillPattern(static_cast<BLUInt32xN<3>*>(dst), *static_cast<const BLUInt32xN<3>*>(fill), n); break; |
474 | case 16: blArrayFillPattern(static_cast<BLUInt32xN<4>*>(dst), *static_cast<const BLUInt32xN<4>*>(fill), n); break; |
475 | |
476 | default: { |
477 | uint32_t* dst32 = static_cast<uint32_t*>(dst); |
478 | const uint32_t* src32 = static_cast<const uint32_t*>(fill); |
479 | size_t itemSizeDiv4 = itemSize / 4; |
480 | |
481 | for (size_t i = 0; i < n; i++) |
482 | for (size_t j = 0; j < itemSizeDiv4; j++) |
483 | *dst32++ = src32[j]; |
484 | break; |
485 | } |
486 | } |
487 | |
488 | return BL_SUCCESS; |
489 | } |
490 | |
491 | BLResult blArrayMakeMutable(BLArrayCore* self, void** dataOut) noexcept { |
492 | BLArrayImpl* selfI = self->impl; |
493 | |
494 | if (!blImplIsMutable(selfI)) { |
495 | size_t size = selfI->size; |
496 | size_t capacity = blArrayFittingCapacity(selfI->itemSize, blMax(size, blArrayInitialCapacity(selfI->itemSize))); |
497 | |
498 | BL_PROPAGATE(blArrayRealloc(self, capacity)); |
499 | selfI = self->impl; |
500 | } |
501 | |
502 | *dataOut = selfI->data; |
503 | return BL_SUCCESS; |
504 | } |
505 | |
506 | BLResult blArrayReserve(BLArrayCore* self, size_t n) noexcept { |
507 | BLArrayImpl* selfI = self->impl; |
508 | size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI)); |
509 | |
510 | if ((n | immutableMsk) > selfI->capacity) { |
511 | if (BL_UNLIKELY(n > blArrayMaximumCapacityTable[selfI->implType])) |
512 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
513 | |
514 | size_t capacity = blArrayFittingCapacity(selfI->itemSize, blMax(n, selfI->size)); |
515 | return blArrayRealloc(self, capacity); |
516 | } |
517 | |
518 | return BL_SUCCESS; |
519 | } |
520 | |
521 | BLResult blArrayModifyOp(BLArrayCore* self, uint32_t op, size_t n, void** dataOut) noexcept { |
522 | BLArrayImpl* selfI = self->impl; |
523 | size_t size = selfI->size; |
524 | size_t itemSize = selfI->itemSize; |
525 | |
526 | size_t index = (op >= BL_MODIFY_OP_APPEND_START) ? size : size_t(0); |
527 | size_t sizeAfter = blUAddSaturate(size, n); |
528 | size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI)); |
529 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(selfI->dispatchType); |
530 | |
531 | if ((sizeAfter | immutableMsk) > selfI->capacity) { |
532 | if (BL_UNLIKELY(sizeAfter > blArrayMaximumCapacityTable[selfI->implType])) |
533 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
534 | |
535 | size_t capacity = |
536 | (op & BL_MODIFY_OP_GROW_MASK) |
537 | ? blArrayGrowingCapacity(itemSize, sizeAfter) |
538 | : blArrayFittingCapacity(itemSize, sizeAfter); |
539 | |
540 | BLArrayImpl* newI = blArrayImplNew(selfI->implType, capacity); |
541 | if (BL_UNLIKELY(!newI)) { |
542 | *dataOut = nullptr; |
543 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
544 | } |
545 | |
546 | self->impl = newI; |
547 | newI->size = sizeAfter; |
548 | |
549 | uint8_t* dst = newI->dataAs<uint8_t>(); |
550 | *dataOut = dst + index * itemSize; |
551 | |
552 | if (immutableMsk) { |
553 | funcs.copyData(dst, selfI->data, index * itemSize); |
554 | return blArrayImplRelease(selfI); |
555 | } |
556 | else { |
557 | // Fallthrough to memcpy as it's faster than IncRef/DecRef. |
558 | selfI->size = 0; |
559 | memcpy(dst, selfI->data, index * itemSize); |
560 | return blArrayImplRelease(selfI); |
561 | } |
562 | } |
563 | else { |
564 | uint8_t* data = selfI->dataAs<uint8_t>(); |
565 | selfI->size = sizeAfter; |
566 | |
567 | *dataOut = data + index * itemSize; |
568 | return funcs.destroyData(data, size * itemSize); |
569 | } |
570 | } |
571 | |
572 | BLResult blArrayInsertOp(BLArrayCore* self, size_t index, size_t n, void** dataOut) noexcept { |
573 | BLArrayImpl* selfI = self->impl; |
574 | size_t size = selfI->size; |
575 | size_t itemSize = selfI->itemSize; |
576 | |
577 | size_t sizeAfter = blUAddSaturate(size, n); |
578 | size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI)); |
579 | |
580 | if ((sizeAfter | immutableMsk) > selfI->capacity) { |
581 | if (BL_UNLIKELY(sizeAfter > blArrayMaximumCapacityTable[selfI->implType])) |
582 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
583 | |
584 | size_t capacity = blArrayGrowingCapacity(itemSize, sizeAfter); |
585 | BLArrayImpl* newI = blArrayImplNew(selfI->implType, capacity); |
586 | |
587 | if (BL_UNLIKELY(!newI)) { |
588 | *dataOut = nullptr; |
589 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
590 | } |
591 | |
592 | self->impl = newI; |
593 | newI->size = sizeAfter; |
594 | |
595 | uint8_t* dst = newI->dataAs<uint8_t>(); |
596 | *dataOut = dst + index * itemSize; |
597 | |
598 | // NOTE: The same trick as used everywhere - if this is a mutable BLVariant[] |
599 | // array we just set its size to zero and use `memcpy()` as it's much faster |
600 | // than going through IncRef/DecRef of BLVariant[]. |
601 | BLArrayFuncs::CopyData copyData = blArrayFuncsByDispatchType(selfI->dispatchType).copyData; |
602 | if (!immutableMsk) { |
603 | selfI->size = 0; |
604 | copyData = (BLArrayFuncs::CopyData)memcpy; |
605 | } |
606 | |
607 | const uint8_t* src = selfI->dataAs<uint8_t>(); |
608 | copyData(dst, src, index * itemSize); |
609 | copyData(dst + (index + n) * itemSize, src + index * itemSize, (size - index) * itemSize); |
610 | return blArrayImplRelease(selfI); |
611 | } |
612 | else { |
613 | selfI->size = sizeAfter; |
614 | uint8_t* data = selfI->dataAs<uint8_t>(); |
615 | |
616 | *dataOut = data + index * itemSize; |
617 | memmove(data + (index + n) * itemSize, data + index * itemSize, (size - index) * itemSize); |
618 | |
619 | return BL_SUCCESS; |
620 | } |
621 | } |
622 | |
623 | // ============================================================================ |
624 | // [BLArray - Assign] |
625 | // ============================================================================ |
626 | |
627 | BLResult blArrayAssignMove(BLArrayCore* self, BLArrayCore* other) noexcept { |
628 | BLArrayImpl* selfI = self->impl; |
629 | BLArrayImpl* otherI = other->impl; |
630 | |
631 | self->impl = otherI; |
632 | other->impl = &blNullArrayImpl[otherI->implType]; |
633 | |
634 | return blArrayImplRelease(selfI); |
635 | } |
636 | |
637 | BLResult blArrayAssignWeak(BLArrayCore* self, const BLArrayCore* other) noexcept { |
638 | BLArrayImpl* selfI = self->impl; |
639 | BLArrayImpl* otherI = other->impl; |
640 | |
641 | self->impl = blImplIncRef(otherI); |
642 | return blArrayImplRelease(selfI); |
643 | } |
644 | |
645 | BLResult blArrayAssignDeep(BLArrayCore* self, const BLArrayCore* other) noexcept { |
646 | BLArrayImpl* otherI = other->impl; |
647 | return blArrayAssignView(self, otherI->data, otherI->size); |
648 | } |
649 | |
650 | BLResult blArrayAssignView(BLArrayCore* self, const void* items, size_t n) noexcept { |
651 | BLArrayImpl* selfI = self->impl; |
652 | size_t size = selfI->size; |
653 | size_t itemSize = selfI->itemSize; |
654 | |
655 | size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI)); |
656 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(selfI->dispatchType); |
657 | |
658 | if ((n | immutableMsk) > selfI->capacity) { |
659 | if (BL_UNLIKELY(n > blArrayMaximumCapacityTable[selfI->implType])) |
660 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
661 | |
662 | size_t capacity = blArrayFittingCapacity(itemSize, size); |
663 | BLArrayImpl* newI = blArrayImplNew(selfI->implType, capacity); |
664 | |
665 | if (BL_UNLIKELY(!newI)) |
666 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
667 | |
668 | newI->size = n; |
669 | self->impl = newI; |
670 | |
671 | funcs.copyData(newI->data, items, n * itemSize); |
672 | return blArrayImplRelease(selfI); |
673 | } |
674 | |
675 | if (!n) |
676 | return blArrayClear(self); |
677 | selfI->size = n; |
678 | |
679 | if (blIsVarArrayImplType(selfI->implType)) { |
680 | size_t replaceSize = blMin(size, n); |
681 | |
682 | uint8_t* dst = selfI->dataAs<uint8_t>(); |
683 | const uint8_t* src = static_cast<const uint8_t*>(items); |
684 | |
685 | funcs.replaceData(dst, src, replaceSize * itemSize); |
686 | return funcs.destroyData(dst + replaceSize * itemSize, (size - replaceSize) * itemSize); |
687 | } |
688 | else { |
689 | // Memory move is required in case of overlap between `data` and `items`. |
690 | memmove(selfI->data, items, n * itemSize); |
691 | return BL_SUCCESS; |
692 | } |
693 | } |
694 | |
695 | // ============================================================================ |
696 | // [BLArray - Append] |
697 | // ============================================================================ |
698 | |
699 | template<typename T> |
700 | static BL_INLINE BLResult blArrayAppendTypeT(BLArrayCore* self, T value) noexcept { |
701 | BLArrayImpl* selfI = self->impl; |
702 | BL_ASSERT(selfI->itemSize == sizeof(T)); |
703 | |
704 | size_t size = selfI->size + 1; |
705 | size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI)); |
706 | |
707 | // No enough capacity or not mutable - don't inline as this is an expensive |
708 | // case anyway. |
709 | if (BL_UNLIKELY((size | immutableMsk) > selfI->capacity)) |
710 | return blArrayAppendItem(self, &value); |
711 | |
712 | T* dst = selfI->dataAs<T>() + size - 1; |
713 | selfI->size = size; |
714 | |
715 | *dst = value; |
716 | return BL_SUCCESS; |
717 | } |
718 | |
719 | BLResult blArrayAppendU8(BLArrayCore* self, uint8_t value) noexcept { return blArrayAppendTypeT<uint8_t>(self, value); } |
720 | BLResult blArrayAppendU16(BLArrayCore* self, uint16_t value) noexcept { return blArrayAppendTypeT<uint16_t>(self, value); } |
721 | BLResult blArrayAppendU32(BLArrayCore* self, uint32_t value) noexcept { return blArrayAppendTypeT<uint32_t>(self, value); } |
722 | BLResult blArrayAppendU64(BLArrayCore* self, uint64_t value) noexcept { return blArrayAppendTypeT<uint64_t>(self, value); } |
723 | BLResult blArrayAppendF32(BLArrayCore* self, float value) noexcept { return blArrayAppendTypeT<float>(self, value); } |
724 | BLResult blArrayAppendF64(BLArrayCore* self, double value) noexcept { return blArrayAppendTypeT<double>(self, value); } |
725 | |
726 | BLResult blArrayAppendItem(BLArrayCore* self, const void* item) noexcept { |
727 | BLArrayImpl* selfI = self->impl; |
728 | size_t size = selfI->size; |
729 | size_t itemSize = selfI->itemSize; |
730 | |
731 | size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI)); |
732 | BLArrayFuncs::CopyData copyData = blArrayFuncsByDispatchType(selfI->dispatchType).copyData; |
733 | |
734 | if (BL_UNLIKELY((size | immutableMsk) >= selfI->capacity)) { |
735 | if (BL_UNLIKELY(size >= blArrayMaximumCapacityTable[selfI->implType])) |
736 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
737 | |
738 | size_t capacity = blArrayGrowingCapacity(itemSize, size + 1); |
739 | BLArrayImpl* newI = blArrayImplNew(selfI->implType, capacity); |
740 | |
741 | if (BL_UNLIKELY(!newI)) |
742 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
743 | |
744 | self->impl = newI; |
745 | newI->size = size + 1; |
746 | |
747 | uint8_t* dst = newI->dataAs<uint8_t>(); |
748 | const uint8_t* src = selfI->dataAs<uint8_t>(); |
749 | |
750 | // NOTE: The same trick as used everywhere - if this is a mutable BLVariant[] |
751 | // array we just set its size to zero and use `memcpy()` as it's much faster |
752 | // than going through IncRef/DecRef of BLVariant[]. |
753 | copyData(dst + size * itemSize, item, itemSize); |
754 | if (!immutableMsk) { |
755 | selfI->size = 0; |
756 | copyData = (BLArrayFuncs::CopyData)memcpy; |
757 | } |
758 | |
759 | copyData(dst, src, size * itemSize); |
760 | return blArrayImplRelease(selfI); |
761 | } |
762 | else { |
763 | void* dst = selfI->dataAs<uint8_t>() + size * itemSize; |
764 | selfI->size = size + 1; |
765 | |
766 | copyData(dst, item, itemSize); |
767 | return BL_SUCCESS; |
768 | } |
769 | } |
770 | |
771 | BLResult blArrayAppendView(BLArrayCore* self, const void* items, size_t n) noexcept { |
772 | BLArrayImpl* selfI = self->impl; |
773 | size_t size = selfI->size; |
774 | size_t itemSize = selfI->itemSize; |
775 | |
776 | size_t sizeAfter = blUAddSaturate(size, n); |
777 | size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI)); |
778 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(selfI->dispatchType); |
779 | |
780 | if (BL_UNLIKELY((sizeAfter | immutableMsk) > selfI->capacity)) { |
781 | if (BL_UNLIKELY(sizeAfter >= blArrayMaximumCapacityTable[selfI->implType])) |
782 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
783 | |
784 | size_t capacity = blArrayGrowingCapacity(itemSize, size + 1); |
785 | BLArrayImpl* newI = blArrayImplNew(selfI->implType, capacity); |
786 | |
787 | if (BL_UNLIKELY(!newI)) |
788 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
789 | |
790 | self->impl = newI; |
791 | newI->size = sizeAfter; |
792 | |
793 | uint8_t* dst = newI->dataAs<uint8_t>(); |
794 | const uint8_t* src = selfI->dataAs<uint8_t>(); |
795 | |
796 | if (!immutableMsk) { |
797 | selfI->size = 0; |
798 | memcpy(dst, src, size * itemSize); |
799 | } |
800 | else { |
801 | funcs.copyData(dst, src, size * itemSize); |
802 | } |
803 | |
804 | funcs.copyData(dst + size * itemSize, items, n * itemSize); |
805 | return blArrayImplRelease(selfI); |
806 | } |
807 | else { |
808 | uint8_t* data = selfI->dataAs<uint8_t>(); |
809 | selfI->size = sizeAfter; |
810 | |
811 | funcs.copyData(data + size * itemSize, items, n * itemSize); |
812 | return BL_SUCCESS; |
813 | } |
814 | } |
815 | |
816 | // ============================================================================ |
817 | // [BLArray - Insert] |
818 | // ============================================================================ |
819 | |
820 | template<typename T> |
821 | static BL_INLINE BLResult blArrayInsertSimple(BLArrayCore* self, size_t index, T value) noexcept { |
822 | BL_ASSERT(self->impl->itemSize == sizeof(T)); |
823 | |
824 | T* dst; |
825 | BL_PROPAGATE(blArrayInsertOp(self, index, 1, (void**)&dst)); |
826 | |
827 | *dst = value; |
828 | return BL_SUCCESS; |
829 | } |
830 | |
831 | BLResult blArrayInsertU8(BLArrayCore* self, size_t index, uint8_t value) noexcept { return blArrayInsertSimple<uint8_t>(self, index, value); } |
832 | BLResult blArrayInsertU16(BLArrayCore* self, size_t index, uint16_t value) noexcept { return blArrayInsertSimple<uint16_t>(self, index, value); } |
833 | BLResult blArrayInsertU32(BLArrayCore* self, size_t index, uint32_t value) noexcept { return blArrayInsertSimple<uint32_t>(self, index, value); } |
834 | BLResult blArrayInsertU64(BLArrayCore* self, size_t index, uint64_t value) noexcept { return blArrayInsertSimple<uint64_t>(self, index, value); } |
835 | BLResult blArrayInsertF32(BLArrayCore* self, size_t index, float value) noexcept { return blArrayInsertSimple<float>(self, index, value); } |
836 | BLResult blArrayInsertF64(BLArrayCore* self, size_t index, double value) noexcept { return blArrayInsertSimple<double>(self, index, value); } |
837 | |
838 | BLResult blArrayInsertItem(BLArrayCore* self, size_t index, const void* item) noexcept { |
839 | return blArrayInsertView(self, index, item, 1); |
840 | } |
841 | |
842 | BLResult blArrayInsertView(BLArrayCore* self, size_t index, const void* items, size_t n) noexcept { |
843 | BLArrayImpl* selfI = self->impl; |
844 | size_t size = selfI->size; |
845 | size_t itemSize = selfI->itemSize; |
846 | |
847 | size_t endIndex = index + n; |
848 | size_t sizeAfter = blUAddSaturate(size, n); |
849 | size_t immutableMsk = blBitMaskFromBool<size_t>(!blImplIsMutable(selfI)); |
850 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(selfI->dispatchType); |
851 | |
852 | if (BL_UNLIKELY((sizeAfter | immutableMsk) > selfI->capacity)) { |
853 | if (BL_UNLIKELY(sizeAfter > blArrayMaximumCapacityTable[selfI->implType])) |
854 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
855 | |
856 | size_t capacity = blArrayGrowingCapacity(itemSize, sizeAfter); |
857 | BLArrayImpl* newI = blArrayImplNew(selfI->implType, capacity); |
858 | |
859 | if (BL_UNLIKELY(!newI)) |
860 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
861 | |
862 | uint8_t* dst = newI->dataAs<uint8_t>(); |
863 | const uint8_t* src = selfI->dataAs<uint8_t>(); |
864 | |
865 | self->impl = newI; |
866 | newI->size = sizeAfter; |
867 | |
868 | BLArrayFuncs::CopyData rawCopyData = (BLArrayFuncs::CopyData)memcpy; |
869 | if (!immutableMsk) |
870 | selfI->size = 0; |
871 | else |
872 | rawCopyData = funcs.copyData; |
873 | |
874 | rawCopyData(dst, src, index * itemSize); |
875 | rawCopyData(dst + endIndex * itemSize, src + index * itemSize, (size - endIndex) * itemSize); |
876 | funcs.copyData(dst + index * itemSize, items, n * itemSize); |
877 | |
878 | return blArrayImplRelease(selfI); |
879 | } |
880 | else { |
881 | size_t nInBytes = n * itemSize; |
882 | selfI->size = sizeAfter; |
883 | |
884 | uint8_t* dst = selfI->dataAs<uint8_t>(); |
885 | uint8_t* dstEnd = dst + size * itemSize; |
886 | |
887 | const uint8_t* src = static_cast<const uint8_t*>(items); |
888 | |
889 | // The destination would point into the first byte that will be modified. |
890 | // So for example if the data is `[ABCDEF]` and we are inserting at index |
891 | // 1 then the `dst` would point to `[BCDEF]`. |
892 | dst += index * itemSize; |
893 | dstEnd += nInBytes; |
894 | |
895 | // Move the memory in-place making space for items to insert. For example |
896 | // if the destination points to [ABCDEF] and we want to insert 4 items we |
897 | // would get [____ABCDEF]. |
898 | memmove(dst + nInBytes, dst, (size - endIndex) * itemSize); |
899 | |
900 | // Split the [src:srcEnd] into LEAD and TRAIL slices and shift TRAIL slice |
901 | // in a way to cancel the `memmove()` if `src` overlaps `dst`. In practice |
902 | // if there is an overlap the [src:srcEnd] source should be within [dst:dstEnd] |
903 | // as it doesn't make sense to insert something which is outside of the current |
904 | // valid area. |
905 | // |
906 | // This illustrates how the input is divided into leading and traling data. |
907 | // |
908 | // BCDEFGH <- Insert This |
909 | // [abcdefghi] |
910 | // ^ <- Here |
911 | // |
912 | // [abcd_______efgh] |
913 | // <- memmove() |
914 | // |
915 | // |-| <- Copy leading data |
916 | // [abcdBCD____efgh] |
917 | // |
918 | // |--| <- Copy shifted trailing data. |
919 | // [abcdBCDEFGHdefgh] |
920 | |
921 | // Leading area precedes `dst` - nothing changed in here and if this is |
922 | // the whole are then there was no overlap that we would have to deal with. |
923 | size_t nLeadBytes = 0; |
924 | if (src < dst) { |
925 | nLeadBytes = blMin<size_t>((size_t)(dst - src), nInBytes); |
926 | |
927 | funcs.copyData(dst, src, nLeadBytes); |
928 | dst += nLeadBytes; |
929 | src += nLeadBytes; |
930 | } |
931 | |
932 | // Trailing area - we either shift none or all of it. |
933 | if (src < dstEnd) |
934 | src += nInBytes; // Shift source in case of overlap. |
935 | |
936 | funcs.copyData(dst, src, nInBytes - nLeadBytes); |
937 | return BL_SUCCESS; |
938 | } |
939 | } |
940 | |
941 | // ============================================================================ |
942 | // [BLArray - Replace] |
943 | // ============================================================================ |
944 | |
945 | template<typename T> |
946 | static BL_INLINE BLResult blArrayReplaceSimple(BLArrayCore* self, size_t index, T value) noexcept { |
947 | BLArrayImpl* selfI = self->impl; |
948 | BL_ASSERT(selfI->itemSize == sizeof(T)); |
949 | |
950 | size_t size = selfI->size; |
951 | if (BL_UNLIKELY(index >= size)) |
952 | return blTraceError(BL_ERROR_INVALID_VALUE); |
953 | |
954 | // No mutable - don't inline as this is an expensive case anyway. |
955 | if (BL_UNLIKELY(!blImplIsMutable(selfI))) |
956 | return blArrayReplaceItem(self, index, &value); |
957 | |
958 | T* data = selfI->dataAs<T>(); |
959 | data[index] = value; |
960 | return BL_SUCCESS; |
961 | } |
962 | |
963 | BLResult blArrayReplaceU8(BLArrayCore* self, size_t index, uint8_t value) noexcept { return blArrayReplaceSimple<uint8_t>(self, index, value); } |
964 | BLResult blArrayReplaceU16(BLArrayCore* self, size_t index, uint16_t value) noexcept { return blArrayReplaceSimple<uint16_t>(self, index, value); } |
965 | BLResult blArrayReplaceU32(BLArrayCore* self, size_t index, uint32_t value) noexcept { return blArrayReplaceSimple<uint32_t>(self, index, value); } |
966 | BLResult blArrayReplaceU64(BLArrayCore* self, size_t index, uint64_t value) noexcept { return blArrayReplaceSimple<uint64_t>(self, index, value); } |
967 | BLResult blArrayReplaceF32(BLArrayCore* self, size_t index, float value) noexcept { return blArrayReplaceSimple<float>(self, index, value); } |
968 | BLResult blArrayReplaceF64(BLArrayCore* self, size_t index, double value) noexcept { return blArrayReplaceSimple<double>(self, index, value); } |
969 | |
970 | BLResult blArrayReplaceItem(BLArrayCore* self, size_t index, const void* item) noexcept { |
971 | BLArrayImpl* selfI = self->impl; |
972 | size_t size = selfI->size; |
973 | size_t itemSize = selfI->itemSize; |
974 | |
975 | if (BL_UNLIKELY(index >= size)) |
976 | return blTraceError(BL_ERROR_INVALID_VALUE); |
977 | |
978 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(selfI->dispatchType); |
979 | if (!blImplIsMutable(selfI)) { |
980 | size_t capacity = blArrayFittingCapacity(itemSize, size); |
981 | BLArrayImpl* newI = blArrayImplNew(selfI->implType, capacity); |
982 | |
983 | if (BL_UNLIKELY(!newI)) |
984 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
985 | |
986 | uint8_t* dst = newI->dataAs<uint8_t>(); |
987 | const uint8_t* src = selfI->dataAs<uint8_t>(); |
988 | |
989 | funcs.copyData(dst, src, index * itemSize); |
990 | dst += index * itemSize; |
991 | src += index * itemSize; |
992 | |
993 | funcs.copyData(dst, item, itemSize); |
994 | dst += itemSize; |
995 | src += itemSize; |
996 | funcs.copyData(dst, src, (size - (index + 1)) * itemSize); |
997 | |
998 | newI->size = size; |
999 | self->impl = newI; |
1000 | return blArrayImplRelease(selfI); |
1001 | } |
1002 | else { |
1003 | void* data = selfI->dataAs<uint8_t>() + index * itemSize; |
1004 | |
1005 | if (blIsVarArrayImplType(selfI->implType)) { |
1006 | BLVariantImpl* oldI = static_cast<BLVariant*>(data)->impl; |
1007 | static_cast<BLVariant*>(data)->impl = blImplIncRef(static_cast<const BLVariant*>(item)->impl); |
1008 | return blVariantImplRelease(oldI); |
1009 | } |
1010 | else { |
1011 | blMemCopyInline(data, item, itemSize); |
1012 | return BL_SUCCESS; |
1013 | } |
1014 | } |
1015 | } |
1016 | |
1017 | BLResult blArrayReplaceView(BLArrayCore* self, size_t rStart, size_t rEnd, const void* items, size_t n) noexcept { |
1018 | BLArrayImpl* selfI = self->impl; |
1019 | size_t size = selfI->size; |
1020 | size_t end = blMin(rEnd, size); |
1021 | size_t index = blMin(rStart, end); |
1022 | size_t rangeSize = end - index; |
1023 | |
1024 | if (!rangeSize) |
1025 | return blArrayInsertView(self, index, items, n); |
1026 | |
1027 | size_t itemSize = selfI->itemSize; |
1028 | size_t tailSize = size - end; |
1029 | size_t sizeAfter = size - rangeSize + n; |
1030 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(selfI->dispatchType); |
1031 | |
1032 | if (blImplIsMutable(selfI)) { |
1033 | // 0 |<-Start End->| | <- Size |
1034 | // ^***********^***************^**********^ |
1035 | // | Unchanged | Replacement | TailSize | |
1036 | // |
1037 | // < Less |+++++++| <- MidEnd |
1038 | // == Equal |+++++++++++++++| <- MidEnd |
1039 | // > Greater |++++++++++++++++++++++| <- MidEnd |
1040 | uint8_t* data = selfI->dataAs<uint8_t>(); |
1041 | const uint8_t* itemsPtr = static_cast<const uint8_t*>(items); |
1042 | const uint8_t* itemsEnd = itemsPtr + itemSize * n; |
1043 | |
1044 | if (BL_LIKELY(itemsPtr >= data + size * n || itemsEnd <= data)) { |
1045 | // Non-overlaping case (the expected one). |
1046 | if (rangeSize == n) { |
1047 | funcs.replaceData(data + index * itemSize, items, n * itemSize); |
1048 | } |
1049 | else { |
1050 | funcs.destroyData(data + index * itemSize, rangeSize * itemSize); |
1051 | memmove(data + (index + rangeSize) * itemSize, data + end * itemSize, tailSize * itemSize); |
1052 | funcs.copyData(data + index * itemSize, items, n * itemSize); |
1053 | selfI->size = sizeAfter; |
1054 | } |
1055 | return BL_SUCCESS; |
1056 | } |
1057 | } |
1058 | |
1059 | // Array is either immmutable or the `items` overlap. |
1060 | size_t capacity = blArrayFittingCapacity(itemSize, sizeAfter); |
1061 | BLArrayImpl* newI = blArrayImplNew(selfI->implType, capacity); |
1062 | |
1063 | if (BL_UNLIKELY(!newI)) |
1064 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
1065 | |
1066 | uint8_t* dst = newI->dataAs<uint8_t>(); |
1067 | const uint8_t* src = selfI->dataAs<uint8_t>(); |
1068 | |
1069 | funcs.copyData(dst, src, index * itemSize); |
1070 | dst += index * itemSize; |
1071 | src += (index + rangeSize) * itemSize; |
1072 | |
1073 | funcs.copyData(dst, items, n * itemSize); |
1074 | dst += n * itemSize; |
1075 | funcs.copyData(dst, src, tailSize * itemSize); |
1076 | |
1077 | newI->size = size; |
1078 | self->impl = newI; |
1079 | return blArrayImplRelease(selfI); |
1080 | } |
1081 | |
1082 | // ============================================================================ |
1083 | // [BLArray - Remove] |
1084 | // ============================================================================ |
1085 | |
1086 | BLResult blArrayRemoveIndex(BLArrayCore* self, size_t index) noexcept { |
1087 | return blArrayRemoveRange(self, index, index + 1); |
1088 | } |
1089 | |
1090 | BLResult blArrayRemoveRange(BLArrayCore* self, size_t rStart, size_t rEnd) noexcept { |
1091 | BLArrayImpl* selfI = self->impl; |
1092 | size_t size = selfI->size; |
1093 | size_t itemSize = selfI->itemSize; |
1094 | |
1095 | size_t end = blMin(rEnd, size); |
1096 | size_t index = blMin(rStart, end); |
1097 | size_t n = end - index; |
1098 | |
1099 | if (!n) |
1100 | return BL_SUCCESS; |
1101 | |
1102 | size_t sizeAfter = size - n; |
1103 | const BLArrayFuncs& funcs = blArrayFuncsByDispatchType(selfI->dispatchType); |
1104 | |
1105 | if (BL_UNLIKELY(!blImplIsMutable(selfI))) { |
1106 | size_t capacity = blArrayFittingCapacity(itemSize, sizeAfter); |
1107 | BLArrayImpl* newI = blArrayImplNew(selfI->implType, capacity); |
1108 | |
1109 | if (BL_UNLIKELY(!newI)) |
1110 | return blTraceError(BL_ERROR_OUT_OF_MEMORY); |
1111 | |
1112 | newI->size = sizeAfter; |
1113 | self->impl = newI; |
1114 | |
1115 | uint8_t* dst = newI->dataAs<uint8_t>(); |
1116 | const uint8_t* src = selfI->dataAs<uint8_t>(); |
1117 | |
1118 | funcs.copyData(dst, src, index * itemSize); |
1119 | funcs.copyData(dst + index * itemSize, src + end * itemSize, (size - end) * itemSize); |
1120 | |
1121 | return blArrayImplRelease(selfI); |
1122 | } |
1123 | else { |
1124 | uint8_t* data = selfI->dataAs<uint8_t>() + index * itemSize; |
1125 | selfI->size = sizeAfter; |
1126 | |
1127 | funcs.destroyData(data, n * itemSize); |
1128 | memmove(data, data + n * itemSize, (size - end) * itemSize); |
1129 | |
1130 | return BL_SUCCESS; |
1131 | } |
1132 | } |
1133 | |
1134 | // =========================================================================== |
1135 | // [BLArray - Equals] |
1136 | // =========================================================================== |
1137 | |
1138 | bool blArrayEquals(const BLArrayCore* a, const BLArrayCore* b) noexcept { |
1139 | const BLArrayImpl* aI = a->impl; |
1140 | const BLArrayImpl* bI = b->impl; |
1141 | |
1142 | size_t size = aI->size; |
1143 | size_t itemSize = aI->itemSize; |
1144 | |
1145 | if ((aI->implType != bI->implType) | (size != bI->size)) |
1146 | return false; |
1147 | |
1148 | if (aI->data == bI->data) |
1149 | return true; |
1150 | |
1151 | if (aI->dispatchType == 0) |
1152 | return memcmp(aI->data, bI->data, size * itemSize) == 0; |
1153 | |
1154 | const uint8_t* aPtr = aI->dataAs<uint8_t>(); |
1155 | const uint8_t* bPtr = bI->dataAs<uint8_t>(); |
1156 | const uint8_t* aEnd = aPtr + size * itemSize; |
1157 | |
1158 | while (aPtr != aEnd) { |
1159 | if (!reinterpret_cast<const BLVariant*>(a)->equals(*reinterpret_cast<const BLVariant*>(b))) |
1160 | return false; |
1161 | |
1162 | aPtr += itemSize; |
1163 | bPtr += itemSize; |
1164 | } |
1165 | |
1166 | return true; |
1167 | } |
1168 | |
1169 | // =========================================================================== |
1170 | // [BLArray - Runtime Init] |
1171 | // =========================================================================== |
1172 | |
1173 | void blArrayRtInit(BLRuntimeContext* rt) noexcept { |
1174 | BL_UNUSED(rt); |
1175 | |
1176 | for (uint32_t implType = BL_IMPL_TYPE_ARRAY_FIRST; implType <= BL_IMPL_TYPE_ARRAY_LAST; implType++) { |
1177 | BLArrayImpl* arrayI = &blNullArrayImpl[implType]; |
1178 | |
1179 | arrayI->implType = uint8_t(implType); |
1180 | arrayI->implTraits = uint8_t(BL_IMPL_TRAIT_NULL); |
1181 | arrayI->itemSize = uint8_t(blArrayItemSizeTable[implType]); |
1182 | arrayI->dispatchType = uint8_t(blArrayDispatchTypeByImplType(implType)); |
1183 | arrayI->data = const_cast<uint8_t*>(blNullArrayBuffer); |
1184 | |
1185 | blAssignBuiltInNull(arrayI); |
1186 | } |
1187 | } |
1188 | |
1189 | // ============================================================================ |
1190 | // [BLArray - Unit Tests] |
1191 | // ============================================================================ |
1192 | |
1193 | #if defined(BL_TEST) |
1194 | UNIT(blend2d_array) { |
1195 | BLArray<int> a; |
1196 | |
1197 | INFO("Base functionality" ); |
1198 | { |
1199 | EXPECT(a.size() == 0); |
1200 | |
1201 | // [42] |
1202 | EXPECT(a.append(42) == BL_SUCCESS); |
1203 | EXPECT(a.size() == 1); |
1204 | EXPECT(a[0] == 42); |
1205 | |
1206 | // [42, 1, 2, 3] |
1207 | EXPECT(a.append(1, 2, 3) == BL_SUCCESS); |
1208 | EXPECT(a.size() == 4); |
1209 | EXPECT(a[0] == 42); |
1210 | EXPECT(a[1] == 1); |
1211 | EXPECT(a[2] == 2); |
1212 | EXPECT(a[3] == 3); |
1213 | |
1214 | // [10, 42, 1, 2, 3] |
1215 | EXPECT(a.prepend(10) == BL_SUCCESS); |
1216 | EXPECT(a.size() == 5); |
1217 | EXPECT(a[0] == 10); |
1218 | EXPECT(a[1] == 42); |
1219 | EXPECT(a[2] == 1); |
1220 | EXPECT(a[3] == 2); |
1221 | EXPECT(a[4] == 3); |
1222 | EXPECT(a.indexOf(4) == SIZE_MAX); |
1223 | EXPECT(a.indexOf(3) == 4); |
1224 | EXPECT(a.lastIndexOf(4) == SIZE_MAX); |
1225 | EXPECT(a.lastIndexOf(10) == 0); |
1226 | |
1227 | BLArray<int> b; |
1228 | EXPECT(b.append(10, 42, 1, 2, 3) == BL_SUCCESS); |
1229 | EXPECT(a.equals(b)); |
1230 | EXPECT(b.append(99) == BL_SUCCESS); |
1231 | EXPECT(!a.equals(b)); |
1232 | |
1233 | // [10, 3] |
1234 | EXPECT(a.remove(BLRange(1, 4)) == BL_SUCCESS); |
1235 | EXPECT(a.size() == 2); |
1236 | EXPECT(a[0] == 10); |
1237 | EXPECT(a[1] == 3); |
1238 | |
1239 | // [10, 33, 3] |
1240 | EXPECT(a.insert(1, 33) == BL_SUCCESS); |
1241 | EXPECT(a.size() == 3); |
1242 | EXPECT(a[0] == 10); |
1243 | EXPECT(a[1] == 33); |
1244 | EXPECT(a[2] == 3); |
1245 | |
1246 | // [10, 33, 3, 999, 1010, 2293] |
1247 | EXPECT(a.insert(2, 999, 1010, 2293) == BL_SUCCESS); |
1248 | EXPECT(a.size() == 6); |
1249 | EXPECT(a[0] == 10); |
1250 | EXPECT(a[1] == 33); |
1251 | EXPECT(a[2] == 999); |
1252 | EXPECT(a[3] == 1010); |
1253 | EXPECT(a[4] == 2293); |
1254 | EXPECT(a[5] == 3); |
1255 | } |
1256 | |
1257 | INFO("External array" ); |
1258 | { |
1259 | int externalData[4] = { 0 }; |
1260 | |
1261 | EXPECT(a.createFromData(externalData, 0, 4, BL_DATA_ACCESS_RW) == BL_SUCCESS); |
1262 | EXPECT(a.data() == externalData); |
1263 | |
1264 | EXPECT(a.append(42) == BL_SUCCESS); |
1265 | EXPECT(externalData[0] == 42); |
1266 | |
1267 | EXPECT(a.append(1, 2, 3) == BL_SUCCESS); |
1268 | EXPECT(externalData[3] == 3); |
1269 | |
1270 | // Appending more items the external array can hold must reallocate it. |
1271 | EXPECT(a.append(4) == BL_SUCCESS); |
1272 | EXPECT(a.data() != externalData); |
1273 | EXPECT(a.at(4) == 4); |
1274 | } |
1275 | } |
1276 | #endif |
1277 | |