1//===-- lib/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 FLANG_RT_RUNTIME_STACK_H_
14#define FLANG_RT_RUNTIME_STACK_H_
15
16#include "flang-rt/runtime/memory.h"
17#include "flang-rt/runtime/terminator.h"
18
19namespace Fortran::runtime {
20// Storage for the Stack elements of type T.
21template <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
37private:
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.
45template <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
50template <typename T, unsigned N = 0> class Stack : public StackStorage<T, N> {
51public:
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
119private:
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 // FLANG_RT_RUNTIME_STACK_H_
137

source code of flang-rt/lib/runtime/stack.h