lists-inlines.h

Go to the documentation of this file.

/*
 * This file is part of the µOS++ project (https://micro-os-plus.github.com/).
 * Copyright (c) 2016 Liviu Ionescu. All rights reserved.
 *
 * Permission to use, copy, modify, and/or distribute this software
 * for any purpose is hereby granted, under the terms of the MIT license.
 *
 * If a copy of the license was not distributed with this file, it can
 * be obtained from https://opensource.org/licenses/mit.
 */

 
#ifndef MICRO_OS_PLUS_UTILS_LISTS_INLINES_H_
#define MICRO_OS_PLUS_UTILS_LISTS_INLINES_H_
 
// ----------------------------------------------------------------------------
 
#ifdef __cplusplus
 
// ----------------------------------------------------------------------------
 
#if defined(__GNUC__)
#pragma GCC diagnostic push
 
#pragma GCC diagnostic ignored "-Waggregate-return"
#if defined(__clang__)
#pragma clang diagnostic ignored "-Wc++98-compat"
#endif
#endif
 
// ----------------------------------------------------------------------------
 
namespace micro_os_plus::utils
{
  // ==========================================================================

  constexpr double_list_links_base::double_list_links_base ()
  {
    // Must be empty! No members must be changed by this constructor!
  }

  constexpr double_list_links_base::~double_list_links_base ()
  {
    // Must be empty! No members must be changed by this constructor!
  }

  constexpr void
  double_list_links_base::initialize (void)
  {
    previous_ = this;
    next_ = this;
  }
 
#pragma GCC diagnostic push
 
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif

  constexpr double_list_links_base*
  double_list_links_base::next (void) const
  {
    return next_;
  }

  constexpr double_list_links_base*
  double_list_links_base::previous (void) const
  {
    return previous_;
  }
 
#pragma GCC diagnostic pop
 
  // ==========================================================================

  constexpr static_double_list_links::static_double_list_links ()
  {
    // Must be empty! No members must be changed by this constructor!
  }
 
#pragma GCC diagnostic push
 
#if defined(__clang__)
#pragma GCC diagnostic ignored "-Wdocumentation-unknown-command"
#endif
#pragma GCC diagnostic pop
  constexpr static_double_list_links::~static_double_list_links ()
  {
    // The goal is to revert the content to a state similar to the
    // statically initialised state (BSS zero).
    // Unfortunately GCC does not honour this.
    // next_ = nullptr;
    // previous_ = nullptr;
  }
 
  // ==========================================================================

  constexpr double_list_links::double_list_links ()
  {
    // For regular (non static) classes the members
    // must be explicitly initialised.
    initialize ();
  }

  constexpr double_list_links::~double_list_links ()
  {
  }
 
  // ==========================================================================

  template <class T, class N, class U>
  constexpr double_list_iterator<T, N, U>::double_list_iterator () : node_{}
  {
  }

  template <class T, class N, class U>
  constexpr double_list_iterator<T, N, U>::double_list_iterator (
      iterator_pointer const node)
      : node_{ node }
  {
  }
 
#if 0
    template <class T, class N, class U>
    constexpr double_list_iterator<T, N, U>::double_list_iterator (
        reference element)
        : node_{ &(element.*MP) }
    {
      static_assert (std::is_convertible<U, T>::value == true,
                     "U must be implicitly convertible to T!");
    }
#endif

  template <class T, class N, class U>
  constexpr typename double_list_iterator<T, N, U>::pointer
  double_list_iterator<T, N, U>::operator->() const
  {
    return get_pointer ();
  }

  template <class T, class N, class U>
  constexpr typename double_list_iterator<T, N, U>::reference
  double_list_iterator<T, N, U>::operator* () const
  {
    return *get_pointer ();
  }

  template <class T, class N, class U>
  constexpr double_list_iterator<T, N, U>&
  double_list_iterator<T, N, U>::operator++ ()
  {
    node_ = static_cast<N*> (node_->next ());
    return *this;
  }

  template <class T, class N, class U>
  constexpr double_list_iterator<T, N, U>
  double_list_iterator<T, N, U>::operator++ (int)
  {
    const auto tmp = *this;
    node_ = static_cast<iterator_pointer> (node_->next);
    return tmp;
  }

