1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
4 ** Contact: https://www.qt.io/licensing/
5 **
6 ** This file is part of the QtQml module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and The Qt Company. For licensing terms
14 ** and conditions see https://www.qt.io/terms-conditions. For further
15 ** information use the contact form at https://www.qt.io/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 3 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 3 requirements
23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24 **
25 ** GNU General Public License Usage
26 ** Alternatively, this file may be used under the terms of the GNU
27 ** General Public License version 2.0 or (at your option) the GNU General
28 ** Public license version 3 or any later version approved by the KDE Free
29 ** Qt Foundation. The licenses are as published by the Free Software
30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31 ** included in the packaging of this file. Please review the following
32 ** information to ensure the GNU General Public License requirements will
33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34 ** https://www.gnu.org/licenses/gpl-3.0.html.
35 **
36 ** $QT_END_LICENSE$
37 **
38 ****************************************************************************/
39
40 #ifndef QINTRUSIVELIST_P_H
41 #define QINTRUSIVELIST_P_H
42
43 //
44 // W A R N I N G
45 // -------------
46 //
47 // This file is not part of the Qt API. It exists purely as an
48 // implementation detail. This header file may change from version to
49 // version without notice, or even be removed.
50 //
51 // We mean it.
52 //
53
54 #include <QtCore/qglobal.h>
55
56 QT_BEGIN_NAMESPACE
57
58 class QIntrusiveListNode;
59 template<class N, QIntrusiveListNode N::*member>
60 class QIntrusiveList
61 {
62 public:
63 inline QIntrusiveList();
64 inline ~QIntrusiveList();
65
66 inline bool isEmpty() const;
67 inline void insert(N *n);
68 inline void remove(N *n);
69 inline bool contains(N *) const;
70
71 class iterator {
72 public:
73 inline iterator();
74 inline iterator(N *value);
75
76 inline N *operator*() const;
77 inline N *operator->() const;
78 inline bool operator==(const iterator &other) const;
79 inline bool operator!=(const iterator &other) const;
80 inline iterator &operator++();
81
82 inline iterator &erase();
83
84 private:
85 N *_value;
86 };
87 typedef iterator Iterator;
88
89 inline N *first() const;
90 static inline N *next(N *current);
91
92 inline iterator begin();
93 inline iterator end();
94
95 private:
96 static inline N *nodeToN(QIntrusiveListNode *node);
97
98 QIntrusiveListNode *__first = nullptr;
99 };
100
101 class QIntrusiveListNode
102 {
103 public:
104 inline QIntrusiveListNode();
105 inline ~QIntrusiveListNode();
106
107 inline void remove();
108 inline bool isInList() const;
109
110 QIntrusiveListNode *_next = nullptr;
111 QIntrusiveListNode**_prev = nullptr;
112 };
113
114 template<class N, QIntrusiveListNode N::*member>
iterator()115 QIntrusiveList<N, member>::iterator::iterator()
116 : _value(nullptr)
117 {
118 }
119
120 template<class N, QIntrusiveListNode N::*member>
iterator(N * value)121 QIntrusiveList<N, member>::iterator::iterator(N *value)
122 : _value(value)
123 {
124 }
125
126 template<class N, QIntrusiveListNode N::*member>
127 N *QIntrusiveList<N, member>::iterator::operator*() const
128 {
129 return _value;
130 }
131
132 template<class N, QIntrusiveListNode N::*member>
133 N *QIntrusiveList<N, member>::iterator::operator->() const
134 {
135 return _value;
136 }
137
138 template<class N, QIntrusiveListNode N::*member>
139 bool QIntrusiveList<N, member>::iterator::operator==(const iterator &other) const
140 {
141 return other._value == _value;
142 }
143
144 template<class N, QIntrusiveListNode N::*member>
145 bool QIntrusiveList<N, member>::iterator::operator!=(const iterator &other) const
146 {
147 return other._value != _value;
148 }
149
150 template<class N, QIntrusiveListNode N::*member>
151 typename QIntrusiveList<N, member>::iterator &QIntrusiveList<N, member>::iterator::operator++()
152 {
153 _value = QIntrusiveList<N, member>::next(_value);
154 return *this;
155 }
156
157 template<class N, QIntrusiveListNode N::*member>
erase()158 typename QIntrusiveList<N, member>::iterator &QIntrusiveList<N, member>::iterator::erase()
159 {
160 N *old = _value;
161 _value = QIntrusiveList<N, member>::next(_value);
162 (old->*member).remove();
163 return *this;
164 }
165
166 template<class N, QIntrusiveListNode N::*member>
QIntrusiveList()167 QIntrusiveList<N, member>::QIntrusiveList()
168
169 {
170 }
171
172 template<class N, QIntrusiveListNode N::*member>
~QIntrusiveList()173 QIntrusiveList<N, member>::~QIntrusiveList()
174 {
175 while (__first) __first->remove();
176 }
177
178 template<class N, QIntrusiveListNode N::*member>
isEmpty()179 bool QIntrusiveList<N, member>::isEmpty() const
180 {
181 return __first == nullptr;
182 }
183
184 template<class N, QIntrusiveListNode N::*member>
insert(N * n)185 void QIntrusiveList<N, member>::insert(N *n)
186 {
187 QIntrusiveListNode *nnode = &(n->*member);
188 nnode->remove();
189
190 nnode->_next = __first;
191 if (nnode->_next) nnode->_next->_prev = &nnode->_next;
192 __first = nnode;
193 nnode->_prev = &__first;
194 }
195
196 template<class N, QIntrusiveListNode N::*member>
remove(N * n)197 void QIntrusiveList<N, member>::remove(N *n)
198 {
199 QIntrusiveListNode *nnode = &(n->*member);
200 nnode->remove();
201 }
202
203 template<class N, QIntrusiveListNode N::*member>
contains(N * n)204 bool QIntrusiveList<N, member>::contains(N *n) const
205 {
206 QIntrusiveListNode *nnode = __first;
207 while (nnode) {
208 if (nodeToN(nnode) == n)
209 return true;
210 nnode = nnode->_next;
211 }
212 return false;
213 }
214
215 template<class N, QIntrusiveListNode N::*member>
first()216 N *QIntrusiveList<N, member>::first() const
217 {
218 return __first?nodeToN(__first):nullptr;
219 }
220
221 template<class N, QIntrusiveListNode N::*member>
next(N * current)222 N *QIntrusiveList<N, member>::next(N *current)
223 {
224 QIntrusiveListNode *nextnode = (current->*member)._next;
225 N *nextstruct = nextnode?nodeToN(nextnode):nullptr;
226 return nextstruct;
227 }
228
229 template<class N, QIntrusiveListNode N::*member>
begin()230 typename QIntrusiveList<N, member>::iterator QIntrusiveList<N, member>::begin()
231 {
232 return __first?iterator(nodeToN(__first)):iterator();
233 }
234
235 template<class N, QIntrusiveListNode N::*member>
end()236 typename QIntrusiveList<N, member>::iterator QIntrusiveList<N, member>::end()
237 {
238 return iterator();
239 }
240
241 template<class N, QIntrusiveListNode N::*member>
nodeToN(QIntrusiveListNode * node)242 N *QIntrusiveList<N, member>::nodeToN(QIntrusiveListNode *node)
243 {
244 return (N *)((char *)node - ((char *)&(((N *)nullptr)->*member) - (char *)nullptr));
245 }
246
QIntrusiveListNode()247 QIntrusiveListNode::QIntrusiveListNode()
248 {
249 }
250
~QIntrusiveListNode()251 QIntrusiveListNode::~QIntrusiveListNode()
252 {
253 remove();
254 }
255
remove()256 void QIntrusiveListNode::remove()
257 {
258 if (_prev) *_prev = _next;
259 if (_next) _next->_prev = _prev;
260 _prev = nullptr;
261 _next = nullptr;
262 }
263
isInList()264 bool QIntrusiveListNode::isInList() const
265 {
266 return _prev != nullptr;
267 }
268
269 QT_END_NAMESPACE
270
271 #endif // QINTRUSIVELIST_P_H
272