1 //===-- runtime/stack.h -----------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 // Trivial implementation of stack that can be used on all targets. 10 // It is a list based stack with dynamic allocation/deallocation 11 // of the list nodes. 12 13 #ifndef FORTRAN_RUNTIME_STACK_H 14 #define FORTRAN_RUNTIME_STACK_H 15 16 #include "terminator.h" 17 #include "flang/Runtime/memory.h" 18 19 namespace Fortran::runtime { 20 // Storage for the Stack elements of type T. 21 template <typename T, unsigned N> struct StackStorage { 22 RT_API_ATTRS void *getElement(unsigned i) { 23 if (i < N) { 24 return storage[i]; 25 } else { 26 return nullptr; 27 } 28 } 29 RT_API_ATTRS const void *getElement(unsigned i) const { 30 if (i < N) { 31 return storage[i]; 32 } else { 33 return nullptr; 34 } 35 } 36 37 private: 38 // Storage to hold N elements of type T. 39 // It is declared as an array of bytes to avoid 40 // default construction (if any is implied by type T). 41 alignas(T) char storage[N][sizeof(T)]; 42 }; 43 44 // 0-size specialization that provides no storage. 45 template <typename T> struct alignas(T) StackStorage<T, 0> { 46 RT_API_ATTRS void *getElement(unsigned) { return nullptr; } 47 RT_API_ATTRS const void *getElement(unsigned) const { return nullptr; } 48 }; 49 50 template <typename T, unsigned N = 0> class Stack : public StackStorage<T, N> { 51 public: 52 Stack() = delete; 53 Stack(const Stack &) = delete; 54 Stack(Stack &&) = delete; 55 RT_API_ATTRS Stack(Terminator &terminator) : terminator_{terminator} {} 56 RT_API_ATTRS ~Stack() { 57 while (!empty()) { 58 pop(); 59 } 60 } 61 RT_API_ATTRS void push(const T &object) { 62 if (void *ptr{this->getElement(size_)}) { 63 new (ptr) T{object}; 64 } else { 65 top_ = New<List>{terminator_}(top_, object).release(); 66 } 67 ++size_; 68 } 69 RT_API_ATTRS void push(T &&object) { 70 if (void *ptr{this->getElement(size_)}) { 71 new (ptr) T{std::move(object)}; 72 } else { 73 top_ = New<List>{terminator_}(top_, std::move(object)).release(); 74 } 75 ++size_; 76 } 77 template <typename... Args> RT_API_ATTRS void emplace(Args &&...args) { 78 if (void *ptr{this->getElement(size_)}) { 79 new (ptr) T{std::forward<Args>(args)...}; 80 } else { 81 top_ = 82 New<List>{terminator_}(top_, std::forward<Args>(args)...).release(); 83 } 84 ++size_; 85 } 86 RT_API_ATTRS T &top() { 87 RUNTIME_CHECK(terminator_, size_ > 0); 88 if (void *ptr{this->getElement(size_ - 1)}) { 89 return *reinterpret_cast<T *>(ptr); 90 } else { 91 RUNTIME_CHECK(terminator_, top_); 92 return top_->object_; 93 } 94 } 95 RT_API_ATTRS const T &top() const { 96 RUNTIME_CHECK(terminator_, size_ > 0); 97 if (void *ptr{this->getElement(size_ - 1)}) { 98 return *reinterpret_cast<const T *>(ptr); 99 } else { 100 RUNTIME_CHECK(terminator_, top_); 101 return top_->object_; 102 } 103 } 104 RT_API_ATTRS void pop() { 105 RUNTIME_CHECK(terminator_, size_ > 0); 106 if (void *ptr{this->getElement(size_ - 1)}) { 107 reinterpret_cast<T *>(ptr)->~T(); 108 } else { 109 RUNTIME_CHECK(terminator_, top_); 110 List *next{top_->next_}; 111 top_->~List(); 112 FreeMemory(top_); 113 top_ = next; 114 } 115 --size_; 116 } 117 RT_API_ATTRS bool empty() const { return size_ == 0; } 118 119 private: 120 struct List { 121 template <typename... Args> 122 RT_API_ATTRS List(List *next, Args &&...args) 123 : next_(next), object_(std::forward<Args>(args)...) {} 124 RT_API_ATTRS List(List *next, const T &object) 125 : next_(next), object_(object) {} 126 RT_API_ATTRS List(List *next, T &&object) 127 : next_(next), object_(std::move(object)) {} 128 List *next_{nullptr}; 129 T object_; 130 }; 131 List *top_{nullptr}; 132 std::size_t size_{0}; 133 Terminator &terminator_; 134 }; 135 } // namespace Fortran::runtime 136 #endif // FORTRAN_RUNTIME_STACK_H 137