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