lists.h

Go to the documentation of this file.

/*
 * This file is part of the µOS++ distribution.
 *   (https://github.com/micro-os-plus)
 * Copyright (c) 2016-2023 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_ */