1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2019 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 QLINKEDSTRINGHASH_P_H |
41 | #define QLINKEDSTRINGHASH_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 <private/qstringhash_p.h> |
55 | |
56 | QT_BEGIN_NAMESPACE |
57 | |
58 | template<class T> |
59 | class QLinkedStringHash : private QStringHash<T> |
60 | { |
61 | public: |
62 | using typename QStringHash<T>::Node; |
63 | using typename QStringHash<T>::NewedNode; |
64 | using typename QStringHash<T>::ReservedNodePool; |
65 | using typename QStringHash<T>::mapped_type; |
66 | |
67 | using ConstIteratorData = QStringHashData::IteratorData<const QLinkedStringHash>; |
68 | using ConstIterator = typename QStringHash<T>::template Iterator<ConstIteratorData, const T>; |
69 | |
70 | void linkAndReserve(const QLinkedStringHash<T> &other, int additionalReserve) |
71 | { |
72 | clear(); |
73 | |
74 | if (other.count()) { |
75 | data.size = other.data.size; |
76 | data.rehashToSize(other.count() + additionalReserve); |
77 | |
78 | if (data.numBuckets == other.data.numBuckets) { |
79 | nodePool = new ReservedNodePool; |
80 | nodePool->count = additionalReserve; |
81 | nodePool->used = 0; |
82 | nodePool->nodes = new Node[additionalReserve]; |
83 | |
84 | for (int ii = 0; ii < data.numBuckets; ++ii) |
85 | data.buckets[ii] = (Node *)other.data.buckets[ii]; |
86 | |
87 | link = &other; |
88 | return; |
89 | } |
90 | |
91 | data.size = 0; |
92 | } |
93 | |
94 | data.numBits = other.data.numBits; |
95 | reserve(other.count() + additionalReserve); |
96 | copy(other); |
97 | } |
98 | |
99 | inline bool isLinked() const |
100 | { |
101 | return link != 0; |
102 | } |
103 | |
104 | void clear() |
105 | { |
106 | QStringHash<T>::clear(); |
107 | link = nullptr; |
108 | } |
109 | |
110 | template<typename K> |
111 | void insert(const K &key, const T &value) |
112 | { |
113 | // If this is a linked hash, we can't rely on owning the node, so we always |
114 | // create a new one. |
115 | Node *n = link ? nullptr : QStringHash<T>::findNode(key); |
116 | if (n) |
117 | n->value = value; |
118 | else |
119 | QStringHash<T>::createNode(key, value); |
120 | } |
121 | |
122 | template<typename K> |
123 | inline ConstIterator find(const K &key) const |
124 | { |
125 | return iterator(n: QStringHash<T>::findNode(key)); |
126 | } |
127 | |
128 | ConstIterator begin() const |
129 | { |
130 | return ConstIterator( |
131 | QStringHash<T>::template iterateFirst<const QLinkedStringHash<T>, |
132 | ConstIteratorData>(this)); |
133 | } |
134 | |
135 | ConstIterator end() const { return ConstIterator(); } |
136 | |
137 | inline T *value(const ConstIterator &iter) { return value(iter.node()->key()); } |
138 | |
139 | using QStringHash<T>::value; |
140 | using QStringHash<T>::reserve; |
141 | using QStringHash<T>::copy; |
142 | |
143 | protected: |
144 | friend QStringHash<T>; |
145 | using QStringHash<T>::data; |
146 | using QStringHash<T>::nodePool; |
147 | |
148 | using QStringHash<T>::createNode; |
149 | |
150 | inline ConstIteratorData iterateFirst() const |
151 | { |
152 | const ConstIteratorData rv |
153 | = QStringHash<T>::template iterateFirst<const QLinkedStringHash<T>, |
154 | ConstIteratorData>(this); |
155 | return (rv.n == nullptr && link) ? link->iterateFirst() : rv; |
156 | } |
157 | |
158 | static inline ConstIteratorData iterateNext(const ConstIteratorData &d) |
159 | { |
160 | const QLinkedStringHash<T> *self = d.p; |
161 | const ConstIteratorData rv = QStringHash<T>::iterateNext(d); |
162 | return (rv.n == nullptr && self->link) ? self->link->iterateFirst() : rv; |
163 | } |
164 | |
165 | inline ConstIterator iterator(Node *n) const |
166 | { |
167 | if (!n) |
168 | return ConstIterator(); |
169 | |
170 | const QLinkedStringHash<T> *container = this; |
171 | |
172 | if (link) { |
173 | // This node could be in the linked hash |
174 | if ((n >= nodePool->nodes) && (n < (nodePool->nodes + nodePool->used))) { |
175 | // The node is in this hash |
176 | } else if ((n >= link->nodePool->nodes) |
177 | && (n < (link->nodePool->nodes + link->nodePool->used))) { |
178 | // The node is in the linked hash |
179 | container = link; |
180 | } else { |
181 | const NewedNode *ln = link->newedNodes; |
182 | while (ln) { |
183 | if (ln == n) { |
184 | // This node is in the linked hash's newed list |
185 | container = link; |
186 | break; |
187 | } |
188 | ln = ln->nextNewed; |
189 | } |
190 | } |
191 | } |
192 | |
193 | |
194 | ConstIteratorData rv; |
195 | rv.n = n; |
196 | rv.p = container; |
197 | return ConstIterator(rv); |
198 | } |
199 | |
200 | const QLinkedStringHash<T> *link = nullptr; |
201 | }; |
202 | |
203 | template<class T> |
204 | class QLinkedStringMultiHash : public QLinkedStringHash<T> |
205 | { |
206 | public: |
207 | using ConstIterator = typename QLinkedStringHash<T>::ConstIterator; |
208 | |
209 | template<typename K> |
210 | inline void insert(const K &key, const T &value) |
211 | { |
212 | // Always create a new node |
213 | QLinkedStringHash<T>::createNode(key, value); |
214 | } |
215 | |
216 | inline void insert(const ConstIterator &iter) |
217 | { |
218 | // Always create a new node |
219 | QLinkedStringHash<T>::createNode(iter.key(), iter.value()); |
220 | } |
221 | |
222 | inline ConstIterator findNext(const ConstIterator &iter) const |
223 | { |
224 | if (auto *node = iter.node()) { |
225 | QHashedString key(node->key()); |
226 | while ((node = static_cast<typename QLinkedStringHash<T>::Node *>(*node->next))) { |
227 | if (node->equals(key)) |
228 | return QLinkedStringHash<T>::iterator(node); |
229 | } |
230 | } |
231 | |
232 | return ConstIterator(); |
233 | } |
234 | }; |
235 | |
236 | QT_END_NAMESPACE |
237 | |
238 | #endif // QLINKEDSTRINGHASH_P_H |
239 | |