lists.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.
 */
 
/*
 * This library implements several doubly linked lists, used by some
 * µOS++ components to keep track of internal objects; however it is
 * generic enough to be useful in other applications too, thus packing
 * it as a separate library.
 *
 * The main differentiator from `std::list` is that the implementation
 * does not require dynamic memory allocation for the list links,
 * hence it does not need an allocator.
 *
 * Instead, it uses intrusive lists, which store the links inside the
 * list elements.
 *
 * Another specific feature is statically initialised lists.
 *
 * These are lists created in the global scope which do not change the
 * content of any of their members in the constructors; instead,
 * they are fully initialized by setting the entire content to zero
 * during startup (via BSS init).
 *
 * This allows other static objects to auto-register themselves to
 * static registrar objects. This requires the registrar to be
 * initialised before the clients need to register; since the order
 * of static constructors is not defined, the only solution that
 * guarantees this is to initialize the registrar during startup
 * (via BSS init) before the static constructors.
 */
 
#ifndef MICRO_OS_PLUS_UTILS_LISTS_H_
#define MICRO_OS_PLUS_UTILS_LISTS_H_
 
// ----------------------------------------------------------------------------
 
#ifdef __cplusplus
 
// ----------------------------------------------------------------------------
 
#if defined(MICRO_OS_PLUS_INCLUDE_CONFIG_H)
#include <micro-os-plus/config.h>
#endif // MICRO_OS_PLUS_INCLUDE_CONFIG_H
 
#include <cstdint>
#include <cstddef>
#include <cassert>
#include <iterator>
 
// ----------------------------------------------------------------------------
 
#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
{
  // ==========================================================================

  class double_list_links_base
  {
  public:
    constexpr double_list_links_base ();

 
    // The rule of five.
    double_list_links_base (const double_list_links_base&) = delete;
    double_list_links_base (double_list_links_base&&) = delete;
    double_list_links_base&
    operator= (const double_list_links_base&)
        = delete;
    double_list_links_base&
    operator= (double_list_links_base&&)
        = delete;


    constexpr ~double_list_links_base ();

    bool
    uninitialized (void) const;

    constexpr void
    initialize (void);

    void
    initialize_once (void);

    void
    link_next (double_list_links_base* node);

    void
    link_previous (double_list_links_base* node);

    void
    unlink (void);

    bool
    linked (void) const;

    constexpr double_list_links_base*
    next (void) const;

    constexpr double_list_links_base*
    previous (void) const;
 
  protected:
    double_list_links_base* previous_;

    double_list_links_base* next_;
  };
 
  // ==========================================================================

  class double_list_links : public double_list_links_base
  {
  public:
    using is_statically_allocated = std::false_type;

    constexpr double_list_links ();

 
    // The rule of five.
    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;


    constexpr ~double_list_links ();
  };
 
  // ==========================================================================

  class static_double_list_links : public double_list_links_base
  {
  public:
    using is_statically_allocated = std::true_type;

    constexpr static_double_list_links ();

 
    // The rule of five.
    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;


    constexpr ~static_double_list_links ();

    void
    nullify (void);
  };
 
  // ==========================================================================

  template <class T, class N = T, class U = T>
  class double_list_iterator
  {
  public:
    using value_type = U;

    using pointer = value_type*;

    using reference = value_type&;

    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);
 
    // DO NOT delete the copy constructors, since the default ones are
    // used.
 
    constexpr pointer
    operator->() const;
 
    constexpr reference
    operator* () const;
 
    constexpr double_list_iterator&
    operator++ ();
 
    constexpr double_list_iterator
    operator++ (int);
 
    constexpr double_list_iterator&
    operator-- ();
 
    constexpr double_list_iterator
    operator-- (int);
 
    constexpr bool
    operator== (const double_list_iterator& other) const;
 
    constexpr bool
    operator!= (const double_list_iterator& other) const;
 
    constexpr pointer
    get_pointer () const;
 
    constexpr iterator_pointer
    get_iterator_pointer () const;
 
  protected:
    iterator_pointer node_;
  };
 
  // ==========================================================================

  template <class T, class L = double_list_links>
  class double_list
  {
  public:
    static_assert (std::is_base_of<double_list_links_base, L>::value == true,
                   "L must be derived from double_list_links_base!");
    static_assert (std::is_base_of<double_list_links_base, T>::value == true,
                   "T must be derived from double_list_links_base!");

    using links_type = L;

    using value_type = T;

    using pointer = value_type*;

    using reference = value_type&;

    using iterator = double_list_iterator<value_type>;

    using iterator_pointer = value_type*;

    using is_statically_allocated =
        typename links_type::is_statically_allocated;

    double_list ();

 
    // The rule of five.
    double_list (const double_list&) = delete;
    double_list (double_list&&) = delete;
    double_list&
    operator= (const double_list&)
        = delete;
    double_list&
    operator= (double_list&&)
        = delete;


    constexpr ~double_list ();
 
  public:
    bool
    uninitialized (void) const;

    void
    initialize_once (void);

    bool
    empty (void) const;

    void
    clear (void);

    constexpr pointer
    head (void) const;

    constexpr pointer
    tail (void) const;

    void
    link_tail (reference node);

    void
    link_head (reference node);
 
    // ------------------------------------------------------------------------

    iterator
    begin () const;

    iterator
    end () const;
 
    // Required in derived class iterator end(), where direct
    // access to member fails.
    constexpr const links_type*
    links_pointer () const
    {
      return &links_;
    }
 
    // ------------------------------------------------------------------------
 
  protected:
    links_type links_;
  };
 
  // ==========================================================================

  template <class T, class N, N T::*MP, class U = T>
  class intrusive_list_iterator
  {
  public:
    using value_type = U;

    using pointer = value_type*;

    using reference = value_type&;

    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);
 
    // DO NOT delete the copy constructors, since the default ones are
    // used.
 
    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_;
  };
 
  // ==========================================================================
 
