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 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
  82     void computeHash() const;
  83     mutable quint32 m_hash;
  84 };
  85
  86 class QHashedV8String
  87 {
  88 public:
  89     inline QHashedV8String();
  90     explicit inline QHashedV8String(v8::Handle<v8::String>);
  91     inline QHashedV8String(const QHashedV8String &string);
  92     inline QHashedV8String &operator=(const QHashedV8String &other);
  93
  94     inline bool operator==(const QHashedV8String &string);
  95
  96     inline quint32 hash() const;
  97     inline int length() const;
  98     inline quint32 symbolId() const;
  99
 100     inline v8::Handle<v8::String> string() const;
 101
 102 private:
 103     v8::String::CompleteHashData m_hash;
 104     v8::Handle<v8::String> m_string;
 105 };
 106
 107 class QHashedStringRef
 108 {
 109 public:
 110     inline QHashedStringRef();
 111     inline QHashedStringRef(const QString &);
 112     inline QHashedStringRef(const QChar *, int);
 113     inline QHashedStringRef(const QChar *, int, quint32);
 114     inline QHashedStringRef(const QHashedString &);
 115     inline QHashedStringRef(const QHashedStringRef &);
 116
 117     inline bool operator==(const QHashedString &string) const;
 118     inline bool operator==(const QHashedStringRef &string) const;
 119
 120     inline quint32 hash() const;
 121
 122     inline const QChar *constData() const;
 123     inline quint32 length() const;
 124     inline bool startsWithUpper() const;
 125
 126 private:
 127     friend class QHashedString;
 128
 129     void computeHash() const;
 130
 131     const QChar *m_data;
 132     quint32 m_length;
 133     mutable quint32 m_hash;
 134 };
 135
 136 class QStringHashData;
 137 class QStringHashNode
 138 {
 139 public:
 140     QStringHashNode(const QHashedString &key)
 141     : nlist(0), next(0), key(key), symbolId(0) {
 142     }
 143
 144     QStringHashNode *nlist;
 145     QStringHashNode *next;
 146     QHashedString key;
 147     quint32 symbolId;
 148
 149     inline bool equals(v8::Handle<v8::String> string) {
 150         return string->Equals((uint16_t*)key.constData(), key.length());
 151     }
 152 };
 153
 154 struct QStringHashData
 155 {
 156 public:
 157     QStringHashData()
 158     : nodes(0), buckets(0), numBuckets(0), size(0), numBits(0) {}
 159
 160     QStringHashNode *nodes;
 161     QStringHashNode **buckets;
 162     int numBuckets;
 163     int size;
 164     short numBits;
 165
 166     void rehash();
 167 };
 168
 169 template<class T>
 170 class QStringHash
 171 {
 172 private:
 173     struct Node : public QStringHashNode {
 174         Node(const QHashedString &key, const T &value) : QStringHashNode(key), value(value) {}
 175         T value;
 176     };
 177
 178     QStringHashData data;
 179
 180     inline Node *findNode(const QHashedStringRef &) const;
 181     inline Node *findNode(const QHashedV8String &) const;
 182     inline Node *findSymbolNode(const QHashedV8String &) const;
 183     Node *createNode(const QHashedString &, const T &);
 184
 185 public:
 186     inline QStringHash();
 187     inline QStringHash(const QStringHash &);
 188     inline ~QStringHash();
 189
 190     QStringHash &operator=(const QStringHash<T> &);
 191
 192     inline bool isEmpty() const;
 193     inline void clear();
 194     inline int count() const;
 195
 196     inline void insert(const QString &, const T &);
 197     inline void insert(const QHashedString &, const T &);
 198     inline void insert(const QHashedStringRef &, const T &);
 199
 200     inline T *value(const QString &) const;
 201     inline T *value(const QHashedString &) const;
 202     inline T *value(const QHashedStringRef &) const;
 203     inline T *value(const QHashedV8String &) const;
 204
 205     inline bool contains(const QString &) const;
 206     inline bool contains(const QHashedString &) const;
 207     inline bool contains(const QHashedStringRef &) const;
 208
 209     T &operator[](const QString &);
 210     T &operator[](const QHashedString &);
 211     T &operator[](const QHashedStringRef &);
 212
 213     class ConstIterator {
 214     public:
 215         ConstIterator() : n(0) {}
 216         ConstIterator(Node *n) : n(n) {}
 217
 218         ConstIterator &operator++() { n = (Node *)n->nlist; return *this; }
 219         bool operator==(const ConstIterator &o) const { return n == o.n; }
 220         bool operator!=(const ConstIterator &o) const { return n != o.n; }
 221
 222         const QHashedString &key() const { return n->key; }
 223         const T &value() const { return n->value; }
 224         const T &operator*() const { return n->value; }
 225     private:
 226         Node *n;
 227     };
 228
 229     ConstIterator begin() const { return ConstIterator((Node *)data.nodes); }
 230     ConstIterator end() const { return ConstIterator(); }
 231 };
 232
 233 template<class T>
 234 QStringHash<T>::QStringHash()
 235 {
 236 }
 237
 238 template<class T>
 239 QStringHash<T>::QStringHash(const QStringHash<T> &other)
 240 : data(other.data)
 241 {
 242     data.nodes = 0;
 243     data.buckets = 0;
 244
 245     QStringHashNode *n = other.data.nodes;
 246     while (n) {
 247         Node *o = (Node *)n;
 248         Node *mynode = new Node(o->key, o->value);
 249         mynode->nlist = data.nodes;
 250         data.nodes = mynode;
 251         n = o->nlist;
 252     }
 253
 254     data.rehash();
 255 }
 256
 257 template<class T>
 258 QStringHash<T> &QStringHash<T>::operator=(const QStringHash<T> &other)
 259 {
 260     if (&other == this)
 261         return *this;
 262
 263     clear();
 264     data = other.data;
 265     data.nodes = 0;
 266     data.buckets = 0;
 267
 268     QStringHashNode *n = other.data.nodes;
 269     while (n) {
 270         Node *o = (Node *)n;
 271         Node *mynode = new Node(o->key, o->value);
 272         mynode->nlist = data.nodes;
 273         data.nodes = mynode;
 274         n = o->nlist;
 275     }
 276
 277     data.rehash();
 278
 279     return *this;
 280 }
 281
 282 template<class T>
 283 QStringHash<T>::~QStringHash()
 284 {
 285     clear();
 286 }
 287
 288 template<class T>
 289 void QStringHash<T>::clear()
 290 {
 291     QStringHashNode *n = data.nodes;
 292     while (n) {
 293         Node *o = (Node *)n;
 294         n = n->nlist;
 295         delete o;
 296     }
 297
 298     delete [] data.buckets;
 299
 300     data = QStringHashData();
 301 }
 302
 303 template<class T>
 304 bool QStringHash<T>::isEmpty() const
 305 {
 306     return data.nodes == 0;
 307 }
 308
 309 template<class T>
 310 int QStringHash<T>::count() const
 311 {
 312     return data.size;
 313 }
 314
 315 template<class T>
 316 typename QStringHash<T>::Node *QStringHash<T>::createNode(const QHashedString &key, const T &value)
 317 {
 318     if (data.size == data.numBuckets)
 319         data.rehash();
 320
 321     Node *n = new Node(key, value);
 322     n->nlist = data.nodes;
 323     data.nodes = n;
 324
 325     int bucket = key.hash() % data.numBuckets;
 326     n->next = data.buckets[bucket];
 327     data.buckets[bucket] = n;
 328
 329     data.size++;
 330
 331     return n;
 332 }
 333
 334 template<class T>
 335 void QStringHash<T>::insert(const QString &key, const T &value)
 336 {
 337     QHashedStringRef ch(key);
 338     Node *n = findNode(key);
 339     if (n) n->value = value;
 340     else createNode(QHashedString(key, ch.hash()), value);
 341 }
 342
 343 template<class T>
 344 void QStringHash<T>::insert(const QHashedString &key, const T &value)
 345 {
 346     Node *n = findNode(key);
 347     if (n) n->value = value;
 348     else createNode(key, value);
 349 }
 350
 351 template<class T>
 352 void QStringHash<T>::insert(const QHashedStringRef &key, const T &value)
 353 {
 354     Node *n = findNode(key);
 355     if (n) n->value = value;
 356     else createNode(key, value);
 357 }
 358
 359 template<class T>
 360 typename QStringHash<T>::Node *QStringHash<T>::findNode(const QHashedStringRef &string) const
 361 {
 362     QStringHashNode *node = 0;
 363     if (data.numBuckets) {
 364         node = data.buckets[string.hash() % data.numBuckets];
 365         while (node && !(node->key == string))
 366             node = node->next;
 367     }
 368
 369     return (Node *)node;
 370 }
 371
 372 template<class T>
 373 typename QStringHash<T>::Node *QStringHash<T>::findNode(const QHashedV8String &string) const
 374 {
 375     QStringHashNode *node = 0;
 376     if (data.numBuckets) {
 377         quint32 hash = string.hash();
 378         node = data.buckets[hash % data.numBuckets];
 379         int length = string.length();
 380         while (node && (length != node->key.length() || hash != node->key.hash() || !node->equals(string.string())))
 381             node = node->next;
 382     }
 383
 384     return (Node *)node;
 385 }
 386
 387 template<class T>
 388 typename QStringHash<T>::Node *QStringHash<T>::findSymbolNode(const QHashedV8String &string) const
 389 {
 390     Q_ASSERT(string.symbolId() != 0);
 391
 392     QStringHashNode *node = 0;
 393     if (data.numBuckets) {
 394         quint32 hash = string.hash();
 395         quint32 symbolId = string.symbolId();
 396         node = data.buckets[hash % data.numBuckets];
 397         int length = string.length();
 398         while (node && (length != node->key.length() || hash != node->key.hash() ||
 399                !(node->symbolId == symbolId || node->equals(string.string()))))
 400             node = node->next;
 401         if (node)
 402             node->symbolId = symbolId;
 403     }
 404
 405     return (Node *)node;
 406 }
 407
 408 template<class T>
 409 T *QStringHash<T>::value(const QString &key) const
 410 {
 411     Node *n = findNode(key);
 412     return n?&n->value:0;
 413 }
 414
 415 template<class T>
 416 T *QStringHash<T>::value(const QHashedString &key) const
 417 {
 418     Node *n = findNode(key);
 419     return n?&n->value:0;
 420 }
 421
 422 template<class T>
 423 T *QStringHash<T>::value(const QHashedStringRef &key) const
 424 {
 425     Node *n = findNode(key);
 426     return n?&n->value:0;
 427 }
 428
 429 template<class T>
 430 T *QStringHash<T>::value(const QHashedV8String &string) const
 431 {
 432     Node *n = string.symbolId()?findSymbolNode(string):findNode(string);
 433     return n?&n->value:0;
 434 }
 435
 436 template<class T>
 437 bool QStringHash<T>::contains(const QString &s) const
 438 {
 439     return 0 != value(s);
 440 }
 441
 442 template<class T>
 443 bool QStringHash<T>::contains(const QHashedString &s) const
 444 {
 445     return 0 != value(s);
 446 }
 447 template<class T>
 448 bool QStringHash<T>::contains(const QHashedStringRef &s) const
 449 {
 450     return 0 != value(s);
 451 }
 452
 453 template<class T>
 454 T &QStringHash<T>::operator[](const QString &key)
 455 {
 456     QHashedStringRef cs(key);
 457     Node *n = findNode(cs);
 458     if (n) return n->value;
 459     else return createNode(QHashedString(key, cs.hash()), T())->value;
 460 }
 461
 462 template<class T>
 463 T &QStringHash<T>::operator[](const QHashedString &key)
 464 {
 465     Node *n = findNode(key);
 466     if (n) return n->value;
 467     else return createNode(key, T())->value;
 468 }
 469
 470 template<class T>
 471 T &QStringHash<T>::operator[](const QHashedStringRef &key)
 472 {
 473     Node *n = findNode(key);
 474     if (n) return n->value;
 475     else return createNode(key, T())->value;
 476 }
 477
 478 inline uint qHash(const QHashedString &string)
 479 {
 480     return uint(string.hash());
 481 }
 482
 483 inline uint qHash(const QHashedStringRef &string)
 484 {
 485     return uint(string.hash());
 486 }
 487
 488 QHashedString::QHashedString()
 489 : QString(), m_hash(0)
 490 {
 491 }
 492
 493 QHashedString::QHashedString(const QString &string)
 494 : QString(string), m_hash(0)
 495 {
 496 }
 497
 498 QHashedString::QHashedString(const QString &string, quint32 hash)
 499 : QString(string), m_hash(hash)
 500 {
 501 }
 502
 503 QHashedString::QHashedString(const QHashedString &string)
 504 : QString(string), m_hash(string.m_hash)
 505 {
 506 }
 507
 508 QHashedString &QHashedString::operator=(const QHashedString &string)
 509 {
 510     static_cast<QString &>(*this) = string;
 511     m_hash = string.m_hash;
 512     return *this;
 513 }
 514
 515 bool QHashedString::operator==(const QHashedString &string) const
 516 {
 517     return (string.m_hash == m_hash || !string.m_hash || !m_hash) &&
 518            static_cast<const QString &>(*this) == static_cast<const QString &>(string);
 519 }
 520
 521 bool QHashedString::operator==(const QHashedStringRef &string) const
 522 {
 523     return (uint)length() == string.m_length &&
 524            (string.m_hash == m_hash || !string.m_hash || !m_hash) &&
 525            0 == ::memcmp(constData(), string.m_data, string.m_length * sizeof(QChar));
 526 }
 527
 528 quint32 QHashedString::hash() const
 529 {
 530     if (!m_hash) computeHash();
 531     return m_hash;
 532 }
 533
 534 quint32 QHashedString::existingHash() const
 535 {
 536     return m_hash;
 537 }
 538
 539 bool QHashedString::isUpper(const QChar &qc)
 540 {
 541     ushort c = qc.unicode();
 542     // Optimize for _, a-z and A-Z.
 543     return ((c != '_' ) && (!(c >= 'a' && c <= 'z')) &&
 544            ((c >= 'A' && c <= 'Z') || QChar::category(c) == QChar::Letter_Uppercase));
 545 }
 546
 547 QHashedV8String::QHashedV8String()
 548 {
 549 }
 550
 551 QHashedV8String::QHashedV8String(v8::Handle<v8::String> string)
 552 : m_hash(string->CompleteHash()), m_string(string)
 553 {
 554     Q_ASSERT(!m_string.IsEmpty());
 555 }
 556
 557 QHashedV8String::QHashedV8String(const QHashedV8String &string)
 558 : m_hash(string.m_hash), m_string(string.m_string)
 559 {
 560 }
 561
 562 QHashedV8String &QHashedV8String::operator=(const QHashedV8String &other)
 563 {
 564     m_hash = other.m_hash;
 565     m_string = other.m_string;
 566     return *this;
 567 }
 568
 569 bool QHashedV8String::operator==(const QHashedV8String &string)
 570 {
 571     return m_hash.hash == string.m_hash.hash && m_hash.length == string.m_hash.length &&
 572            m_string.IsEmpty() == m_string.IsEmpty() &&
 573            (m_string.IsEmpty() || m_string->StrictEquals(string.m_string));
 574 }
 575
 576 quint32 QHashedV8String::hash() const
 577 {
 578     return m_hash.hash;
 579 }
 580
 581 int QHashedV8String::length() const
 582 {
 583     return m_hash.length;
 584 }
 585
 586 quint32 QHashedV8String::symbolId() const
 587 {
 588     return m_hash.symbol_id;
 589 }
 590
 591 v8::Handle<v8::String> QHashedV8String::string() const
 592 {
 593     return m_string;
 594 }
 595
 596 QHashedStringRef::QHashedStringRef()
 597 : m_data(0), m_length(0), m_hash(0)
 598 {
 599 }
 600
 601 QHashedStringRef::QHashedStringRef(const QString &str)
 602 : m_data(str.constData()), m_length(str.length()), m_hash(0)
 603 {
 604 }
 605
 606 QHashedStringRef::QHashedStringRef(const QChar *data, int length)
 607 : m_data(data), m_length(length), m_hash(0)
 608 {
 609 }
 610
 611 QHashedStringRef::QHashedStringRef(const QChar *data, int length, quint32 hash)
 612 : m_data(data), m_length(length), m_hash(hash)
 613 {
 614 }
 615
 616 QHashedStringRef::QHashedStringRef(const QHashedString &string)
 617 : m_data(string.constData()), m_length(string.length()), m_hash(string.m_hash)
 618 {
 619 }
 620
 621 QHashedStringRef::QHashedStringRef(const QHashedStringRef &string)
 622 : m_data(string.m_data), m_length(string.m_length), m_hash(string.m_hash)
 623 {
 624 }
 625
 626 bool QHashedStringRef::operator==(const QHashedString &string) const
 627 {
 628     return m_length == (uint)string.length() &&
 629            (m_hash == string.m_hash || !m_hash || !string.m_hash) &&
 630            0 == ::memcmp(string.constData(), m_data, m_length * sizeof(QChar));
 631 }
 632
 633 bool QHashedStringRef::operator==(const QHashedStringRef &string) const
 634 {
 635     return m_length == string.m_length &&
 636            (m_hash == string.m_hash || !m_hash || !string.m_hash) &&
 637            0 == ::memcmp(string.m_data, m_data, m_length * sizeof(QChar));
 638 }
 639
 640 const QChar *QHashedStringRef::constData() const
 641 {
 642     return m_data;
 643 }
 644
 645 quint32 QHashedStringRef::length() const
 646 {
 647     return m_length;
 648 }
 649
 650 bool QHashedStringRef::startsWithUpper() const
 651 {
 652     if (m_length < 1) return false;
 653     return QHashedString::isUpper(m_data[0]);
 654 }
 655
 656 quint32 QHashedStringRef::hash() const
 657 {
 658     if (!m_hash) computeHash();
 659     return m_hash;
 660 }
 661
 662 QT_END_NAMESPACE
 663
 664 #endif // QHASHEDSTRING_P_H