  template <class T, class N, class U>
  constexpr double_list_iterator<T, N, U>&
  double_list_iterator<T, N, U>::operator-- ()
  {
    node_ = static_cast<iterator_pointer> (node_->previous);
    return *this;
  }

  template <class T, class N, class U>
  constexpr double_list_iterator<T, N, U>
  double_list_iterator<T, N, U>::operator-- (int)
  {
    const auto tmp = *this;
    node_ = static_cast<iterator_pointer> (node_->previous);
    return tmp;
  }

  template <class T, class N, class U>
  constexpr bool
  double_list_iterator<T, N, U>::operator== (
      const double_list_iterator& other) const
  {
    return node_ == other.node_;
  }

  template <class T, class N, class U>
  constexpr bool
  double_list_iterator<T, N, U>::operator!= (
      const double_list_iterator& other) const
  {
    return node_ != other.node_;
  }

  template <class T, class N, class U>
  constexpr typename double_list_iterator<T, N, U>::iterator_pointer
  double_list_iterator<T, N, U>::get_iterator_pointer () const
  {
    return node_;
  }
 
  // ==========================================================================

  template <class T, class L>
  double_list<T, L>::double_list ()
  {
#if defined(MICRO_OS_PLUS_TRACE_UTILS_LISTS_CONSTRUCT)
    trace::printf ("%s() @%p \n", __func__, this);
#endif
 
    if constexpr (is_statically_allocated::value)
      {
        // By all means, do not add any code to clear the pointers, since
        // the links node was statically initialised.
      }
    else
      {
        clear ();
      }
  }

  template <class T, class L>
  constexpr double_list<T, L>::~double_list ()
  {
#if defined(MICRO_OS_PLUS_TRACE_UTILS_LISTS_CONSTRUCT)
    trace::printf ("%s() @%p \n", __func__, this);
#endif
 
    // Perhaps enable it for non statically allocated lists.
    // assert (empty ());
#if defined(MICRO_OS_PLUS_TRACE_UTILS_LISTS)
    if (!empty ())
      {
        trace::printf ("%s() @%p list not empty\n", __func__, this);
      }
#endif
  }

   * Only statically allocated nodes in the initial state are considered
   * _uninitialized_. For dynamically allocated lists, this method always
   * returns `false` since their nodes are explicitly initialized during
   * construction.
   */
  template <class T, class L>
  bool
  double_list<T, L>::uninitialized (void) const
  {
    if constexpr (is_statically_allocated::value)
      {
        return links_.uninitialized ();
      }
    else
      {
        return false;
      }
  }

  /**
   * @details
   * If the statically allocated list is still in the initial
   * _uninitialised_ state (with both pointers null), this method
   * initialises the list to the empty state, with both pointers
   * pointing to itself. For non-statically initialised lists,
   * this method has no effect.
   *
   * @note
   * Must be manually called for statically allocated lists before
   * inserting elements or performing any other operations.
   */
  template <class T, class L>
  void
  double_list<T, L>::initialize_once (void)
  {
    if constexpr (is_statically_allocated::value)
      {
        links_.initialize_once ();
      }
  }

   * Checks whether the list contains any nodes.
   * The list is considered empty if the internal links node is not linked to
   * any other nodes. This method provides a fast way to determine if the list
   * has elements or is currently empty.
   */
  template <class T, class L>
  bool
  double_list<T, L>::empty (void) const
  {
    // If the links node is not linked, the list is empty.
    return !links_.linked ();
  }

   * both its `previous_` and `next_` pointers refer to itself. This marks the
   * list as empty and ensures it is in a safe, known state, ready for new
   * insertions. This operation is typically used to reset the list, removing
   * all elements and breaking any existing links.
   */
  template <class T, class L>
  void
  double_list<T, L>::clear (void)
  {
#if defined(MICRO_OS_PLUS_TRACE_UTILS_LISTS)
    trace::printf ("%s() @%p\n", __func__, this);
#endif
    links_.initialize ();
  }

   * The returned pointer should be checked against `end()` or the sentinel
   * node to determine if the list contains any elements.
   */
  template <class T, class L>
  constexpr typename double_list<T, L>::pointer
  double_list<T, L>::head (void) const
  {
    return reinterpret_cast<pointer> (links_.next ());
  }

