137 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9// Trivial implementation of stack that can be used on all targets.10// It is a list based stack with dynamic allocation/deallocation11// 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 avoid40 // 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::runtime136#endif // FLANG_RT_RUNTIME_STACK_H_137