flang/runtime/stack.h

   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