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 Liviu Ionescu.
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom
 * the Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef CMSIS_PLUS_UTILS_LISTS_H_
#define CMSIS_PLUS_UTILS_LISTS_H_

// ----------------------------------------------------------------------------

#ifdef  __cplusplus

#include <cstdint>
#include <cstddef>
#include <cassert>
#include <iterator>

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 ()
    {
      ;
    }

    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 ()));
      }

    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_)) };
      }

    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 */

// ----------------------------------------------------------------------------

#endif /* __cplusplus */

#endif /* CMSIS_PLUS_RTOS_INTERNAL_OS_LISTS_H_ */