1// Copyright (C) 2008-2012 NVIDIA Corporation.
2// Copyright (C) 2019 The Qt Company Ltd.
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only
4
5#ifndef QSSGINVASIVELINKEDLIST_H
6#define QSSGINVASIVELINKEDLIST_H
7
8//
9// W A R N I N G
10// -------------
11//
12// This file is not part of the Qt API. It exists purely as an
13// implementation detail. This header file may change from version to
14// version without notice, or even be removed.
15//
16// We mean it.
17//
18
19#include <QtQuick3DUtils/private/qtquick3dutilsglobal_p.h>
20
21QT_BEGIN_NAMESPACE
22
23#ifdef QT_DEBUG
24#define QSSG_VERIFY_NODE(X) if (!(X)) qCritical("Node links are not null!");
25#else
26#define QSSG_VERIFY_NODE(X) Q_UNUSED((X));
27#endif
28
29// Used for singly linked list where
30// items have either no head or tail ptr.
31template<typename T>
32struct QSSGNullOp
33{
34 static void set(T &, T *) {}
35 static T *get(const T &) { return nullptr; }
36};
37
38template <typename T, T *T::*n>
39struct QSSGListAccessorNext
40{
41 static inline T *get(T &o) { return o.*n; }
42 static inline const T *get(const T &o) { return o.*n; }
43 static inline void set(T &o, T *next) { o.*n = next; }
44};
45
46template <typename T, T *T::*p>
47struct QSSGListAccessorPrevious
48{
49 static inline T *get(T &o) { return o.*p; }
50 static inline const T *get(const T &o) { return o.*p; }
51 static inline void set(T &o, T *prev) { o.*p = prev; }
52};
53
54// Base linked list without an included head or tail member.
55template<typename T, typename HeadOp, typename TailOp>
56struct QSSGInvasiveLinkListBase
57{
58 inline T *tail(T *inObj) { return inObj ? TailOp::get(inObj) : nullptr; }
59 inline T *head(T *inObj) { return inObj ? HeadOp::get(inObj) : nullptr; }
60 inline const T *tail(const T *inObj) { return inObj ? TailOp::get(inObj) : nullptr; }
61 inline const T *head(const T *inObj) { return inObj ? HeadOp::get(inObj) : nullptr; }
62
63 void remove(T &inObj)
64 {
65 T *theHead = HeadOp::get(inObj);
66 T *theTail = TailOp::get(inObj);
67 if (theHead)
68 TailOp::set(*theHead, theTail);
69 if (theTail)
70 HeadOp::set(*theTail, theHead);
71 HeadOp::set(inObj, nullptr);
72 TailOp::set(inObj, nullptr);
73 }
74
75 void insert_after(T &inPosition, T &inObj)
76 {
77 T *theHead = &inPosition;
78 T *theTail = TailOp::get(inPosition);
79 insert_unsafe(inHead: theHead, inTail: theTail, inObj);
80 }
81
82 void insert_before(T &inPosition, T &inObj)
83 {
84 T *theHead = HeadOp::get(inPosition);
85 T *theTail = &inPosition;
86 insert_unsafe(inHead: theHead, inTail: theTail, inObj);
87 }
88
89 // The name here is intentionally named "unsafe" to discourage use
90 // with out knowing what it implies to call this function.
91 // In most cases this will be used to insert before and after a neighboring pair
92 // (see: insert_before()/_after), but it can also be convenient if you want to split
93 // up a list and retain the chain for the removed section.
94 void insert_unsafe(T *inHead, T *inTail, T &inObj)
95 {
96 if (inHead)
97 TailOp::set(*inHead, &inObj);
98 if (inTail)
99 HeadOp::set(*inTail, &inObj);
100 HeadOp::set(inObj, inHead);
101 TailOp::set(inObj, inTail);
102 }
103};
104
105template<typename T, typename TailOp>
106struct QSSGLinkedListIterator
107{
108 using Iterator = QSSGLinkedListIterator<T, TailOp>;
109 T *m_obj;
110 explicit QSSGLinkedListIterator(T *inObj = nullptr) : m_obj(inObj) {}
111
112 inline bool operator!=(const Iterator &inIter) const { return m_obj != inIter.m_obj; }
113 inline bool operator==(const Iterator &inIter) const { return m_obj == inIter.m_obj; }
114
115 Iterator &operator++()
116 {
117 if (m_obj)
118 m_obj = TailOp::get(*m_obj);
119 return *this;
120 }
121
122 Iterator operator++(int)
123 {
124 Iterator retval(*this);
125 ++(*this);
126 return retval;
127 }
128
129 T &operator*() { return *m_obj; }
130 T *operator->() { return m_obj; }
131};
132
133template<typename T, T *T::*Next>
134struct QSSGInvasiveSingleLinkedList : public QSSGInvasiveLinkListBase<T, QSSGNullOp<T>, QSSGListAccessorNext<T, Next>>
135{
136 using TailOp = QSSGListAccessorNext<T, Next>;
137 using List = QSSGInvasiveSingleLinkedList<T, Next>;
138 using BaseList = QSSGInvasiveLinkListBase<T, QSSGNullOp<T>, TailOp>;
139 using iterator = QSSGLinkedListIterator<T, TailOp>;
140 using const_iterator = iterator;
141 T *m_head = nullptr;
142
143 inline T &front() const { return *m_head; }
144
145 void push_front(T &inObj)
146 {
147 if (m_head != nullptr)
148 BaseList::insert_before(*m_head, inObj);
149 m_head = &inObj;
150 }
151
152 void push_back(T &inObj)
153 {
154 // The next pointer of the tail must be null.
155 // We assert because if the inObj actually points somewhere then it's
156 // likely that we: Crash at some later point, we loop, or we broke the links
157 // in another list.
158 QSSG_VERIFY_NODE(TailOp::get(inObj) == nullptr);
159
160 if (m_head == nullptr) {
161 m_head = &inObj;
162 } else {
163 T *lastObj = nullptr;
164 for (iterator iter = begin(), endIter = end(); iter != endIter; ++iter)
165 lastObj = &(*iter);
166
167 Q_ASSERT(lastObj);
168 if (lastObj)
169 TailOp::set(*lastObj, &inObj);
170 }
171 TailOp::set(inObj, nullptr);
172 }
173
174 void remove(T &inObj)
175 {
176 if (m_head == &inObj) {
177 m_head = TailOp::get(inObj);
178 BaseList::remove(inObj);
179 } else if (m_head) {
180 // We need to find the node pointing to inObj
181 T *head = m_head;
182 T *tail = TailOp::get(*head);
183 while (head && tail != &inObj) {
184 head = TailOp::get(*head);
185 tail = head ? TailOp::get(*head) : nullptr;
186 }
187
188 if (head && tail == &inObj) {
189 T *oldTail = TailOp::get(inObj);
190 TailOp::set(inObj, nullptr); // deteach from the list
191 TailOp::set(*head, oldTail); // insert old tail to head of inObj
192 }
193 }
194 }
195
196 /*!
197 * \brief removeAll removes all nodes and re-sets their tail to null.
198 */
199 void removeAll()
200 {
201 for (auto it = begin(), e = end(); it != e;)
202 remove(inObj&: *(it++));
203 }
204
205 /*!
206 * \brief clear will set the head of the list to null.
207 * Note that the nodes are not updated in this case!
208 */
209 void clear()
210 {
211 m_head = nullptr;
212 }
213
214 inline bool isEmpty() const { return m_head == nullptr; }
215
216 inline iterator begin() { return iterator(m_head); }
217 inline iterator end() { return iterator(nullptr); }
218 inline const_iterator begin() const { return iterator(m_head); }
219 inline const_iterator end() const { return iterator(nullptr); }
220};
221
222template<typename T, T *T::*Previous, T *T::*Next>
223struct QSSGInvasiveLinkedList : public QSSGInvasiveLinkListBase<T, QSSGListAccessorPrevious<T, Previous>, QSSGListAccessorNext<T, Next>>
224{
225 using HeadOp = QSSGListAccessorPrevious<T, Previous>;
226 using TailOp = QSSGListAccessorNext<T, Next>;
227 using List = QSSGInvasiveLinkedList<T, Previous, Next>;
228 using BaseList = QSSGInvasiveLinkListBase<T, HeadOp, TailOp>;
229 using iterator = QSSGLinkedListIterator<T, TailOp>;
230 using const_iterator = iterator;
231 using reverse_iterator = QSSGLinkedListIterator<T, HeadOp>;
232 using const_reverse_iterator = reverse_iterator;
233
234 T *m_head = nullptr;
235 T *m_tail = nullptr;
236
237 inline T &front() const
238 {
239 Q_ASSERT(m_head);
240 return *m_head;
241 }
242 inline T &back() const
243 {
244 Q_ASSERT(m_tail);
245 return *m_tail;
246 }
247
248 inline T *front_ptr() const { return m_head; }
249 inline T *back_ptr() const { return m_tail; }
250
251 void push_front(T &inObj)
252 {
253 // The prev pointer of the head must be null.
254 // If the inObj actually points somewhere then it's likely that we're going to:
255 // Crash at some later point, loop, or that the we just broke the another list.
256 QSSG_VERIFY_NODE(HeadOp::get(inObj) == nullptr);
257
258 if (m_head != nullptr)
259 BaseList::insert_before(*m_head, inObj);
260 else
261 HeadOp::set(inObj, nullptr);
262
263 m_head = &inObj;
264
265 if (m_tail == nullptr)
266 m_tail = &inObj;
267 }
268
269 void push_back(T &inObj)
270 {
271 // The next pointer of the tail must be null.
272 // We assert because if the inObj actually points somewhere then it's
273 // likely that we: Crash at some later point, we loop, or we broke the links
274 // in another list.
275 QSSG_VERIFY_NODE(TailOp::get(inObj) == nullptr);
276
277 if (m_tail != nullptr)
278 BaseList::insert_after(*m_tail, inObj);
279 else
280 TailOp::set(inObj, nullptr);
281
282 m_tail = &inObj;
283
284 if (m_head == nullptr)
285 m_head = &inObj;
286 }
287
288 void remove(T &inObj)
289 {
290 if (m_head == &inObj)
291 m_head = TailOp::get(inObj);
292 if (m_tail == &inObj)
293 m_tail = HeadOp::get(inObj);
294
295 BaseList::remove(inObj);
296 }
297
298 /*!
299 * \brief removeAll removes all nodes and re-sets their head and tail to null.
300 */
301 void removeAll()
302 {
303 for (auto it = begin(), e = end(); it != e;)
304 remove(inObj&: *(it++));
305 }
306
307 /*!
308 * \brief clear will set the head and tail of the list to null.
309 * Note that the nodes are not updated in this case!
310 */
311 void clear()
312 {
313 m_head = m_tail = nullptr;
314 }
315
316 inline bool isEmpty() const { return m_head == nullptr; }
317
318 inline iterator begin() { return iterator(m_head); }
319 inline iterator end() { return iterator(nullptr); }
320
321 inline const_iterator begin() const { return iterator(m_head); }
322 inline const_iterator end() const { return iterator(nullptr); }
323
324 inline reverse_iterator rbegin() { return reverse_iterator(m_tail); }
325 inline reverse_iterator rend() { return reverse_iterator(nullptr); }
326
327 inline const_reverse_iterator rbegin() const { return reverse_iterator(m_tail); }
328 inline const_reverse_iterator rend() const { return reverse_iterator(nullptr); }
329};
330
331QT_END_NAMESPACE
332
333#endif // QSSGINVASIVELINKEDLIST_H
334

source code of qtquick3d/src/utils/qssginvasivelinkedlist_p.h