Skip to content

iceoryx_utils/cxx/forward_list.hpp🔗

Namespaces🔗

Name
iox
building block to easily create free function for logging in a library context
iox::cxx

Classes🔗

Name
class iox::cxx::forward_list
C++11 compatible uni-directional forward list implementation.

Source code🔗

// Copyright (c) 2020 by Robert Bosch GmbH. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// SPDX-License-Identifier: Apache-2.0

#ifndef IOX_UTILS_CXX_FORWARD_LIST_HPP
#define IOX_UTILS_CXX_FORWARD_LIST_HPP

#include <cstdint>
#include <iostream>

#include "iceoryx_utils/platform/platform_correction.hpp"

namespace iox
{
namespace cxx
{
template <typename T, uint64_t Capacity>
class forward_list
{
  private:
    // forward declarations, private
    struct ListLink;
    template <bool>
    class IteratorBase;

  public:
    using iterator = IteratorBase<false>;
    using const_iterator = IteratorBase<true>;
    using value_type = T;
    using size_type = decltype(Capacity);

    forward_list() noexcept;

    ~forward_list();

    forward_list(const forward_list& rhs) noexcept;

    forward_list(forward_list&& rhs) noexcept;

    forward_list& operator=(const forward_list& rhs) noexcept;

    forward_list& operator=(forward_list&& rhs) noexcept;

    iterator before_begin() noexcept;

    const_iterator before_begin() const noexcept;

    const_iterator cbefore_begin() const noexcept;

    iterator begin() noexcept;

    const_iterator begin() const noexcept;

    const_iterator cbegin() const noexcept;

    iterator end() noexcept;

    const_iterator end() const noexcept;

    const_iterator cend() const noexcept;

    bool empty() const noexcept;

    bool full() const noexcept;

    size_type size() const noexcept;

    size_type capacity() const noexcept;

    size_type max_size() const noexcept;

    T& front() noexcept;

    const T& front() const noexcept;

    bool push_front(const T& data) noexcept;

    bool push_front(T&& data) noexcept;

    bool pop_front() noexcept;

    void clear() noexcept;

    iterator erase_after(const_iterator beforeToBeErasedIter) noexcept;

    size_type remove(const T& data) noexcept;

    template <typename UnaryPredicate>
    size_type remove_if(UnaryPredicate pred) noexcept;

    template <typename... ConstructorArgs>
    T& emplace_front(ConstructorArgs&&... args) noexcept;

    template <typename... ConstructorArgs>
    iterator emplace_after(const_iterator afterToBeEmplacedIter, ConstructorArgs&&... args) noexcept;

    iterator insert_after(const_iterator citer, const T& data) noexcept;

    iterator insert_after(const_iterator citer, T&& data) noexcept;

  private:
    template <bool IsConstIterator = true>
    class IteratorBase
    {
      public:
        // provide the following public types for a std::iterator compatible iterator_category interface
        using iterator_category = std::forward_iterator_tag;
        using value_type = typename std::conditional<IsConstIterator, const T, T>::type;
        using difference_type = void;
        using pointer = typename std::conditional<IsConstIterator, const T*, T*>::type;
        using reference = typename std::conditional<IsConstIterator, const T&, T&>::type;


        IteratorBase(const IteratorBase<false>& iter) noexcept;

        IteratorBase& operator=(const IteratorBase<false>& rhs) noexcept;

        IteratorBase& operator++() noexcept;

        template <bool IsConstIteratorOther>
        bool operator==(const IteratorBase<IsConstIteratorOther>& rhs) const noexcept;

        template <bool IsConstIteratorOther>
        bool operator!=(const IteratorBase<IsConstIteratorOther>& rhs) const noexcept;

        reference operator*() const noexcept;

        pointer operator->() const noexcept;


      private:
        using parentListPointer = typename std::
            conditional<IsConstIterator, const forward_list<T, Capacity>*, forward_list<T, Capacity>*>::type;

        explicit IteratorBase(parentListPointer parent, size_type idx) noexcept;

        // Make IteratorBase<true> a friend class of IteratorBase<false> so the copy constructor can access the
        // private member variables.
        friend class IteratorBase<true>;
        friend class forward_list<T, Capacity>;
        parentListPointer m_list;
        size_type m_iterListNodeIdx;
    };

    struct NodeLink
    {
        size_type nextIdx;
        bool invalidElement;
    };

    void init() noexcept;
    T* getDataPtrFromIdx(const size_type idx) noexcept;
    const T* getDataPtrFromIdx(const size_type idx) const noexcept;

    bool isValidElementIdx(const size_type idx) const noexcept;
    bool handleInvalidElement(const size_type idx) const noexcept;
    bool handleInvalidIterator(const const_iterator& iter) const noexcept;
    bool isInvalidIterOrDifferentLists(const const_iterator& iter) const noexcept;
    bool isInvalidElement(const size_type idx) const noexcept;
    void setInvalidElement(const size_type idx, const bool value) noexcept;
    size_type& getNextIdx(const size_type idx) noexcept;
    const size_type& getNextIdx(const size_type idx) const noexcept;
    size_type& getNextIdx(const const_iterator& iter) noexcept;
    const size_type& getNextIdx(const const_iterator& iter) const noexcept;
    void setNextIdx(const size_type idx, const size_type nextIdx) noexcept;
    static void errorMessage(const char* source, const char* msg) noexcept;

    //***************************************
    //    members
    //***************************************

    // two extra slots in the list to handle the 'before_begin' and 'end' element
    // the necessity for 'before_begin' elements stems from the way a forward_list removes elements at an arbitrary
    // position. Removing the front-most list element (aka begin()) requires an element pointing towards this position,
    // hence 'before_begin'. The before_begin index is the head of the list.
    static constexpr size_type BEFORE_BEGIN_INDEX{Capacity};
    static constexpr size_type END_INDEX{size_type(Capacity) + 1U};
    static constexpr size_type NODE_LINK_COUNT{size_type(Capacity) + 2U};

    // available storage-indices are moved between a 'freeList' (m_freeListHeadIdx) and 'usedList' where elements
    // are inserted by the user (starting from BEFORE_BEGIN_INDEX)
    size_type m_freeListHeadIdx{0U};

    NodeLink m_links[NODE_LINK_COUNT];
    using element_t = uint8_t[sizeof(T)];
    alignas(T) element_t m_data[Capacity];

    size_type m_size{0U};
}; // forward_list

} // namespace cxx
} // namespace iox

#include "iceoryx_utils/internal/cxx/forward_list.inl"

#endif // IOX_UTILS_CXX_FORWARD_LIST_HPP

Updated on 26 April 2021 at 15:31:01 CEST