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 | |
20 | QT_BEGIN_NAMESPACE |
21 | |
22 | class QInheritedListNode |
23 | { |
24 | public: |
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 | |
32 | private: |
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 | |
52 | template<class N> |
53 | class QDoubleEndedList |
54 | { |
55 | public: |
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 | |
227 | private: |
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 | |
254 | QT_END_NAMESPACE |
255 | |
256 | #endif // QDOUBLEENDEDLIST_P_H |
257 |