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 QSTRINGHASH_P_H |
41 | #define QSTRINGHASH_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/qhashedstring_p.h> |
55 | #include <private/qprimefornumbits_p.h> |
56 | |
57 | #include <QtCore/qglobal.h> |
58 | |
59 | QT_BEGIN_NAMESPACE |
60 | |
61 | class QStringHashData; |
62 | class QStringHashNode |
63 | { |
64 | public: |
65 | QStringHashNode() |
66 | : ckey(nullptr) |
67 | { |
68 | } |
69 | |
70 | QStringHashNode(const QHashedString &key) |
71 | : length(key.length()), hash(key.hash()), symbolId(0) |
72 | { |
73 | strData = const_cast<QHashedString &>(key).data_ptr(); |
74 | setQString(true); |
75 | strData->ref.ref(); |
76 | } |
77 | |
78 | QStringHashNode(const QHashedCStringRef &key) |
79 | : length(key.length()), hash(key.hash()), symbolId(0), ckey(key.constData()) |
80 | { |
81 | } |
82 | |
83 | QStringHashNode(const QStringHashNode &o) |
84 | : length(o.length), hash(o.hash), symbolId(o.symbolId), ckey(o.ckey) |
85 | { |
86 | setQString(o.isQString()); |
87 | if (isQString()) { strData->ref.ref(); } |
88 | } |
89 | |
90 | ~QStringHashNode() |
91 | { |
92 | if (isQString()) { if (!strData->ref.deref()) free(ptr: strData); } |
93 | } |
94 | |
95 | QFlagPointer<QStringHashNode> next; |
96 | |
97 | qint32 length = 0; |
98 | quint32 hash = 0; |
99 | quint32 symbolId = 0; |
100 | |
101 | union { |
102 | const char *ckey; |
103 | QStringData *strData; |
104 | }; |
105 | |
106 | inline QHashedString key() const |
107 | { |
108 | if (isQString()) |
109 | return QHashedString(QString((QChar *)strData->data(), length), hash); |
110 | |
111 | return QHashedString(QString::fromLatin1(str: ckey, size: length), hash); |
112 | } |
113 | |
114 | bool isQString() const { return next.flag(); } |
115 | void setQString(bool v) { if (v) next.setFlag(); else next.clearFlag(); } |
116 | |
117 | inline char *cStrData() const { return (char *)ckey; } |
118 | inline quint16 *utf16Data() const { return (quint16 *)strData->data(); } |
119 | |
120 | inline bool equals(const QV4::Value &string) const { |
121 | QString s = string.toQStringNoThrow(); |
122 | if (isQString()) { |
123 | QStringDataPtr dd; |
124 | dd.ptr = strData; |
125 | strData->ref.ref(); |
126 | return QString(dd) == s; |
127 | } else { |
128 | return QLatin1String(cStrData(), length) == s; |
129 | } |
130 | } |
131 | |
132 | inline bool equals(const QV4::String *string) const { |
133 | if (length != string->d()->length() || hash != string->hashValue()) |
134 | return false; |
135 | if (isQString()) { |
136 | QStringDataPtr dd; |
137 | dd.ptr = strData; |
138 | strData->ref.ref(); |
139 | return QString(dd) == string->toQString(); |
140 | } else { |
141 | return QLatin1String(cStrData(), length) == string->toQString(); |
142 | } |
143 | } |
144 | |
145 | inline bool equals(const QHashedStringRef &string) const { |
146 | return length == string.length() && |
147 | hash == string.hash() && |
148 | (isQString()?QHashedString::compare(lhs: string.constData(), rhs: (const QChar *)utf16Data(), length): |
149 | QHashedString::compare(lhs: string.constData(), rhs: cStrData(), length)); |
150 | } |
151 | |
152 | inline bool equals(const QHashedCStringRef &string) const { |
153 | return length == string.length() && |
154 | hash == string.hash() && |
155 | (isQString()?QHashedString::compare(lhs: (const QChar *)utf16Data(), rhs: string.constData(), length): |
156 | QHashedString::compare(lhs: string.constData(), rhs: cStrData(), length)); |
157 | } |
158 | }; |
159 | |
160 | class QStringHashData |
161 | { |
162 | Q_DISABLE_COPY_MOVE(QStringHashData) |
163 | public: |
164 | QStringHashData() = default; |
165 | ~QStringHashData() = default; |
166 | |
167 | /* |
168 | A QHash has initially around pow(2, MinNumBits) buckets. For |
169 | example, if MinNumBits is 4, it has 17 buckets. |
170 | */ |
171 | enum { MinNumBits = 4 }; |
172 | |
173 | QStringHashNode **buckets = nullptr; // life cycle managed by QStringHash |
174 | int numBuckets = 0; |
175 | int size = 0; |
176 | short numBits = 0; |
177 | |
178 | template<typename StringHash> |
179 | struct IteratorData { |
180 | IteratorData(QStringHashNode *n = nullptr, StringHash *p = nullptr) : n(n), p(p) {} |
181 | |
182 | template<typename OtherData> |
183 | IteratorData(const OtherData &other) : n(other.n), p(other.p) {} |
184 | |
185 | QStringHashNode *n; |
186 | StringHash *p; |
187 | }; |
188 | |
189 | void rehashToBits(short bits) |
190 | { |
191 | numBits = qMax(a: short(MinNumBits), b: bits); |
192 | |
193 | int nb = qPrimeForNumBits(numBits); |
194 | if (nb == numBuckets && buckets) |
195 | return; |
196 | |
197 | QStringHashNode **newBuckets = new QStringHashNode *[nb]; |
198 | ::memset(s: newBuckets, c: 0, n: sizeof(QStringHashNode *) * nb); |
199 | |
200 | // Preserve the existing order within buckets so that items with the |
201 | // same key will retain the same find/findNext order |
202 | for (int i = 0; i < numBuckets; ++i) { |
203 | QStringHashNode *bucket = buckets[i]; |
204 | if (bucket) |
205 | rehashNode(newBuckets, nb, node: bucket); |
206 | } |
207 | |
208 | delete [] buckets; |
209 | buckets = newBuckets; |
210 | numBuckets = nb; |
211 | } |
212 | |
213 | void rehashToSize(int size) |
214 | { |
215 | short bits = qMax(a: short(MinNumBits), b: numBits); |
216 | while (qPrimeForNumBits(numBits: bits) < size) |
217 | bits++; |
218 | |
219 | if (bits > numBits) |
220 | rehashToBits(bits); |
221 | } |
222 | |
223 | void rehashNode(QStringHashNode **newBuckets, int nb, QStringHashNode *node) |
224 | { |
225 | QStringHashNode *next = node->next.data(); |
226 | if (next) |
227 | rehashNode(newBuckets, nb, node: next); |
228 | |
229 | int bucket = node->hash % nb; |
230 | node->next = newBuckets[bucket]; |
231 | newBuckets[bucket] = node; |
232 | } |
233 | }; |
234 | |
235 | // For a supplied key type, in what form do we need to keep a hashed version? |
236 | template<typename T> |
237 | struct HashedForm {}; |
238 | |
239 | template<> struct HashedForm<QString> { typedef QHashedString Type; }; |
240 | template<> struct HashedForm<QStringRef> { typedef QHashedStringRef Type; }; |
241 | template<> struct HashedForm<QHashedString> { typedef const QHashedString &Type; }; |
242 | template<> struct HashedForm<QV4::String *> { typedef const QV4::String *Type; }; |
243 | template<> struct HashedForm<const QV4::String *> { typedef const QV4::String *Type; }; |
244 | template<> struct HashedForm<QHashedStringRef> { typedef const QHashedStringRef &Type; }; |
245 | template<> struct HashedForm<QLatin1String> { typedef QHashedCStringRef Type; }; |
246 | template<> struct HashedForm<QHashedCStringRef> { typedef const QHashedCStringRef &Type; }; |
247 | |
248 | class QStringHashBase |
249 | { |
250 | public: |
251 | static HashedForm<QString>::Type hashedString(const QString &s) { return QHashedString(s);} |
252 | static HashedForm<QStringRef>::Type hashedString(const QStringRef &s) { return QHashedStringRef(s.constData(), s.size());} |
253 | static HashedForm<QHashedString>::Type hashedString(const QHashedString &s) { return s; } |
254 | static HashedForm<QV4::String *>::Type hashedString(QV4::String *s) { return s; } |
255 | static HashedForm<const QV4::String *>::Type hashedString(const QV4::String *s) { return s; } |
256 | static HashedForm<QHashedStringRef>::Type hashedString(const QHashedStringRef &s) { return s; } |
257 | |
258 | static HashedForm<QLatin1String>::Type hashedString(const QLatin1String &s) { return QHashedCStringRef(s.data(), s.size()); } |
259 | static HashedForm<QHashedCStringRef>::Type hashedString(const QHashedCStringRef &s) { return s; } |
260 | |
261 | static const QString &toQString(const QString &s) { return s; } |
262 | static const QString &toQString(const QHashedString &s) { return s; } |
263 | static QString toQString(const QV4::String *s) { return s->toQString(); } |
264 | static QString toQString(const QHashedStringRef &s) { return s.toString(); } |
265 | |
266 | static QString toQString(const QLatin1String &s) { return QString(s); } |
267 | static QString toQString(const QHashedCStringRef &s) { return s.toUtf16(); } |
268 | |
269 | static inline quint32 hashOf(const QHashedStringRef &s) { return s.hash(); } |
270 | static inline quint32 hashOf(QV4::String *s) { return s->hashValue(); } |
271 | static inline quint32 hashOf(const QV4::String *s) { return s->hashValue(); } |
272 | |
273 | template<typename K> |
274 | static inline quint32 hashOf(const K &key) { return hashedString(key).hash(); } |
275 | }; |
276 | |
277 | template<class T> |
278 | class QStringHash : public QStringHashBase |
279 | { |
280 | public: |
281 | typedef QHashedString key_type; |
282 | typedef T mapped_type; |
283 | |
284 | using MutableIteratorData = QStringHashData::IteratorData<QStringHash<T>>; |
285 | using ConstIteratorData = QStringHashData::IteratorData<const QStringHash<T>>; |
286 | |
287 | struct Node : public QStringHashNode { |
288 | Node(const QHashedString &key, const T &value) : QStringHashNode(key), value(value) {} |
289 | Node(const QHashedCStringRef &key, const T &value) : QStringHashNode(key), value(value) {} |
290 | Node(const Node &o) : QStringHashNode(o), value(o.value) {} |
291 | Node() {} |
292 | T value; |
293 | }; |
294 | struct NewedNode : public Node { |
295 | NewedNode(const QHashedString &key, const T &value) : Node(key, value), nextNewed(nullptr) {} |
296 | NewedNode(const QHashedCStringRef &key, const T &value) : Node(key, value), nextNewed(nullptr) {} |
297 | NewedNode(const Node &o) : Node(o), nextNewed(nullptr) {} |
298 | NewedNode *nextNewed; |
299 | }; |
300 | struct ReservedNodePool |
301 | { |
302 | ReservedNodePool() : nodes(nullptr) {} |
303 | ~ReservedNodePool() { delete [] nodes; } |
304 | int count = 0; |
305 | int used = 0; |
306 | Node *nodes; |
307 | }; |
308 | |
309 | QStringHashData data; |
310 | NewedNode *newedNodes; |
311 | ReservedNodePool *nodePool; |
312 | |
313 | template<typename K> |
314 | inline Node *findNode(const K &) const; |
315 | |
316 | inline Node *createNode(const Node &o); |
317 | |
318 | template<typename K> |
319 | inline Node *createNode(const K &, const T &); |
320 | |
321 | inline Node *insertNode(Node *, quint32); |
322 | |
323 | inline void initializeNode(Node *, const QHashedString &key); |
324 | inline void initializeNode(Node *, const QHashedCStringRef &key); |
325 | |
326 | template<typename K> |
327 | inline Node *takeNode(const K &key, const T &value); |
328 | |
329 | inline Node *takeNode(const Node &o); |
330 | |
331 | inline void copy(const QStringHash<T> &); |
332 | |
333 | void copyNode(const QStringHashNode *otherNode); |
334 | |
335 | template<typename StringHash, typename Data> |
336 | static inline Data iterateFirst(StringHash *self); |
337 | |
338 | template<typename Data> |
339 | static inline Data iterateNext(const Data &); |
340 | |
341 | public: |
342 | inline QStringHash(); |
343 | inline QStringHash(const QStringHash &); |
344 | inline ~QStringHash(); |
345 | |
346 | QStringHash &operator=(const QStringHash<T> &); |
347 | |
348 | void copyAndReserve(const QStringHash<T> &other, int additionalReserve); |
349 | |
350 | inline bool isEmpty() const; |
351 | inline void clear(); |
352 | inline int count() const; |
353 | |
354 | inline int numBuckets() const; |
355 | |
356 | template<typename Data, typename Value> |
357 | class Iterator { |
358 | public: |
359 | inline Iterator() = default; |
360 | inline Iterator(const Data &d) : d(d) {} |
361 | |
362 | inline Iterator &operator++() |
363 | { |
364 | d = QStringHash<T>::iterateNext(d); |
365 | return *this; |
366 | } |
367 | |
368 | inline bool operator==(const Iterator &o) const { return d.n == o.d.n; } |
369 | inline bool operator!=(const Iterator &o) const { return d.n != o.d.n; } |
370 | |
371 | template<typename K> |
372 | inline bool equals(const K &key) const { return d.n->equals(key); } |
373 | |
374 | inline QHashedString key() const { return static_cast<Node *>(d.n)->key(); } |
375 | inline Value &value() const { return static_cast<Node *>(d.n)->value; } |
376 | inline Value &operator*() const { return static_cast<Node *>(d.n)->value; } |
377 | |
378 | Node *node() const { return static_cast<Node *>(d.n); } |
379 | private: |
380 | Data d; |
381 | }; |
382 | |
383 | using MutableIterator = Iterator<MutableIteratorData, T>; |
384 | using ConstIterator = Iterator<ConstIteratorData, const T>; |
385 | |
386 | template<typename K> |
387 | inline void insert(const K &, const T &); |
388 | inline void insert(const MutableIterator &); |
389 | inline void insert(const ConstIterator &); |
390 | |
391 | template<typename K> |
392 | inline T *value(const K &) const; |
393 | inline T *value(const QV4::String *string) const; |
394 | inline T *value(const MutableIterator &) const; |
395 | inline T *value(const ConstIterator &) const; |
396 | |
397 | template<typename K> |
398 | inline bool contains(const K &) const; |
399 | |
400 | template<typename K> |
401 | inline T &operator[](const K &); |
402 | |
403 | inline MutableIterator begin(); |
404 | inline ConstIterator begin() const; |
405 | inline ConstIterator constBegin() const { return begin(); } |
406 | |
407 | inline MutableIterator end(); |
408 | inline ConstIterator end() const; |
409 | inline ConstIterator constEnd() const { return end(); } |
410 | |
411 | template<typename K> |
412 | inline MutableIterator find(const K &); |
413 | |
414 | template<typename K> |
415 | inline ConstIterator find(const K &) const; |
416 | |
417 | inline void reserve(int); |
418 | }; |
419 | |
420 | template<class T> |
421 | QStringHash<T>::QStringHash() |
422 | : newedNodes(nullptr), nodePool(nullptr) |
423 | { |
424 | } |
425 | |
426 | template<class T> |
427 | QStringHash<T>::QStringHash(const QStringHash<T> &other) |
428 | : newedNodes(nullptr), nodePool(nullptr) |
429 | { |
430 | data.numBits = other.data.numBits; |
431 | data.size = other.data.size; |
432 | reserve(other.count()); |
433 | copy(other); |
434 | } |
435 | |
436 | template<class T> |
437 | QStringHash<T> &QStringHash<T>::operator=(const QStringHash<T> &other) |
438 | { |
439 | if (&other == this) |
440 | return *this; |
441 | |
442 | clear(); |
443 | |
444 | data.numBits = other.data.numBits; |
445 | data.size = other.data.size; |
446 | reserve(other.count()); |
447 | copy(other); |
448 | |
449 | return *this; |
450 | } |
451 | |
452 | template<class T> |
453 | void QStringHash<T>::copyAndReserve(const QStringHash<T> &other, int additionalReserve) |
454 | { |
455 | clear(); |
456 | data.numBits = other.data.numBits; |
457 | reserve(other.count() + additionalReserve); |
458 | copy(other); |
459 | } |
460 | |
461 | template<class T> |
462 | QStringHash<T>::~QStringHash() |
463 | { |
464 | clear(); |
465 | } |
466 | |
467 | template<class T> |
468 | void QStringHash<T>::clear() |
469 | { |
470 | // Delete the individually allocated nodes |
471 | NewedNode *n = newedNodes; |
472 | while (n) { |
473 | NewedNode *c = n; |
474 | n = c->nextNewed; |
475 | delete c; |
476 | } |
477 | // Delete the pool allocated nodes |
478 | if (nodePool) delete nodePool; |
479 | delete [] data.buckets; |
480 | |
481 | data.buckets = nullptr; |
482 | data.numBuckets = 0; |
483 | data.numBits = 0; |
484 | data.size = 0; |
485 | |
486 | newedNodes = nullptr; |
487 | nodePool = nullptr; |
488 | } |
489 | |
490 | template<class T> |
491 | bool QStringHash<T>::isEmpty() const |
492 | { |
493 | return data.size== 0; |
494 | } |
495 | |
496 | template<class T> |
497 | int QStringHash<T>::count() const |
498 | { |
499 | return data.size; |
500 | } |
501 | |
502 | template<class T> |
503 | int QStringHash<T>::numBuckets() const |
504 | { |
505 | return data.numBuckets; |
506 | } |
507 | |
508 | template<class T> |
509 | void QStringHash<T>::initializeNode(Node *node, const QHashedString &key) |
510 | { |
511 | node->length = key.length(); |
512 | node->hash = key.hash(); |
513 | node->strData = const_cast<QHashedString &>(key).data_ptr(); |
514 | node->strData->ref.ref(); |
515 | node->setQString(true); |
516 | } |
517 | |
518 | template<class T> |
519 | void QStringHash<T>::initializeNode(Node *node, const QHashedCStringRef &key) |
520 | { |
521 | node->length = key.length(); |
522 | node->hash = key.hash(); |
523 | node->ckey = key.constData(); |
524 | } |
525 | |
526 | template<class T> |
527 | template<class K> |
528 | typename QStringHash<T>::Node *QStringHash<T>::takeNode(const K &key, const T &value) |
529 | { |
530 | if (nodePool && nodePool->used != nodePool->count) { |
531 | Node *rv = nodePool->nodes + nodePool->used++; |
532 | initializeNode(rv, hashedString(key)); |
533 | rv->value = value; |
534 | return rv; |
535 | } else { |
536 | NewedNode *rv = new NewedNode(hashedString(key), value); |
537 | rv->nextNewed = newedNodes; |
538 | newedNodes = rv; |
539 | return rv; |
540 | } |
541 | } |
542 | |
543 | template<class T> |
544 | typename QStringHash<T>::Node *QStringHash<T>::takeNode(const Node &o) |
545 | { |
546 | if (nodePool && nodePool->used != nodePool->count) { |
547 | Node *rv = nodePool->nodes + nodePool->used++; |
548 | rv->length = o.length; |
549 | rv->hash = o.hash; |
550 | if (o.isQString()) { |
551 | rv->strData = o.strData; |
552 | rv->strData->ref.ref(); |
553 | rv->setQString(true); |
554 | } else { |
555 | rv->ckey = o.ckey; |
556 | } |
557 | rv->symbolId = o.symbolId; |
558 | rv->value = o.value; |
559 | return rv; |
560 | } else { |
561 | NewedNode *rv = new NewedNode(o); |
562 | rv->nextNewed = newedNodes; |
563 | newedNodes = rv; |
564 | return rv; |
565 | } |
566 | } |
567 | |
568 | template<class T> |
569 | void QStringHash<T>::copyNode(const QStringHashNode *otherNode) |
570 | { |
571 | // Copy the predecessor before the successor |
572 | QStringHashNode *next = otherNode->next.data(); |
573 | if (next) |
574 | copyNode(otherNode: next); |
575 | |
576 | Node *mynode = takeNode(*(const Node *)otherNode); |
577 | int bucket = mynode->hash % data.numBuckets; |
578 | mynode->next = data.buckets[bucket]; |
579 | data.buckets[bucket] = mynode; |
580 | } |
581 | |
582 | template<class T> |
583 | void QStringHash<T>::copy(const QStringHash<T> &other) |
584 | { |
585 | Q_ASSERT(data.size == 0); |
586 | |
587 | data.size = other.data.size; |
588 | |
589 | // Ensure buckets array is created |
590 | data.rehashToBits(bits: data.numBits); |
591 | |
592 | // Preserve the existing order within buckets |
593 | for (int i = 0; i < other.data.numBuckets; ++i) { |
594 | QStringHashNode *bucket = other.data.buckets[i]; |
595 | if (bucket) |
596 | copyNode(otherNode: bucket); |
597 | } |
598 | } |
599 | |
600 | template<class T> |
601 | template<typename Data> |
602 | Data QStringHash<T>::iterateNext(const Data &d) |
603 | { |
604 | auto *This = d.p; |
605 | Node *node = (Node *)d.n; |
606 | |
607 | if (This->nodePool && node >= This->nodePool->nodes && |
608 | node < (This->nodePool->nodes + This->nodePool->used)) { |
609 | node--; |
610 | if (node < This->nodePool->nodes) |
611 | node = nullptr; |
612 | } else { |
613 | NewedNode *nn = (NewedNode *)node; |
614 | node = nn->nextNewed; |
615 | |
616 | if (node == nullptr && This->nodePool && This->nodePool->used) |
617 | node = This->nodePool->nodes + This->nodePool->used - 1; |
618 | } |
619 | |
620 | Data rv; |
621 | rv.n = node; |
622 | rv.p = d.p; |
623 | return rv; |
624 | } |
625 | |
626 | template<class T> |
627 | template<typename StringHash, typename Data> |
628 | Data QStringHash<T>::iterateFirst(StringHash *self) |
629 | { |
630 | typename StringHash::Node *n = nullptr; |
631 | if (self->newedNodes) |
632 | n = self->newedNodes; |
633 | else if (self->nodePool && self->nodePool->used) |
634 | n = self->nodePool->nodes + self->nodePool->used - 1; |
635 | |
636 | Data rv; |
637 | rv.n = n; |
638 | rv.p = self; |
639 | return rv; |
640 | } |
641 | |
642 | template<class T> |
643 | typename QStringHash<T>::Node *QStringHash<T>::createNode(const Node &o) |
644 | { |
645 | Node *n = takeNode(o); |
646 | return insertNode(n, n->hash); |
647 | } |
648 | |
649 | template<class T> |
650 | template<class K> |
651 | typename QStringHash<T>::Node *QStringHash<T>::createNode(const K &key, const T &value) |
652 | { |
653 | Node *n = takeNode(key, value); |
654 | return insertNode(n, hashOf(key)); |
655 | } |
656 | |
657 | template<class T> |
658 | typename QStringHash<T>::Node *QStringHash<T>::insertNode(Node *n, quint32 hash) |
659 | { |
660 | if (data.size >= data.numBuckets) |
661 | data.rehashToBits(bits: data.numBits + 1); |
662 | |
663 | int bucket = hash % data.numBuckets; |
664 | n->next = data.buckets[bucket]; |
665 | data.buckets[bucket] = n; |
666 | |
667 | data.size++; |
668 | |
669 | return n; |
670 | } |
671 | |
672 | template<class T> |
673 | template<class K> |
674 | void QStringHash<T>::insert(const K &key, const T &value) |
675 | { |
676 | Node *n = findNode(key); |
677 | if (n) |
678 | n->value = value; |
679 | else |
680 | createNode(key, value); |
681 | } |
682 | |
683 | template<class T> |
684 | void QStringHash<T>::insert(const MutableIterator &iter) |
685 | { |
686 | insert(iter.key(), iter.value()); |
687 | } |
688 | |
689 | template<class T> |
690 | void QStringHash<T>::insert(const ConstIterator &iter) |
691 | { |
692 | insert(iter.key(), iter.value()); |
693 | } |
694 | |
695 | template<class T> |
696 | template<class K> |
697 | typename QStringHash<T>::Node *QStringHash<T>::findNode(const K &key) const |
698 | { |
699 | QStringHashNode *node = data.numBuckets?data.buckets[hashOf(key) % data.numBuckets]:nullptr; |
700 | |
701 | typename HashedForm<K>::Type hashedKey(hashedString(key)); |
702 | while (node && !node->equals(hashedKey)) |
703 | node = (*node->next); |
704 | |
705 | return (Node *)node; |
706 | } |
707 | |
708 | template<class T> |
709 | template<class K> |
710 | T *QStringHash<T>::value(const K &key) const |
711 | { |
712 | Node *n = findNode(key); |
713 | return n?&n->value:nullptr; |
714 | } |
715 | |
716 | template<typename T> |
717 | T *QStringHash<T>::value(const MutableIterator &iter) const |
718 | { |
719 | return value(iter.node()->key()); |
720 | } |
721 | |
722 | template<class T> |
723 | T *QStringHash<T>::value(const ConstIterator &iter) const |
724 | { |
725 | return value(iter.node()->key()); |
726 | } |
727 | |
728 | template<class T> |
729 | T *QStringHash<T>::value(const QV4::String *string) const |
730 | { |
731 | Node *n = findNode(string); |
732 | return n?&n->value:nullptr; |
733 | } |
734 | |
735 | template<class T> |
736 | template<class K> |
737 | bool QStringHash<T>::contains(const K &key) const |
738 | { |
739 | return nullptr != value(key); |
740 | } |
741 | |
742 | template<class T> |
743 | template<class K> |
744 | T &QStringHash<T>::operator[](const K &key) |
745 | { |
746 | Node *n = findNode(key); |
747 | if (n) return n->value; |
748 | else return createNode(key, T())->value; |
749 | } |
750 | |
751 | template<class T> |
752 | void QStringHash<T>::reserve(int n) |
753 | { |
754 | if (nodePool || 0 == n) |
755 | return; |
756 | |
757 | nodePool = new ReservedNodePool; |
758 | nodePool->count = n; |
759 | nodePool->used = 0; |
760 | nodePool->nodes = new Node[n]; |
761 | |
762 | data.rehashToSize(size: n); |
763 | } |
764 | |
765 | template<class T> |
766 | typename QStringHash<T>::MutableIterator QStringHash<T>::begin() |
767 | { |
768 | return MutableIterator(iterateFirst<QStringHash<T>, MutableIteratorData>(this)); |
769 | } |
770 | |
771 | template<class T> |
772 | typename QStringHash<T>::ConstIterator QStringHash<T>::begin() const |
773 | { |
774 | return ConstIterator(iterateFirst<const QStringHash<T>, ConstIteratorData>(this)); |
775 | } |
776 | |
777 | template<class T> |
778 | typename QStringHash<T>::MutableIterator QStringHash<T>::end() |
779 | { |
780 | return MutableIterator(); |
781 | } |
782 | |
783 | template<class T> |
784 | typename QStringHash<T>::ConstIterator QStringHash<T>::end() const |
785 | { |
786 | return ConstIterator(); |
787 | } |
788 | |
789 | template<class T> |
790 | template<class K> |
791 | typename QStringHash<T>::MutableIterator QStringHash<T>::find(const K &key) |
792 | { |
793 | Node *n = findNode(key); |
794 | return n ? MutableIterator(MutableIteratorData(n, this)) : MutableIterator(); |
795 | } |
796 | |
797 | template<class T> |
798 | template<class K> |
799 | typename QStringHash<T>::ConstIterator QStringHash<T>::find(const K &key) const |
800 | { |
801 | Node *n = findNode(key); |
802 | return n ? ConstIterator(ConstIteratorData(n, this)) : ConstIterator(); |
803 | } |
804 | |
805 | QT_END_NAMESPACE |
806 | |
807 | #endif // QSTRINGHASH_P_H |
808 | |