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 QDOUBLEENDEDLIST_P_H
5#define QDOUBLEENDEDLIST_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 QInheritedListNode
23{
24public:
25 ~QInheritedListNode() { remove(); }
26 bool isInList() const
27 {
28 Q_ASSERT((m_prev && m_next) || (!m_prev && !m_next));
29 return m_prev != nullptr;
30 }
31
32private:
33 template<class N>
34 friend class QDoubleEndedList;
35
36 void remove()
37 {
38 Q_ASSERT((m_prev && m_next) || (!m_prev && !m_next));
39 if (!m_prev)
40 return;
41
42 m_prev->m_next = m_next;
43 m_next->m_prev = m_prev;
44 m_prev = nullptr;
45 m_next = nullptr;
46 }
47
48 QInheritedListNode *m_next = nullptr;
49 QInheritedListNode *m_prev = nullptr;
50};
51
52template<class N>
53class QDoubleEndedList
54{
55public:
56 QDoubleEndedList()
57 {
58 m_head.m_next = &m_head;
59 m_head.m_prev = &m_head;
60 assertHeadConsistent();
61 }
62
63 ~QDoubleEndedList()
64 {
65 assertHeadConsistent();
66 while (!isEmpty())
67 m_head.m_next->remove();
68 assertHeadConsistent();
69 }
70
71 bool isEmpty() const
72 {
73 assertHeadConsistent();
74 return m_head.m_next == &m_head;
75 }
76
77 void prepend(N *n)
78 {
79 assertHeadConsistent();
80 QInheritedListNode *nnode = n;
81 nnode->remove();
82
83 nnode->m_next = m_head.m_next ? m_head.m_next : &m_head;
84 nnode->m_next->m_prev = nnode;
85
86 m_head.m_next = nnode;
87 nnode->m_prev = &m_head;
88 assertHeadConsistent();
89 }
90
91 void append(N *n)
92 {
93 assertHeadConsistent();
94 QInheritedListNode *nnode = n;
95 nnode->remove();
96
97 nnode->m_prev = m_head.m_prev ? m_head.m_prev : &m_head;
98 nnode->m_prev->m_next = nnode;
99
100 m_head.m_prev = nnode;
101 nnode->m_next = &m_head;
102 assertHeadConsistent();
103 }
104
105 void remove(N *n) {
106 Q_ASSERT(contains(n));
107 QInheritedListNode *nnode = n;
108 nnode->remove();
109 assertHeadConsistent();
110 }
111
112 bool contains(const N *n) const
113 {
114 assertHeadConsistent();
115 for (const QInheritedListNode *nnode = m_head.m_next;
116 nnode != &m_head; nnode = nnode->m_next) {
117 if (nnode == n)
118 return true;
119 }
120
121 return false;
122 }
123
124 template<typename T, typename Node>
125 class base_iterator {
126 public:
127 T *operator*() const { return QDoubleEndedList<N>::nodeToN(m_node); }
128 T *operator->() const { return QDoubleEndedList<N>::nodeToN(m_node); }
129
130 bool operator==(const base_iterator &other) const { return other.m_node == m_node; }
131 bool operator!=(const base_iterator &other) const { return other.m_node != m_node; }
132
133 base_iterator &operator++()
134 {
135 m_node = m_node->m_next;
136 return *this;
137 }
138
139 base_iterator operator++(int)
140 {
141 const base_iterator self(m_node);
142 m_node = m_node->m_next;
143 return self;
144 }
145
146 private:
147 friend class QDoubleEndedList<N>;
148
149 base_iterator(Node *node) : m_node(node)
150 {
151 Q_ASSERT(m_node != nullptr);
152 }
153
154 Node *m_node = nullptr;
155 };
156
157 using iterator = base_iterator<N, QInheritedListNode>;
158 using const_iterator = base_iterator<const N, const QInheritedListNode>;
159
160 const N *first() const { return checkedNodeToN(node: m_head.m_next); }
161 N *first() { return checkedNodeToN(node: m_head.m_next); }
162
163 const N *last() const { return checkedNodeToN(node: m_head.m_prev); }
164 N *last() { return checkedNodeToN(node: m_head.m_prev); }
165
166 const N *next(const N *current) const
167 {
168 Q_ASSERT(contains(current));
169 const QInheritedListNode *nnode = current;
170 return checkedNodeToN(node: nnode->m_next);
171 }
172
173 N *next(N *current)
174 {
175 Q_ASSERT(contains(current));
176 const QInheritedListNode *nnode = current;
177 return checkedNodeToN(node: nnode->m_next);
178 }
179
180 const N *prev(const N *current) const
181 {
182 Q_ASSERT(contains(current));
183 const QInheritedListNode *nnode = current;
184 return checkedNodeToN(node: nnode->m_prev);
185 }
186
187 N *prev(N *current)
188 {
189 Q_ASSERT(contains(current));
190 const QInheritedListNode *nnode = current;
191 return checkedNodeToN(node: nnode->m_prev);
192 }
193
194 iterator begin()
195 {
196 assertHeadConsistent();
197 return iterator(m_head.m_next);
198 }
199
200 iterator end()
201 {
202 assertHeadConsistent();
203 return iterator(&m_head);
204 }
205
206 const_iterator begin() const
207 {
208 assertHeadConsistent();
209 return const_iterator(m_head.m_next);
210 }
211
212 const_iterator end() const
213 {
214 assertHeadConsistent();
215 return const_iterator(&m_head);
216 }
217
218 qsizetype count() const
219 {
220 assertHeadConsistent();
221 qsizetype result = 0;
222 for (const auto *node = m_head.m_next; node != &m_head; node = node->m_next)
223 ++result;
224 return result;
225 }
226
227private:
228 static N *nodeToN(QInheritedListNode *node)
229 {
230 return static_cast<N *>(node);
231 }
232
233 static const N *nodeToN(const QInheritedListNode *node)
234 {
235 return static_cast<const N *>(node);
236 }
237
238 N *checkedNodeToN(QInheritedListNode *node) const
239 {
240 assertHeadConsistent();
241 return (!node || node == &m_head) ? nullptr : nodeToN(node);
242 }
243
244 void assertHeadConsistent() const
245 {
246 Q_ASSERT(m_head.m_next != nullptr);
247 Q_ASSERT(m_head.m_prev != nullptr);
248 Q_ASSERT(m_head.m_next != &m_head || m_head.m_prev == &m_head);
249 }
250
251 QInheritedListNode m_head;
252};
253
254QT_END_NAMESPACE
255
256#endif // QDOUBLEENDEDLIST_P_H
257

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