lists.h

Go to the documentation of this file.

/*
 * This file is part of the µOS++ project (https://micro-os-plus.github.io/).
 * Copyright (c) 2016-2025 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 CMSIS_PLUS_UTILS_LISTS_H_
#define CMSIS_PLUS_UTILS_LISTS_H_
 
// ----------------------------------------------------------------------------
 
#ifdef __cplusplus
 
// ----------------------------------------------------------------------------
 
#include <cstdint>
#include <cstddef>
#include <cassert>
#include <iterator>
 
// ----------------------------------------------------------------------------
 
#pragma GCC diagnostic push
#if defined(__clang__)
#pragma clang diagnostic ignored "-Wc++98-compat"
#endif
 
// ----------------------------------------------------------------------------
 
namespace os
{
  namespace utils
  {
    // ========================================================================
 
    class static_double_list_links
    {
    public:
      static_double_list_links ();
 
      static_double_list_links (const static_double_list_links&) = delete;
      static_double_list_links (static_double_list_links&&) = delete;
      static_double_list_links&
      operator= (const static_double_list_links&)
          = delete;
      static_double_list_links&
      operator= (static_double_list_links&&)
          = delete;
 
      ~static_double_list_links ();
 
      void
      unlink (void);
 
      bool
      unlinked (void);
 
      static_double_list_links*
      next (void) const;
 
      static_double_list_links*
      prev (void) const;
 
      void
      next (static_double_list_links* n);
 
      void
      prev (static_double_list_links* n);
 
    protected:
      static_double_list_links* prev_;
 
      static_double_list_links* next_;
 
    };
 
    // ========================================================================
 
    class double_list_links : public static_double_list_links
    {
    public:
      double_list_links ();
 
      double_list_links (const double_list_links&) = delete;
      double_list_links (double_list_links&&) = delete;
      double_list_links&
      operator= (const double_list_links&)
          = delete;
      double_list_links&
      operator= (double_list_links&&)
          = delete;
 
      ~double_list_links ();
 
    };
 
    // ========================================================================
 
    template <typename T, typename N, T* N::* MP, typename U = T>
    class double_list_iterator
    {
    public:
      using value_type = U;
 
      using pointer = U*;
 
      using reference = U&;
 
      using iterator_pointer = N*;
 
      using difference_type = ptrdiff_t;
 
      using iterator_category = std::forward_iterator_tag;
 
      // ----------------------------------------------------------------------
      constexpr double_list_iterator ();
 
      constexpr explicit double_list_iterator (iterator_pointer const node);
 
      constexpr explicit double_list_iterator (reference element);
 
      pointer
      operator->() const;
 
      reference
      operator* () const;
 
      double_list_iterator&
      operator++ ();
 
      double_list_iterator
      operator++ (int);
 
      double_list_iterator&
      operator-- ();
 
      double_list_iterator
      operator-- (int);
 
      bool
      operator== (const double_list_iterator& other) const;
 
      bool
      operator!= (const double_list_iterator& other) const;
 
      pointer
      get_pointer (void) const;
 
      iterator_pointer
      get_iterator_pointer () const;
 
    protected:
      iterator_pointer node_;
 
    };
 
    // ========================================================================
 
    class static_double_list
    {
    public:
      static_double_list ();
 
      static_double_list (const static_double_list&) = delete;
      static_double_list (static_double_list&&) = delete;
      static_double_list&
      operator= (const static_double_list&)
          = delete;
      static_double_list&
      operator= (static_double_list&&)
          = delete;
 
      ~static_double_list ();
 
    public:
      bool
      uninitialized (void) const;
 
      void
      clear (void);
 
      bool
      empty (void) const;
 
      // TODO add iterator begin(), end()
 
      volatile static_double_list_links*
      head (void) const;
 
      volatile static_double_list_links*
      tail (void) const;
 
    protected:
      void
      insert_after (static_double_list_links& node,
                    static_double_list_links* after);
 
    protected:
      static_double_list_links head_;
 
    };
 
    // ========================================================================
 
    class double_list : public static_double_list
    {
    public:
      double_list ();
 
      double_list (const double_list&) = delete;
      double_list (double_list&&) = delete;
      double_list&
      operator= (const double_list&)
          = delete;
      double_list&
      operator= (double_list&&)
          = delete;
 
      ~double_list ();
 
    };
 
    // ========================================================================
 
    template <typename T, typename N, N T::* MP, typename U = T>
    class intrusive_list_iterator
    {
    public:
      using value_type = U;
 
      using pointer = U*;
 
      using reference = U&;
 
      using iterator_pointer = N*;
 
      using difference_type = ptrdiff_t;
 
      using iterator_category = std::forward_iterator_tag;
 
      // ----------------------------------------------------------------------
      constexpr intrusive_list_iterator ();
 
      constexpr explicit intrusive_list_iterator (iterator_pointer const node);
 
      constexpr explicit intrusive_list_iterator (reference element);
 
      pointer
      operator->() const;
 
      reference
      operator* () const;
 
      intrusive_list_iterator&
      operator++ ();
 
      intrusive_list_iterator
      operator++ (int);
 
      intrusive_list_iterator&
      operator-- ();
 
      intrusive_list_iterator
      operator-- (int);
 
      bool
      operator== (const intrusive_list_iterator& other) const;
 
      bool
      operator!= (const intrusive_list_iterator& other) const;
 
      pointer
      get_pointer (void) const;
 
      iterator_pointer
      get_iterator_pointer () const;
 
    protected:
      iterator_pointer node_;
 
    };
 
    // ========================================================================
 
    template <typename T, typename N, N T::* MP, typename U = T>
    class intrusive_list : public static_double_list
    {
    public:
      using value_type = U;
      using pointer = U*;
      using reference = U&;
      using difference_type = ptrdiff_t;
 
      using iterator = intrusive_list_iterator<T, N, MP, U>;
 
      using iterator_pointer = N*;
 
      intrusive_list ();
 
      intrusive_list (bool clr);
 
      intrusive_list (const intrusive_list&) = delete;
      intrusive_list (intrusive_list&&) = delete;
      intrusive_list&
      operator= (const intrusive_list&)
          = delete;
      intrusive_list&
      operator= (intrusive_list&&)
          = delete;
 
      ~intrusive_list ();
 
    protected:
      pointer
      get_pointer (iterator_pointer node) const;
 
    public:
      void
      link (reference node);
 
      iterator
      begin ();
 
      iterator
      end () const;
 
      pointer
      unlink_head (void);
 
      pointer
      unlink_tail (void);
 
    };
 
    // ------------------------------------------------------------------------
  } /* namespace utils */
} /* namespace os */
 
