| /**************************************************************************** |
| ** |
| ** Copyright (C) 2008-2012 NVIDIA Corporation. |
| ** Copyright (C) 2019 The Qt Company Ltd. |
| ** Contact: https://www.qt.io/licensing/ |
| ** |
| ** This file is part of Qt Quick 3D. |
| ** |
| ** $QT_BEGIN_LICENSE:GPL$ |
| ** Commercial License Usage |
| ** Licensees holding valid commercial Qt licenses may use this file in |
| ** accordance with the commercial license agreement provided with the |
| ** Software or, alternatively, in accordance with the terms contained in |
| ** a written agreement between you and The Qt Company. For licensing terms |
| ** and conditions see https://www.qt.io/terms-conditions. For further |
| ** information use the contact form at https://www.qt.io/contact-us. |
| ** |
| ** GNU General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU |
| ** General Public License version 3 or (at your option) any later version |
| ** approved by the KDE Free Qt Foundation. The licenses are as published by |
| ** the Free Software Foundation and appearing in the file LICENSE.GPL3 |
| ** included in the packaging of this file. Please review the following |
| ** information to ensure the GNU General Public License requirements will |
| ** be met: https://www.gnu.org/licenses/gpl-3.0.html. |
| ** |
| ** $QT_END_LICENSE$ |
| ** |
| ****************************************************************************/ |
| |
| #ifndef QSSGINVASIVELINKEDLIST_H |
| #define QSSGINVASIVELINKEDLIST_H |
| |
| // |
| // W A R N I N G |
| // ------------- |
| // |
| // This file is not part of the Qt API. It exists purely as an |
| // implementation detail. This header file may change from version to |
| // version without notice, or even be removed. |
| // |
| // We mean it. |
| // |
| |
| #include <QtQuick3DUtils/private/qtquick3dutilsglobal_p.h> |
| |
| QT_BEGIN_NAMESPACE |
| |
| // Base linked list without an included head or tail member. |
| template<typename TObjType, typename TObjHeadOp, typename TObjTailOp> |
| struct QSSGInvasiveLinkListBase |
| { |
| TObjType *tail(TObjType *inObj) |
| { |
| if (inObj) |
| return TObjTailOp().get(inObj); |
| return nullptr; |
| } |
| |
| TObjType *head(TObjType *inObj) |
| { |
| if (inObj) |
| return TObjHeadOp().get(inObj); |
| return nullptr; |
| } |
| |
| const TObjType *tail(const TObjType *inObj) |
| { |
| if (inObj) |
| return TObjTailOp().get(inObj); |
| return nullptr; |
| } |
| |
| const TObjType *head(const TObjType *inObj) |
| { |
| if (inObj) |
| return TObjHeadOp().get(inObj); |
| return nullptr; |
| } |
| |
| void remove(TObjType &inObj) |
| { |
| TObjHeadOp theHeadOp; |
| TObjTailOp theTailOp; |
| TObjType *theHead = theHeadOp.get(inObj); |
| TObjType *theTail = theTailOp.get(inObj); |
| if (theHead) |
| theTailOp.set(*theHead, theTail); |
| if (theTail) |
| theHeadOp.set(*theTail, theHead); |
| theHeadOp.set(inObj, nullptr); |
| theTailOp.set(inObj, nullptr); |
| } |
| |
| void insert_after(TObjType &inPosition, TObjType &inObj) |
| { |
| TObjTailOp theTailOp; |
| TObjType *theHead = &inPosition; |
| TObjType *theTail = theTailOp.get(inPosition); |
| insert(theHead, theTail, inObj); |
| } |
| |
| void insert_before(TObjType &inPosition, TObjType &inObj) |
| { |
| TObjHeadOp theHeadOp; |
| TObjType *theHead = theHeadOp.get(inPosition); |
| TObjType *theTail = &inPosition; |
| insert(theHead, theTail, inObj); |
| } |
| |
| void insert(TObjType *inHead, TObjType *inTail, TObjType &inObj) |
| { |
| TObjHeadOp theHeadOp; |
| TObjTailOp theTailOp; |
| if (inHead) |
| theTailOp.set(*inHead, &inObj); |
| if (inTail) |
| theHeadOp.set(*inTail, &inObj); |
| theHeadOp.set(inObj, inHead); |
| theTailOp.set(inObj, inTail); |
| } |
| }; |
| |
| template<typename TObjType, typename TObjTailOp> |
| struct QSSGLinkedListIterator |
| { |
| typedef QSSGLinkedListIterator<TObjType, TObjTailOp> TMyType; |
| TObjType *m_obj; |
| QSSGLinkedListIterator(TObjType *inObj = nullptr) : m_obj(inObj) {} |
| |
| bool operator!=(const TMyType &inIter) const { return m_obj != inIter.m_obj; } |
| bool operator==(const TMyType &inIter) const { return m_obj == inIter.m_obj; } |
| |
| TMyType &operator++() |
| { |
| if (m_obj) |
| m_obj = TObjTailOp().get(*m_obj); |
| return *this; |
| } |
| |
| TMyType &operator++(int) |
| { |
| TMyType retval(*this); |
| ++(*this); |
| return retval; |
| } |
| |
| TObjType &operator*() { return *m_obj; } |
| TObjType *operator->() { return m_obj; } |
| }; |
| |
| // Used for singly linked list where |
| // items have either no head or tail ptr. |
| template<typename TObjType> |
| struct QSSGNullOp |
| { |
| void set(TObjType &, TObjType *) {} |
| TObjType *get(const TObjType &) { return nullptr; } |
| }; |
| |
| template<typename TObjType, typename TObjTailOp> |
| struct QSSGInvasiveSingleLinkedList : public QSSGInvasiveLinkListBase<TObjType, QSSGNullOp<TObjType>, TObjTailOp> |
| { |
| typedef QSSGInvasiveSingleLinkedList<TObjType, TObjTailOp> TMyType; |
| typedef QSSGInvasiveLinkListBase<TObjType, QSSGNullOp<TObjType>, TObjTailOp> TBaseType; |
| typedef QSSGLinkedListIterator<TObjType, TObjTailOp> iterator; |
| typedef iterator const_iterator; |
| TObjType *m_head = nullptr; |
| QSSGInvasiveSingleLinkedList() = default; |
| QSSGInvasiveSingleLinkedList(const TMyType &inOther) : m_head(inOther.m_head) {} |
| TMyType &operator=(const TMyType &inOther) |
| { |
| m_head = inOther.m_head; |
| return *this; |
| } |
| |
| TObjType &front() const { return *m_head; } |
| |
| void push_front(TObjType &inObj) |
| { |
| if (m_head != nullptr) |
| TBaseType::insert_before(*m_head, inObj); |
| m_head = &inObj; |
| } |
| |
| void push_back(TObjType &inObj) |
| { |
| if (m_head == nullptr) |
| m_head = &inObj; |
| else { |
| TObjType *lastObj = nullptr; |
| for (iterator iter = begin(), endIter = end(); iter != endIter; ++iter) |
| lastObj = &(*iter); |
| |
| Q_ASSERT(lastObj); |
| if (lastObj) |
| TObjTailOp().set(*lastObj, &inObj); |
| } |
| } |
| |
| void remove(TObjType &inObj) |
| { |
| if (m_head == &inObj) |
| m_head = TObjTailOp().get(inObj); |
| TBaseType::remove(inObj); |
| } |
| |
| bool empty() const { return m_head == nullptr; } |
| |
| iterator begin() { return iterator(m_head); } |
| iterator end() { return iterator(nullptr); } |
| |
| const_iterator begin() const { return iterator(m_head); } |
| const_iterator end() const { return iterator(nullptr); } |
| }; |
| |
| template<typename TObjType, typename TObjHeadOp, typename TObjTailOp> |
| struct QSSGInvasiveLinkedList : public QSSGInvasiveLinkListBase<TObjType, TObjHeadOp, TObjTailOp> |
| { |
| typedef QSSGInvasiveLinkedList<TObjType, TObjHeadOp, TObjTailOp> TMyType; |
| typedef QSSGInvasiveLinkListBase<TObjType, TObjHeadOp, TObjTailOp> TBaseType; |
| typedef QSSGLinkedListIterator<TObjType, TObjTailOp> iterator; |
| typedef iterator const_iterator; |
| typedef QSSGLinkedListIterator<TObjType, TObjHeadOp> reverse_iterator; |
| typedef reverse_iterator const_reverse_iterator; |
| |
| TObjType *m_head = nullptr; |
| TObjType *m_tail = nullptr; |
| |
| QSSGInvasiveLinkedList() = default; |
| QSSGInvasiveLinkedList(const TMyType &inOther) : m_head(inOther.m_head), m_tail(inOther.m_tail) {} |
| TMyType &operator=(const TMyType &inOther) |
| { |
| m_head = inOther.m_head; |
| m_tail = inOther.m_tail; |
| return *this; |
| } |
| |
| TObjType &front() const |
| { |
| Q_ASSERT(m_head); |
| return *m_head; |
| } |
| TObjType &back() const |
| { |
| Q_ASSERT(m_tail); |
| return *m_tail; |
| } |
| |
| TObjType *front_ptr() const { return m_head; } |
| TObjType *back_ptr() const { return m_tail; } |
| |
| void push_front(TObjType &inObj) |
| { |
| if (m_head != nullptr) |
| TBaseType::insert_before(*m_head, inObj); |
| m_head = &inObj; |
| |
| if (m_tail == nullptr) |
| m_tail = &inObj; |
| } |
| |
| void push_back(TObjType &inObj) |
| { |
| if (m_tail != nullptr) |
| TBaseType::insert_after(*m_tail, inObj); |
| m_tail = &inObj; |
| |
| if (m_head == nullptr) |
| m_head = &inObj; |
| } |
| |
| void remove(TObjType &inObj) |
| { |
| if (m_head == &inObj) |
| m_head = TObjTailOp().get(inObj); |
| if (m_tail == &inObj) |
| m_tail = TObjHeadOp().get(inObj); |
| |
| TBaseType::remove(inObj); |
| } |
| |
| bool empty() const { return m_head == nullptr; } |
| |
| iterator begin() { return iterator(m_head); } |
| iterator end() { return iterator(nullptr); } |
| |
| const_iterator begin() const { return iterator(m_head); } |
| const_iterator end() const { return iterator(nullptr); } |
| |
| reverse_iterator rbegin() { return reverse_iterator(m_tail); } |
| reverse_iterator rend() { return reverse_iterator(nullptr); } |
| |
| const_reverse_iterator rbegin() const { return reverse_iterator(m_tail); } |
| const_reverse_iterator rend() const { return reverse_iterator(nullptr); } |
| }; |
| |
| // Macros to speed up the definitely of invasive linked lists. |
| #define DEFINE_INVASIVE_SINGLE_LIST(type) \ |
| struct type; \ |
| struct type##NextOp \ |
| { \ |
| type *get(type &s); \ |
| const type *get(const type &s) const; \ |
| void set(type &inItem, type *inNext); \ |
| }; \ |
| typedef QSSGInvasiveSingleLinkedList<type, type##NextOp> type##List; |
| |
| #define DEFINE_INVASIVE_LIST(type) \ |
| struct type; \ |
| struct type##NextOp \ |
| { \ |
| type *get(type &s); \ |
| const type *get(const type &s) const; \ |
| void set(type &inItem, type *inNext); \ |
| }; \ |
| struct type##PreviousOp \ |
| { \ |
| type *get(type &s); \ |
| const type *get(const type &s) const; \ |
| void set(type &inItem, type *inNext); \ |
| }; \ |
| typedef QSSGInvasiveLinkedList<type, type##PreviousOp, type##NextOp> type##List; |
| |
| #define IMPLEMENT_INVASIVE_LIST(type, prevMember, nextMember) \ |
| inline type *type##NextOp::get(type &s) { return s.nextMember; } \ |
| inline const type *type##NextOp::get(const type &s) const { return s.nextMember; } \ |
| inline void type##NextOp::set(type &inItem, type *inNext) { inItem.nextMember = inNext; } \ |
| inline type *type##PreviousOp::get(type &s) { return s.prevMember; } \ |
| inline const type *type##PreviousOp::get(const type &s) const { return s.prevMember; } \ |
| inline void type##PreviousOp::set(type &inItem, type *inNext) { inItem.prevMember = inNext; } |
| |
| #define IMPLEMENT_INVASIVE_SINGLE_LIST(type, nextMember) \ |
| inline type *type##NextOp::get(type &s) { return s.nextMember; } \ |
| inline const type *type##NextOp::get(const type &s) const { return s.nextMember; } \ |
| inline void type##NextOp::set(type &inItem, type *inNext) { inItem.nextMember = inNext; } |
| |
| QT_END_NAMESPACE |
| |
| #endif // QSSGINVASIVELINKEDLIST_H |