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 | |
25 | QT_BEGIN_NAMESPACE |
26 | |
27 | static inline QString::DataPointer &mutableStringData(const QHashedString &key) |
28 | { |
29 | return const_cast<QHashedString &>(key).data_ptr(); |
30 | } |
31 | |
32 | class QStringHashData; |
33 | class QStringHashNode |
34 | { |
35 | public: |
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 | |
144 | class QStringHashData |
145 | { |
146 | Q_DISABLE_COPY_MOVE(QStringHashData) |
147 | public: |
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? |
220 | template<typename T> |
221 | struct HashedForm {}; |
222 | |
223 | template<> struct HashedForm<QString> { typedef QHashedString Type; }; |
224 | template<> struct HashedForm<QStringView> { typedef QHashedStringRef Type; }; |
225 | template<> struct HashedForm<QHashedString> { typedef const QHashedString &Type; }; |
226 | template<> struct HashedForm<QV4::String *> { typedef const QV4::String *Type; }; |
227 | template<> struct HashedForm<const QV4::String *> { typedef const QV4::String *Type; }; |
228 | template<> struct HashedForm<QHashedStringRef> { typedef const QHashedStringRef &Type; }; |
229 | template<> struct HashedForm<QLatin1String> { typedef QHashedCStringRef Type; }; |
230 | template<> struct HashedForm<QHashedCStringRef> { typedef const QHashedCStringRef &Type; }; |
231 | |
232 | class QStringHashBase |
233 | { |
234 | public: |
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 | |
269 | template<class T> |
270 | class QStringHash : public QStringHashBase |
271 | { |
272 | public: |
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 | |
333 | public: |
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 | |
412 | template<class T> |
413 | QStringHash<T>::QStringHash() |
414 | : newedNodes(nullptr), nodePool(nullptr) |
415 | { |
416 | } |
417 | |
418 | template<class T> |
419 | QStringHash<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 | |
428 | template<class T> |
429 | QStringHash<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 | |
444 | template<class T> |
445 | void 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 | |
453 | template<class T> |
454 | QStringHash<T>::~QStringHash() |
455 | { |
456 | clear(); |
457 | } |
458 | |
459 | template<class T> |
460 | void 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 | |
482 | template<class T> |
483 | bool QStringHash<T>::isEmpty() const |
484 | { |
485 | return data.size== 0; |
486 | } |
487 | |
488 | template<class T> |
489 | int QStringHash<T>::count() const |
490 | { |
491 | return data.size; |
492 | } |
493 | |
494 | template<class T> |
495 | int QStringHash<T>::numBuckets() const |
496 | { |
497 | return data.numBuckets; |
498 | } |
499 | |
500 | template<class T> |
501 | void 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 | |
512 | template<class T> |
513 | void 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 | |
520 | template<class T> |
521 | template<class K> |
522 | typename 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 | |
537 | template<class T> |
538 | typename 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 | |
564 | template<class T> |
565 | void 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 | |
578 | template<class T> |
579 | void 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 | |
596 | template<class T> |
597 | template<typename Data> |
598 | Data 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 | |
622 | template<class T> |
623 | template<typename StringHash, typename Data> |
624 | Data 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 | |
638 | template<class T> |
639 | typename QStringHash<T>::Node *QStringHash<T>::createNode(const Node &o) |
640 | { |
641 | Node *n = takeNode(o); |
642 | return insertNode(n, n->hash); |
643 | } |
644 | |
645 | template<class T> |
646 | template<class K> |
647 | typename 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 | |
653 | template<class T> |
654 | typename 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 | |
668 | template<class T> |
669 | template<class K> |
670 | void 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 | |
679 | template<class T> |
680 | void QStringHash<T>::insert(const MutableIterator &iter) |
681 | { |
682 | insert(iter.key(), iter.value()); |
683 | } |
684 | |
685 | template<class T> |
686 | void QStringHash<T>::insert(const ConstIterator &iter) |
687 | { |
688 | insert(iter.key(), iter.value()); |
689 | } |
690 | |
691 | template<class T> |
692 | template<class K> |
693 | typename 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 | |
704 | template<class T> |
705 | template<class K> |
706 | T *QStringHash<T>::value(const K &key) const |
707 | { |
708 | Node *n = findNode(key); |
709 | return n?&n->value:nullptr; |
710 | } |
711 | |
712 | template<typename T> |
713 | T *QStringHash<T>::value(const MutableIterator &iter) const |
714 | { |
715 | return value(iter.node()->key()); |
716 | } |
717 | |
718 | template<class T> |
719 | T *QStringHash<T>::value(const ConstIterator &iter) const |
720 | { |
721 | return value(iter.node()->key()); |
722 | } |
723 | |
724 | template<class T> |
725 | T *QStringHash<T>::value(const QV4::String *string) const |
726 | { |
727 | Node *n = findNode(string); |
728 | return n?&n->value:nullptr; |
729 | } |
730 | |
731 | template<class T> |
732 | template<class K> |
733 | bool QStringHash<T>::contains(const K &key) const |
734 | { |
735 | return nullptr != value(key); |
736 | } |
737 | |
738 | template<class T> |
739 | template<class K> |
740 | T &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 | |
747 | template<class T> |
748 | void 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 | |
761 | template<class T> |
762 | typename QStringHash<T>::MutableIterator QStringHash<T>::begin() |
763 | { |
764 | return MutableIterator(iterateFirst<QStringHash<T>, MutableIteratorData>(this)); |
765 | } |
766 | |
767 | template<class T> |
768 | typename QStringHash<T>::ConstIterator QStringHash<T>::begin() const |
769 | { |
770 | return ConstIterator(iterateFirst<const QStringHash<T>, ConstIteratorData>(this)); |
771 | } |
772 | |
773 | template<class T> |
774 | typename QStringHash<T>::MutableIterator QStringHash<T>::end() |
775 | { |
776 | return MutableIterator(); |
777 | } |
778 | |
779 | template<class T> |
780 | typename QStringHash<T>::ConstIterator QStringHash<T>::end() const |
781 | { |
782 | return ConstIterator(); |
783 | } |
784 | |
785 | template<class T> |
786 | template<class K> |
787 | typename 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 | |
793 | template<class T> |
794 | template<class K> |
795 | typename 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 | |
801 | QT_END_NAMESPACE |
802 | |
803 | #endif // QSTRINGHASH_P_H |
804 | |