#if defined(__clang__)
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wdocumentation"
#endif
#if defined(__clang__)
#pragma clang diagnostic pop
#endif
 
  template <class T, class N, N T::*MP, class L = double_list_links,
            class U = T>
  class intrusive_list : public double_list<N, L>
  {
  public:
    static_assert (std::is_base_of<double_list_links_base, L>::value == true,
                   "L must be derived from double_list_links_base!");
    static_assert (std::is_base_of<double_list_links_base, N>::value == true,
                   "N must be derived from double_list_links_base!");

    using links_type = L;

    using value_type = U;

    using pointer = value_type*;

    using reference = value_type&;

    using iterator = intrusive_list_iterator<T, N, MP, U>;

    using is_statically_allocated =
        typename links_type::is_statically_allocated;

    using iterator_pointer = N*;

    using difference_type = ptrdiff_t;

    constexpr intrusive_list ();

 
    // The rule of five.
    intrusive_list (const intrusive_list&) = delete;
    intrusive_list (intrusive_list&&) = delete;
    intrusive_list&
    operator= (const intrusive_list&)
        = delete;
    intrusive_list&
    operator= (intrusive_list&&)
        = delete;


    constexpr ~intrusive_list ();
 
  public:
    void
    initialize_once (void);

    constexpr bool
    empty (void) const;

    void
    link_tail (reference node);

    void
    link_head (reference node);

    pointer
    unlink_tail (void);

    pointer
    unlink_head (void);
 
    // ------------------------------------------------------------------------

    iterator
    begin () const;

    iterator
    end () const;
 
    // ------------------------------------------------------------------------
  protected:
    pointer
    get_pointer (iterator_pointer node) const;
  };
 
  // --------------------------------------------------------------------------
} // namespace micro_os_plus::utils
 
#if defined(__GNUC__)
#pragma GCC diagnostic pop
#endif
 
// ----------------------------------------------------------------------------
 
#endif // __cplusplus
 
// ===== Inline & template implementations ====================================
 
// All other inlines.
#include "inlines.h"
 
// ----------------------------------------------------------------------------
 
#endif // MICRO_OS_PLUS_UTILS_LISTS_H_
 
// ----------------------------------------------------------------------------