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

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