  template <class T, class L>
  constexpr typename double_list<T, L>::pointer
  double_list<T, L>::tail (void) const
  {
    return reinterpret_cast<pointer> (links_.previous ());
  }

  template <class T, class L>
  void
  double_list<T, L>::link_tail (reference node)
  {
    if constexpr (is_statically_allocated::value)
      {
        assert (!links_.uninitialized ());
      }
 
    // Add new node at the end of the list.
    tail ()->link_next (&node);
  }

  template <class T, class L>
  void
  double_list<T, L>::link_head (reference node)
  {
    if constexpr (is_statically_allocated::value)
      {
        assert (!links_.uninitialized ());
      }
 
    // Add the new node at the head of the list.
    head ()->link_previous (&node);
  }

  template <class T, class L>
  typename double_list<T, L>::iterator
  double_list<T, L>::begin () const
  {
    if constexpr (is_statically_allocated::value)
      {
        assert (!links_.uninitialized ());
      }
 
    return iterator{ static_cast<iterator_pointer> (links_.next ()) };
  }

  template <class T, class L>
  typename double_list<T, L>::iterator
  double_list<T, L>::end () const
  {
    // The assert would probably be redundant, since it was
    // already tested in `begin()`.
 
    return iterator{ reinterpret_cast<iterator_pointer> (
        const_cast<links_type*> (&links_)) };
  }
 
  // ==========================================================================

  /**
   * @details
   * The default constructor for `intrusive_list_iterator` initialises the
   * iterator to a null state, meaning it does not point to any node in the
   * list. This is typically used to create an "end" iterator or to initialise
   * an iterator variable before assigning it to a valid node.
   *
   * @note
   * The internal node pointer is value-initialised (set to `nullptr`),
   * ensuring that the iterator is safe to use in comparisons and will not
   * dereference an invalid address.
   */
  template <class T, class N, N T::* MP, class U>
  constexpr intrusive_list_iterator<T, N, MP, U>::intrusive_list_iterator ()
      : node_{}
  {
  }

  template <class T, class N, N T::* MP, class U>
  constexpr intrusive_list_iterator<T, N, MP, U>::intrusive_list_iterator (
      N* const node)
      : node_{ node }
  {
  }

  template <class T, class N, N T::* MP, class U>
  constexpr intrusive_list_iterator<T, N, MP, U>::intrusive_list_iterator (
      reference element)
      : node_{ &(element.*MP) }
  {
    static_assert (std::is_convertible<U, T>::value == true,
                   "U must be implicitly convertible to T!");
  }

  template <class T, class N, N T::* MP, class U>
  inline typename intrusive_list_iterator<T, N, MP, U>::pointer
  intrusive_list_iterator<T, N, MP, U>::operator->() const
  {
    return get_pointer ();
  }

   * This allows the iterator to be used in a manner similar to standard C++
   * iterators, enabling direct access to the list element for reading or
   * modification.
   */
  template <class T, class N, N T::* MP, class U>
  inline typename intrusive_list_iterator<T, N, MP, U>::reference
  intrusive_list_iterator<T, N, MP, U>::operator* () const
  {
    return *get_pointer ();
  }

  /**
   * @details
   * The pre-increment operator (`operator++`) advances the intrusive list
   * iterator to the next node in the list. It updates the internal node
   * pointer to point to the node returned by the current node's `next()`
   * method. This enables forward traversal of the list, following the linked
   * structure.
   */
  template <class T, class N, N T::* MP, class U>
  inline intrusive_list_iterator<T, N, MP, U>&
  intrusive_list_iterator<T, N, MP, U>::operator++ ()
  {
    node_ = static_cast<iterator_pointer> (node_->next ());
    return *this;
  }

   * requires access to the current element before moving to the next one,
   * following the standard C++ iterator semantics for post-increment.
   */
  template <class T, class N, N T::* MP, class U>
  inline intrusive_list_iterator<T, N, MP, U>
  intrusive_list_iterator<T, N, MP, U>::operator++ (int)
  {
    const auto tmp = *this;
    node_ = static_cast<iterator_pointer> (node_->next ());
    return tmp;
  }

