1/*
2 * Copyright 2019-2021 Hans-Kristian Arntzen
3 * SPDX-License-Identifier: Apache-2.0 OR MIT
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18/*
19 * At your option, you may choose to accept this material under either:
20 * 1. The Apache License, Version 2.0, found at <http://www.apache.org/licenses/LICENSE-2.0>, or
21 * 2. The MIT License, found at <http://opensource.org/licenses/MIT>.
22 */
23
24#ifndef SPIRV_CROSS_CONTAINERS_HPP
25#define SPIRV_CROSS_CONTAINERS_HPP
26
27#include "spirv_cross_error_handling.hpp"
28#include <algorithm>
29#include <functional>
30#include <iterator>
31#include <limits>
32#include <memory>
33#include <stack>
34#include <stddef.h>
35#include <stdint.h>
36#include <stdlib.h>
37#include <string.h>
38#include <type_traits>
39#include <unordered_map>
40#include <unordered_set>
41#include <utility>
42#include <vector>
43
44#ifdef SPIRV_CROSS_NAMESPACE_OVERRIDE
45#define SPIRV_CROSS_NAMESPACE SPIRV_CROSS_NAMESPACE_OVERRIDE
46#else
47#define SPIRV_CROSS_NAMESPACE spirv_cross
48#endif
49
50namespace SPIRV_CROSS_NAMESPACE
51{
52#ifndef SPIRV_CROSS_FORCE_STL_TYPES
53// std::aligned_storage does not support size == 0, so roll our own.
54template <typename T, size_t N>
55class AlignedBuffer
56{
57public:
58 T *data()
59 {
60#if defined(_MSC_VER) && _MSC_VER < 1900
61 // MSVC 2013 workarounds, sigh ...
62 // Only use this workaround on MSVC 2013 due to some confusion around default initialized unions.
63 // Spec seems to suggest the memory will be zero-initialized, which is *not* what we want.
64 return reinterpret_cast<T *>(u.aligned_char);
65#else
66 return reinterpret_cast<T *>(aligned_char);
67#endif
68 }
69
70private:
71#if defined(_MSC_VER) && _MSC_VER < 1900
72 // MSVC 2013 workarounds, sigh ...
73 union
74 {
75 char aligned_char[sizeof(T) * N];
76 double dummy_aligner;
77 } u;
78#else
79 alignas(T) char aligned_char[sizeof(T) * N];
80#endif
81};
82
83template <typename T>
84class AlignedBuffer<T, 0>
85{
86public:
87 T *data()
88 {
89 return nullptr;
90 }
91};
92
93// An immutable version of SmallVector which erases type information about storage.
94template <typename T>
95class VectorView
96{
97public:
98 T &operator[](size_t i) SPIRV_CROSS_NOEXCEPT
99 {
100 return ptr[i];
101 }
102
103 const T &operator[](size_t i) const SPIRV_CROSS_NOEXCEPT
104 {
105 return ptr[i];
106 }
107
108 bool empty() const SPIRV_CROSS_NOEXCEPT
109 {
110 return buffer_size == 0;
111 }
112
113 size_t size() const SPIRV_CROSS_NOEXCEPT
114 {
115 return buffer_size;
116 }
117
118 T *data() SPIRV_CROSS_NOEXCEPT
119 {
120 return ptr;
121 }
122
123 const T *data() const SPIRV_CROSS_NOEXCEPT
124 {
125 return ptr;
126 }
127
128 T *begin() SPIRV_CROSS_NOEXCEPT
129 {
130 return ptr;
131 }
132
133 T *end() SPIRV_CROSS_NOEXCEPT
134 {
135 return ptr + buffer_size;
136 }
137
138 const T *begin() const SPIRV_CROSS_NOEXCEPT
139 {
140 return ptr;
141 }
142
143 const T *end() const SPIRV_CROSS_NOEXCEPT
144 {
145 return ptr + buffer_size;
146 }
147
148 T &front() SPIRV_CROSS_NOEXCEPT
149 {
150 return ptr[0];
151 }
152
153 const T &front() const SPIRV_CROSS_NOEXCEPT
154 {
155 return ptr[0];
156 }
157
158 T &back() SPIRV_CROSS_NOEXCEPT
159 {
160 return ptr[buffer_size - 1];
161 }
162
163 const T &back() const SPIRV_CROSS_NOEXCEPT
164 {
165 return ptr[buffer_size - 1];
166 }
167
168 // Makes it easier to consume SmallVector.
169#if defined(_MSC_VER) && _MSC_VER < 1900
170 explicit operator std::vector<T>() const
171 {
172 // Another MSVC 2013 workaround. It does not understand lvalue/rvalue qualified operations.
173 return std::vector<T>(ptr, ptr + buffer_size);
174 }
175#else
176 // Makes it easier to consume SmallVector.
177 explicit operator std::vector<T>() const &
178 {
179 return std::vector<T>(ptr, ptr + buffer_size);
180 }
181
182 // If we are converting as an r-value, we can pilfer our elements.
183 explicit operator std::vector<T>() &&
184 {
185 return std::vector<T>(std::make_move_iterator(ptr), std::make_move_iterator(ptr + buffer_size));
186 }
187#endif
188
189 // Avoid sliced copies. Base class should only be read as a reference.
190 VectorView(const VectorView &) = delete;
191 void operator=(const VectorView &) = delete;
192
193protected:
194 VectorView() = default;
195 T *ptr = nullptr;
196 size_t buffer_size = 0;
197};
198
199// Simple vector which supports up to N elements inline, without malloc/free.
200// We use a lot of throwaway vectors all over the place which triggers allocations.
201// This class only implements the subset of std::vector we need in SPIRV-Cross.
202// It is *NOT* a drop-in replacement in general projects.
203template <typename T, size_t N = 8>
204class SmallVector : public VectorView<T>
205{
206public:
207 SmallVector() SPIRV_CROSS_NOEXCEPT
208 {
209 this->ptr = stack_storage.data();
210 buffer_capacity = N;
211 }
212
213 SmallVector(const T *arg_list_begin, const T *arg_list_end) SPIRV_CROSS_NOEXCEPT : SmallVector()
214 {
215 auto count = size_t(arg_list_end - arg_list_begin);
216 reserve(count);
217 for (size_t i = 0; i < count; i++, arg_list_begin++)
218 new (&this->ptr[i]) T(*arg_list_begin);
219 this->buffer_size = count;
220 }
221
222 SmallVector(std::initializer_list<T> init) SPIRV_CROSS_NOEXCEPT : SmallVector(init.begin(), init.end())
223 {
224 }
225
226 SmallVector(SmallVector &&other) SPIRV_CROSS_NOEXCEPT : SmallVector()
227 {
228 *this = std::move(other);
229 }
230
231 SmallVector &operator=(SmallVector &&other) SPIRV_CROSS_NOEXCEPT
232 {
233 clear();
234 if (other.ptr != other.stack_storage.data())
235 {
236 // Pilfer allocated pointer.
237 if (this->ptr != stack_storage.data())
238 free(this->ptr);
239 this->ptr = other.ptr;
240 this->buffer_size = other.buffer_size;
241 buffer_capacity = other.buffer_capacity;
242 other.ptr = nullptr;
243 other.buffer_size = 0;
244 other.buffer_capacity = 0;
245 }
246 else
247 {
248 // Need to move the stack contents individually.
249 reserve(count: other.buffer_size);
250 for (size_t i = 0; i < other.buffer_size; i++)
251 {
252 new (&this->ptr[i]) T(std::move(other.ptr[i]));
253 other.ptr[i].~T();
254 }
255 this->buffer_size = other.buffer_size;
256 other.buffer_size = 0;
257 }
258 return *this;
259 }
260
261 SmallVector(const SmallVector &other) SPIRV_CROSS_NOEXCEPT : SmallVector()
262 {
263 *this = other;
264 }
265
266 SmallVector &operator=(const SmallVector &other) SPIRV_CROSS_NOEXCEPT
267 {
268 if (this == &other)
269 return *this;
270
271 clear();
272 reserve(count: other.buffer_size);
273 for (size_t i = 0; i < other.buffer_size; i++)
274 new (&this->ptr[i]) T(other.ptr[i]);
275 this->buffer_size = other.buffer_size;
276 return *this;
277 }
278
279 explicit SmallVector(size_t count) SPIRV_CROSS_NOEXCEPT : SmallVector()
280 {
281 resize(new_size: count);
282 }
283
284 ~SmallVector()
285 {
286 clear();
287 if (this->ptr != stack_storage.data())
288 free(this->ptr);
289 }
290
291 void clear() SPIRV_CROSS_NOEXCEPT
292 {
293 for (size_t i = 0; i < this->buffer_size; i++)
294 this->ptr[i].~T();
295 this->buffer_size = 0;
296 }
297
298 void push_back(const T &t) SPIRV_CROSS_NOEXCEPT
299 {
300 reserve(count: this->buffer_size + 1);
301 new (&this->ptr[this->buffer_size]) T(t);
302 this->buffer_size++;
303 }
304
305 void push_back(T &&t) SPIRV_CROSS_NOEXCEPT
306 {
307 reserve(count: this->buffer_size + 1);
308 new (&this->ptr[this->buffer_size]) T(std::move(t));
309 this->buffer_size++;
310 }
311
312 void pop_back() SPIRV_CROSS_NOEXCEPT
313 {
314 // Work around false positive warning on GCC 8.3.
315 // Calling pop_back on empty vector is undefined.
316 if (!this->empty())
317 resize(new_size: this->buffer_size - 1);
318 }
319
320 template <typename... Ts>
321 void emplace_back(Ts &&... ts) SPIRV_CROSS_NOEXCEPT
322 {
323 reserve(count: this->buffer_size + 1);
324 new (&this->ptr[this->buffer_size]) T(std::forward<Ts>(ts)...);
325 this->buffer_size++;
326 }
327
328 void reserve(size_t count) SPIRV_CROSS_NOEXCEPT
329 {
330 if ((count > (std::numeric_limits<size_t>::max)() / sizeof(T)) ||
331 (count > (std::numeric_limits<size_t>::max)() / 2))
332 {
333 // Only way this should ever happen is with garbage input, terminate.
334 std::terminate();
335 }
336
337 if (count > buffer_capacity)
338 {
339 size_t target_capacity = buffer_capacity;
340 if (target_capacity == 0)
341 target_capacity = 1;
342
343 // Weird parens works around macro issues on Windows if NOMINMAX is not used.
344 target_capacity = (std::max)(a: target_capacity, b: N);
345
346 // Need to ensure there is a POT value of target capacity which is larger than count,
347 // otherwise this will overflow.
348 while (target_capacity < count)
349 target_capacity <<= 1u;
350
351 T *new_buffer =
352 target_capacity > N ? static_cast<T *>(malloc(size: target_capacity * sizeof(T))) : stack_storage.data();
353
354 // If we actually fail this malloc, we are hosed anyways, there is no reason to attempt recovery.
355 if (!new_buffer)
356 std::terminate();
357
358 // In case for some reason two allocations both come from same stack.
359 if (new_buffer != this->ptr)
360 {
361 // We don't deal with types which can throw in move constructor.
362 for (size_t i = 0; i < this->buffer_size; i++)
363 {
364 new (&new_buffer[i]) T(std::move(this->ptr[i]));
365 this->ptr[i].~T();
366 }
367 }
368
369 if (this->ptr != stack_storage.data())
370 free(this->ptr);
371 this->ptr = new_buffer;
372 buffer_capacity = target_capacity;
373 }
374 }
375
376 void insert(T *itr, const T *insert_begin, const T *insert_end) SPIRV_CROSS_NOEXCEPT
377 {
378 auto count = size_t(insert_end - insert_begin);
379 if (itr == this->end())
380 {
381 reserve(count: this->buffer_size + count);
382 for (size_t i = 0; i < count; i++, insert_begin++)
383 new (&this->ptr[this->buffer_size + i]) T(*insert_begin);
384 this->buffer_size += count;
385 }
386 else
387 {
388 if (this->buffer_size + count > buffer_capacity)
389 {
390 auto target_capacity = this->buffer_size + count;
391 if (target_capacity == 0)
392 target_capacity = 1;
393 if (target_capacity < N)
394 target_capacity = N;
395
396 while (target_capacity < count)
397 target_capacity <<= 1u;
398
399 // Need to allocate new buffer. Move everything to a new buffer.
400 T *new_buffer =
401 target_capacity > N ? static_cast<T *>(malloc(target_capacity * sizeof(T))) : stack_storage.data();
402
403 // If we actually fail this malloc, we are hosed anyways, there is no reason to attempt recovery.
404 if (!new_buffer)
405 std::terminate();
406
407 // First, move elements from source buffer to new buffer.
408 // We don't deal with types which can throw in move constructor.
409 auto *target_itr = new_buffer;
410 auto *original_source_itr = this->begin();
411
412 if (new_buffer != this->ptr)
413 {
414 while (original_source_itr != itr)
415 {
416 new (target_itr) T(std::move(*original_source_itr));
417 original_source_itr->~T();
418 ++original_source_itr;
419 ++target_itr;
420 }
421 }
422
423 // Copy-construct new elements.
424 for (auto *source_itr = insert_begin; source_itr != insert_end; ++source_itr, ++target_itr)
425 new (target_itr) T(*source_itr);
426
427 // Move over the other half.
428 if (new_buffer != this->ptr || insert_begin != insert_end)
429 {
430 while (original_source_itr != this->end())
431 {
432 new (target_itr) T(std::move(*original_source_itr));
433 original_source_itr->~T();
434 ++original_source_itr;
435 ++target_itr;
436 }
437 }
438
439 if (this->ptr != stack_storage.data())
440 free(this->ptr);
441 this->ptr = new_buffer;
442 buffer_capacity = target_capacity;
443 }
444 else
445 {
446 // Move in place, need to be a bit careful about which elements are constructed and which are not.
447 // Move the end and construct the new elements.
448 auto *target_itr = this->end() + count;
449 auto *source_itr = this->end();
450 while (target_itr != this->end() && source_itr != itr)
451 {
452 --target_itr;
453 --source_itr;
454 new (target_itr) T(std::move(*source_itr));
455 }
456
457 // For already constructed elements we can move-assign.
458 std::move_backward(itr, source_itr, target_itr);
459
460 // For the inserts which go to already constructed elements, we can do a plain copy.
461 while (itr != this->end() && insert_begin != insert_end)
462 *itr++ = *insert_begin++;
463
464 // For inserts into newly allocated memory, we must copy-construct instead.
465 while (insert_begin != insert_end)
466 {
467 new (itr) T(*insert_begin);
468 ++itr;
469 ++insert_begin;
470 }
471 }
472
473 this->buffer_size += count;
474 }
475 }
476
477 void insert(T *itr, const T &value) SPIRV_CROSS_NOEXCEPT
478 {
479 insert(itr, &value, &value + 1);
480 }
481
482 T *erase(T *itr) SPIRV_CROSS_NOEXCEPT
483 {
484 std::move(itr + 1, this->end(), itr);
485 this->ptr[--this->buffer_size].~T();
486 return itr;
487 }
488
489 void erase(T *start_erase, T *end_erase) SPIRV_CROSS_NOEXCEPT
490 {
491 if (end_erase == this->end())
492 {
493 resize(new_size: size_t(start_erase - this->begin()));
494 }
495 else
496 {
497 auto new_size = this->buffer_size - (end_erase - start_erase);
498 std::move(end_erase, this->end(), start_erase);
499 resize(new_size);
500 }
501 }
502
503 void resize(size_t new_size) SPIRV_CROSS_NOEXCEPT
504 {
505 if (new_size < this->buffer_size)
506 {
507 for (size_t i = new_size; i < this->buffer_size; i++)
508 this->ptr[i].~T();
509 }
510 else if (new_size > this->buffer_size)
511 {
512 reserve(count: new_size);
513 for (size_t i = this->buffer_size; i < new_size; i++)
514 new (&this->ptr[i]) T();
515 }
516
517 this->buffer_size = new_size;
518 }
519
520private:
521 size_t buffer_capacity = 0;
522 AlignedBuffer<T, N> stack_storage;
523};
524
525// A vector without stack storage.
526// Could also be a typedef-ed to std::vector,
527// but might as well use the one we have.
528template <typename T>
529using Vector = SmallVector<T, 0>;
530
531#else // SPIRV_CROSS_FORCE_STL_TYPES
532
533template <typename T, size_t N = 8>
534using SmallVector = std::vector<T>;
535template <typename T>
536using Vector = std::vector<T>;
537template <typename T>
538using VectorView = std::vector<T>;
539
540#endif // SPIRV_CROSS_FORCE_STL_TYPES
541
542// An object pool which we use for allocating IVariant-derived objects.
543// We know we are going to allocate a bunch of objects of each type,
544// so amortize the mallocs.
545class ObjectPoolBase
546{
547public:
548 virtual ~ObjectPoolBase() = default;
549 virtual void deallocate_opaque(void *ptr) = 0;
550};
551
552template <typename T>
553class ObjectPool : public ObjectPoolBase
554{
555public:
556 explicit ObjectPool(unsigned start_object_count_ = 16)
557 : start_object_count(start_object_count_)
558 {
559 }
560
561 template <typename... P>
562 T *allocate(P &&... p)
563 {
564 if (vacants.empty())
565 {
566 unsigned num_objects = start_object_count << memory.size();
567 T *ptr = static_cast<T *>(malloc(size: num_objects * sizeof(T)));
568 if (!ptr)
569 return nullptr;
570
571 for (unsigned i = 0; i < num_objects; i++)
572 vacants.push_back(&ptr[i]);
573
574 memory.emplace_back(ptr);
575 }
576
577 T *ptr = vacants.back();
578 vacants.pop_back();
579 new (ptr) T(std::forward<P>(p)...);
580 return ptr;
581 }
582
583 void deallocate(T *ptr)
584 {
585 ptr->~T();
586 vacants.push_back(ptr);
587 }
588
589 void deallocate_opaque(void *ptr) override
590 {
591 deallocate(ptr: static_cast<T *>(ptr));
592 }
593
594 void clear()
595 {
596 vacants.clear();
597 memory.clear();
598 }
599
600protected:
601 Vector<T *> vacants;
602
603 struct MallocDeleter
604 {
605 void operator()(T *ptr)
606 {
607 ::free(ptr: ptr);
608 }
609 };
610
611 SmallVector<std::unique_ptr<T, MallocDeleter>> memory;
612 unsigned start_object_count;
613};
614
615template <size_t StackSize = 4096, size_t BlockSize = 4096>
616class StringStream
617{
618public:
619 StringStream()
620 {
621 reset();
622 }
623
624 ~StringStream()
625 {
626 reset();
627 }
628
629 // Disable copies and moves. Makes it easier to implement, and we don't need it.
630 StringStream(const StringStream &) = delete;
631 void operator=(const StringStream &) = delete;
632
633 template <typename T, typename std::enable_if<!std::is_floating_point<T>::value, int>::type = 0>
634 StringStream &operator<<(const T &t)
635 {
636 auto s = std::to_string(t);
637 append(s: s.data(), len: s.size());
638 return *this;
639 }
640
641 // Only overload this to make float/double conversions ambiguous.
642 StringStream &operator<<(uint32_t v)
643 {
644 auto s = std::to_string(val: v);
645 append(s: s.data(), len: s.size());
646 return *this;
647 }
648
649 StringStream &operator<<(char c)
650 {
651 append(s: &c, len: 1);
652 return *this;
653 }
654
655 StringStream &operator<<(const std::string &s)
656 {
657 append(s: s.data(), len: s.size());
658 return *this;
659 }
660
661 StringStream &operator<<(const char *s)
662 {
663 append(s, len: strlen(s: s));
664 return *this;
665 }
666
667 template <size_t N>
668 StringStream &operator<<(const char (&s)[N])
669 {
670 append(s, len: strlen(s));
671 return *this;
672 }
673
674 std::string str() const
675 {
676 std::string ret;
677 size_t target_size = 0;
678 for (auto &saved : saved_buffers)
679 target_size += saved.offset;
680 target_size += current_buffer.offset;
681 ret.reserve(res_arg: target_size);
682
683 for (auto &saved : saved_buffers)
684 ret.insert(ret.end(), saved.buffer, saved.buffer + saved.offset);
685 ret.insert(ret.end(), current_buffer.buffer, current_buffer.buffer + current_buffer.offset);
686 return ret;
687 }
688
689 void reset()
690 {
691 for (auto &saved : saved_buffers)
692 if (saved.buffer != stack_buffer)
693 free(saved.buffer);
694 if (current_buffer.buffer != stack_buffer)
695 free(current_buffer.buffer);
696
697 saved_buffers.clear();
698 current_buffer.buffer = stack_buffer;
699 current_buffer.offset = 0;
700 current_buffer.size = sizeof(stack_buffer);
701 }
702
703private:
704 struct Buffer
705 {
706 char *buffer = nullptr;
707 size_t offset = 0;
708 size_t size = 0;
709 };
710 Buffer current_buffer;
711 char stack_buffer[StackSize];
712 SmallVector<Buffer> saved_buffers;
713
714 void append(const char *s, size_t len)
715 {
716 size_t avail = current_buffer.size - current_buffer.offset;
717 if (avail < len)
718 {
719 if (avail > 0)
720 {
721 memcpy(current_buffer.buffer + current_buffer.offset, s, avail);
722 s += avail;
723 len -= avail;
724 current_buffer.offset += avail;
725 }
726
727 saved_buffers.push_back(current_buffer);
728 size_t target_size = len > BlockSize ? len : BlockSize;
729 current_buffer.buffer = static_cast<char *>(malloc(size: target_size));
730 if (!current_buffer.buffer)
731 SPIRV_CROSS_THROW("Out of memory.");
732
733 memcpy(current_buffer.buffer, s, len);
734 current_buffer.offset = len;
735 current_buffer.size = target_size;
736 }
737 else
738 {
739 memcpy(current_buffer.buffer + current_buffer.offset, s, len);
740 current_buffer.offset += len;
741 }
742 }
743};
744
745} // namespace SPIRV_CROSS_NAMESPACE
746
747#endif
748

source code of qtshadertools/src/3rdparty/SPIRV-Cross/spirv_cross_containers.hpp