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     Q_ASSERT(data.size == 0);
 483
 484     if (other.data.size <= SmallThreshold) {
 485         QStringHashNode *n = other.data.nodes;
 486         while (n) {
 487             Node *o = (Node *)n;
 488             Node *mynode = takeNode(*o);
 489             mynode->nlist = data.nodes;
 490             mynode->next = data.nodes;
 491             data.nodes = mynode;
 492
 493             n = o->nlist;
 494         }
 495     } else {
 496         // Ensure buckets array is created
 497         data.rehashToBits(data.numBits);
 498
 499         QStringHashNode *n = other.data.nodes;
 500         while (n) {
 501             Node *o = (Node *)n;
 502             Node *mynode = takeNode(*o);
 503             mynode->nlist = data.nodes;
 504             data.nodes = mynode;
 505
 506             int bucket = mynode->hash % data.numBuckets;
 507             mynode->next = data.buckets[bucket];
 508             data.buckets[bucket] = mynode;
 509
 510             n = o->nlist;
 511         }
 512     }
 513 }
 514
 515 template<class T, int SmallThreshold>
 516 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::createNode(const QHashedString &key, const T &value)
 517 {
 518     Node *n = takeNode(key, value);
 519
 520     if (data.size < SmallThreshold) {
 521
 522         n->nlist = data.nodes;
 523         n->next = data.nodes;
 524         data.nodes = n;
 525
 526     } else {
 527         if (data.size >= data.numBuckets)
 528             data.rehashToBits(data.numBits + 1);
 529
 530         n->nlist = data.nodes;
 531         data.nodes = n;
 532
 533         int bucket = key.hash() % data.numBuckets;
 534         n->next = data.buckets[bucket];
 535         data.buckets[bucket] = n;
 536     }
 537
 538     data.size++;
 539
 540     return n;
 541 }
 542
 543 template<class T, int SmallThreshold>
 544 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::createNode(const QHashedCStringRef &key, const T &value)
 545 {
 546     Node *n = takeNode(key, value);
 547
 548     if (data.size < SmallThreshold) {
 549
 550         n->nlist = data.nodes;
 551         n->next = data.nodes;
 552         data.nodes = n;
 553
 554     } else {
 555         if (data.size >= data.numBuckets)
 556             data.rehashToBits(data.numBits + 1);
 557
 558         n->nlist = data.nodes;
 559         data.nodes = n;
 560
 561         int bucket = key.hash() % data.numBuckets;
 562         n->next = data.buckets[bucket];
 563         data.buckets[bucket] = n;
 564     }
 565
 566     data.size++;
 567
 568     return n;
 569 }
 570
 571 template<class T, int SmallThreshold>
 572 void QStringHash<T,SmallThreshold>::insert(const QString &key, const T &value)
 573 {
 574     QHashedStringRef ch(key);
 575     Node *n = findNode(key);
 576     if (n) n->value = value;
 577     else createNode(QHashedString(key, ch.hash()), value);
 578 }
 579
 580 template<class T, int SmallThreshold>
 581 void QStringHash<T,SmallThreshold>::insert(const QHashedString &key, const T &value)
 582 {
 583     Node *n = findNode(key);
 584     if (n) n->value = value;
 585     else createNode(key, value);
 586 }
 587
 588 template<class T, int SmallThreshold>
 589 void QStringHash<T,SmallThreshold>::insert(const QHashedStringRef &key, const T &value)
 590 {
 591     Node *n = findNode(key);
 592     if (n) n->value = value;
 593     else createNode(key, value);
 594 }
 595
 596 template<class T, int SmallThreshold>
 597 void QStringHash<T,SmallThreshold>::insert(const QHashedCStringRef &key, const T &value)
 598 {
 599     Node *n = findNode(key);
 600     if (n) n->value = value;
 601     else createNode(key, value);
 602 }
 603
 604 template<class T, int SmallThreshold>
 605 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findNode(const QString &string) const
 606 {
 607     return findNode(QHashedStringRef(string));
 608 }
 609
 610 template<class T, int SmallThreshold>
 611 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findNode(const QHashedString &string) const
 612 {
 613     return findNode(QHashedStringRef(string.constData(), string.length(), string.hash()));
 614 }
 615
 616 template<class T, int SmallThreshold>
 617 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findNode(const QHashedStringRef &string) const
 618 {
 619     QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets];
 620     while (node && !node->equals(string))
 621         node = node->next;
 622
 623     return (Node *)node;
 624 }
 625
 626 template<class T, int SmallThreshold>
 627 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findNode(const QHashedCStringRef &string) const
 628 {
 629     QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets];
 630     while (node && !node->equals(string))
 631         node = node->next;
 632
 633     return (Node *)node;
 634 }
 635
 636 template<class T, int SmallThreshold>
 637 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findNode(const QHashedV8String &string) const
 638 {
 639     QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets];
 640     while (node && !node->equals(string))
 641         node = node->next;
 642
 643     return (Node *)node;
 644 }
 645
 646 template<class T, int SmallThreshold>
 647 typename QStringHash<T,SmallThreshold>::Node *QStringHash<T,SmallThreshold>::findSymbolNode(const QHashedV8String &string) const
 648 {
 649     Q_ASSERT(string.symbolId() != 0);
 650
 651     QStringHashNode *node = (data.size <= SmallThreshold)?data.nodes:data.buckets[string.hash() % data.numBuckets];
 652     while (node && !node->symbolEquals(string))
 653         node = node->next;
 654
 655     if (node)
 656         node->symbolId = string.symbolId();
 657
 658     return (Node *)node;
 659 }
 660
 661 template<class T, int SmallThreshold>
 662 T *QStringHash<T,SmallThreshold>::value(const QString &key) const
 663 {
 664     Node *n = findNode(key);
 665     return n?&n->value:0;
 666 }
 667
 668 template<class T, int SmallThreshold>
 669 T *QStringHash<T,SmallThreshold>::value(const QHashedString &key) const
 670 {
 671     Node *n = findNode(key);
 672     return n?&n->value:0;
 673 }
 674
 675 template<class T, int SmallThreshold>
 676 T *QStringHash<T,SmallThreshold>::value(const QHashedStringRef &key) const
 677 {
 678     Node *n = findNode(key);
 679     return n?&n->value:0;
 680 }
 681
 682 template<class T, int SmallThreshold>
 683 T *QStringHash<T,SmallThreshold>::value(const QHashedCStringRef &key) const
 684 {
 685     Node *n = findNode(key);
 686     return n?&n->value:0;
 687 }
 688
 689 template<class T, int SmallThreshold>
 690 T *QStringHash<T,SmallThreshold>::value(const QHashedV8String &string) const
 691 {
 692     Node *n = string.symbolId()?findSymbolNode(string):findNode(string);
 693     return n?&n->value:0;
 694 }
 695
 696 template<class T, int SmallThreshold>
 697 bool QStringHash<T,SmallThreshold>::contains(const QString &s) const
 698 {
 699     return 0 != value(s);
 700 }
 701
 702 template<class T, int SmallThreshold>
 703 bool QStringHash<T,SmallThreshold>::contains(const QHashedString &s) const
 704 {
 705     return 0 != value(s);
 706 }
 707
 708 template<class T, int SmallThreshold>
 709 bool QStringHash<T,SmallThreshold>::contains(const QHashedStringRef &s) const
 710 {
 711     return 0 != value(s);
 712 }
 713
 714 template<class T, int SmallThreshold>
 715 bool QStringHash<T,SmallThreshold>::contains(const QHashedCStringRef &s) const
 716 {
 717     return 0 != value(s);
 718 }
 719
 720 template<class T, int SmallThreshold>
 721 T &QStringHash<T,SmallThreshold>::operator[](const QString &key)
 722 {
 723     QHashedStringRef cs(key);
 724     Node *n = findNode(cs);
 725     if (n) return n->value;
 726     else return createNode(QHashedString(key, cs.hash()), T())->value;
 727 }
 728
 729 template<class T, int SmallThreshold>
 730 T &QStringHash<T,SmallThreshold>::operator[](const QHashedString &key)
 731 {
 732     Node *n = findNode(key);
 733     if (n) return n->value;
 734     else return createNode(key, T())->value;
 735 }
 736
 737 template<class T, int SmallThreshold>
 738 T &QStringHash<T,SmallThreshold>::operator[](const QHashedStringRef &key)
 739 {
 740     Node *n = findNode(key);
 741     if (n) return n->value;
 742     else return createNode(key, T())->value;
 743 }
 744
 745 template<class T, int SmallThreshold>
 746 T &QStringHash<T,SmallThreshold>::operator[](const QHashedCStringRef &key)
 747 {
 748     Node *n = findNode(key);
 749     if (n) return n->value;
 750     else return createNode(key, T())->value;
 751 }
 752
 753 template<class T, int SmallThreshold>
 754 void QStringHash<T,SmallThreshold>::reserve(int n)
 755 {
 756     if (nodePool || 0 == n)
 757         return;
 758     nodePool = new ReservedNodePool;
 759     nodePool->count = n;
 760     nodePool->used = 0;
 761     nodePool->nodes = new Node[n];
 762
 763     if (n > SmallThreshold)
 764         data.rehashToSize(n);
 765 }
 766
 767 inline uint qHash(const QHashedString &string)
 768 {
 769     return uint(string.hash());
 770 }
 771
 772 inline uint qHash(const QHashedStringRef &string)
 773 {
 774     return uint(string.hash());
 775 }
 776
 777 QHashedString::QHashedString()
 778 : QString(), m_hash(0)
 779 {
 780 }
 781
 782 QHashedString::QHashedString(const QString &string)
 783 : QString(string), m_hash(0)
 784 {
 785 }
 786
 787 QHashedString::QHashedString(const QString &string, quint32 hash)
 788 : QString(string), m_hash(hash)
 789 {
 790 }
 791
 792 QHashedString::QHashedString(const QHashedString &string)
 793 : QString(string), m_hash(string.m_hash)
 794 {
 795 }
 796
 797 QHashedString &QHashedString::operator=(const QHashedString &string)
 798 {
 799     static_cast<QString &>(*this) = string;
 800     m_hash = string.m_hash;
 801     return *this;
 802 }
 803
 804 bool QHashedString::operator==(const QHashedString &string) const
 805 {
 806     return (string.m_hash == m_hash || !string.m_hash || !m_hash) &&
 807            static_cast<const QString &>(*this) == static_cast<const QString &>(string);
 808 }
 809
 810 bool QHashedString::operator==(const QHashedStringRef &string) const
 811 {
 812     return length() == string.m_length &&
 813            (string.m_hash == m_hash || !string.m_hash || !m_hash) &&
 814            QHashedString::compare(constData(), string.m_data, string.m_length);
 815 }
 816
 817 quint32 QHashedString::hash() const
 818 {
 819     if (!m_hash) computeHash();
 820     return m_hash;
 821 }
 822
 823 quint32 QHashedString::existingHash() const
 824 {
 825     return m_hash;
 826 }
 827
 828 bool QHashedString::isUpper(const QChar &qc)
 829 {
 830     ushort c = qc.unicode();
 831     // Optimize for _, a-z and A-Z.
 832     return ((c != '_' ) && (!(c >= 'a' && c <= 'z')) &&
 833            ((c >= 'A' && c <= 'Z') || QChar::category(c) == QChar::Letter_Uppercase));
 834 }
 835
 836 QHashedV8String::QHashedV8String()
 837 {
 838 }
 839
 840 QHashedV8String::QHashedV8String(v8::Handle<v8::String> string)
 841 : m_hash(string->CompleteHash()), m_string(string)
 842 {
 843     Q_ASSERT(!m_string.IsEmpty());
 844 }
 845
 846 QHashedV8String::QHashedV8String(const QHashedV8String &string)
 847 : m_hash(string.m_hash), m_string(string.m_string)
 848 {
 849 }
 850
 851 QHashedV8String &QHashedV8String::operator=(const QHashedV8String &other)
 852 {
 853     m_hash = other.m_hash;
 854     m_string = other.m_string;
 855     return *this;
 856 }
 857
 858 bool QHashedV8String::operator==(const QHashedV8String &string)
 859 {
 860     return m_hash.hash == string.m_hash.hash && m_hash.length == string.m_hash.length &&
 861            m_string.IsEmpty() == m_string.IsEmpty() &&
 862            (m_string.IsEmpty() || m_string->StrictEquals(string.m_string));
 863 }
 864
 865 quint32 QHashedV8String::hash() const
 866 {
 867     return m_hash.hash;
 868 }
 869
 870 int QHashedV8String::length() const
 871 {
 872     return m_hash.length;
 873 }
 874
 875 quint32 QHashedV8String::symbolId() const
 876 {
 877     return m_hash.symbol_id;
 878 }
 879
 880 v8::Handle<v8::String> QHashedV8String::string() const
 881 {
 882     return m_string;
 883 }
 884
 885 QHashedStringRef::QHashedStringRef()
 886 : m_data(0), m_length(0), m_hash(0)
 887 {
 888 }
 889
 890 QHashedStringRef::QHashedStringRef(const QString &str)
 891 : m_data(str.constData()), m_length(str.length()), m_hash(0)
 892 {
 893 }
 894
 895 QHashedStringRef::QHashedStringRef(const QChar *data, int length)
 896 : m_data(data), m_length(length), m_hash(0)
 897 {
 898 }
 899
 900 QHashedStringRef::QHashedStringRef(const QChar *data, int length, quint32 hash)
 901 : m_data(data), m_length(length), m_hash(hash)
 902 {
 903 }
 904
 905 QHashedStringRef::QHashedStringRef(const QHashedString &string)
 906 : m_data(string.constData()), m_length(string.length()), m_hash(string.m_hash)
 907 {
 908 }
 909
 910 QHashedStringRef::QHashedStringRef(const QHashedStringRef &string)
 911 : m_data(string.m_data), m_length(string.m_length), m_hash(string.m_hash)
 912 {
 913 }
 914
 915 bool QHashedStringRef::operator==(const QHashedString &string) const
 916 {
 917     return m_length == string.length() &&
 918            (m_hash == string.m_hash || !m_hash || !string.m_hash) &&
 919            QHashedString::compare(string.constData(), m_data, m_length);
 920 }
 921
 922 bool QHashedStringRef::operator==(const QHashedStringRef &string) const
 923 {
 924     return m_length == string.m_length &&
 925            (m_hash == string.m_hash || !m_hash || !string.m_hash) &&
 926            QHashedString::compare(string.m_data, m_data, m_length);
 927 }
 928
 929 const QChar *QHashedStringRef::constData() const
 930 {
 931     return m_data;
 932 }
 933
 934 int QHashedStringRef::length() const
 935 {
 936     return m_length;
 937 }
 938
 939 bool QHashedStringRef::startsWithUpper() const
 940 {
 941     if (m_length < 1) return false;
 942     return QHashedString::isUpper(m_data[0]);
 943 }
 944
 945 quint32 QHashedStringRef::hash() const
 946 {
 947     if (!m_hash) computeHash();
 948     return m_hash;
 949 }
 950
 951 QHashedCStringRef::QHashedCStringRef()
 952 : m_data(0), m_length(0), m_hash(0)
 953 {
 954 }
 955
 956 QHashedCStringRef::QHashedCStringRef(const char *data, int length)
 957 : m_data(data), m_length(length), m_hash(0)
 958 {
 959 }
 960
 961 QHashedCStringRef::QHashedCStringRef(const char *data, int length, quint32 hash)
 962 : m_data(data), m_length(length), m_hash(hash)
 963 {
 964 }
 965
 966 QHashedCStringRef::QHashedCStringRef(const QHashedCStringRef &o)
 967 : m_data(o.m_data), m_length(o.m_length), m_hash(o.m_hash)
 968 {
 969 }
 970
 971 quint32 QHashedCStringRef::hash() const
 972 {
 973     if (!m_hash) computeHash();
 974     return m_hash;
 975 }
 976
 977 const char *QHashedCStringRef::constData() const
 978 {
 979     return m_data;
 980 }
 981
 982 int QHashedCStringRef::length() const
 983 {
 984     return m_length;
 985 }
 986
 987 bool QHashedString::compare(const QChar *lhs, const char *rhs, int length)
 988 {
 989     Q_ASSERT(lhs && rhs);
 990     const quint16 *l = (const quint16*)lhs;
 991     while (length--)
 992         if (*l++ != *rhs++) return false;
 993     return true;
 994 }
 995
 996 bool QHashedString::compare(const char *lhs, const char *rhs, int length)
 997 {
 998     Q_ASSERT(lhs && rhs);
 999     return 0 == ::memcmp(lhs, rhs, length);
1000 }
1001
1002 QT_END_NAMESPACE
1003
1004 #endif // QHASHEDSTRING_P_H