fwd_llist.h

#pragma once
#include "gaia/config/config.h"
 
#include "gaia/core/iterator.h"
 
namespace gaia {
  namespace cnt {
    template <class T>
    struct fwd_llist_link {
      T* next = nullptr;
      T** prevs_next = nullptr;
 
      GAIA_NODISCARD bool linked() const {
        return next != nullptr || prevs_next != nullptr;
      }
    };
 
    template <class T>
    struct fwd_llist_base {
      fwd_llist_link<T> fwd_link_GAIA;
 
      fwd_llist_link<T>& get_fwd_llist_link() {
        return fwd_link_GAIA;
      }
      const fwd_llist_link<T>& get_fwd_llist_link() const {
        return fwd_link_GAIA;
      }
    };
 
    template <typename T>
    struct fwd_llist_iterator {
      using iterator_category = core::forward_iterator_tag;
      using value_type = T;
      using pointer = T*;
      using reference = T&;
      using difference_type = uint32_t;
      using size_type = uint32_t;
      using iterator = fwd_llist_iterator;
 
    private:
      T* m_pNode;
 
    public:
      explicit fwd_llist_iterator(T* pNode): m_pNode(pNode) {}
 
      reference operator*() const {
        return *m_pNode;
      }
      pointer operator->() const {
        return m_pNode;
      }
 
      iterator& operator++() {
        auto& list = m_pNode->get_fwd_llist_link();
        m_pNode = list.next;
        return *this;
      }
      iterator operator++(int) {
        iterator temp(*this);
        ++*this;
        return temp;
      }
 
      GAIA_NODISCARD bool operator==(const iterator& other) const {
        return m_pNode == other.m_pNode;
      }
      GAIA_NODISCARD bool operator!=(const iterator& other) const {
        return m_pNode != other.m_pNode;
      }
    };
 
    template <class T>
    struct fwd_llist {
      uint32_t count = 0;
      T* first = nullptr;
 
      void clear() {
        count = 0;
        first = nullptr;
      }
 
      void link(T* pNode) {
        GAIA_ASSERT(pNode != nullptr);
 
        auto& link = pNode->get_fwd_llist_link();
        link.next = first;
        if (first != nullptr) {
          auto& linkFirst = first->get_fwd_llist_link();
          linkFirst.prevs_next = &(link.next);
          first = pNode;
        }
        link.prevs_next = &first;
        first = pNode;
 
        ++count;
      }
 
      void unlink(T* pNode) {
        GAIA_ASSERT(pNode != nullptr);
 
        auto& link = pNode->get_fwd_llist_link();
        *(link.prevs_next) = link.next;
        if (link.next != nullptr) {
          auto& linkNext = link.next->get_fwd_llist_link();
          linkNext.prevs_next = link.prevs_next;
        }
 
        // Reset the node's link
        link = {};
 
        --count;
      }
 
      GAIA_NODISCARD bool has(T* pNode) const {
        GAIA_ASSERT(pNode != nullptr);
 
        for (auto& curr: *this) {
          if (&curr == pNode)
            return true;
        }
 
        return false;
      }
 
      GAIA_NODISCARD bool empty() const {
        GAIA_ASSERT(count == 0);
        return first == nullptr;
      }
 
      GAIA_NODISCARD uint32_t size() const {
        return count;
      }
 
      fwd_llist_iterator<T> begin() {
        return fwd_llist_iterator<T>(first);
      }
 
      fwd_llist_iterator<const T> begin() const {
        return fwd_llist_iterator((const T*)first);
      }
 
      fwd_llist_iterator<const T> cbegin() const {
        return fwd_llist_iterator((const T*)first);
      }
 
      fwd_llist_iterator<T> end() {
        return fwd_llist_iterator<T>(nullptr);
      }
 
      fwd_llist_iterator<const T> end() const {
        return fwd_llist_iterator((const T*)nullptr);
      }
 
      fwd_llist_iterator<const T> cend() const {
        return fwd_llist_iterator((const T*)nullptr);
      }
    };
  } // namespace cnt
} // namespace gaia