// ----------------------------------------------------------------------------
 
namespace os
{
  namespace utils
  {
    // ========================================================================
 
    // Code analysis may trigger:
    // "Member 'prev' was not initialized in constructor"
    // "Member 'next' was not initialized in constructor"
 
    inline static_double_list_links::static_double_list_links ()
    {
    }
 
    inline static_double_list_links::~static_double_list_links ()
    {
      // Revert the content to a state similar to the statically initialised
      // state (BSS zero).
      // Unfortunately GCC removes this code as part of
      // _dead store elimination_.
      // next_ = nullptr;
      // prev_ = nullptr;
    }
 
    inline bool
    static_double_list_links::unlinked (void)
    {
      return (next_ == nullptr);
    }
 
    inline static_double_list_links*
    static_double_list_links::next (void) const
    {
      return next_;
    }
 
    inline static_double_list_links*
    static_double_list_links::prev (void) const
    {
      return prev_;
    }
 
    inline void
    static_double_list_links::next (static_double_list_links* n)
    {
      next_ = n;
    }
 
    inline void
    static_double_list_links::prev (static_double_list_links* n)
    {
      prev_ = n;
    }
 
    // ========================================================================
 
    inline double_list_links::double_list_links ()
    {
      prev_ = nullptr;
      next_ = nullptr;
    }
 
    inline double_list_links::~double_list_links ()
    {
    }
 
