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> |
115 | QIntrusiveList<N, member>::iterator::iterator() |
116 | : _value(nullptr) |
117 | { |
118 | } |
119 | |
120 | template<class N, QIntrusiveListNode N::*member> |
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(current: _value); |
154 | return *this; |
155 | } |
156 | |
157 | template<class N, QIntrusiveListNode N::*member> |
158 | typename QIntrusiveList<N, member>::iterator &QIntrusiveList<N, member>::iterator::erase() |
159 | { |
160 | N *old = _value; |
161 | _value = QIntrusiveList<N, member>::next(current: _value); |
162 | (old->*member).remove(); |
163 | return *this; |
164 | } |
165 | |
166 | template<class N, QIntrusiveListNode N::*member> |
167 | QIntrusiveList<N, member>::QIntrusiveList() |
168 | |
169 | { |
170 | } |
171 | |
172 | template<class N, QIntrusiveListNode N::*member> |
173 | QIntrusiveList<N, member>::~QIntrusiveList() |
174 | { |
175 | while (__first) __first->remove(); |
176 | } |
177 | |
178 | template<class N, QIntrusiveListNode N::*member> |
179 | bool QIntrusiveList<N, member>::isEmpty() const |
180 | { |
181 | return __first == nullptr; |
182 | } |
183 | |
184 | template<class N, QIntrusiveListNode N::*member> |
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> |
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> |
204 | bool QIntrusiveList<N, member>::contains(N *n) const |
205 | { |
206 | QIntrusiveListNode *nnode = __first; |
207 | while (nnode) { |
208 | if (nodeToN(node: nnode) == n) |
209 | return true; |
210 | nnode = nnode->_next; |
211 | } |
212 | return false; |
213 | } |
214 | |
215 | template<class N, QIntrusiveListNode N::*member> |
216 | N *QIntrusiveList<N, member>::first() const |
217 | { |
218 | return __first?nodeToN(node: __first):nullptr; |
219 | } |
220 | |
221 | template<class N, QIntrusiveListNode N::*member> |
222 | N *QIntrusiveList<N, member>::next(N *current) |
223 | { |
224 | QIntrusiveListNode *nextnode = (current->*member)._next; |
225 | N *nextstruct = nextnode?nodeToN(node: nextnode):nullptr; |
226 | return nextstruct; |
227 | } |
228 | |
229 | template<class N, QIntrusiveListNode N::*member> |
230 | typename QIntrusiveList<N, member>::iterator QIntrusiveList<N, member>::begin() |
231 | { |
232 | return __first?iterator(nodeToN(node: __first)):iterator(); |
233 | } |
234 | |
235 | template<class N, QIntrusiveListNode N::*member> |
236 | typename QIntrusiveList<N, member>::iterator QIntrusiveList<N, member>::end() |
237 | { |
238 | return iterator(); |
239 | } |
240 | |
241 | template<class N, QIntrusiveListNode N::*member> |
242 | N *QIntrusiveList<N, member>::nodeToN(QIntrusiveListNode *node) |
243 | { |
244 | return (N *)((char *)node - ((char *)&(((N *)nullptr)->*member) - (char *)nullptr)); |
245 | } |
246 | |
247 | QIntrusiveListNode::QIntrusiveListNode() |
248 | { |
249 | } |
250 | |
251 | QIntrusiveListNode::~QIntrusiveListNode() |
252 | { |
253 | remove(); |
254 | } |
255 | |
256 | void QIntrusiveListNode::remove() |
257 | { |
258 | if (_prev) *_prev = _next; |
259 | if (_next) _next->_prev = _prev; |
260 | _prev = nullptr; |
261 | _next = nullptr; |
262 | } |
263 | |
264 | bool QIntrusiveListNode::isInList() const |
265 | { |
266 | return _prev != nullptr; |
267 | } |
268 | |
269 | QT_END_NAMESPACE |
270 | |
271 | #endif // QINTRUSIVELIST_P_H |
272 | |