  template <class T, class N, N T::* MP, class U>
  inline intrusive_list_iterator<T, N, MP, U>&
  intrusive_list_iterator<T, N, MP, U>::operator-- ()
  {
    node_ = static_cast<iterator_pointer> (node_->previous ());
    return *this;
  }

   * The post-decrement operator (`operator--(int)`) moves the intrusive list
   * iterator to the previous node in the list, but returns a copy of the
   * iterator as it was before the decrement. This enables iteration logic that
   * requires access to the current element before moving backward, following
   * the standard C++ iterator semantics for post-decrement.
   */
  template <class T, class N, N T::* MP, class U>
  intrusive_list_iterator<T, N, MP, U>
  intrusive_list_iterator<T, N, MP, U>::operator-- (int)
  {
    const auto tmp = *this;
    node_ = static_cast<iterator_pointer> (node_->previous ());
    return tmp;
  }

   * intrusive list iterators point to the same node in the list by comparing
   * their internal node pointers. This enables standard iterator comparisons,
   * such as detecting the end of a range or verifying if two iterators refer
   * to the same position within the list.
   */
  template <class T, class N, N T::* MP, class U>
  inline bool
  intrusive_list_iterator<T, N, MP, U>::operator== (
      const intrusive_list_iterator& other) const
  {
    return node_ == other.node_;
  }

  template <class T, class N, N T::* MP, class U>
  inline bool
  intrusive_list_iterator<T, N, MP, U>::operator!= (
      const intrusive_list_iterator& other) const
  {
    return node_ != other.node_;
  }

  template <class T, class N, N T::* MP, class U>
  inline typename intrusive_list_iterator<T, N, MP, U>::pointer
  intrusive_list_iterator<T, N, MP, U>::get_pointer (void) const
  {
    // static_assert(std::is_convertible<U, T>::value == true, "U must be
    // implicitly convertible to T!");
 
    // Compute the distance between the member intrusive link
    // node and the class begin.
    const auto offset = reinterpret_cast<difference_type> (
        &(static_cast<T*> (nullptr)->*MP));
 
    // Compute the address of the object which includes the
    // intrusive node, by adjusting down the node address.
    return reinterpret_cast<pointer> (reinterpret_cast<difference_type> (node_)
                                      - offset);
  }

  template <class T, class N, N T::* MP, class U>
  inline typename intrusive_list_iterator<T, N, MP, U>::iterator_pointer
  intrusive_list_iterator<T, N, MP, U>::get_iterator_pointer () const
  {
    return node_;
  }
 
  // ==========================================================================

  template <class T, class N, N T::* MP, class L, class U>
  constexpr intrusive_list<T, N, MP, L, U>::intrusive_list ()
  {
  }

   * The destructor for `intrusive_list` does not perform any cleanup or
   * pointer manipulation. List management and node unlinking are handled
   * elsewhere, so the destructor is intentionally left empty to avoid
   * unnecessary writes or side effects during object destruction.
   */
  template <class T, class N, N T::* MP, class L, class U>
  constexpr intrusive_list<T, N, MP, L, U>::~intrusive_list ()
  {
  }

   * initialised lists, this method has no effect.
   *
   * @note
   * Must be manually called for statically allocated lists before inserting
   * elements or performing any other operations.
   */
  template <class T, class N, N T::* MP, class L, class U>
  void
  intrusive_list<T, N, MP, L, U>::initialize_once (void)
  {
    return double_list<N, L>::initialize_once ();
  }

   */
  template <class T, class N, N T::* MP, class L, class U>
  constexpr bool
  intrusive_list<T, N, MP, L, U>::empty (void) const
  {
    return double_list<N, L>::empty ();
  }

  /**
   * @details
   * Adds a new node to the end (tail) of the intrusive list.
   * The offset of the intrusive node member within the containing object is
   * computed, and the node is linked after the current tail node. This
   * operation does not check for duplicate nodes or whether the node is
   * already linked elsewhere. For statically allocated lists, the
   * initialisation check is handled by the links class.
   */
  template <class T, class N, N T::* MP, class L, class U>
  void
  intrusive_list<T, N, MP, L, U>::link_tail (U& node)
  {
    // The assert(links_.initialised()) is checked by the L class.
 
    // Compute the distance between the member intrusive link
    // node and the class begin.
    const auto offset = reinterpret_cast<difference_type> (
        &(static_cast<T*> (nullptr)->*MP));
 
    // Add thread intrusive node at the end of the list.
    (const_cast<N*> (double_list<N, L>::tail ()))
        ->link_next (reinterpret_cast<N*> (
            reinterpret_cast<difference_type> (&node) + offset));
  }

