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
56QT_BEGIN_NAMESPACE
57
58class QIntrusiveListNode;
59template<class N, QIntrusiveListNode N::*member>
60class QIntrusiveList
61{
62public:
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
95private:
96 static inline N *nodeToN(QIntrusiveListNode *node);
97
98 QIntrusiveListNode *__first = nullptr;
99};
100
101class QIntrusiveListNode
102{
103public:
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
114template<class N, QIntrusiveListNode N::*member>
115QIntrusiveList<N, member>::iterator::iterator()
116: _value(nullptr)
117{
118}
119
120template<class N, QIntrusiveListNode N::*member>
121QIntrusiveList<N, member>::iterator::iterator(N *value)
122: _value(value)
123{
124}
125
126template<class N, QIntrusiveListNode N::*member>
127N *QIntrusiveList<N, member>::iterator::operator*() const
128{
129 return _value;
130}
131
132template<class N, QIntrusiveListNode N::*member>
133N *QIntrusiveList<N, member>::iterator::operator->() const
134{
135 return _value;
136}
137
138template<class N, QIntrusiveListNode N::*member>
139bool QIntrusiveList<N, member>::iterator::operator==(const iterator &other) const
140{
141 return other._value == _value;
142}
143
144template<class N, QIntrusiveListNode N::*member>
145bool QIntrusiveList<N, member>::iterator::operator!=(const iterator &other) const
146{
147 return other._value != _value;
148}
149
150template<class N, QIntrusiveListNode N::*member>
151typename QIntrusiveList<N, member>::iterator &QIntrusiveList<N, member>::iterator::operator++()
152{
153 _value = QIntrusiveList<N, member>::next(_value);
154 return *this;
155}
156
157template<class N, QIntrusiveListNode N::*member>
158typename 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
166template<class N, QIntrusiveListNode N::*member>
167QIntrusiveList<N, member>::QIntrusiveList()
168
169{
170}
171
172template<class N, QIntrusiveListNode N::*member>
173QIntrusiveList<N, member>::~QIntrusiveList()
174{
175 while (__first) __first->remove();
176}
177
178template<class N, QIntrusiveListNode N::*member>
179bool QIntrusiveList<N, member>::isEmpty() const
180{
181 return __first == nullptr;
182}
183
184template<class N, QIntrusiveListNode N::*member>
185void 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
196template<class N, QIntrusiveListNode N::*member>
197void QIntrusiveList<N, member>::remove(N *n)
198{
199 QIntrusiveListNode *nnode = &(n->*member);
200 nnode->remove();
201}
202
203template<class N, QIntrusiveListNode N::*member>
204bool 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
215template<class N, QIntrusiveListNode N::*member>
216N *QIntrusiveList<N, member>::first() const
217{
218 return __first?nodeToN(__first):nullptr;
219}
220
221template<class N, QIntrusiveListNode N::*member>
222N *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
229template<class N, QIntrusiveListNode N::*member>
230typename QIntrusiveList<N, member>::iterator QIntrusiveList<N, member>::begin()
231{
232 return __first?iterator(nodeToN(__first)):iterator();
233}
234
235template<class N, QIntrusiveListNode N::*member>
236typename QIntrusiveList<N, member>::iterator QIntrusiveList<N, member>::end()
237{
238 return iterator();
239}
240
241template<class N, QIntrusiveListNode N::*member>
242N *QIntrusiveList<N, member>::nodeToN(QIntrusiveListNode *node)
243{
244 return (N *)((char *)node - ((char *)&(((N *)nullptr)->*member) - (char *)nullptr));
245}
246
247QIntrusiveListNode::QIntrusiveListNode()
248{
249}
250
251QIntrusiveListNode::~QIntrusiveListNode()
252{
253 remove();
254}
255
256void QIntrusiveListNode::remove()
257{
258 if (_prev) *_prev = _next;
259 if (_next) _next->_prev = _prev;
260 _prev = nullptr;
261 _next = nullptr;
262}
263
264bool QIntrusiveListNode::isInList() const
265{
266 return _prev != nullptr;
267}
268
269QT_END_NAMESPACE
270
271#endif // QINTRUSIVELIST_P_H
272