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
20QT_BEGIN_NAMESPACE
21
22template<class T>
23class QLinkedStringHash : private QStringHash<T>
24{
25public:
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
107protected:
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
167template<class T>
168class QLinkedStringMultiHash : public QLinkedStringHash<T>
169{
170public:
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
200QT_END_NAMESPACE
201
202#endif // QLINKEDSTRINGHASH_P_H
203

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