src/declarative/qml/ftw/qhashedstring_p.h

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