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 | |
20 | QT_BEGIN_NAMESPACE |
21 | |
22 | class QIntrusiveListNode; |
23 | template<class N, QIntrusiveListNode N::*member> |
24 | class QIntrusiveList |
25 | { |
26 | public: |
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 | |
59 | private: |
60 | static inline N *nodeToN(QIntrusiveListNode *node); |
61 | |
62 | QIntrusiveListNode *__first = nullptr; |
63 | }; |
64 | |
65 | class QIntrusiveListNode |
66 | { |
67 | public: |
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 | |
78 | template<class N, QIntrusiveListNode N::*member> |
79 | QIntrusiveList<N, member>::iterator::iterator() |
80 | : _value(nullptr) |
81 | { |
82 | } |
83 | |
84 | template<class N, QIntrusiveListNode N::*member> |
85 | QIntrusiveList<N, member>::iterator::iterator(N *value) |
86 | : _value(value) |
87 | { |
88 | } |
89 | |
90 | template<class N, QIntrusiveListNode N::*member> |
91 | N *QIntrusiveList<N, member>::iterator::operator*() const |
92 | { |
93 | return _value; |
94 | } |
95 | |
96 | template<class N, QIntrusiveListNode N::*member> |
97 | N *QIntrusiveList<N, member>::iterator::operator->() const |
98 | { |
99 | return _value; |
100 | } |
101 | |
102 | template<class N, QIntrusiveListNode N::*member> |
103 | bool QIntrusiveList<N, member>::iterator::operator==(const iterator &other) const |
104 | { |
105 | return other._value == _value; |
106 | } |
107 | |
108 | template<class N, QIntrusiveListNode N::*member> |
109 | bool QIntrusiveList<N, member>::iterator::operator!=(const iterator &other) const |
110 | { |
111 | return other._value != _value; |
112 | } |
113 | |
114 | template<class N, QIntrusiveListNode N::*member> |
115 | typename QIntrusiveList<N, member>::iterator &QIntrusiveList<N, member>::iterator::operator++() |
116 | { |
117 | _value = QIntrusiveList<N, member>::next(current: _value); |
118 | return *this; |
119 | } |
120 | |
121 | template<class N, QIntrusiveListNode N::*member> |
122 | typename 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 | |
130 | template<class N, QIntrusiveListNode N::*member> |
131 | QIntrusiveList<N, member>::QIntrusiveList() |
132 | |
133 | { |
134 | } |
135 | |
136 | template<class N, QIntrusiveListNode N::*member> |
137 | QIntrusiveList<N, member>::~QIntrusiveList() |
138 | { |
139 | while (__first) __first->remove(); |
140 | } |
141 | |
142 | template<class N, QIntrusiveListNode N::*member> |
143 | bool QIntrusiveList<N, member>::isEmpty() const |
144 | { |
145 | return __first == nullptr; |
146 | } |
147 | |
148 | template<class N, QIntrusiveListNode N::*member> |
149 | void 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 | |
160 | template<class N, QIntrusiveListNode N::*member> |
161 | void QIntrusiveList<N, member>::remove(N *n) |
162 | { |
163 | QIntrusiveListNode *nnode = &(n->*member); |
164 | nnode->remove(); |
165 | } |
166 | |
167 | template<class N, QIntrusiveListNode N::*member> |
168 | bool 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 | |
179 | template<class N, QIntrusiveListNode N::*member> |
180 | N *QIntrusiveList<N, member>::first() const |
181 | { |
182 | return __first?nodeToN(node: __first):nullptr; |
183 | } |
184 | |
185 | template<class N, QIntrusiveListNode N::*member> |
186 | N *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 | |
193 | template<class N, QIntrusiveListNode N::*member> |
194 | typename QIntrusiveList<N, member>::iterator QIntrusiveList<N, member>::begin() |
195 | { |
196 | return __first?iterator(nodeToN(node: __first)):iterator(); |
197 | } |
198 | |
199 | template<class N, QIntrusiveListNode N::*member> |
200 | typename QIntrusiveList<N, member>::iterator QIntrusiveList<N, member>::end() |
201 | { |
202 | return iterator(); |
203 | } |
204 | |
205 | template<class N, QIntrusiveListNode N::*member> |
206 | N *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 | |
216 | QIntrusiveListNode::QIntrusiveListNode() |
217 | { |
218 | } |
219 | |
220 | QIntrusiveListNode::~QIntrusiveListNode() |
221 | { |
222 | remove(); |
223 | } |
224 | |
225 | void QIntrusiveListNode::remove() |
226 | { |
227 | if (_prev) *_prev = _next; |
228 | if (_next) _next->_prev = _prev; |
229 | _prev = nullptr; |
230 | _next = nullptr; |
231 | } |
232 | |
233 | bool QIntrusiveListNode::isInList() const |
234 | { |
235 | return _prev != nullptr; |
236 | } |
237 | |
238 | QT_END_NAMESPACE |
239 | |
240 | #endif // QINTRUSIVELIST_P_H |
241 | |