1// Copyright (C) 2021 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QINTRUSIVELIST_P_H
5#define QINTRUSIVELIST_P_H
6
7//
8// W A R N I N G
9// -------------
10//
11// This file is not part of the Qt API. It exists purely as an
12// implementation detail. This header file may change from version to
13// version without notice, or even be removed.
14//
15// We mean it.
16//
17
18#include <QtCore/private/qglobal_p.h>
19
20QT_BEGIN_NAMESPACE
21
22class QIntrusiveListNode;
23template<class N, QIntrusiveListNode N::*member>
24class QIntrusiveList
25{
26public:
27 inline QIntrusiveList();
28 inline ~QIntrusiveList();
29
30 inline bool isEmpty() const;
31 inline void insert(N *n);
32 inline void remove(N *n);
33 inline bool contains(N *) const;
34
35 class iterator {
36 public:
37 inline iterator();
38 inline iterator(N *value);
39
40 inline N *operator*() const;
41 inline N *operator->() const;
42 inline bool operator==(const iterator &other) const;
43 inline bool operator!=(const iterator &other) const;
44 inline iterator &operator++();
45
46 inline iterator &erase();
47
48 private:
49 N *_value;
50 };
51 typedef iterator Iterator;
52
53 inline N *first() const;
54 static inline N *next(N *current);
55
56 inline iterator begin();
57 inline iterator end();
58
59private:
60 static inline N *nodeToN(QIntrusiveListNode *node);
61
62 QIntrusiveListNode *__first = nullptr;
63};
64
65class QIntrusiveListNode
66{
67public:
68 inline QIntrusiveListNode();
69 inline ~QIntrusiveListNode();
70
71 inline void remove();
72 inline bool isInList() const;
73
74 QIntrusiveListNode *_next = nullptr;
75 QIntrusiveListNode**_prev = nullptr;
76};
77
78template<class N, QIntrusiveListNode N::*member>
79QIntrusiveList<N, member>::iterator::iterator()
80: _value(nullptr)
81{
82}
83
84template<class N, QIntrusiveListNode N::*member>
85QIntrusiveList<N, member>::iterator::iterator(N *value)
86: _value(value)
87{
88}
89
90template<class N, QIntrusiveListNode N::*member>
91N *QIntrusiveList<N, member>::iterator::operator*() const
92{
93 return _value;
94}
95
96template<class N, QIntrusiveListNode N::*member>
97N *QIntrusiveList<N, member>::iterator::operator->() const
98{
99 return _value;
100}
101
102template<class N, QIntrusiveListNode N::*member>
103bool QIntrusiveList<N, member>::iterator::operator==(const iterator &other) const
104{
105 return other._value == _value;
106}
107
108template<class N, QIntrusiveListNode N::*member>
109bool QIntrusiveList<N, member>::iterator::operator!=(const iterator &other) const
110{
111 return other._value != _value;
112}
113
114template<class N, QIntrusiveListNode N::*member>
115typename QIntrusiveList<N, member>::iterator &QIntrusiveList<N, member>::iterator::operator++()
116{
117 _value = QIntrusiveList<N, member>::next(current: _value);
118 return *this;
119}
120
121template<class N, QIntrusiveListNode N::*member>
122typename QIntrusiveList<N, member>::iterator &QIntrusiveList<N, member>::iterator::erase()
123{
124 N *old = _value;
125 _value = QIntrusiveList<N, member>::next(current: _value);
126 (old->*member).remove();
127 return *this;
128}
129
130template<class N, QIntrusiveListNode N::*member>
131QIntrusiveList<N, member>::QIntrusiveList()
132
133{
134}
135
136template<class N, QIntrusiveListNode N::*member>
137QIntrusiveList<N, member>::~QIntrusiveList()
138{
139 while (__first) __first->remove();
140}
141
142template<class N, QIntrusiveListNode N::*member>
143bool QIntrusiveList<N, member>::isEmpty() const
144{
145 return __first == nullptr;
146}
147
148template<class N, QIntrusiveListNode N::*member>
149void QIntrusiveList<N, member>::insert(N *n)
150{
151 QIntrusiveListNode *nnode = &(n->*member);
152 nnode->remove();
153
154 nnode->_next = __first;
155 if (nnode->_next) nnode->_next->_prev = &nnode->_next;
156 __first = nnode;
157 nnode->_prev = &__first;
158}
159
160template<class N, QIntrusiveListNode N::*member>
161void QIntrusiveList<N, member>::remove(N *n)
162{
163 QIntrusiveListNode *nnode = &(n->*member);
164 nnode->remove();
165}
166
167template<class N, QIntrusiveListNode N::*member>
168bool QIntrusiveList<N, member>::contains(N *n) const
169{
170 QIntrusiveListNode *nnode = __first;
171 while (nnode) {
172 if (nodeToN(node: nnode) == n)
173 return true;
174 nnode = nnode->_next;
175 }
176 return false;
177}
178
179template<class N, QIntrusiveListNode N::*member>
180N *QIntrusiveList<N, member>::first() const
181{
182 return __first?nodeToN(node: __first):nullptr;
183}
184
185template<class N, QIntrusiveListNode N::*member>
186N *QIntrusiveList<N, member>::next(N *current)
187{
188 QIntrusiveListNode *nextnode = (current->*member)._next;
189 N *nextstruct = nextnode?nodeToN(node: nextnode):nullptr;
190 return nextstruct;
191}
192
193template<class N, QIntrusiveListNode N::*member>
194typename QIntrusiveList<N, member>::iterator QIntrusiveList<N, member>::begin()
195{
196 return __first?iterator(nodeToN(node: __first)):iterator();
197}
198
199template<class N, QIntrusiveListNode N::*member>
200typename QIntrusiveList<N, member>::iterator QIntrusiveList<N, member>::end()
201{
202 return iterator();
203}
204
205template<class N, QIntrusiveListNode N::*member>
206N *QIntrusiveList<N, member>::nodeToN(QIntrusiveListNode *node)
207{
208 QT_WARNING_PUSH
209#if defined(Q_CC_CLANG) && Q_CC_CLANG >= 1300
210 QT_WARNING_DISABLE_CLANG("-Wnull-pointer-subtraction")
211#endif
212 return (N *)((char *)node - ((char *)&(((N *)nullptr)->*member) - (char *)nullptr));
213 QT_WARNING_POP
214}
215
216QIntrusiveListNode::QIntrusiveListNode()
217{
218}
219
220QIntrusiveListNode::~QIntrusiveListNode()
221{
222 remove();
223}
224
225void QIntrusiveListNode::remove()
226{
227 if (_prev) *_prev = _next;
228 if (_next) _next->_prev = _prev;
229 _prev = nullptr;
230 _next = nullptr;
231}
232
233bool QIntrusiveListNode::isInList() const
234{
235 return _prev != nullptr;
236}
237
238QT_END_NAMESPACE
239
240#endif // QINTRUSIVELIST_P_H
241

source code of qtdeclarative/src/qml/qml/ftw/qintrusivelist_p.h