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

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