Dequeue.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_DEQUEUE_H
#define IMT_BASE_CORE_UTIL_DEQUEUE_H
 
//AXIVION File Style CodingStyle-Naming.Method: function names similar to stl
//AXIVION File Style AutosarC++19_03-M5.0.15: array indexing (or pointer arithmetic) required because does not own the buffer
 
#include <Imt.Base.Core.Diagnostics/Diagnostics.h>
#include <Imt.Base.Core.Platform/Platform.h>
 
namespace imt {
namespace base {
namespace core {
namespace util {
 
template<typename T>
class Dequeue final {
public:
 
    Dequeue(T* mem, uint16_t queueSize) noexcept;
 
    void push_back(T const& e);
 
    void push_front(T const& e);
 
    void pop_front();
 
    void pop_back();
 
    T& front() {
        return m_pMem[m_tail];
    }
 
    T const& front() const {
        return m_pMem[m_tail];
    }
 
    T& back() {
        return m_pMem[this->circularAddTo(m_head, m_queueSize - 1, m_queueSize)];
    }
 
    T const& back() const {
        return m_pMem[this->circularAddTo(m_head, m_queueSize - 1, m_queueSize)];
    }
 
    size_t size() const;
 
    bool empty() const {
        // Not use multiple volatile statements in same c statement
        // https://www.iar.com/knowledge/support/technical-notes/compiler/warningpa082-undefined-behavior-the-order-of-volatile-accesses-is-undefined-in-this-statement/
        size_t const head {m_head};
        size_t const tail {m_tail};
 
        return head == tail;
    }
 
    bool full() const {
        // Not use multiple volatile statements in same c statement
        // https://www.iar.com/knowledge/support/technical-notes/compiler/warningpa082-undefined-behavior-the-order-of-volatile-accesses-is-undefined-in-this-statement/
        size_t const add {this->circularAddTo(m_head, 1, m_queueSize)};
        size_t const tail {m_tail};
 
        return add == tail;
    }
 
private:
 
    // Size of the queue.
    size_t const m_queueSize;
 
    // The queue memory.
    T* m_pMem;
 
    // Head index, points to the element right after the last written element.
    // AXIVION Next Codeline AutosarC++19_03-A12.1.3: No NSDMI for only part of the members, all data members initialized in custom constructor
    // AXIVION Next Codeline AutosarC++19_03-A2.11.1: volatile seems to be required here according to original implementer
    size_t volatile m_head; // prevent optimizer from reordering
 
    // Tail index, points to the element right after the last read element.
    // AXIVION Next Codeline AutosarC++19_03-A12.1.3: No NSDMI for only part of the members, all data members initialized in custom constructor
    // AXIVION Next Codeline AutosarC++19_03-A2.11.1: volatile seems to be required here according to original implementer
    size_t volatile m_tail; // prevent optimizer from reordering
 
    static size_t circularAddTo(size_t volatile to, size_t val, size_t size) { // AXIVION Line AutosarC++19_03-A2.11.1: volatile seems to be required here according to original implementer
        return (to + val) % size;
    }
};
 
// Implementation
template<typename T>
Dequeue<T>::Dequeue(T* mem, uint16_t queueSize) noexcept :
    m_queueSize {queueSize},
    m_pMem {mem},
    m_head {0},
    m_tail {0} {
}
 
template<typename T>
void Dequeue<T>::push_back(T const& e) {
    size_t const tmp {this->circularAddTo(m_head, 1, m_queueSize)}; // increment current head
    if (tmp != m_tail) {
        m_pMem[m_head] = e; // copy
        m_head = tmp;       // must be the last operation to finalize a change on the back of the queue.
    }
}
 
template<typename T>
void Dequeue<T>::push_front(T const& e) {
    size_t const tmp {this->circularAddTo(m_tail, m_queueSize - 1, m_queueSize)}; // decrement current tail
    if (tmp != m_head) {
        m_pMem[tmp] = e; // copy
        m_tail = tmp;    // must be the last operation to finalize a change on the back of the queue.
    }
}
 
template<typename T>
void Dequeue<T>::pop_front() {
    // Not use multiple volatile statements in same c statement
    // https://www.iar.com/knowledge/support/technical-notes/compiler/warningpa082-undefined-behavior-the-order-of-volatile-accesses-is-undefined-in-this-statement/
    size_t const head {m_head};
    size_t const tail {m_tail};
 
    if (tail != head) {
        size_t const tmp {this->circularAddTo(m_tail, 1, m_queueSize)}; // increment current tail
        m_tail = tmp;                                            // must be the last operation to indicate a change on the front of the queue.
    }
}
 
template<typename T>
void Dequeue<T>::pop_back() {
    // Not use multiple volatile statements in same c statement
    // https://www.iar.com/knowledge/support/technical-notes/compiler/warningpa082-undefined-behavior-the-order-of-volatile-accesses-is-undefined-in-this-statement/
    size_t const head {m_head};
    size_t const tail {m_tail};
 
    if (tail != head) {
        size_t const tmp {this->circularAddTo(m_head, m_queueSize - 1, m_queueSize)}; // decrement current head
        m_head = tmp;                                                         // must be the last operation to indicate a change on the back of the queue.
    }
}
 
template<typename T>
size_t Dequeue<T>::size() const {
    size_t const tmpHead {m_head};
    size_t const tmpTail {m_tail};
 
    if (tmpHead >= tmpTail) {
        return tmpHead - tmpTail;
    }
    else {
        return (m_queueSize - tmpTail) + tmpHead;
    }
}
 
} // namespace util
} // namespace core
} // namespace base
} // namespace imt
 
#endif // IMT_BASE_CORE_UTIL_DEQUEUE_H