LinkedList.h

Go to the documentation of this file.

// (c) IMT - Information Management Technology AG, CH-9470 Buchs, www.imt.ch.
//
// ActiveParts (AP) and the corresponding Data Flow Framework (DFF) is invented and designed by Jakob Daescher.
// ANY USE OF THIS CODE CONSTITUTES ACCEPTANCE OF THE TERMS OF THE COPYRIGHT NOTICE.
// ===================================================================================================
// COPYRIGHT NOTICE
// ===================================================================================================
// Copyright (C) 2005-2075, IMT Information Management Technology AG, 9470 Buchs, Switzerland
// All rights reserved.
// This code is proprietary software of IMT Information Management Technology AG (hereinafter: "IMT").
// Proprietary software is computer software licensed under exclusive legal right of IMT.
//
// The licensee is given the irrevocable, perpetual, worldwide, non-exclusive right and license to use,
// execute and reproduce the software in binary form within the licensed products.
//
// Redistribution and use in source forms, without modification, are permitted provided that the following conditions are met:
// (1) Copying of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
// (2) Copying of source code is only allowed for regulatory documentation and archiving purposes
// (3) Redistributions in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
//
// IMT provide no reassurances that the source code provided does not infringe
// any patent, copyright, or any other intellectual property rights of third parties.
// IMT disclaim any liability to any recipient for claims brought against
// recipient by any third party for infringement of that parties intellectual property rights.
//
// THIS SOFTWARE IS PROVIDED BY IMT AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
// IN NO EVENT SHALL IMT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
// OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCURE-MENT OF SUBSTITUTE GOODS OR SERVICES;
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
// IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
// ===================================================================================================
 
#ifndef IMT_BASE_CORE_UTIL_LINKED_LIST_H
#define IMT_BASE_CORE_UTIL_LINKED_LIST_H
 
#include <Imt.Base.Core.Diagnostics/Diagnostics.h>
#include <Imt.Base.Core.Platform/Platform.h>
#include <Imt.Base.Core.Util/PoolAllocator.h>
#include <type_traits>
 
namespace imt {
namespace base {
namespace core {
namespace util {
 
enum class LinkedListType : uint8_t {
    SINGLE, 
    DOUBLE  
};
 
// AXIVION Next Construct AutosarC++19_03-A9.6.1 : layout of data is not important for the linked list implementation (no HW interfacing)
template<typename T, LinkedListType type = LinkedListType::SINGLE>
struct ListNode { // AXIVION Line AutosarC++19_03-A9.6.1 : layout of data is not important for the linked list implementation (no HW interfacing)
};
 
template<typename T>
struct ListNode<T, LinkedListType::SINGLE> {                            // AXIVION Line AutosarC++19_03-A9.6.1 : layout of data is not important for the linked list implementation (no HW interfacing)
    static constexpr LinkedListType LIST_TYPE {LinkedListType::SINGLE}; // AXIVION Line AutosarC++19_03-M0.1.4: is referenced in template push_back below
    using ItemType = T;
 
    T m_item;
 
    ListNode* m_pNext;
};
 
template<typename T>
struct ListNode<T, LinkedListType::DOUBLE> {                            // AXIVION Line AutosarC++19_03-A9.6.1 : layout of data is not important for the linked list implementation (no HW interfacing)
    static constexpr LinkedListType LIST_TYPE {LinkedListType::DOUBLE}; // AXIVION Line AutosarC++19_03-M0.1.4: is referenced in template push_back below
 
    using ItemType = T;
 
    T m_item;
 
    ListNode* m_pNext;
 
    ListNode* m_pPrev;
};
 
template<typename Node, typename T = typename Node::ItemType, typename Allocator = PoolAllocator<Node>, LinkedListType type = LinkedListType::SINGLE>
class LinkedList final {
public:
 
    // AXIVION Line AutosarC++19_03-A9.6.1 : layout of data is not important for the linked list implementation (no HW interfacing)
    using ItemType = typename Node::ItemType;
 
    class Iterator {
    public:
 
        Iterator(Node* ptr = nullptr) noexcept :
            m_pNode {ptr} {
        }
 
        Iterator& operator=(Node* ptr) & noexcept {
            if (m_pNode == nullptr) {
                ASSERT_DEBUG(false);
                return *this;
            }
            m_pNode = ptr;
            return *this;
        }
 
        friend bool operator==(Iterator const& lhs, Iterator const& rhs) noexcept {
            return (lhs.m_pNode == rhs.m_pNode);
        }
 
        friend bool operator!=(Iterator const& lhs, Iterator const& rhs) noexcept {
            return !(lhs == rhs);
        }
 
