Skip to content



building block to easily create free function for logging in a library context


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.
// Copyright (c) 2021 by Apex.AI Inc. 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
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// See the License for the specific language governing permissions and
// limitations under the License.
// SPDX-License-Identifier: Apache-2.0


#include "iceoryx_hoofs/cxx/helplets.hpp"

#include <cstdint>
#include <iostream>

#include "iceoryx_hoofs/platform/platform_correction.hpp"

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

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

    forward_list() noexcept;

    ~forward_list() noexcept;

    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;

    template <bool IsConstIterator = true>
    class IteratorBase
        // 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;

        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 isInvalidIterator(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_hoofs/internal/cxx/forward_list.inl"


Updated on 18 December 2023 at 13:11:42 CET