Debian Codegraph @

third_party/spirv-cross/spirv_cross_containers.hpp

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