src/declarative/qml/ftw/qhashedstring_p.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** All rights reserved.
   5 ** Contact: http://www.qt-project.org/
   6 **
   7 ** This file is part of the QtDeclarative module of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #ifndef QHASHEDSTRING_P_H
  43 #define QHASHEDSTRING_P_H
  44
  45 //
  46 //  W A R N I N G
  47 //  -------------
  48 //
  49 // This file is not part of the Qt API.  It exists purely as an
  50 // implementation detail.  This header file may change from version to
  51 // version without notice, or even be removed.
  52 //
  53 // We mean it.
  54 //
  55
  56 #include <QtCore/qglobal.h>
  57 #include <QtCore/qstring.h>
  58 #include <private/qv8_p.h>
  59
  60 QT_BEGIN_NAMESPACE
  61
  62 class QHashedStringRef;
  63 class Q_AUTOTEST_EXPORT QHashedString : public QString
  64 {
  65 public:
  66     inline QHashedString();
  67     inline QHashedString(const QString &string);
  68     inline QHashedString(const QString &string, quint32);
  69     inline QHashedString(const QHashedString &string);
  70
  71     inline QHashedString &operator=(const QHashedString &string);
  72     inline bool operator==(const QHashedString &string) const;
  73     inline bool operator==(const QHashedStringRef &string) const;
  74
  75     inline quint32 hash() const;
  76     inline quint32 existingHash() const;
  77
  78     static inline bool isUpper(const QChar &);
  79
  80     static bool compare(const QChar *lhs, const QChar *rhs, int length);
  81     static inline bool compare(const QChar *lhs, const char *rhs, int length);
  82     static inline bool compare(const char *lhs, const char *rhs, int length);
  83 private:
  84     friend class QHashedStringRef;
  85     friend class QStringHashNode;
  86
  87     void computeHash() const;
  88     mutable quint32 m_hash;
  89 };
  90
  91 class Q_AUTOTEST_EXPORT QHashedV8String
  92 {
  93 public:
  94     inline QHashedV8String();
  95     explicit inline QHashedV8String(v8::Handle<v8::String>);
  96     inline QHashedV8String(const QHashedV8String &string);
  97     inline QHashedV8String &operator=(const QHashedV8String &other);
  98
  99     inline bool operator==(const QHashedV8String &string);
 100
 101     inline quint32 hash() const;
 102     inline int length() const;
 103     inline quint32 symbolId() const;
 104
 105     inline v8::Handle<v8::String> string() const;
 106
 107     inline QString toString() const;
 108
 109 private:
 110     v8::String::CompleteHashData m_hash;
 111     v8::Handle<v8::String> m_string;
 112 };
 113
 114 class QHashedCStringRef;
 115 class Q_AUTOTEST_EXPORT QHashedStringRef
 116 {
 117 public:
 118     inline QHashedStringRef();
 119     inline QHashedStringRef(const QString &);
 120     inline QHashedStringRef(const QStringRef &);
 121     inline QHashedStringRef(const QChar *, int);
 122     inline QHashedStringRef(const QChar *, int, quint32);
 123     inline QHashedStringRef(const QHashedString &);
 124     inline QHashedStringRef(const QHashedStringRef &);
 125     inline QHashedStringRef &operator=(const QHashedStringRef &);
 126
 127     inline bool operator==(const QString &string) const;
 128     inline bool operator==(const QHashedString &string) const;
 129     inline bool operator==(const QHashedStringRef &string) const;
 130     inline bool operator==(const QHashedCStringRef &string) const;
 131     inline bool operator!=(const QString &string) const;
 132     inline bool operator!=(const QHashedString &string) const;
 133     inline bool operator!=(const QHashedStringRef &string) const;
 134     inline bool operator!=(const QHashedCStringRef &string) const;
 135
 136     inline quint32 hash() const;
 137
 138     inline const QChar &at(int) const;
 139     inline const QChar *constData() const;
 140     bool startsWith(const QString &) const;
 141     bool endsWith(const QString &) const;
 142     QHashedStringRef mid(int, int) const;
 143
 144     inline bool isEmpty() const;
 145     inline int length() const;
 146     inline bool startsWithUpper() const;
 147
 148     QString toString() const;
 149
 150     inline int utf8length() const;
 151     QByteArray toUtf8() const;
 152     void writeUtf8(char *) const;
 153 private:
 154     friend class QHashedString;
 155
 156     void computeHash() const;
 157     void computeUtf8Length() const;
 158
 159     const QChar *m_data;
 160     int m_length;
 161     mutable int m_utf8length;
 162     mutable quint32 m_hash;
 163 };
 164
 165 class Q_AUTOTEST_EXPORT QHashedCStringRef
 166 {
 167 public:
 168     inline QHashedCStringRef();
 169     inline QHashedCStringRef(const char *, int);
 170     inline QHashedCStringRef(const char *, int, quint32);
 171     inline QHashedCStringRef(const QHashedCStringRef &);
 172
 173     inline quint32 hash() const;
 174
 175     inline const char *constData() const;
 176     inline int length() const;
 177
 178     QString toUtf16() const;
 179     inline int utf16length() const;
 180     inline void writeUtf16(QChar *) const;
 181     inline void writeUtf16(uint16_t *) const;
 182 private:
 183     friend class QHashedStringRef;
 184
 185     void computeHash() const;
 186
 187     const char *m_data;
 188     int m_length;
 189     mutable quint32 m_hash;
 190 };
 191
 192 class QStringHashData;
 193 class Q_AUTOTEST_EXPORT QStringHashNode
 194 {
 195 public:
 196     QStringHashNode()
 197     : nlist(0), next(0), length(0), hash(0), pooled(0), ckey(0), ukey(0), symbolId()
 198     {
 199     }
 200
 201     QStringHashNode(const QHashedString &key)
 202     : nlist(0), next(0), length(key.length()), hash(key.hash()), pooled(0), ckey(0), key(key),
 203       ukey(key.constData()), symbolId(0) {
 204     }
 205
 206     QStringHashNode(const QHashedCStringRef &key)
 207     : nlist(0), next(0), length(key.length()), hash(key.hash()), pooled(0), ckey(key.constData()),
 208       ukey(0), symbolId(0) {
 209     }
 210
 211     QStringHashNode(const QStringHashNode &o)
 212     : nlist(0), next(0), length(o.length), hash(o.hash), pooled(0), ckey(o.ckey), key(o.key),
 213       ukey(o.ukey), symbolId(o.symbolId) {
 214     }
 215
 216     QStringHashNode *nlist;
 217     QStringHashNode *next;
 218     qint32 length;
 219     quint32 hash;
 220
 221     quint32 pooled:1;
 222     const char *ckey;
 223     QString key;
 224     const QChar *ukey;
 225
 226     quint32 symbolId;
 227
 228     inline bool equals(v8::Handle<v8::String> string) {
 229         return ckey?string->Equals((char*)ckey, length):
 230                     string->Equals((uint16_t*)ukey, length);
 231     }
 232
 233     inline bool symbolEquals(const QHashedV8String &string) {
 234         Q_ASSERT(string.symbolId() != 0);
 235         return length == string.length() && hash == string.hash() &&
 236                (string.symbolId() == symbolId || equals(string.string()));
 237     }
 238
 239     inline bool equals(const QHashedV8String &string) {
 240         return length == string.length() && hash == string.hash() &&
 241                equals(string.string());
 242     }
 243
 244     inline bool equals(const QHashedStringRef &string) {
 245         return length == string.length() &&
 246                hash == string.hash() &&
 247                (ckey?(QHashedString::compare(string.constData(), ckey, length)):
 248                      (QHashedString::compare(string.constData(), ukey, length)));
 249     }
 250
 251     inline bool equals(const QHashedCStringRef &string) {
 252         return length == string.length() &&
 253                hash == string.hash() &&
 254                (ckey?(QHashedString::compare(string.constData(), ckey, length)):
 255                      (QHashedString::compare(ukey, string.constData(), length)));
 256     }
 257 };
 258
 259 class Q_AUTOTEST_EXPORT QStringHashData
 260 {
 261 public:
 262     QStringHashData()
 263     : nodes(0), buckets(0), numBuckets(0), size(0), numBits(0) {}
 264
 265     QStringHashNode *nodes;
 266     QStringHashNode **buckets;
 267     int numBuckets;
 268     int size;
 269     short numBits;
 270
 271     void rehashToBits(short);
 272     void rehashToSize(int);
 273
 274 private:
 275     QStringHashData(const QStringHashData &);
 276     QStringHashData &operator=(const QStringHashData &);
 277 };
 278
 279 template<class T, int SmallThreshold = 0>
 280 class QStringHash
 281 {
 282 public:
 283     struct Node : public QStringHashNode {
 284         Node(const QHashedString &key, const T &value) : QStringHashNode(key), value(value) {}
 285         Node(const QHashedCStringRef &key, const T &value) : QStringHashNode(key), value(value) {}
 286         Node(const Node &o) : QStringHashNode(o), value(o.value) {}
 287         Node() {}
 288         T value;
 289     };
 290     struct ReservedNodePool
 291     {
 292         ReservedNodePool() : count(0), used(0), nodes(0) {}
 293         ~ReservedNodePool() { delete [] nodes; }
 294         int count;
 295         int used;
 296         Node *nodes;
 297     };
 298
 299     QStringHashData data;
 300     ReservedNodePool *nodePool;
 301
 302     inline Node *findNode(const QString &) const;
 303     inline Node *findNode(const QHashedString &) const;
 304     inline Node *findNode(const QHashedStringRef &) const;
 305     inline Node *findNode(const QHashedCStringRef &) const;
 306     inline Node *findNode(const QHashedV8String &) const;
 307     inline Node *findSymbolNode(const QHashedV8String &) const;
 308     inline Node *createNode(const QHashedString &, const T &);
 309     inline Node *createNode(const QHashedCStringRef &, const T &);
 310
 311     inline Node *takeNode(const QHashedString &key, const T &value);
 312     inline Node *takeNode(const QHashedCStringRef &key, const T &value);
 313     inline Node *takeNode(const Node &o);
 314
 315     inline void copy(const QStringHash<T,SmallThreshold> &);
 316 public:
 317     inline QStringHash();
 318     inline QStringHash(const QStringHash &);
 319     inline ~QStringHash();
 320
 321     QStringHash &operator=(const QStringHash<T,SmallThreshold> &);
 322
 323     void copyAndReserve(const QStringHash<T,SmallThreshold> &other, int additionalReserve);
 324
 325     inline bool isEmpty() const;
 326     inline void clear();
 327     inline int count() const;
 328
 329     inline void insert(const QString &, const T &);
 330     inline void insert(const QHashedString &, const T &);
 331     inline void insert(const QHashedStringRef &, const T &);
 332     inline void insert(const QHashedCStringRef &, const T &);
 333
 334     inline T *value(const QString &) const;
 335     inline T *value(const QHashedString &) const;
 336     inline T *value(const QHashedStringRef &) const;
 337     inline T *value(const QHashedV8String &) const;
 338     inline T *value(const QHashedCStringRef &) const;
 339
 340     inline bool contains(const QString &) const;
 341     inline bool contains(const QHashedString &) const;
 342     inline bool contains(const QHashedStringRef &) const;
 343     inline bool contains(const QHashedCStringRef &) const;
 344
 345     T &operator[](const QString &);
 346     T &operator[](const QHashedString &);
 347     T &operator[](const QHashedStringRef &);
 348     T &operator[](const QHashedCStringRef &);
 349
 350     class ConstIterator {
 351     public:
 352         ConstIterator() : n(0) {}
 353         ConstIterator(Node *n) : n(n) {}
 354
 355         ConstIterator &operator++() { n = (Node *)n->nlist; return *this; }
 356         bool operator==(const ConstIterator &o) const { return n == o.n; }
 357         bool operator!=(const ConstIterator &o) const { return n != o.n; }
 358
 359         QHashedString key() const {
 360             if (n->ckey) {
 361                 return QHashedString(QString::fromLatin1(n->ckey, n->length), n->hash);
 362             } else {
 363                 return QHashedString(n->key, n->hash);
 364             }
 365         }
 366         const T &value() const { return n->value; }
 367         const T &operator*() const { return n->value; }
 368     private:
 369         Node *n;
 370     };
 371
 372     ConstIterator begin() const { return ConstIterator((Node *)data.nodes); }
 373     ConstIterator end() const { return ConstIterator(); }
 374
 375     inline void reserve(int);
 376 };
 377
 378 template<class T, int SmallThreshold>
 379 QStringHash<T,SmallThreshold>::QStringHash()
 380 : nodePool(0)
 381 {
 382 }
 383
 384 template<class T, int SmallThreshold>
 385 QStringHash<T,SmallThreshold>::QStringHash(const QStringHash<T,SmallThreshold> &other)
 386 : nodePool(0)
 387 {
 388     data.numBits = other.data.numBits;
 389     data.size = other.data.size;
 390     reserve(other.count());
 391     copy(other);
 392 }
 393
 394 template<class T, int SmallThreshold>
 395 QStringHash<T,SmallThreshold> &QStringHash<T,SmallThreshold>::operator=(const QStringHash<T,SmallThreshold> &other)
 396 {
 397     if (&other == this)
 398         return *this;
 399
 400     clear();
 401
 402     data.numBits = other.data.numBits;
 403     data.size = other.data.size;
 404     reserve(other.count());
 405     copy(other);
 406
 407     return *this;
 408 }
 409
 410 template<class T, int SmallThreshold>
 411 void QStringHash<T,SmallThreshold>::copyAndReserve(const QStringHash<T,SmallThreshold> &other, int additionalReserve)
 412 {
 413     clear();
 414
 415     data.numBits = other.data.numBits;
 416     data.size = other.data.size;;
 417     reserve(other.count() + additionalReserve);
 418     copy(other);
 419 }
 420
 421 template<class T, int SmallThreshold>
 422 QStringHash<T,SmallThreshold>::~QStringHash()
 423 {
 424     clear();
 425 }
 426
 427 template<class T, int SmallThreshold>
 428 void QStringHash<T,SmallThreshold>::clear()
 429 {
 430     // If all the nodes were allocated from the node pool, we
 431     // don't need to clean them individually
 432     if (!nodePool || data.size != nodePool->used) {
 433         QStringHashNode *n = data.nodes;
 434         while (n) {
 435             Node *o = (Node *)n;
 436             n = n->nlist;
 437             if (!o->pooled) delete o;
 438         }
 439     }
 440     if (nodePool) delete nodePool;
 441     delete [] data.buckets;
 442
 443     data.nodes = 0;
 444     data.buckets = 0;
 445     data.numBuckets = 0;
 446     data.numBits = 0;
 447     data.size = 0;
 448
 449     nodePool = 0;
 450 }
 451
 452 template<class T, int SmallThreshold>
 453 bool QStringHash<T,SmallThreshold>::isEmpty() const
 454 {
 455     return data.nodes == 0;
 456 }
 457
 458 template<class T, int SmallThreshold>
 459 int QStringHash<T,SmallThreshold>::count() const
 460 {
 461     return data.size;
 462 }
 463
 464 template<class T, int SmallThreshold>
 465 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::takeNode(const QHashedString &key, const T &value)
 466 {
 467     if (nodePool && nodePool->used != nodePool->count) {
 468         Node *rv = nodePool->nodes + nodePool->used++;
 469         rv->length = key.length();
 470         rv->hash = key.hash();
 471         rv->key = key;
 472         rv->ukey = rv->key.constData();
 473         rv->pooled = 1;
 474         rv->value = value;
 475         return rv;
 476     } else {
 477         return new Node(key, value);
 478     }
 479 }
 480
 481 template<class T, int SmallThreshold>
 482 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::takeNode(const QHashedCStringRef &key, const T &value)
 483 {
 484     if (nodePool && nodePool->used != nodePool->count) {
 485         Node *rv = nodePool->nodes + nodePool->used++;
 486         rv->length = key.length();
 487         rv->hash = key.hash();
 488         rv->ckey = key.constData();
 489         rv->pooled = 1;
 490         rv->value = value;
 491         return rv;
 492     } else {
 493         return new Node(key, value);
 494     }
 495 }
 496
 497 template<class T, int SmallThreshold>
 498 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::takeNode(const Node &o)
 499 {
 500     if (nodePool && nodePool->used != nodePool->count) {
 501         Node *rv = nodePool->nodes + nodePool->used++;
 502         rv->length = o.length;
 503         rv->hash = o.hash;
 504         rv->ckey = o.ckey;
 505         rv->key = o.key;
 506         rv->ukey = o.ukey;
 507         rv->pooled = 1;
 508         rv->symbolId = o.symbolId;
 509         rv->value = o.value;
 510         return rv;
 511     } else {
 512         return new Node(o);
 513     }
 514 }
 515
 516 template<class T, int SmallThreshold>
 517 void QStringHash<T,SmallThreshold>::copy(const QStringHash<T,SmallThreshold> &other)
 518 {
 519     Q_ASSERT(data.nodes == 0);
 520
 521     if (other.data.size <= SmallThreshold) {
 522         QStringHashNode *n = other.data.nodes;
 523         while (n) {
 524             Node *o = (Node *)n;
 525             Node *mynode = takeNode(*o);
 526             mynode->nlist = data.nodes;
 527             mynode->next = data.nodes;
 528             data.nodes = mynode;
 529
 530             n = o->nlist;
 531         }
 532     } else {
 533         // Ensure buckets array is created
 534         data.rehashToBits(data.numBits);
 535
 536         QStringHashNode *n = other.data.nodes;
 537         while (n) {
 538             Node *o = (Node *)n;
 539             Node *mynode = takeNode(*o);
 540             mynode->nlist = data.nodes;
 541             data.nodes = mynode;
 542
 543             int bucket = mynode->hash % data.numBuckets;
 544             mynode->next = data.buckets[bucket];
 545             data.buckets[bucket] = mynode;
 546
 547             n = o->nlist;
 548         }
 549     }
 550 }
 551
 552 template<class T, int SmallThreshold>
 553 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::createNode(const QHashedString &key, const T &value)
 554 {
 555     Node *n = takeNode(key, value);
 556
 557     if (data.size < SmallThreshold) {
 558
 559         n->nlist = data.nodes;
 560         n->next = data.nodes;
 561         data.nodes = n;
 562
 563     } else {
 564         if (data.size >= data.numBuckets)
 565             data.rehashToBits(data.numBits + 1);
 566
 567         n->nlist = data.nodes;
 568         data.nodes = n;
 569
 570         int bucket = key.hash() % data.numBuckets;
 571         n->next = data.buckets[bucket];
 572         data.buckets[bucket] = n;
 573     }
 574
 575     data.size++;
 576
 577     return n;
 578 }
 579
 580 template<class T, int SmallThreshold>
 581 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::createNode(const QHashedCStringRef &key, const T &value)
 582 {
 583     Node *n = takeNode(key, value);
 584
 585     if (data.size < SmallThreshold) {
 586
 587         n->nlist = data.nodes;
 588         n->next = data.nodes;
 589         data.nodes = n;
 590
 591     } else {
 592         if (data.size >= data.numBuckets)
 593             data.rehashToBits(data.numBits + 1);
 594
 595         n->nlist = data.nodes;
 596         data.nodes = n;
 597
 598         int bucket = key.hash() % data.numBuckets;
 599         n->next = data.buckets[bucket];
 600         data.buckets[bucket] = n;
 601     }
 602
 603     data.size++;
 604
 605     return n;
 606 }
 607
 608 template<class T, int SmallThreshold>
 609 void QStringHash<T,SmallThreshold>::insert(const QString &key, const T &value)
 610 {
 611     QHashedStringRef ch(key);
 612     Node *n = findNode(key);
 613     if (n) n->value = value;
 614     else createNode(QHashedString(key, ch.hash()), value);
 615 }
 616
 617 template<class T, int SmallThreshold>
 618 void QStringHash<T,SmallThreshold>::insert(const QHashedString &key, const T &value)
 619 {
 620     Node *n = findNode(key);
 621     if (n) n->value = value;
 622     else createNode(key, value);
 623 }
 624
 625 template<class T, int SmallThreshold>
 626 void QStringHash<T,SmallThreshold>::insert(const QHashedStringRef &key, const T &value)
 627 {
 628     Node *n = findNode(key);
 629     if (n) n->value = value;
 630     else createNode(key, value);
 631 }
 632
 633 template<class T, int SmallThreshold>
 634 void QStringHash<T,SmallThreshold>::insert(const QHashedCStringRef &key, const T &value)
 635 {
 636     Node *n = findNode(key);
 637     if (n) n->value = value;
 638     else createNode(key, value);
 639 }
 640
 641 template<class T, int SmallThreshold>
 642 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findNode(const QString &string) const
 643 {
 644     return findNode(QHashedStringRef(string));
 645 }
 646
 647 template<class T, int SmallThreshold>
 648 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findNode(const QHashedString &string) const
 649 {
 650     return findNode(QHashedStringRef(string.constData(), string.length(), string.hash()));
 651 }
 652
 653 template<class T, int SmallThreshold>
 654 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findNode(const QHashedStringRef &string) const
 655 {
 656     QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets];
 657     while (node && !node->equals(string))
 658         node = node->next;
 659
 660     return (Node *)node;
 661 }
 662
 663 template<class T, int SmallThreshold>
 664 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findNode(const QHashedCStringRef &string) const
 665 {
 666     QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets];
 667     while (node && !node->equals(string))
 668         node = node->next;
 669
 670     return (Node *)node;
 671 }
 672
 673 template<class T, int SmallThreshold>
 674 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findNode(const QHashedV8String &string) const
 675 {
 676     QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets];
 677     while (node && !node->equals(string))
 678         node = node->next;
 679
 680     return (Node *)node;
 681 }
 682
 683 template<class T, int SmallThreshold>
 684 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findSymbolNode(const QHashedV8String &string) const
 685 {
 686     Q_ASSERT(string.symbolId() != 0);
 687
 688     QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets];
 689     while (node && !node->symbolEquals(string))
 690         node = node->next;
 691
 692     if (node)
 693         node->symbolId = string.symbolId();
 694
 695     return (Node *)node;
 696 }
 697
 698 template<class T, int SmallThreshold>
 699 T *QStringHash<T,SmallThreshold>::value(const QString &key) const
 700 {
 701     Node *n = findNode(key);
 702     return n?&n->value:0;
 703 }
 704
 705 template<class T, int SmallThreshold>
 706 T *QStringHash<T,SmallThreshold>::value(const QHashedString &key) const
 707 {
 708     Node *n = findNode(key);
 709     return n?&n->value:0;
 710 }
 711
 712 template<class T, int SmallThreshold>
 713 T *QStringHash<T,SmallThreshold>::value(const QHashedStringRef &key) const
 714 {
 715     Node *n = findNode(key);
 716     return n?&n->value:0;
 717 }
 718
 719 template<class T, int SmallThreshold>
 720 T *QStringHash<T,SmallThreshold>::value(const QHashedCStringRef &key) const
 721 {
 722     Node *n = findNode(key);
 723     return n?&n->value:0;
 724 }
 725
 726 template<class T, int SmallThreshold>
 727 T *QStringHash<T,SmallThreshold>::value(const QHashedV8String &string) const
 728 {
 729     Node *n = string.symbolId()?findSymbolNode(string):findNode(string);
 730     return n?&n->value:0;
 731 }
 732
 733 template<class T, int SmallThreshold>
 734 bool QStringHash<T,SmallThreshold>::contains(const QString &s) const
 735 {
 736     return 0 != value(s);
 737 }
 738
 739 template<class T, int SmallThreshold>
 740 bool QStringHash<T,SmallThreshold>::contains(const QHashedString &s) const
 741 {
 742     return 0 != value(s);
 743 }
 744
 745 template<class T, int SmallThreshold>
 746 bool QStringHash<T,SmallThreshold>::contains(const QHashedStringRef &s) const
 747 {
 748     return 0 != value(s);
 749 }
 750
 751 template<class T, int SmallThreshold>
 752 bool QStringHash<T,SmallThreshold>::contains(const QHashedCStringRef &s) const
 753 {
 754     return 0 != value(s);
 755 }
 756
 757 template<class T, int SmallThreshold>
 758 T &QStringHash<T,SmallThreshold>::operator[](const QString &key)
 759 {
 760     QHashedStringRef cs(key);
 761     Node *n = findNode(cs);
 762     if (n) return n->value;
 763     else return createNode(QHashedString(key, cs.hash()), T())->value;
 764 }
 765
 766 template<class T, int SmallThreshold>
 767 T &QStringHash<T,SmallThreshold>::operator[](const QHashedString &key)
 768 {
 769     Node *n = findNode(key);
 770     if (n) return n->value;
 771     else return createNode(key, T())->value;
 772 }
 773
 774 template<class T, int SmallThreshold>
 775 T &QStringHash<T,SmallThreshold>::operator[](const QHashedStringRef &key)
 776 {
 777     Node *n = findNode(key);
 778     if (n) return n->value;
 779     else return createNode(key, T())->value;
 780 }
 781
 782 template<class T, int SmallThreshold>
 783 T &QStringHash<T,SmallThreshold>::operator[](const QHashedCStringRef &key)
 784 {
 785     Node *n = findNode(key);
 786     if (n) return n->value;
 787     else return createNode(key, T())->value;
 788 }
 789
 790 template<class T, int SmallThreshold>
 791 void QStringHash<T,SmallThreshold>::reserve(int n)
 792 {
 793     if (nodePool || 0 == n)
 794         return;
 795     nodePool = new ReservedNodePool;
 796     nodePool->count = n;
 797     nodePool->used = 0;
 798     nodePool->nodes = new Node[n];
 799
 800     if (n > SmallThreshold)
 801         data.rehashToSize(n);
 802 }
 803
 804 inline uint qHash(const QHashedString &string)
 805 {
 806     return uint(string.hash());
 807 }
 808
 809 inline uint qHash(const QHashedStringRef &string)
 810 {
 811     return uint(string.hash());
 812 }
 813
 814 QHashedString::QHashedString()
 815 : QString(), m_hash(0)
 816 {
 817 }
 818
 819 QHashedString::QHashedString(const QString &string)
 820 : QString(string), m_hash(0)
 821 {
 822 }
 823
 824 QHashedString::QHashedString(const QString &string, quint32 hash)
 825 : QString(string), m_hash(hash)
 826 {
 827 }
 828
 829 QHashedString::QHashedString(const QHashedString &string)
 830 : QString(string), m_hash(string.m_hash)
 831 {
 832 }
 833
 834 QHashedString &QHashedString::operator=(const QHashedString &string)
 835 {
 836     static_cast<QString &>(*this) = string;
 837     m_hash = string.m_hash;
 838     return *this;
 839 }
 840
 841 bool QHashedString::operator==(const QHashedString &string) const
 842 {
 843     return (string.m_hash == m_hash || !string.m_hash || !m_hash) &&
 844            static_cast<const QString &>(*this) == static_cast<const QString &>(string);
 845 }
 846
 847 bool QHashedString::operator==(const QHashedStringRef &string) const
 848 {
 849     return length() == string.m_length &&
 850            (string.m_hash == m_hash || !string.m_hash || !m_hash) &&
 851            QHashedString::compare(constData(), string.m_data, string.m_length);
 852 }
 853
 854 quint32 QHashedString::hash() const
 855 {
 856     if (!m_hash) computeHash();
 857     return m_hash;
 858 }
 859
 860 quint32 QHashedString::existingHash() const
 861 {
 862     return m_hash;
 863 }
 864
 865 bool QHashedString::isUpper(const QChar &qc)
 866 {
 867     ushort c = qc.unicode();
 868     // Optimize for _, a-z and A-Z.
 869     return ((c != '_' ) && (!(c >= 'a' && c <= 'z')) &&
 870            ((c >= 'A' && c <= 'Z') || QChar::category(c) == QChar::Letter_Uppercase));
 871 }
 872
 873 QHashedV8String::QHashedV8String()
 874 {
 875 }
 876
 877 QHashedV8String::QHashedV8String(v8::Handle<v8::String> string)
 878 : m_hash(string->CompleteHash()), m_string(string)
 879 {
 880     Q_ASSERT(!m_string.IsEmpty());
 881 }
 882
 883 QHashedV8String::QHashedV8String(const QHashedV8String &string)
 884 : m_hash(string.m_hash), m_string(string.m_string)
 885 {
 886 }
 887
 888 QHashedV8String &QHashedV8String::operator=(const QHashedV8String &other)
 889 {
 890     m_hash = other.m_hash;
 891     m_string = other.m_string;
 892     return *this;
 893 }
 894
 895 bool QHashedV8String::operator==(const QHashedV8String &string)
 896 {
 897     return m_hash.hash == string.m_hash.hash && m_hash.length == string.m_hash.length &&
 898            m_string.IsEmpty() == m_string.IsEmpty() &&
 899            (m_string.IsEmpty() || m_string->StrictEquals(string.m_string));
 900 }
 901
 902 quint32 QHashedV8String::hash() const
 903 {
 904     return m_hash.hash;
 905 }
 906
 907 int QHashedV8String::length() const
 908 {
 909     return m_hash.length;
 910 }
 911
 912 quint32 QHashedV8String::symbolId() const
 913 {
 914     return m_hash.symbol_id;
 915 }
 916
 917 v8::Handle<v8::String> QHashedV8String::string() const
 918 {
 919     return m_string;
 920 }
 921
 922 QString QHashedV8String::toString() const
 923 {
 924     QString result;
 925     result.reserve(m_hash.length);
 926
 927     for (int i = 0; i < m_hash.length; ++i)
 928         result.append(m_string->GetCharacter(i));
 929
 930     return result;
 931 }
 932
 933 QHashedStringRef::QHashedStringRef()
 934 : m_data(0), m_length(0), m_utf8length(-1), m_hash(0)
 935 {
 936 }
 937
 938 QHashedStringRef::QHashedStringRef(const QString &str)
 939 : m_data(str.constData()), m_length(str.length()), m_utf8length(0), m_hash(0)
 940 {
 941 }
 942
 943 QHashedStringRef::QHashedStringRef(const QStringRef &str)
 944 : m_data(str.constData()), m_length(str.length()), m_utf8length(0), m_hash(0)
 945 {
 946 }
 947
 948 QHashedStringRef::QHashedStringRef(const QChar *data, int length)
 949 : m_data(data), m_length(length), m_utf8length(0), m_hash(0)
 950 {
 951 }
 952
 953 QHashedStringRef::QHashedStringRef(const QChar *data, int length, quint32 hash)
 954 : m_data(data), m_length(length), m_utf8length(0), m_hash(hash)
 955 {
 956 }
 957
 958 QHashedStringRef::QHashedStringRef(const QHashedString &string)
 959 : m_data(string.constData()), m_length(string.length()), m_utf8length(0), m_hash(string.m_hash)
 960 {
 961 }
 962
 963 QHashedStringRef::QHashedStringRef(const QHashedStringRef &string)
 964 : m_data(string.m_data), m_length(string.m_length), m_utf8length(string.m_utf8length),
 965   m_hash(string.m_hash)
 966 {
 967 }
 968
 969 QHashedStringRef &QHashedStringRef::operator=(const QHashedStringRef &o)
 970 {
 971     m_data = o.m_data;
 972     m_length = o.m_length;
 973     m_utf8length = o.m_utf8length;
 974     m_hash = o.m_hash;
 975     return *this;
 976 }
 977
 978 bool QHashedStringRef::operator==(const QString &string) const
 979 {
 980     return m_length == string.length() &&
 981            QHashedString::compare(string.constData(), m_data, m_length);
 982 }
 983
 984 bool QHashedStringRef::operator==(const QHashedString &string) const
 985 {
 986     return m_length == string.length() &&
 987            (m_hash == string.m_hash || !m_hash || !string.m_hash) &&
 988            QHashedString::compare(string.constData(), m_data, m_length);
 989 }
 990
 991 bool QHashedStringRef::operator==(const QHashedStringRef &string) const
 992 {
 993     return m_length == string.m_length &&
 994            (m_hash == string.m_hash || !m_hash || !string.m_hash) &&
 995            QHashedString::compare(string.m_data, m_data, m_length);
 996 }
 997
 998 bool QHashedStringRef::operator==(const QHashedCStringRef &string) const
 999 {
1000     return m_length == string.m_length &&
1001            (m_hash == string.m_hash || !m_hash || !string.m_hash) &&
1002            QHashedString::compare(m_data, string.m_data, m_length);
1003 }
1004
1005 bool QHashedStringRef::operator!=(const QString &string) const
1006 {
1007     return m_length != string.length() ||
1008            !QHashedString::compare(string.constData(), m_data, m_length);
1009 }
1010
1011 bool QHashedStringRef::operator!=(const QHashedString &string) const
1012 {
1013     return m_length != string.length() ||
1014            (m_hash != string.m_hash && m_hash && string.m_hash) ||
1015            !QHashedString::compare(string.constData(), m_data, m_length);
1016 }
1017
1018 bool QHashedStringRef::operator!=(const QHashedStringRef &string) const
1019 {
1020     return m_length != string.m_length ||
1021            (m_hash != string.m_hash && m_hash && string.m_hash) ||
1022            QHashedString::compare(string.m_data, m_data, m_length);
1023 }
1024
1025 bool QHashedStringRef::operator!=(const QHashedCStringRef &string) const
1026 {
1027     return m_length != string.m_length ||
1028            (m_hash != string.m_hash && m_hash && string.m_hash) ||
1029            QHashedString::compare(m_data, string.m_data, m_length);
1030 }
1031
1032 const QChar &QHashedStringRef::at(int index) const
1033 {
1034     Q_ASSERT(index < m_length);
1035     return m_data[index];
1036 }
1037
1038 const QChar *QHashedStringRef::constData() const
1039 {
1040     return m_data;
1041 }
1042
1043 bool QHashedStringRef::isEmpty() const
1044 {
1045     return m_length == 0;
1046 }
1047
1048 int QHashedStringRef::length() const
1049 {
1050     return m_length;
1051 }
1052
1053 int QHashedStringRef::utf8length() const
1054 {
1055     if (m_utf8length < m_length)
1056         computeUtf8Length();
1057     return m_utf8length;
1058 }
1059
1060 bool QHashedStringRef::startsWithUpper() const
1061 {
1062     if (m_length < 1) return false;
1063     return QHashedString::isUpper(m_data[0]);
1064 }
1065
1066 quint32 QHashedStringRef::hash() const
1067 {
1068     if (!m_hash) computeHash();
1069     return m_hash;
1070 }
1071
1072 QHashedCStringRef::QHashedCStringRef()
1073 : m_data(0), m_length(0), m_hash(0)
1074 {
1075 }
1076
1077 QHashedCStringRef::QHashedCStringRef(const char *data, int length)
1078 : m_data(data), m_length(length), m_hash(0)
1079 {
1080 }
1081
1082 QHashedCStringRef::QHashedCStringRef(const char *data, int length, quint32 hash)
1083 : m_data(data), m_length(length), m_hash(hash)
1084 {
1085 }
1086
1087 QHashedCStringRef::QHashedCStringRef(const QHashedCStringRef &o)
1088 : m_data(o.m_data), m_length(o.m_length), m_hash(o.m_hash)
1089 {
1090 }
1091
1092 quint32 QHashedCStringRef::hash() const
1093 {
1094     if (!m_hash) computeHash();
1095     return m_hash;
1096 }
1097
1098 const char *QHashedCStringRef::constData() const
1099 {
1100     return m_data;
1101 }
1102
1103 int QHashedCStringRef::length() const
1104 {
1105     return m_length;
1106 }
1107
1108 int QHashedCStringRef::utf16length() const
1109 {
1110     return m_length;
1111 }
1112
1113 void QHashedCStringRef::writeUtf16(QChar *output) const
1114 {
1115     writeUtf16((uint16_t *)output);
1116 }
1117
1118 void QHashedCStringRef::writeUtf16(uint16_t *output) const
1119 {
1120     int l = m_length;
1121     const char *d = m_data;
1122     while (l--)
1123         *output++ = *d++;
1124 }
1125
1126 bool QHashedString::compare(const QChar *lhs, const char *rhs, int length)
1127 {
1128     Q_ASSERT(lhs && rhs);
1129     const quint16 *l = (const quint16*)lhs;
1130     while (length--)
1131         if (*l++ != *rhs++) return false;
1132     return true;
1133 }
1134
1135 bool QHashedString::compare(const char *lhs, const char *rhs, int length)
1136 {
1137     Q_ASSERT(lhs && rhs);
1138     return 0 == ::memcmp(lhs, rhs, length);
1139 }
1140
1141 QT_END_NAMESPACE
1142
1143 #endif // QHASHEDSTRING_P_H