stackallocator.h

#pragma once
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <type_traits>

template <size_t N>
class StackStorage {
private:

  alignas(std::max_align_t) std::byte cont_[N];
  size_t offset_ = 0ULL;
  
public:

  StackStorage()                                = default;
  ~StackStorage()                               = default;
  StackStorage(const StackStorage&)             = delete;
  StackStorage& operator=(const StackStorage&)  = delete;

  std::byte* allocate(size_t bytes, size_t alignment) {
    void* current_ptr = cont_ + offset_;
    size_t available_space = N - offset_;
    void* aligned_ptr = current_ptr;

    if (std::align(alignment, bytes, aligned_ptr, available_space) == nullptr) {
      throw std::bad_alloc();
    }
    
    std::byte* result_ptr = static_cast<std::byte*>(aligned_ptr);
    offset_ = (result_ptr - cont_) + bytes;
    return result_ptr;
  }
};

template <typename T, size_t N>
class StackAllocator {
  template <typename U, size_t M>
  friend class StackAllocator;

private:
  StackStorage<N>* storage_ = nullptr;

public:

  using value_type            = T;
  using pointer               = T*;
  using const_pointer         = const T*;
  using size_type             = size_t;
  using difference_type       = std::ptrdiff_t;
  
  template <typename U> struct rebind { using other = StackAllocator<U, N>; };

  using propagate_on_container_copy_assignment = std::false_type;
  using propagate_on_container_move_assignment = std::true_type; 
  using propagate_on_container_swap            = std::true_type; 


  StackAllocator(StackStorage<N>& storage) noexcept : storage_(&storage) {}

  template <typename U>
  StackAllocator(const StackAllocator<U, N>& other) noexcept : storage_(other.storage_) {}
  
  StackAllocator(const StackAllocator& other) noexcept = default;
  StackAllocator& operator=(const StackAllocator& other) noexcept = default;
  ~StackAllocator() noexcept = default;

  pointer allocate(size_t objects) {
    return reinterpret_cast<pointer>(storage_->allocate(objects * sizeof(T), alignof(T)));
  }
  void deallocate(pointer, size_t) const noexcept {}

  StackAllocator select_on_container_copy_construction() const noexcept { 
    return *this;
  }

  bool operator==(const StackAllocator& other) const noexcept { return storage_ == other.storage_; }
  bool operator!=(const StackAllocator& other) const noexcept { return storage_ != other.storage_; }
};

template <typename T, typename Alloc = std::allocator<T>>
class List {
private:

  struct BaseNode {
    BaseNode* prev = this;
    BaseNode* next = this;
  };

  BaseNode sentinel_;
  size_t sz_ = 0ULL;

  struct Node : BaseNode {
    T value;
    Node(const T& val) : value(val) {}
    Node() = default;
  };

  [[no_unique_address]] Alloc alloc_;

  using AllocNode = typename std::allocator_traits<Alloc>::template rebind_alloc<Node>;
  using AllocNodeTraits = std::allocator_traits<AllocNode>;

  template <typename... Args>
  Node* create_node(Args&&... args) {
    AllocNode node_alloc(alloc_);
    Node* new_node = AllocNodeTraits::allocate(node_alloc, 1);
    try {
      AllocNodeTraits::construct(node_alloc, new_node, std::forward<Args>(args)...);
    }
    catch (...) {
      AllocNodeTraits::deallocate(node_alloc, new_node, 1);
      throw;
    }
    return new_node;
  }

  void destroy_node(Node* node) {
    AllocNode node_alloc(alloc_);
    AllocNodeTraits::destroy(node_alloc, node);
    AllocNodeTraits::deallocate(node_alloc, node, 1);
  }
  
  template <typename... Args>
  void internal_emplace(BaseNode* pos_node, Args&&... args) {
    Node* new_node = create_node(std::forward<Args>(args)...);
    new_node->prev = pos_node->prev;
    new_node->next = pos_node;
    pos_node->prev->next = new_node;
    pos_node->prev = new_node;
    ++sz_;
  }

public:

  List(Alloc a = Alloc()) :
    alloc_(std::allocator_traits<Alloc>::select_on_container_copy_construction(a))
  {}
  
  explicit List(size_t n, Alloc a = Alloc()) : List(a) {
    try {
      for (size_t i = 0; i < n; ++i) {
        internal_emplace(&sentinel_);
      }
    } catch (...) {
      clear();
      throw;
    }
  }
  
  List(size_t n, const T& v, Alloc a = Alloc()) : List(a) {
    try {
      for (size_t i = 0; i < n; ++i) {
        internal_emplace(&sentinel_, v);
      }
    } catch (...) {
      clear();
      throw;
    }
  }

  List(const List& other) :
    List(std::allocator_traits<Alloc>::select_on_container_copy_construction(other.alloc_))
  {
    try {
      for (const T& x : other) {
        push_back(x);
      }
    } catch (...) {
      clear();
      throw;
    }
  }