    // ========================================================================
    template <typename T, typename N, T* N::* MP, typename U>
    constexpr double_list_iterator<T, N, MP, U>::double_list_iterator ()
        : node_{}
    {
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    constexpr double_list_iterator<T, N, MP, U>::double_list_iterator (
        iterator_pointer const node)
        : node_{ node }
    {
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    constexpr double_list_iterator<T, N, MP, 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!");
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    inline typename double_list_iterator<T, N, MP, U>::pointer
    double_list_iterator<T, N, MP, U>::operator->() const
    {
      return get_pointer ();
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    inline typename double_list_iterator<T, N, MP, U>::reference
    double_list_iterator<T, N, MP, U>::operator* () const
    {
      return *get_pointer ();
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    inline double_list_iterator<T, N, MP, U>&
    double_list_iterator<T, N, MP, U>::operator++ ()
    {
      node_ = static_cast<N*> (node_->next ());
      return *this;
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    inline double_list_iterator<T, N, MP, U>
    double_list_iterator<T, N, MP, U>::operator++ (int)
    {
      const auto tmp = *this;
      node_ = static_cast<iterator_pointer> (node_->next);
      return tmp;
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    inline double_list_iterator<T, N, MP, U>&
    double_list_iterator<T, N, MP, U>::operator-- ()
    {
      node_ = static_cast<iterator_pointer> (node_->prev);
      return *this;
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    double_list_iterator<T, N, MP, U>
    double_list_iterator<T, N, MP, U>::operator-- (int)
    {
      const auto tmp = *this;
      node_ = static_cast<iterator_pointer> (node_->prev);
      return tmp;
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    inline bool
    double_list_iterator<T, N, MP, U>::operator== (
        const double_list_iterator& other) const
    {
      return node_ == other.node_;
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    inline bool
    double_list_iterator<T, N, MP, U>::operator!= (
        const double_list_iterator& other) const
    {
      return node_ != other.node_;
    }
 
#if 1
    template <typename T, typename N, T* N::* MP, typename U>
    inline typename double_list_iterator<T, N, MP, U>::pointer
    double_list_iterator<T, N, MP, U>::get_pointer (void) const
    {
      return (node_->*MP);
    }
 
    template <typename T, typename N, T* N::* MP, typename U>
    inline typename double_list_iterator<T, N, MP, U>::iterator_pointer
    double_list_iterator<T, N, MP, U>::get_iterator_pointer () const
    {
      return node_;
    }
#endif
 
    // ========================================================================
 
    inline static_double_list::static_double_list ()
    {
      // By all means, do not add any code here.
      // The constructor was not `default` to benefit from inline.
    }
 
    inline static_double_list::~static_double_list ()
    {
    }
 
    inline bool
    static_double_list::uninitialized (void) const
    {
      // If it points to nowhere, it is not yet initialised.
      return (head_.prev () == nullptr);
    }
 
    inline bool
    static_double_list::empty (void) const
    {
      // If it points to itself, it is empty.
      return (head_.next () == &head_) || (head_.next () == nullptr);
    }
 
    inline volatile static_double_list_links*
    static_double_list::head (void) const
    {
      return static_cast<volatile static_double_list_links*> (head_.next ());
    }
 
    inline volatile static_double_list_links*
    static_double_list::tail (void) const
    {
      return (head_.prev ());
    }
 
    // ========================================================================
 
    template <typename T, typename N, N T::* MP, typename U>
    constexpr intrusive_list_iterator<T, N, MP, U>::intrusive_list_iterator ()
        : node_{}
    {
    }
 
    template <typename T, typename N, N T::* MP, typename U>
    constexpr intrusive_list_iterator<T, N, MP, U>::intrusive_list_iterator (
        N* const node)
        : node_{ node }
    {
    }
 
    template <typename T, typename N, N T::* MP, typename 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 <typename T, typename N, N T::* MP, typename U>
    inline typename intrusive_list_iterator<T, N, MP, U>::pointer
    intrusive_list_iterator<T, N, MP, U>::operator->() const
    {
      return get_pointer ();
    }
 
    template <typename T, typename N, N T::* MP, typename U>
    inline typename intrusive_list_iterator<T, N, MP, U>::reference
    intrusive_list_iterator<T, N, MP, U>::operator* () const
    {
      return *get_pointer ();
    }
 
    template <typename T, typename N, N T::* MP, typename 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;
    }
 
    template <typename T, typename N, N T::* MP, typename 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 <typename T, typename N, N T::* MP, typename U>
    inline intrusive_list_iterator<T, N, MP, U>&
    intrusive_list_iterator<T, N, MP, U>::operator-- ()
    {
      node_ = static_cast<iterator_pointer> (node_->prev ());
      return *this;
    }
 
    template <typename T, typename N, N T::* MP, typename 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_->prev ());
      return tmp;
    }
 
    template <typename T, typename N, N T::* MP, typename U>
    inline bool
    intrusive_list_iterator<T, N, MP, U>::operator== (
        const intrusive_list_iterator& other) const
    {
      return node_ == other.node_;
    }
 
    template <typename T, typename N, N T::* MP, typename U>
    inline bool
    intrusive_list_iterator<T, N, MP, U>::operator!= (
        const intrusive_list_iterator& other) const
    {
      return node_ != other.node_;
    }
 
    template <typename T, typename N, N T::* MP, typename 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 <typename T, typename N, N T::* MP, typename 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 <typename T, typename N, N T::* MP, typename U>
    inline intrusive_list<T, N, MP, U>::intrusive_list ()
    {
    }
 
    template <typename T, typename N, N T::* MP, typename U>
    inline intrusive_list<T, N, MP, U>::intrusive_list (bool clr)
    {
      if (clr)
        {
          clear ();
        }
    }
 
    template <typename T, typename N, N T::* MP, typename U>
    inline intrusive_list<T, N, MP, U>::~intrusive_list ()
    {
    }
 
    template <typename T, typename N, N T::* MP, typename U>
    void
    intrusive_list<T, N, MP, U>::link (U& node)
    {
      if (uninitialized ())
        {
          // If this is the first time, initialise the list to empty.
          clear ();
        }
 
      // 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.
      insert_after (*reinterpret_cast<static_double_list_links*> (
                        reinterpret_cast<difference_type> (&node) + offset),
                    const_cast<static_double_list_links*> (tail ()));
    }
 
#pragma GCC diagnostic push
#if defined(__clang__)
#elif defined(__GNUC__)
#pragma GCC diagnostic ignored "-Waggregate-return"
#endif
 
    template <typename T, typename N, N T::* MP, typename U>
    inline typename intrusive_list<T, N, MP, U>::iterator
    intrusive_list<T, N, MP, U>::begin ()
    {
      if (uninitialized ())
        {
          // If this is the first time, initialise the list to empty.
          clear ();
        }
      return iterator{ static_cast<iterator_pointer> (head_.next ()) };
    }
 
    template <typename T, typename N, N T::* MP, typename U>
    inline typename intrusive_list<T, N, MP, U>::iterator
    intrusive_list<T, N, MP, U>::end () const
    {
      return iterator{ static_cast<iterator_pointer> (
          const_cast<static_double_list_links*> (&head_)) };
    }
 
#pragma GCC diagnostic pop
 
    template <typename T, typename N, N T::* MP, typename U>
    inline typename intrusive_list<T, N, MP, U>::pointer
    intrusive_list<T, N, MP, 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 <typename T, typename N, N T::* MP, typename U>
    typename intrusive_list<T, N, MP, U>::pointer
    intrusive_list<T, N, MP, U>::unlink_head (void)
    {
      assert (!empty ());
 
      // The first element in the list.
      iterator_pointer link = static_cast<iterator_pointer> (head_.next ());
      link->unlink ();
 
      return get_pointer (link);
    }
 
    template <typename T, typename N, N T::* MP, typename U>
    typename intrusive_list<T, N, MP, U>::pointer
    intrusive_list<T, N, MP, U>::unlink_tail (void)
    {
      assert (!empty ());
 
      // The last element in the list.
      iterator_pointer link = static_cast<iterator_pointer> (head_.prev ());
      link->unlink ();
 
      return get_pointer (link);
    }
 
  } /* namespace utils */
} /* namespace os */
 
#pragma GCC diagnostic pop
 
// ----------------------------------------------------------------------------
 
#endif /* __cplusplus */
 
// ----------------------------------------------------------------------------
 
#endif /* CMSIS_PLUS_RTOS_INTERNAL_OS_LISTS_H_ */