        Iterator& operator++() noexcept {
            if (m_pNode != nullptr) {
                m_pNode = m_pNode->m_pNext;
            }
            else {
                // do nothing
            }
            return *this;
        }
 
        template<typename N = Node, typename std::enable_if<N::LIST_TYPE == LinkedListType::DOUBLE, bool>::type = true>
        Iterator& operator--() noexcept {
            if (m_pNode != nullptr) {
                m_pNode = m_pNode->m_pPrev;
            }
            return *this;
        }
 
        Node& operator*() noexcept {
            ASSERT_EX(m_pNode != nullptr);
            return *m_pNode;
        }
 
        Node const& operator*() const noexcept {
            ASSERT_EX(m_pNode == nullptr);
            return *m_pNode;
        }
 
        Node* operator->() const noexcept {
            return m_pNode;
        }
 
        // AXIVION Next Line AutosarC++19_03-A13.5.3: STL Interface
        explicit operator bool() const noexcept {
            return m_pNode != nullptr;
        }
 
        Node* getPtr() const noexcept {
            return m_pNode;
        }
 
        Node const* getConstPtr() const noexcept {
            return m_pNode;
        }
 
    private:
 
        // AXIVION Next Line AutosarC++19_03-M11.0.1: Allowed usage
        Node* m_pNode;
    };
 
    using ConstIterator = typename LinkedList<Node const>::Iterator; // AXIVION Line AutosarC++19_03-A14.7.1: false positive: all functions are disabled who require m_pPrev when using iterator for single-linked-nodes
 
