runtime/stack.h

//===-- runtime/stack.h -----------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

// Trivial implementation of stack that can be used on all targets.
// It is a list based stack with dynamic allocation/deallocation
// of the list nodes.

#ifndef FORTRAN_RUNTIME_STACK_H
#define FORTRAN_RUNTIME_STACK_H

#include "terminator.h"
#include "flang/Runtime/memory.h"

namespace Fortran::runtime {
// Storage for the Stack elements of type T.
template <typename T, unsigned N> struct StackStorage {
  RT_API_ATTRS void *getElement(unsigned i) {
    if (i < N) {
      return storage[i];
    } else {
      return nullptr;
    }
  }
  RT_API_ATTRS const void *getElement(unsigned i) const {
    if (i < N) {
      return storage[i];
    } else {
      return nullptr;
    }
  }

private:
  // Storage to hold N elements of type T.
  // It is declared as an array of bytes to avoid
  // default construction (if any is implied by type T).
  alignas(T) char storage[N][sizeof(T)];
};

// 0-size specialization that provides no storage.
template <typename T> struct alignas(T) StackStorage<T, 0> {
  RT_API_ATTRS void *getElement(unsigned) { return nullptr; }
  RT_API_ATTRS const void *getElement(unsigned) const { return nullptr; }
};

template <typename T, unsigned N = 0> class Stack : public StackStorage<T, N> {
public:
  Stack() = delete;
  Stack(const Stack &) = delete;
  Stack(Stack &&) = delete;
  RT_API_ATTRS Stack(Terminator &terminator) : terminator_{terminator} {}
  RT_API_ATTRS ~Stack() {
    while (!empty()) {
      pop();
    }
  }
  RT_API_ATTRS void push(const T &object) {
    if (void *ptr{this->getElement(size_)}) {
      new (ptr) T{object};
    } else {
      top_ = New<List>{terminator_}(top_, object).release();
    }
    ++size_;
  }
  RT_API_ATTRS void push(T &&object) {
    if (void *ptr{this->getElement(size_)}) {
      new (ptr) T{std::move(object)};
    } else {
      top_ = New<List>{terminator_}(top_, std::move(object)).release();
    }
    ++size_;
  }
  template <typename... Args> RT_API_ATTRS void emplace(Args &&...args) {
    if (void *ptr{this->getElement(size_)}) {
      new (ptr) T{std::forward<Args>(args)...};
    } else {
      top_ =
          New<List>{terminator_}(top_, std::forward<Args>(args)...).release();
    }
    ++size_;
  }
  RT_API_ATTRS T &top() {
    RUNTIME_CHECK(terminator_, size_ > 0);
    if (void *ptr{this->getElement(size_ - 1)}) {
      return *reinterpret_cast<T *>(ptr);
    } else {
      RUNTIME_CHECK(terminator_, top_);
      return top_->object_;
    }
  }
  RT_API_ATTRS const T &top() const {
    RUNTIME_CHECK(terminator_, size_ > 0);
    if (void *ptr{this->getElement(size_ - 1)}) {
      return *reinterpret_cast<const T *>(ptr);
    } else {
      RUNTIME_CHECK(terminator_, top_);
      return top_->object_;
    }
  }
  RT_API_ATTRS void pop() {
    RUNTIME_CHECK(terminator_, size_ > 0);
    if (void *ptr{this->getElement(size_ - 1)}) {
      reinterpret_cast<T *>(ptr)->~T();
    } else {
      RUNTIME_CHECK(terminator_, top_);
      List *next{top_->next_};
      top_->~List();
      FreeMemory(top_);
      top_ = next;
    }
    --size_;
  }
  RT_API_ATTRS bool empty() const { return size_ == 0; }

private:
  struct List {
    template <typename... Args>
    RT_API_ATTRS List(List *next, Args &&...args)
        : next_(next), object_(std::forward<Args>(args)...) {}
    RT_API_ATTRS List(List *next, const T &object)
        : next_(next), object_(object) {}
    RT_API_ATTRS List(List *next, T &&object)
        : next_(next), object_(std::move(object)) {}
    List *next_{nullptr};
    T object_;
  };
  List *top_{nullptr};
  std::size_t size_{0};
  Terminator &terminator_;
};
} // namespace Fortran::runtime
#endif // FORTRAN_RUNTIME_STACK_H