  List& operator=(const List& other) {
    if (this == &other) {
      return *this;
    }
    if constexpr (std::allocator_traits<Alloc>::propagate_on_container_copy_assignment::value) {
      if (alloc_ != other.alloc_) {
        clear(); 
        alloc_ = other.alloc_; 
        for (const T& x : other) {
          push_back(x); 
        }
        return *this;
      }
    }
    
    List temp(other);
    swap(temp); 
    return *this;
  }
  
  void swap(List& other) noexcept {
    if (this == &other) {
      return;
    }
    using POCCS = typename std::allocator_traits<Alloc>::propagate_on_container_swap;
    if constexpr (POCCS::value) {
      std::swap(alloc_, other.alloc_);
    }
    std::swap(sz_, other.sz_);
    std::swap(sentinel_.next, other.sentinel_.next);
    std::swap(sentinel_.prev, other.sentinel_.prev);

    sentinel_.next->prev = sentinel_.prev->next = &sentinel_;
    other.sentinel_.next->prev = other.sentinel_.prev->next = &other.sentinel_;
  }

  ~List() {
    clear();
  }

  void clear() noexcept {
    while (!empty()) {
      erase(cbegin()); 
    }
  }

  size_t size()         const noexcept { return sz_; }
  bool empty()          const noexcept { return sz_ == 0ULL; }
  Alloc get_allocator() const noexcept { return alloc_; }

  template <bool IsConst>
  class common_iterator {
  private:
    friend class List;
    BaseNode* node_;
    
  public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = T;
    using pointer           = std::conditional_t<IsConst, const T*, T*>;
    using reference         = std::conditional_t<IsConst, const T&, T&>;
    using difference_type   = std::ptrdiff_t;

    common_iterator(BaseNode* node = nullptr) : node_(node) {}

    template <bool OtherIsConstDummy = false, typename = std::enable_if_t<IsConst && !OtherIsConstDummy>>
    common_iterator(const common_iterator<OtherIsConstDummy>& other) noexcept : node_(other.node_) {}

    reference operator*()   const noexcept {
      return static_cast<std::conditional_t<IsConst, const Node*, Node*>>(node_)->value;
    }
    pointer   operator->()  const noexcept {
      return &(static_cast<std::conditional_t<IsConst, const Node*, Node*>>(node_)->value);
    }
    
    common_iterator& operator++()     noexcept {
      node_ = node_->next;
      return *this;
    }
    common_iterator  operator++(int)  noexcept {
      common_iterator temp(*this);
      node_ = node_->next; 
      return temp;
    }
    common_iterator& operator--()     noexcept {
      node_ = node_->prev;
      return *this;
    }
    common_iterator  operator--(int)  noexcept {
      common_iterator temp(*this);
      node_ = node_->prev; 
      return temp;
    }
    
    bool operator==(const common_iterator& other) const noexcept { return node_ == other.node_; }
    bool operator!=(const common_iterator& other) const noexcept { return node_ != other.node_; }

    BaseNode* get_base_node() const { return node_; }

  };

  using iterator =                  common_iterator<false>;
  using const_iterator =            common_iterator<true>;
  using reverse_iterator =          std::reverse_iterator<iterator>;
  using const_reverse_iterator =    std::reverse_iterator<const_iterator>;

  iterator begin()              noexcept { return iterator(sentinel_.next); }
  iterator end()                noexcept { return iterator(&sentinel_); }

  const_iterator begin()  const noexcept { return const_iterator(sentinel_.next); }
  const_iterator end()    const noexcept { return const_iterator(const_cast<BaseNode*>(&sentinel_)); }
  
  const_iterator cbegin() const noexcept { return begin(); }
  const_iterator cend()   const noexcept { return end(); }

  reverse_iterator rbegin()               noexcept { return reverse_iterator(end()); }
  reverse_iterator rend()                 noexcept { return reverse_iterator(begin()); }
  const_reverse_iterator rbegin()   const noexcept { return const_reverse_iterator(cend()); }
  const_reverse_iterator rend()     const noexcept { return const_reverse_iterator(cbegin()); }
  
  const_reverse_iterator crbegin()  const noexcept { return rbegin(); }
  const_reverse_iterator crend()    const noexcept { return rend(); }

  void push_back(const T& value)  { insert(cend(), value); }
  void push_front(const T& value) { insert(cbegin(), value); }
  void pop_back()                 { erase(--cend()); } 
  void pop_front()                { erase(cbegin()); } 
  
  void insert(const_iterator pos, const T& value) {
    internal_emplace(pos.get_base_node(), value);
  }

  void erase(const_iterator pos) {
    BaseNode* node_to_erase = pos.get_base_node();
    node_to_erase->prev->next = node_to_erase->next;
    node_to_erase->next->prev = node_to_erase->prev;
    destroy_node(static_cast<Node*>(node_to_erase));
    --sz_;
  }
};