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