1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2010 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 Qt Mobility Components.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "longstring_p.h"

    43 #include "qmaillog.h"

    44 #include <QDataStream>

    45 #include <QFile>

    46 #include <QFileInfo>

    47 #include <QTextStream>

    48 #include <QtDebug>

    49 

    50 #ifndef USE_FANCY_MATCH_ALGORITHM

    51 #include <ctype.h>

    52 #endif

    53 

    54 // LongString: A string/array class for processing IETF documents such as

    55 // RFC(2)822 messages in a memory efficient method.

    56 

    57 // The LongString string/array class implemented in this file provides 2

    58 // primary benefits over the QString/QByteArray string/array classes namely:

    59 //

    60 // 1) Inbuilt support for mmap'ing a file so that a string can parsed without

    61 //    requiring all bytes of that string to be loaded into physical memory.

    62 //

    63 // 2) left, mid and right methods that don't create deep copies of the

    64 //    string data, this is achieved by using ref counting and

    65 //    QByteArray::fromRawData

    66 //

    67 // Normal QByteArray methods can be used on LongStrings by utilizing the

    68 // LongString::toQByteArray method.

    69 //

    70 // Known Limitations:

    71 //

    72 // 1) The internal representation is 8bit ascii, which is fine for 7bit ascii

    73 //    email messages.

    74 //

    75 // 2) The underlying data is treated as read only.

    76 //

    77 // 3) mmap may not be supported on non *nix platforms.

    78 //

    79 // Additionally LongString provides a case insensitive indexOf method, this

    80 // is useful as email fields/tokens (From, Date, Subject etc) are case

    81 // insensitive.

    82 

    83 #ifdef USE_FANCY_MATCH_ALGORITHM

    84 #define REHASH(a) \

    85     if (ol_minus_1 < sizeof(uint) * CHAR_BIT) \

    86         hashHaystack -= (a) << ol_minus_1; \

    87     hashHaystack <<= 1

    88 #endif

    89 

    90 static int insensitiveIndexOf(const QByteArray& target, const QByteArray &source, int from, int off, int len) 

    91 {

    92 #ifndef USE_FANCY_MATCH_ALGORITHM

    93     const char* const matchBegin = target.constData();

    94     const char* const matchEnd = matchBegin + target.length();

    95 

    96     const char* const begin = source.constData() + off;

    97     const char* const end = begin + len - (target.length() - 1);

    98 

    99     const char* it = 0;

   100     if (from >= 0) {

   101         it = begin + from;

   102     } else {

   103         it = begin + len + from;

   104     }

   105 

   106     while (it < end)

   107     {

   108         if (toupper(*it++) == toupper(*matchBegin))

   109         {

   110             const char* restart = it;

   111 

   112             // See if the remainder matches

   113             const char* searchIt = it;

   114             const char* matchIt = matchBegin + 1;

   115 

   116             do 

   117             {

   118                 if (matchIt == matchEnd)

   119                     return ((it - 1) - begin);

   120 

   121                 // We may find the next place to search in our scan

   122                 if ((restart == it) && (*searchIt == *(it - 1)))

   123                     restart = searchIt;

   124             }

   125             while (toupper(*searchIt++) == toupper(*matchIt++));

   126 

   127             // No match

   128             it = restart;

   129         }

   130     }

   131 

   132     return -1;

   133 #else

   134     // Based on QByteArray::indexOf, except use strncasecmp for

   135     // case-insensitive string comparison

   136     const int ol = target.length();

   137     if (from > len || ol + from > len)

   138         return -1;

   139     if (ol == 0)

   140         return from;

   141 

   142     const char *needle = target.data();

   143     const char *haystack = source.data() + off + from;

   144     const char *end = source.data() + off + (len - ol);

   145     const uint ol_minus_1 = ol - 1;

   146     uint hashNeedle = 0, hashHaystack = 0;

   147     int idx;

   148     for (idx = 0; idx < ol; ++idx) {

   149         hashNeedle = ((hashNeedle<<1) + needle[idx]);

   150         hashHaystack = ((hashHaystack<<1) + haystack[idx]);

   151     }

   152     hashHaystack -= *(haystack + ol_minus_1);

   153 

   154     while (haystack <= end) {

   155         hashHaystack += *(haystack + ol_minus_1);

   156         if (hashHaystack == hashNeedle  && *needle == *haystack

   157              && strncasecmp(needle, haystack, ol) == 0)

   158         {

   159             return haystack - source.data();

   160         }

   161         REHASH(*haystack);

   162         ++haystack;

   163     }

   164     return -1;

   165 #endif

   166 }

   167 

   168 

   169 class LongStringFileMapping

   170 {

   171 public:

   172     LongStringFileMapping();

   173     LongStringFileMapping(const QString& name);

   174     ~LongStringFileMapping();

   175 

   176     const QString &fileName() const { return filename; }

   177     int length() const { return len; }

   178     bool mapped() const { return (buffer != 0); }

   179 

   180     const QByteArray toQByteArray() const;

   181 

   182     template <typename Stream> void serialize(Stream &stream) const;

   183     template <typename Stream> void deserialize(Stream &stream);

   184 

   185 private:

   186     void init();

   187     void map() const;

   188 

   189     QString filename;

   190     mutable const char* buffer;

   191     int len;

   192 

   193     // We need to keep these in an external map, because QFile is noncopyable

   194     struct QFileMapping

   195     {

   196         QFileMapping() : file(0), mapping(0), refCount(0), mapCount(0), size(0) {}

   197 

   198         QFile* file;

   199         char* mapping;

   200         int refCount;

   201         int mapCount;

   202         qint64 size;

   203     };

   204 

   205     static QMap<QString, QFileMapping> fileMap;

   206 };

   207 

   208 QMap<QString, LongStringFileMapping::QFileMapping> LongStringFileMapping::fileMap;

   209 

   210 template <typename Stream> 

   211 Stream& operator<<(Stream &stream, const LongStringFileMapping& mapping) { mapping.serialize(stream); return stream; }

   212 

   213 template <typename Stream> 

   214 Stream& operator>>(Stream &stream, LongStringFileMapping& mapping) { mapping.deserialize(stream); return stream; }

   215 

   216 LongStringFileMapping::LongStringFileMapping()

   217     : buffer(0),

   218       len(0)

   219 {

   220 }

   221 

   222 LongStringFileMapping::LongStringFileMapping(const QString& name)

   223     : filename(name),

   224       buffer(0),

   225       len(0)

   226 {

   227     init();

   228 }

   229 

   230 LongStringFileMapping::~LongStringFileMapping()

   231 {

   232     if (!filename.isEmpty()) {

   233         QMap<QString, QFileMapping>::iterator it = fileMap.find(filename);

   234         if (it == fileMap.end()) {

   235             qWarning() << "Unable to find mapped file:" << filename;

   236         } else {

   237             QFileMapping& fileMapping(it.value());

   238 

   239             if (fileMapping.refCount > 1) {

   240                 fileMapping.refCount -= 1;

   241 

   242                 // See if we're the last user with a mapping

   243                 if (mapped() && (fileMapping.mapCount > 0)) {

   244                     fileMapping.mapCount -= 1;

   245                     if (fileMapping.mapCount == 0) {

   246                         // Unmap this file

   247                         if (fileMapping.file->unmap(reinterpret_cast<uchar*>(fileMapping.mapping))) {

   248                             fileMapping.mapping = 0;

   249                         } else {

   250                             qWarning() << "Unable to unmap file:" << filename;

   251                         }

   252                     }

   253                 } 

   254             } else {

   255                 // We're the last user - delete the file

   256                 delete fileMapping.file;

   257                 fileMap.erase(it);

   258             }

   259         }

   260     }

   261 }

   262 

   263 void LongStringFileMapping::init()

   264 {

   265     if (!filename.isEmpty()) {

   266         QMap<QString, QFileMapping>::iterator it = fileMap.find(filename);

   267         if (it == fileMap.end()) {

   268             // This file is not referenced yet

   269             QFileInfo fi(filename);

   270             if (fi.exists() && fi.isFile() && fi.isReadable()) {

   271                 filename = fi.absoluteFilePath();

   272 

   273                 if (fi.size() > 0) {

   274                     QFileMapping fileMapping;

   275 

   276                     fileMapping.file = new QFile(filename);

   277                     fileMapping.size = fi.size();

   278                     it = fileMap.insert(filename, fileMapping);

   279                 }

   280             }

   281         }

   282 

   283         if (it != fileMap.end()) {

   284             len = it.value().size;

   285             it.value().refCount += 1;

   286         }

   287     }

   288 }

   289 

   290 void LongStringFileMapping::map() const

   291 {

   292     if ((len > 0) && !filename.isEmpty()) {

   293         QMap<QString, QFileMapping>::iterator it = fileMap.find(filename);

   294         if (it != fileMap.end()) {

   295             QFileMapping &fileMapping(it.value());

   296 

   297             if (fileMapping.mapping == 0) {

   298                 if (fileMapping.file->open(QIODevice::ReadOnly)) {

   299                     fileMapping.mapping = reinterpret_cast<char*>(fileMapping.file->map(0, fileMapping.size));

   300                     fileMapping.file->close();

   301 

   302                     if (!fileMapping.mapping) {

   303                         qWarning() << "Unable to map file:" << filename;

   304                     }

   305                 } else {

   306                     qWarning() << "Unable to open file for mapping:" << filename;

   307                 }

   308             }

   309 

   310             buffer = fileMapping.mapping;

   311             fileMapping.mapCount += 1;

   312         }

   313     }

   314 }

   315 

   316 const QByteArray LongStringFileMapping::toQByteArray() const

   317 {

   318     if (!mapped())

   319         map();

   320 

   321     // Does not create a copy:

   322     return QByteArray::fromRawData(buffer, len);

   323 }

   324 

   325 template <typename Stream> 

   326 void LongStringFileMapping::serialize(Stream &stream) const

   327 {

   328     stream << filename;

   329 }

   330 

   331 template <typename Stream> 

   332 void LongStringFileMapping::deserialize(Stream &stream)

   333 {

   334     stream >> filename;

   335     init();

   336 }

   337 

   338 

   339 class LongStringPrivate

   340 {

   341 public:

   342     LongStringPrivate();

   343     LongStringPrivate(const QByteArray& ba);

   344     LongStringPrivate(const QString& filename);

   345     LongStringPrivate(const LongStringPrivate& other);

   346     ~LongStringPrivate();

   347 

   348     const LongStringPrivate &operator=(const LongStringPrivate &);

   349 

   350     QString fileName() const;

   351     int length() const;

   352     bool isEmpty() const;

   353 

   354     int indexOf(const QByteArray &target, int from) const;

   355 

   356     void midAdjust(int i, int len);

   357     void leftAdjust(int i);

   358     void rightAdjust(int i);

   359 

   360     const QByteArray toQByteArray() const;

   361 

   362     QDataStream* dataStream() const;

   363     QTextStream* textStream() const;

   364 

   365     template <typename Stream> void serialize(Stream &stream) const;

   366     template <typename Stream> void deserialize(Stream &stream);

   367 

   368 private:

   369     mutable LongStringFileMapping* mapping;

   370     mutable QByteArray data;

   371     int offset;

   372     int len;

   373 };

   374 

   375 template <typename Stream> 

   376 Stream& operator<<(Stream &stream, const LongStringPrivate& ls) { ls.serialize(stream); return stream; }

   377 

   378 template <typename Stream> 

   379 Stream& operator>>(Stream &stream, LongStringPrivate& ls) { ls.deserialize(stream); return stream; }

   380 

   381 LongStringPrivate::LongStringPrivate()

   382     : mapping(0),

   383       offset(0), 

   384       len(0) 

   385 {

   386 }

   387 

   388 LongStringPrivate::LongStringPrivate(const QByteArray& ba)

   389     : mapping(0),

   390       data(ba),

   391       offset(0), 

   392       len(data.length()) 

   393 {

   394 }

   395 

   396 LongStringPrivate::LongStringPrivate(const QString& filename)

   397     : mapping(new LongStringFileMapping(filename)),

   398       offset(0), 

   399       len(mapping->length())

   400 {

   401 }

   402 

   403 LongStringPrivate::LongStringPrivate(const LongStringPrivate &other)

   404     : mapping(0),

   405       offset(0),

   406       len(0)

   407 {

   408     this->operator=(other);

   409 }

   410 

   411 LongStringPrivate::~LongStringPrivate()

   412 {

   413     delete mapping;

   414 }

   415 

   416 const LongStringPrivate &LongStringPrivate::operator=(const LongStringPrivate &other)

   417 {

   418     if (&other != this) {

   419         delete mapping;

   420 

   421         mapping = (other.mapping ? new LongStringFileMapping(other.mapping->fileName()) : 0);

   422         data = (other.mapping ? QByteArray() : other.data);

   423         offset = other.offset;

   424         len = other.len;

   425     }

   426 

   427     return *this;

   428 }

   429 

   430 QString LongStringPrivate::fileName() const

   431 {

   432     if (mapping) {

   433         return mapping->fileName();

   434     }

   435 

   436     return QString();

   437 }

   438 

   439 int LongStringPrivate::length() const

   440 {

   441     return len;

   442 }

   443 

   444 bool LongStringPrivate::isEmpty() const

   445 {

   446     return (len == 0);

   447 }

   448 

   449 int LongStringPrivate::indexOf(const QByteArray &target, int from) const

   450 {

   451     if (mapping) {

   452         return insensitiveIndexOf(target, mapping->toQByteArray(), from, offset, len);

   453     }

   454     if (!data.isEmpty()) {

   455         return insensitiveIndexOf(target, data, from, offset, len);

   456     }

   457 

   458     return -1;

   459 }

   460 

   461 void LongStringPrivate::midAdjust(int i, int size)

   462 {

   463     i = qMax(i, 0);

   464     if (i > len) {

   465         len = 0;

   466     } else {

   467         int remainder = len - i;

   468         if (size < 0 || size > remainder)

   469             size = remainder;

   470 

   471         offset += i;

   472         len = size;

   473     }

   474 }

   475 

   476 void LongStringPrivate::leftAdjust(int size)

   477 {

   478     if (size < 0 || size > len)

   479         size = len;

   480 

   481     len = size;

   482 }

   483 

   484 void LongStringPrivate::rightAdjust(int size)

   485 {

   486     if (size < 0 || size > len)

   487         size = len;

   488 

   489     offset = (len - size) + offset;

   490     len = size;

   491 }

   492 

   493 const QByteArray LongStringPrivate::toQByteArray() const

   494 {

   495     if (mapping) {

   496         // Does not copy:

   497         return QByteArray::fromRawData(mapping->toQByteArray().constData() + offset, len);

   498     }

   499     if (!data.isEmpty()) {

   500         return QByteArray::fromRawData(data.constData() + offset, len);

   501     }

   502 

   503     return QByteArray();

   504 }

   505 

   506 QDataStream* LongStringPrivate::dataStream() const

   507 {

   508     // This is safe because QByteArray has shared implementation objects:

   509     const QByteArray input = toQByteArray();

   510     return new QDataStream(input);

   511 }

   512 

   513 QTextStream* LongStringPrivate::textStream() const

   514 {

   515     const QByteArray input = toQByteArray();

   516     return new QTextStream(input);

   517 }

   518 

   519 template <typename Stream> 

   520 void LongStringPrivate::serialize(Stream &stream) const

   521 {

   522     bool usesMapping(mapping != 0);

   523 

   524     stream << usesMapping;

   525     if (usesMapping) {

   526         stream << *mapping;

   527     } else {

   528         stream << data;

   529     }

   530     stream << offset;

   531     stream << len;

   532 }

   533 

   534 template <typename Stream> 

   535 void LongStringPrivate::deserialize(Stream &stream)

   536 {

   537     bool usesMapping;

   538 

   539     stream >> usesMapping;

   540     if (usesMapping) {

   541         mapping = new LongStringFileMapping();

   542         stream >> *mapping;

   543     } else {

   544         stream >> data;

   545     }

   546     stream >> offset;

   547     stream >> len;

   548 }

   549 

   550 

   551 LongString::LongString()

   552     : d(new LongStringPrivate())

   553 {

   554 }

   555 

   556 LongString::LongString(const LongString &other)

   557     : d(new LongStringPrivate(*other.d))

   558 {

   559 }

   560 

   561 LongString::LongString(const QByteArray &ba)

   562     : d(new LongStringPrivate(ba))

   563 {

   564 }

   565 

   566 LongString::LongString(const QString &fileName)

   567     : d(new LongStringPrivate(fileName))

   568 {

   569 }

   570 

   571 LongString::~LongString()

   572 {

   573     delete d;

   574 }

   575 

   576 LongString &LongString::operator=(const LongString &other)

   577 {

   578     if (&other != this) {

   579         delete d;

   580         d = new LongStringPrivate(*other.d);

   581     }

   582 

   583     return *this;

   584 }

   585 

   586 int LongString::length() const

   587 {

   588     return d->length();

   589 }

   590 

   591 bool LongString::isEmpty() const

   592 {

   593     return d->isEmpty();

   594 }

   595 

   596 void LongString::close()

   597 {

   598     QString filename(d->fileName());

   599     delete d;

   600 

   601     if (filename.isEmpty()) {

   602         d = new LongStringPrivate();

   603     } else {

   604         d = new LongStringPrivate(filename);

   605     }

   606 }

   607 

   608 int LongString::indexOf(const QByteArray &target, int from) const

   609 {

   610     return d->indexOf(target, from);

   611 }

   612 

   613 LongString LongString::mid(int i, int len) const

   614 {

   615     LongString copy(*this);

   616     copy.d->midAdjust(i, len);

   617     return copy;

   618 }

   619 

   620 LongString LongString::left(int len) const

   621 {

   622     LongString copy(*this);

   623     copy.d->leftAdjust(len);

   624     return copy;

   625 }

   626 

   627 LongString LongString::right(int len) const

   628 {

   629     LongString copy(*this);

   630     copy.d->rightAdjust(len);

   631     return copy;

   632 }

   633 

   634 const QByteArray LongString::toQByteArray() const

   635 {

   636     return d->toQByteArray();

   637 }

   638 

   639 QDataStream* LongString::dataStream() const

   640 {

   641     return d->dataStream();

   642 }

   643 

   644 QTextStream* LongString::textStream() const

   645 {

   646     return d->textStream();

   647 }

   648 

   649 template <typename Stream> 

   650 void LongString::serialize(Stream &stream) const

   651 {

   652     d->serialize(stream);

   653 }

   654 

   655 template <typename Stream> 

   656 void LongString::deserialize(Stream &stream)

   657 {

   658     d->deserialize(stream);

   659 }

   660 

   661 

   662 // We need to instantiate serialization functions for QDataStream

   663 template void LongString::serialize<QDataStream>(QDataStream&) const;

   664 template void LongString::deserialize<QDataStream>(QDataStream&);

   665