Revision control
Copy as Markdown
// Copyright (C) 2008-2012 NVIDIA Corporation.
// Copyright (C) 2019 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only
// Qt-Security score:significant reason:default
#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
#ifdef QT_DEBUG
#define QSSG_VERIFY_NODE(X) if (!(X)) qCritical("Node links are not null!");
#else
#define QSSG_VERIFY_NODE(X) Q_UNUSED((X));
#endif
// Used for singly linked list where
// items have either no head or tail ptr.
template<typename T>
struct QSSGNullOp
{
static void set(T &, T *) {}
static T *get(const T &) { return nullptr; }
};
template <typename T, T *T::*n>
struct QSSGListAccessorNext
{
static inline T *get(T &o) { return o.*n; }
static inline const T *get(const T &o) { return o.*n; }
static inline void set(T &o, T *next) { o.*n = next; }
};
template <typename T, T *T::*p>
struct QSSGListAccessorPrevious
{
static inline T *get(T &o) { return o.*p; }
static inline const T *get(const T &o) { return o.*p; }
static inline void set(T &o, T *prev) { o.*p = prev; }
};
// Base linked list without an included head or tail member.
template<typename T, typename HeadOp, typename TailOp>
struct QSSGInvasiveLinkListBase
{
inline T *tail(T *inObj) { return inObj ? TailOp::get(inObj) : nullptr; }
inline T *head(T *inObj) { return inObj ? HeadOp::get(inObj) : nullptr; }
inline const T *tail(const T *inObj) { return inObj ? TailOp::get(inObj) : nullptr; }
inline const T *head(const T *inObj) { return inObj ? HeadOp::get(inObj) : nullptr; }
void remove(T &inObj)
{
T *theHead = HeadOp::get(inObj);
T *theTail = TailOp::get(inObj);
if (theHead)
TailOp::set(*theHead, theTail);
if (theTail)
HeadOp::set(*theTail, theHead);
HeadOp::set(inObj, nullptr);
TailOp::set(inObj, nullptr);
}
void insert_after(T &inPosition, T &inObj)
{
T *theHead = &inPosition;
T *theTail = TailOp::get(inPosition);
insert_unsafe(theHead, theTail, inObj);
}
void insert_before(T &inPosition, T &inObj)
{
T *theHead = HeadOp::get(inPosition);
T *theTail = &inPosition;
insert_unsafe(theHead, theTail, inObj);
}
// The name here is intentionally named "unsafe" to discourage use
// with out knowing what it implies to call this function.
// In most cases this will be used to insert before and after a neighboring pair
// (see: insert_before()/_after), but it can also be convenient if you want to split
// up a list and retain the chain for the removed section.
void insert_unsafe(T *inHead, T *inTail, T &inObj)
{
if (inHead)
TailOp::set(*inHead, &inObj);
if (inTail)
HeadOp::set(*inTail, &inObj);
HeadOp::set(inObj, inHead);
TailOp::set(inObj, inTail);
}
};
template<typename T, typename TailOp>
struct QSSGLinkedListIterator
{
using Iterator = QSSGLinkedListIterator<T, TailOp>;
T *m_obj;
explicit QSSGLinkedListIterator(T *inObj = nullptr) : m_obj(inObj) {}
inline bool operator!=(const Iterator &inIter) const { return m_obj != inIter.m_obj; }
inline bool operator==(const Iterator &inIter) const { return m_obj == inIter.m_obj; }
Iterator &operator++()
{
if (m_obj)
m_obj = TailOp::get(*m_obj);
return *this;
}
Iterator operator++(int)
{
Iterator retval(*this);
++(*this);
return retval;
}
T &operator*() { return *m_obj; }
T *operator->() { return m_obj; }
};
template<typename T, T *T::*Next>
struct QSSGInvasiveSingleLinkedList : public QSSGInvasiveLinkListBase<T, QSSGNullOp<T>, QSSGListAccessorNext<T, Next>>
{
using TailOp = QSSGListAccessorNext<T, Next>;
using List = QSSGInvasiveSingleLinkedList<T, Next>;
using BaseList = QSSGInvasiveLinkListBase<T, QSSGNullOp<T>, TailOp>;
using iterator = QSSGLinkedListIterator<T, TailOp>;
using const_iterator = iterator;
T *m_head = nullptr;
inline T &front() const { return *m_head; }
void push_front(T &inObj)
{
if (m_head != nullptr)
BaseList::insert_before(*m_head, inObj);
m_head = &inObj;
}
void push_back(T &inObj)
{
// The next pointer of the tail must be null.
// We assert because if the inObj actually points somewhere then it's
// likely that we: Crash at some later point, we loop, or we broke the links
// in another list.
QSSG_VERIFY_NODE(TailOp::get(inObj) == nullptr);
if (m_head == nullptr) {
m_head = &inObj;
} else {
T *lastObj = nullptr;
for (iterator iter = begin(), endIter = end(); iter != endIter; ++iter)
lastObj = &(*iter);
Q_ASSERT(lastObj);
if (lastObj)
TailOp::set(*lastObj, &inObj);
}
TailOp::set(inObj, nullptr);
}
void remove(T &inObj)
{
if (m_head == &inObj) {
m_head = TailOp::get(inObj);
BaseList::remove(inObj);
} else if (m_head) {
// We need to find the node pointing to inObj
T *head = m_head;
T *tail = TailOp::get(*head);
while (head && tail != &inObj) {
head = TailOp::get(*head);
tail = head ? TailOp::get(*head) : nullptr;
}
if (head && tail == &inObj) {
T *oldTail = TailOp::get(inObj);
TailOp::set(inObj, nullptr); // deteach from the list
TailOp::set(*head, oldTail); // insert old tail to head of inObj
}
}
}
/*!
* \brief removeAll removes all nodes and re-sets their tail to null.
*/
void removeAll()
{
for (auto it = begin(), e = end(); it != e;)
remove(*(it++));
}
/*!
* \brief clear will set the head of the list to null.
* Note that the nodes are not updated in this case!
*/
void clear()
{
m_head = nullptr;
}
inline bool isEmpty() const { return m_head == nullptr; }
inline iterator begin() { return iterator(m_head); }
inline iterator end() { return iterator(nullptr); }
inline const_iterator begin() const { return iterator(m_head); }
inline const_iterator end() const { return iterator(nullptr); }
};
template<typename T, T *T::*Previous, T *T::*Next>
struct QSSGInvasiveLinkedList : public QSSGInvasiveLinkListBase<T, QSSGListAccessorPrevious<T, Previous>, QSSGListAccessorNext<T, Next>>
{
using HeadOp = QSSGListAccessorPrevious<T, Previous>;
using TailOp = QSSGListAccessorNext<T, Next>;
using List = QSSGInvasiveLinkedList<T, Previous, Next>;
using BaseList = QSSGInvasiveLinkListBase<T, HeadOp, TailOp>;
using iterator = QSSGLinkedListIterator<T, TailOp>;
using const_iterator = iterator;
using reverse_iterator = QSSGLinkedListIterator<T, HeadOp>;
using const_reverse_iterator = reverse_iterator;
T *m_head = nullptr;
T *m_tail = nullptr;
inline T &front() const
{
Q_ASSERT(m_head);
return *m_head;
}
inline T &back() const
{
Q_ASSERT(m_tail);
return *m_tail;
}
inline T *front_ptr() const { return m_head; }
inline T *back_ptr() const { return m_tail; }
void push_front(T &inObj)
{
// The prev pointer of the head must be null.
// If the inObj actually points somewhere then it's likely that we're going to:
// Crash at some later point, loop, or that the we just broke the another list.
QSSG_VERIFY_NODE(HeadOp::get(inObj) == nullptr);
if (m_head != nullptr)
BaseList::insert_before(*m_head, inObj);
else
HeadOp::set(inObj, nullptr);
m_head = &inObj;
if (m_tail == nullptr)
m_tail = &inObj;
}
void push_back(T &inObj)
{
// The next pointer of the tail must be null.
// We assert because if the inObj actually points somewhere then it's
// likely that we: Crash at some later point, we loop, or we broke the links
// in another list.
QSSG_VERIFY_NODE(TailOp::get(inObj) == nullptr);
if (m_tail != nullptr)
BaseList::insert_after(*m_tail, inObj);
else
TailOp::set(inObj, nullptr);
m_tail = &inObj;
if (m_head == nullptr)
m_head = &inObj;
}
void remove(T &inObj)
{
if (m_head == &inObj)
m_head = TailOp::get(inObj);
if (m_tail == &inObj)
m_tail = HeadOp::get(inObj);
BaseList::remove(inObj);
}
/*!
* \brief removeAll removes all nodes and re-sets their head and tail to null.
*/
void removeAll()
{
for (auto it = begin(), e = end(); it != e;)
remove(*(it++));
}
/*!
* \brief clear will set the head and tail of the list to null.
* Note that the nodes are not updated in this case!
*/
void clear()
{
m_head = m_tail = nullptr;
}
inline bool isEmpty() const { return m_head == nullptr; }
inline iterator begin() { return iterator(m_head); }
inline iterator end() { return iterator(nullptr); }
inline const_iterator begin() const { return iterator(m_head); }
inline const_iterator end() const { return iterator(nullptr); }
inline reverse_iterator rbegin() { return reverse_iterator(m_tail); }
inline reverse_iterator rend() { return reverse_iterator(nullptr); }
inline const_reverse_iterator rbegin() const { return reverse_iterator(m_tail); }
inline const_reverse_iterator rend() const { return reverse_iterator(nullptr); }
};
QT_END_NAMESPACE
#endif // QSSGINVASIVELINKEDLIST_H