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