    LinkedList(PoolAllocator<Node>& listAllocator, size_t listSize) noexcept :
        m_allocator {listAllocator},
        m_listSize {listSize},
        m_pHead {nullptr},
        m_pTail {nullptr},
        m_currentSize {0} {
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    Iterator begin() noexcept {
        // AXIVION Next Line AutosarC++19_03-A5.2.3: Removal of volatile required
        return Iterator(const_cast<Node*>(m_pHead));
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    // AXIVION Next Construct AutosarC++19_03-M9.3.3: Must not be static to match STL iterator API.
    ConstIterator cbegin() const noexcept {
        // AXIVION Next Line AutosarC++19_03-A5.2.3: Removal of volatile required
        return ConstIterator(const_cast<Node const*>(m_pHead));
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    // AXIVION Next Construct AutosarC++19_03-M9.3.3: Must not be static to match STL iterator API.
    Iterator end() noexcept {
        return nullptr;
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    // AXIVION Next Construct AutosarC++19_03-M9.3.3: Must not be static to match STL iterator API.
    ConstIterator cend() const noexcept {
        return nullptr;
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    template<typename N = Node, typename std::enable_if<N::LIST_TYPE == LinkedListType::SINGLE, bool>::type = true>
    void push_back(typename N::ItemType const& e) noexcept {
        Node* const pNewNode {m_allocator.allocate()};
        if (pNewNode == nullptr) {
            // AXIVION Next Line AutosarC++19_03-A5.1.1: Usage allowed, defined assert message
            ASSERT_DEBUG1(false, "list allocator full");
            return;
        }
        bool const headIsNullptr {m_pHead == nullptr};
        bool const tailIsNullptr {m_pTail == nullptr};
        if (!headIsNullptr && tailIsNullptr) {
            ASSERT_DEBUG1(false, "m_pTail is in invalid state"); // Axivion Line AutosarC++19_03-A5.1.1 : magic string literal required here
            return;
        }
        pNewNode->m_item = e;
        pNewNode->m_pNext = nullptr;
 
        if (m_pHead == nullptr) {
            m_pHead = pNewNode;
            m_pTail = pNewNode;
        }
        else {
            m_pTail->m_pNext = pNewNode;
            m_pTail = m_pTail->m_pNext;
        }
        m_currentSize++;
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    template<typename N = Node, typename std::enable_if<N::LIST_TYPE == LinkedListType::DOUBLE, bool>::type = true>
    void push_back(typename N::ItemType const& e) noexcept {
        Node* const pNewNode {m_allocator.allocate()};
        if (pNewNode == nullptr) {
            // AXIVION Next Line AutosarC++19_03-A5.1.1: Usage allowed, defined assert message
            ASSERT_DEBUG1(false, "list allocator full");
            return;
        }
        bool const headIsNullptr {m_pHead == nullptr};
        bool const tailIsNullptr {m_pTail == nullptr};
        if (!headIsNullptr && tailIsNullptr) {
            ASSERT_DEBUG1(false, "m_pTail is in invalid state"); // Axivion Line AutosarC++19_03-A5.1.1 : magic string literal required here
            return;
        }
        pNewNode->m_item = e;
        pNewNode->m_pNext = nullptr;
 
        if (m_pHead == nullptr) {
            pNewNode->m_pPrev = nullptr;
            m_pHead = pNewNode;
            m_pTail = pNewNode;
        }
        else {
            // AXIVION Next Line AutosarC++19_03-A5.2.3: Removal of volatile required
            pNewNode->m_pPrev = const_cast<Node*>(m_pTail);
            m_pTail->m_pNext = pNewNode;
            m_pTail = m_pTail->m_pNext;
        }
        m_currentSize++;
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    void pop_front() noexcept {
        ASSERT_EX(m_pHead != nullptr);
        // AXIVION Next Line AutosarC++19_03-A5.2.3: Removal of volatile required
        Node* pOldNode {const_cast<Node*>(m_pHead)};
        m_pHead = m_pHead->m_pNext;
        m_allocator.deallocate(pOldNode);
        m_currentSize--;
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    ItemType& front() noexcept {
        ASSERT_EX(m_pHead != nullptr);
        return *const_cast<T*>(&m_pHead->m_item);
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    ItemType const& front() const noexcept {
        ASSERT_EX(m_pHead != nullptr);
        return static_cast<T>(m_pHead->m_item);
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    size_t size() const noexcept {
        return m_currentSize;
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    bool empty() const noexcept {
        return m_currentSize == 0;
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    bool full() const noexcept {
        return m_listSize == m_currentSize;
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    template<typename I = ItemType, typename N = Node, typename std::enable_if<N::LIST_TYPE == LinkedListType::DOUBLE, bool>::type = true>
    void remove(I const& item) noexcept {
        Iterator it {begin()};
        while (it != end()) {
            if (it->m_item == item) {
                if ((it.getPtr() == m_pTail) && (it.getPtr() == m_pHead)) { // remove the only item
                    m_pHead = nullptr;
                    m_pTail = nullptr;
                }
                else if (it.getPtr() == m_pTail) { // remove the last item
                    if (m_pTail != nullptr) {
                        m_pTail = m_pTail->m_pPrev;
                    }
                    else {
                        ASSERT_DEBUG1(false, "m_pTail is null"); // Axivion Line AutosarC++19_03-A5.1.1 : magic string literal required here
                    }
                }
                else if (it.getPtr() == m_pHead) { // remove the first item
                    if (m_pHead != nullptr) {
                        m_pHead = m_pHead->m_pNext;
                    }
                    else {
                        ASSERT_DEBUG1(false, "m_pHead is null"); // Axivion Line AutosarC++19_03-A5.1.1 : magic string literal required here
                    }
                }
                else {
                    it->m_pPrev->m_pNext = it->m_pNext;
                    it->m_pNext->m_pPrev = it->m_pPrev;
                }
                m_allocator.deallocate(it.getPtr());
                m_currentSize--;
                break;
            }
            ++it;
        }
    }
 
    // AXIVION Next Construct CodingStyle-Naming.Method: Allowed naming, STL iterator API.
    template<typename TT>
    bool contains(const TT& item) const noexcept {
        ConstIterator it {cbegin()};
        while (it != cend()) {
            if (it->m_item == item) {
                return true;
            }
            ++it;
        }
        return false;
    }
 
private:
 
    PoolAllocator<Node>& m_allocator;
 
    // The size of the list.
    // AXIVION Next Codeline AutosarC++19_03-M0.1.4: field may be not used in member function if full() is not called in the project
    size_t const m_listSize;
 
    // Head index, points to the element right after the last written element.
    // AXIVION Next Codeline AutosarC++19_03-A2.11.1: Allowed usage, prevents optimizer from reordering
    // AXIVION Next Codeline AutosarC++19_03-A12.1.3: All data members initialized in custom constructor and would collide with AutosarC++19_03-A12.1.2
    Node volatile* m_pHead;
 
    // Tail index, points to the element right after the last read element.
    // AXIVION Next Codeline AutosarC++19_03-A2.11.1: Allowed usage, prevents optimizer from reordering
    // AXIVION Next Codeline AutosarC++19_03-A12.1.3: All data members initialized in custom constructor and would collide with AutosarC++19_03-A12.1.2
    Node volatile* m_pTail;
 
    // AXIVION Next Codeline AutosarC++19_03-A12.1.3: All data members initialized in custom constructor and would collide with AutosarC++19_03-A12.1.2
    size_t m_currentSize;
};
 
} // namespace util
} // namespace core
} // namespace base
} // namespace imt
 
#endif // IMT_BASE_CORE_UTIL_LINKED_LIST_H