   */
  template <class T, class N, N T::* MP, class L, class U>
  void
  intrusive_list<T, N, MP, L, U>::link_head (U& node)
  {
    // The assert(links_.initialised()) is checked by the L class.
 
    // Compute the distance between the member intrusive link
    // node and the class begin.
    const auto offset = reinterpret_cast<difference_type> (
        &(static_cast<T*> (nullptr)->*MP));
 
    // Add thread intrusive node at the end of the list.
    (const_cast<N*> (double_list<N, L>::head ()))
        ->link_previous (reinterpret_cast<N*> (
            reinterpret_cast<difference_type> (&node) + offset));
  }
 
#if defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Waggregate-return"
#endif

   * `end()`.
   */
  template <class T, class N, N T::* MP, class L, class U>
  inline typename intrusive_list<T, N, MP, L, U>::iterator
  intrusive_list<T, N, MP, L, U>::begin () const
  {
    // The assert(links_.initialised()) is checked by the L class.
 
    return iterator{ static_cast<iterator_pointer> (
        double_list<N, L>::links_.next ()) };
  }

  template <class T, class N, N T::* MP, class L, class U>
  inline typename intrusive_list<T, N, MP, L, U>::iterator
  intrusive_list<T, N, MP, L, U>::end () const
  {
    // The assert would probably be redundant, since it was
    // already tested in `begin()`.
 
    using head_type_ = typename double_list<N, L>::links_type;
    return iterator{ reinterpret_cast<iterator_pointer> (
        const_cast<head_type_*> (double_list<N, L>::links_pointer ())) };
  }
 
#if defined(__GNUC__)
#pragma GCC diagnostic pop
#endif

  template <class T, class N, N T::* MP, class L, class U>
  inline typename intrusive_list<T, N, MP, L, U>::pointer
  intrusive_list<T, N, MP, L, U>::get_pointer (iterator_pointer node) const
  {
    // static_assert(std::is_convertible<U, T>::value == true, "U must be
    // implicitly convertible to T!");
 
    // Compute the distance between the member intrusive link
    // node and the class begin.
    const auto offset = reinterpret_cast<difference_type> (
        &(static_cast<T*> (nullptr)->*MP));
 
    // Compute the address of the object which includes the
    // intrusive node, by adjusting down the node address.
    return reinterpret_cast<pointer> (reinterpret_cast<difference_type> (node)
                                      - offset);
  }

  template <class T, class N, N T::* MP, class L, class U>
  typename intrusive_list<T, N, MP, L, U>::pointer
  intrusive_list<T, N, MP, L, U>::unlink_head (void)
  {
    // No assert here, treat empty link unlinks as nop.
 
    // The first element in the list.
    iterator_pointer it
        = static_cast<iterator_pointer> (double_list<N, L>::links_.next ());
    it->unlink ();
 
    return get_pointer (it);
  }

  template <class T, class N, N T::* MP, class L, class U>
  typename intrusive_list<T, N, MP, L, U>::pointer
  intrusive_list<T, N, MP, L, U>::unlink_tail (void)
  {
    // No assert here, treat empty link unlinks as nop.
 
    // The last element in the list.
    iterator_pointer it = static_cast<iterator_pointer> (
        double_list<N, L>::links_.previous ());
    it->unlink ();
 
    return get_pointer (it);
  }
 
  // ==========================================================================
} // namespace micro_os_plus::utils
 
#if defined(__GNUC__)
#pragma GCC diagnostic pop
#endif
 
// ----------------------------------------------------------------------------
 
#endif // __cplusplus
 
// ----------------------------------------------------------------------------
 
#endif // MICRO_OS_PLUS_UTILS_LISTS_INLINES_H_
 
// ----------------------------------------------------------------------------