Skip to content

iceoryx_hoofs/cxx/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::list
C++11 compatible bi-directional 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
//
//     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_HOOFS_CXX_LIST_HPP
#define IOX_HOOFS_CXX_LIST_HPP

#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 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);

    list() noexcept;

    ~list() noexcept;

    list(const list& rhs) noexcept;

    list(list&& rhs) noexcept;

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

    list& operator=(list&& rhs) 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;

    T& back() noexcept;

    const T& back() const noexcept;

    bool push_front(const T& data) noexcept;

    bool push_front(T&& data) noexcept;

    bool push_back(const T& data) noexcept;

    bool push_back(T&& data) noexcept;

    bool pop_front() noexcept;

    bool pop_back() noexcept;

    void clear() noexcept;

    iterator erase(const_iterator iter) 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>
    T& emplace_back(ConstructorArgs&&... args) noexcept;

    template <typename... ConstructorArgs>
    iterator emplace(const_iterator iter, ConstructorArgs&&... args) noexcept;

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

    iterator insert(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::bidirectional_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;

        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 list<T, Capacity>*, 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 list<T, Capacity>;
        parentListPointer m_list;
        size_type m_iterListNodeIdx;
    };

    struct NodeLink
    {
        size_type nextIdx;
        size_type prevIdx;
    };

    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;
    size_type& getPrevIdx(const size_type idx) noexcept;
    size_type& getNextIdx(const size_type idx) noexcept;
    size_type& getPrevIdx(const const_iterator& iter) noexcept;
    size_type& getNextIdx(const const_iterator& iter) noexcept;
    const size_type& getPrevIdx(const size_type idx) const noexcept;
    const size_type& getNextIdx(const size_type idx) const noexcept;
    const size_type& getPrevIdx(const const_iterator& iter) const noexcept;
    const size_type& getNextIdx(const const_iterator& iter) const noexcept;
    void setPrevIdx(const size_type idx, const size_type prevIdx) noexcept;
    void setNextIdx(const size_type idx, const size_type nextIdx) noexcept;

    static void errorMessage(const char* source, const char* msg) noexcept;

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

    static constexpr size_type BEGIN_END_LINK_INDEX{size_type(Capacity)};
    static constexpr size_type NODE_LINK_COUNT{size_type(Capacity) + 1U};
    static constexpr size_type INVALID_INDEX{NODE_LINK_COUNT};

    // unused/free elements are stored in an internal list (freeList), this freeList is accessed via the
    // member variable m_freeListHeadIdx; user insert- and erase- operations move elements between the freeList and
    // active list
    size_type m_freeListHeadIdx{0U};

    // m_links array is one element bigger than request element count. In this additional element links are stored
    // to the beginning and end of the list. This additional element (index position 'capacity' aka
    // BEGIN_END_LINK_INDEX) 'previous' will point to the last valid element (end()) and 'next' will point to the
    // first used list element (begin())
    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};
}; // list

} // namespace cxx
} // namespace iox

#include "iceoryx_hoofs/internal/cxx/list.inl"

#endif // IOX_HOOFS_CXX_LIST_HPP

Updated on 31 May 2022 at 11:34:55 CEST