File indexing completed on 2024-04-21 03:54:57

 /*
     This file is part of the KDE project
     SPDX-FileCopyrightText: 2004-2014 David Faure <faure@kde.org>
 
     SPDX-License-Identifier: LGPL-2.0-or-later
 */
 
 #include <QTest>
 
 #include <QHash>
 #include <QList>
 #include <QMap>
 
 #include <kio/global.h> // filesize_t
 #include <kio/udsentry.h>
 
 /*
    This is to compare the old list-of-lists API vs a QMap/QHash-based API
    in terms of performance.
 
    The number of atoms and their type map to what kio_file would put in
    for any normal file.
 
    The lookups are done for two atoms that are present, and for one that is not.
 */
 
 class UdsEntryBenchmark : public QObject
 {
     Q_OBJECT
 public:
     UdsEntryBenchmark()
         : nameStr(QStringLiteral("name"))
         , now(QDateTime::currentDateTime())
         , now_time_t(now.toSecsSinceEpoch())
     {
     }
 private Q_SLOTS:
     void testKDE3Slave();
     void testKDE3App();
     void testHashVariantSlave();
     void testHashVariantApp();
     void testHashStructSlave();
     void testHashStructApp();
     void testMapStructSlave();
     void testMapStructApp();
     void testTwoVectorsSlaveFill();
     void testTwoVectorsSlaveCompare();
     void testTwoVectorsApp();
     void testAnotherSlaveFill();
     void testAnotherSlaveCompare();
     void testAnotherApp();
     void testAnotherV2SlaveFill();
     void testAnotherV2SlaveCompare();
     void testAnotherV2App();
 
 private:
     const QString nameStr;
     const QDateTime now;
     const time_t now_time_t;
 };
 
 class OldUDSAtom
 {
 public:
     QString m_str;
     long long m_long;
     unsigned int m_uds;
 };
 typedef QList<OldUDSAtom> OldUDSEntry; // well it was a QValueList :)
 
 static void fillOldUDSEntry(OldUDSEntry &entry, time_t now_time_t, const QString &nameStr)
 {
     OldUDSAtom atom;
     atom.m_uds = KIO::UDSEntry::UDS_NAME;
     atom.m_str = nameStr;
     entry.append(atom);
     atom.m_uds = KIO::UDSEntry::UDS_SIZE;
     atom.m_long = 123456ULL;
     entry.append(atom);
     atom.m_uds = KIO::UDSEntry::UDS_MODIFICATION_TIME;
     atom.m_long = now_time_t;
     entry.append(atom);
     atom.m_uds = KIO::UDSEntry::UDS_ACCESS_TIME;
     atom.m_long = now_time_t;
     entry.append(atom);
     atom.m_uds = KIO::UDSEntry::UDS_FILE_TYPE;
     atom.m_long = S_IFREG;
     entry.append(atom);
     atom.m_uds = KIO::UDSEntry::UDS_ACCESS;
     atom.m_long = 0644;
     entry.append(atom);
     atom.m_uds = KIO::UDSEntry::UDS_USER;
     atom.m_str = nameStr;
     entry.append(atom);
     atom.m_uds = KIO::UDSEntry::UDS_GROUP;
     atom.m_str = nameStr;
     entry.append(atom);
 }
 
 void UdsEntryBenchmark::testKDE3Slave()
 {
     QBENCHMARK {
         OldUDSEntry entry;
         fillOldUDSEntry(entry, now_time_t, nameStr);
         QCOMPARE(entry.count(), 8);
     }
 }
 
 void UdsEntryBenchmark::testKDE3App()
 {
     OldUDSEntry entry;
     fillOldUDSEntry(entry, now_time_t, nameStr);
 
     QString displayName;
     KIO::filesize_t size;
     QString url;
 
     QBENCHMARK {
         OldUDSEntry::ConstIterator it2 = entry.constBegin();
         for (; it2 != entry.constEnd(); it2++) {
             switch ((*it2).m_uds) {
             case KIO::UDSEntry::UDS_NAME:
                 displayName = (*it2).m_str;
                 break;
             case KIO::UDSEntry::UDS_URL:
                 url = (*it2).m_str;
                 break;
             case KIO::UDSEntry::UDS_SIZE:
                 size = (*it2).m_long;
                 break;
             }
         }
         QCOMPARE(size, 123456ULL);
         QCOMPARE(displayName, QStringLiteral("name"));
         QVERIFY(url.isEmpty());
     }
 }
 
 // QHash or QMap? doesn't seem to make much difference.
 typedef QHash<uint, QVariant> UDSEntryHV;
 
 // This uses QDateTime instead of time_t
 static void fillUDSEntryHV(UDSEntryHV &entry, const QDateTime &now, const QString &nameStr)
 {
     entry.reserve(8);
     entry.insert(KIO::UDSEntry::UDS_NAME, nameStr);
     // we might need a method to make sure people use unsigned long long
     entry.insert(KIO::UDSEntry::UDS_SIZE, 123456ULL);
     entry.insert(KIO::UDSEntry::UDS_MODIFICATION_TIME, now);
     entry.insert(KIO::UDSEntry::UDS_ACCESS_TIME, now);
     entry.insert(KIO::UDSEntry::UDS_FILE_TYPE, S_IFREG);
     entry.insert(KIO::UDSEntry::UDS_ACCESS, 0644);
     entry.insert(KIO::UDSEntry::UDS_USER, nameStr);
     entry.insert(KIO::UDSEntry::UDS_GROUP, nameStr);
 }
 
 void UdsEntryBenchmark::testHashVariantSlave()
 {
     const QDateTime now = QDateTime::currentDateTime();
     QBENCHMARK {
         UDSEntryHV entry;
         fillUDSEntryHV(entry, now, nameStr);
         QCOMPARE(entry.count(), 8);
     }
 }
 
 void UdsEntryBenchmark::testHashVariantApp()
 {
     // Normally the code would look like this, but let's change it to time it like the old api
     /*
        QString displayName = entry.value( KIO::UDSEntry::UDS_NAME ).toString();
        QUrl url = entry.value( KIO::UDSEntry::UDS_URL ).toString();
        KIO::filesize_t size = entry.value( KIO::UDSEntry::UDS_SIZE ).toULongLong();
      */
     UDSEntryHV entry;
     fillUDSEntryHV(entry, now, nameStr);
 
     QString displayName;
     KIO::filesize_t size;
     QString url;
 
     QBENCHMARK {
         // For a field that we assume to always be there
         displayName = entry.value(KIO::UDSEntry::UDS_NAME).toString();
 
         // For a field that might not be there
         auto it = entry.constFind(KIO::UDSEntry::UDS_URL);
         const auto end = entry.cend();
         if (it != end) {
             url = it.value().toString();
         }
 
         it = entry.constFind(KIO::UDSEntry::UDS_SIZE);
         if (it != end) {
             size = it.value().toULongLong();
         }
 
         QCOMPARE(size, 123456ULL);
         QCOMPARE(displayName, QStringLiteral("name"));
         QVERIFY(url.isEmpty());
     }
 }
 
 // The KDE4 solution: QHash+struct
 
 // Which one is used depends on UDS_STRING vs UDS_LONG
 struct UDSAtom4 { // can't be a union due to qstring...
     UDSAtom4()
     {
     } // for QHash or QMap
     UDSAtom4(const QString &s)
         : m_str(s)
     {
     }
     UDSAtom4(long long l)
         : m_long(l)
     {
     }
 
     QString m_str;
     long long m_long;
 };
 
 // Another possibility, to save on QVariant costs
 typedef QHash<uint, UDSAtom4> UDSEntryHS; // hash+struct
 
 static void fillQHashStructEntry(UDSEntryHS &entry, time_t now_time_t, const QString &nameStr)
 {
     entry.reserve(8);
     entry.insert(KIO::UDSEntry::UDS_NAME, nameStr);
     entry.insert(KIO::UDSEntry::UDS_SIZE, 123456ULL);
     entry.insert(KIO::UDSEntry::UDS_MODIFICATION_TIME, now_time_t);
     entry.insert(KIO::UDSEntry::UDS_ACCESS_TIME, now_time_t);
     entry.insert(KIO::UDSEntry::UDS_FILE_TYPE, S_IFREG);
     entry.insert(KIO::UDSEntry::UDS_ACCESS, 0644);
     entry.insert(KIO::UDSEntry::UDS_USER, nameStr);
     entry.insert(KIO::UDSEntry::UDS_GROUP, nameStr);
 }
 void UdsEntryBenchmark::testHashStructSlave()
 {
     QBENCHMARK {
         UDSEntryHS entry;
         fillQHashStructEntry(entry, now_time_t, nameStr);
         QCOMPARE(entry.count(), 8);
     }
 }
 
 void UdsEntryBenchmark::testHashStructApp()
 {
     UDSEntryHS entry;
     fillQHashStructEntry(entry, now_time_t, nameStr);
 
     QString displayName;
     KIO::filesize_t size;
     QString url;
 
     QBENCHMARK {
         // For a field that we assume to always be there
         displayName = entry.value(KIO::UDSEntry::UDS_NAME).m_str;
 
         // For a field that might not be there
         auto it = entry.constFind(KIO::UDSEntry::UDS_URL);
         const auto end = entry.cend();
         if (it != end) {
             url = it.value().m_str;
         }
 
         it = entry.constFind(KIO::UDSEntry::UDS_SIZE);
         if (it != end) {
             size = it.value().m_long;
         }
         QCOMPARE(size, 123456ULL);
         QCOMPARE(displayName, QStringLiteral("name"));
         QVERIFY(url.isEmpty());
     }
 }
 
 // Let's see if QMap makes any difference
 typedef QMap<uint, UDSAtom4> UDSEntryMS; // map+struct
 
 static void fillQMapStructEntry(UDSEntryMS &entry, time_t now_time_t, const QString &nameStr)
 {
     entry.insert(KIO::UDSEntry::UDS_NAME, nameStr);
     entry.insert(KIO::UDSEntry::UDS_SIZE, 123456ULL);
     entry.insert(KIO::UDSEntry::UDS_MODIFICATION_TIME, now_time_t);
     entry.insert(KIO::UDSEntry::UDS_ACCESS_TIME, now_time_t);
     entry.insert(KIO::UDSEntry::UDS_FILE_TYPE, S_IFREG);
     entry.insert(KIO::UDSEntry::UDS_ACCESS, 0644);
     entry.insert(KIO::UDSEntry::UDS_USER, nameStr);
     entry.insert(KIO::UDSEntry::UDS_GROUP, nameStr);
 }
 
 void UdsEntryBenchmark::testMapStructSlave()
 {
     QBENCHMARK {
         UDSEntryMS entry;
         fillQMapStructEntry(entry, now_time_t, nameStr);
         QCOMPARE(entry.count(), 8);
     }
 }
 
 void UdsEntryBenchmark::testMapStructApp()
 {
     UDSEntryMS entry;
     fillQMapStructEntry(entry, now_time_t, nameStr);
 
     QString displayName;
     KIO::filesize_t size;
     QString url;
 
     QBENCHMARK {
         // For a field that we assume to always be there
         displayName = entry.value(KIO::UDSEntry::UDS_NAME).m_str;
 
         // For a field that might not be there
         auto it = entry.constFind(KIO::UDSEntry::UDS_URL);
         const auto end = entry.cend();
         if (it != end) {
             url = it.value().m_str;
         }
 
         it = entry.constFind(KIO::UDSEntry::UDS_SIZE);
         if (it != end) {
             size = it.value().m_long;
         }
 
         QCOMPARE(size, 123456ULL);
         QCOMPARE(displayName, QStringLiteral("name"));
         QVERIFY(url.isEmpty());
     }
 }
 
 // Frank's suggestion in https://git.reviewboard.kde.org/r/118452/
 class FrankUDSEntry
 {
 public:
     class Field
     {
     public:
         inline Field(const QString &value)
             : m_str(value)
             , m_long(0)
         {
         }
         inline Field(long long value = 0)
             : m_long(value)
         {
         }
         QString m_str;
         long long m_long;
     };
     QList<Field> fields;
     // If udsIndexes[i] == uds, then fields[i] contains the value for 'uds'.
     QList<uint> udsIndexes;
 
     void reserve(int size)
     {
         fields.reserve(size);
         udsIndexes.reserve(size);
     }
     void insert(uint udsField, const QString &value)
     {
         const int index = udsIndexes.indexOf(udsField);
         if (index >= 0) {
             fields[index] = Field(value);
         } else {
             udsIndexes.append(udsField);
             fields.append(Field(value));
         }
     }
     void replaceOrInsert(uint udsField, const QString &value)
     {
         insert(udsField, value);
     }
     void insert(uint udsField, long long value)
     {
         const int index = udsIndexes.indexOf(udsField);
         if (index >= 0) {
             fields[index] = Field(value);
         } else {
             udsIndexes.append(udsField);
             fields.append(Field(value));
         }
     }
     void replaceOrInsert(uint udsField, long long value)
     {
         insert(udsField, value);
     }
     int count() const
     {
         return udsIndexes.count();
     }
     QString stringValue(uint udsField) const
     {
         const int index = udsIndexes.indexOf(udsField);
         if (index >= 0) {
             return fields.at(index).m_str;
         } else {
             return QString();
         }
     }
     long long numberValue(uint udsField, long long defaultValue = -1) const
     {
         const int index = udsIndexes.indexOf(udsField);
         if (index >= 0) {
             return fields.at(index).m_long;
         } else {
             return defaultValue;
         }
     }
 };
 
 template<class T>
 static void fillUDSEntries(T &entry, time_t now_time_t, const QString &nameStr)
 {
     entry.reserve(8);
     // In random order of index
     entry.insert(KIO::UDSEntry::UDS_ACCESS_TIME, now_time_t);
     entry.insert(KIO::UDSEntry::UDS_MODIFICATION_TIME, now_time_t);
     entry.insert(KIO::UDSEntry::UDS_SIZE, 123456ULL);
     entry.insert(KIO::UDSEntry::UDS_NAME, nameStr);
     entry.insert(KIO::UDSEntry::UDS_GROUP, nameStr);
     entry.insert(KIO::UDSEntry::UDS_USER, nameStr);
     entry.insert(KIO::UDSEntry::UDS_ACCESS, 0644);
     entry.insert(KIO::UDSEntry::UDS_FILE_TYPE, S_IFREG);
 }
 
 template<class T>
 void testFill(time_t now_time_t, const QString &nameStr)
 {
     QBENCHMARK {
         T entry;
         fillUDSEntries<T>(entry, now_time_t, nameStr);
         QCOMPARE(entry.count(), 8);
     }
 }
 
 template<class T>
 void testCompare(time_t now_time_t, const QString &nameStr)
 {
     T entry;
     T entry2;
     fillUDSEntries<T>(entry, now_time_t, nameStr);
     fillUDSEntries<T>(entry2, now_time_t, nameStr);
     QCOMPARE(entry.count(), 8);
     QCOMPARE(entry2.count(), 8);
     QBENCHMARK {
         bool equal = entry.stringValue(KIO::UDSEntry::UDS_NAME) == entry2.stringValue(KIO::UDSEntry::UDS_NAME)
             && entry.numberValue(KIO::UDSEntry::UDS_SIZE) == entry2.numberValue(KIO::UDSEntry::UDS_SIZE)
             && entry.numberValue(KIO::UDSEntry::UDS_MODIFICATION_TIME) == entry2.numberValue(KIO::UDSEntry::UDS_MODIFICATION_TIME)
             && entry.numberValue(KIO::UDSEntry::UDS_ACCESS_TIME) == entry2.numberValue(KIO::UDSEntry::UDS_ACCESS_TIME)
             && entry.numberValue(KIO::UDSEntry::UDS_FILE_TYPE) == entry2.numberValue(KIO::UDSEntry::UDS_FILE_TYPE)
             && entry.numberValue(KIO::UDSEntry::UDS_ACCESS) == entry2.numberValue(KIO::UDSEntry::UDS_ACCESS)
             && entry.stringValue(KIO::UDSEntry::UDS_USER) == entry2.stringValue(KIO::UDSEntry::UDS_USER)
             && entry.stringValue(KIO::UDSEntry::UDS_GROUP) == entry2.stringValue(KIO::UDSEntry::UDS_GROUP);
         QVERIFY(equal);
     }
 }
 
 template<class T>
 void testApp(time_t now_time_t, const QString &nameStr)
 {
     T entry;
     fillUDSEntries<T>(entry, now_time_t, nameStr);
 
     QString displayName;
     KIO::filesize_t size;
     QString url;
 
     QBENCHMARK {
         displayName = entry.stringValue(KIO::UDSEntry::UDS_NAME);
         url = entry.stringValue(KIO::UDSEntry::UDS_URL);
         size = entry.numberValue(KIO::UDSEntry::UDS_SIZE);
         QCOMPARE(size, 123456ULL);
         QCOMPARE(displayName, QStringLiteral("name"));
         QVERIFY(url.isEmpty());
     }
 }
 
 void UdsEntryBenchmark::testTwoVectorsSlaveFill()
 {
     testFill<FrankUDSEntry>(now_time_t, nameStr);
 }
 void UdsEntryBenchmark::testTwoVectorsSlaveCompare()
 {
     testCompare<FrankUDSEntry>(now_time_t, nameStr);
 }
 void UdsEntryBenchmark::testTwoVectorsApp()
 {
     testApp<FrankUDSEntry>(now_time_t, nameStr);
 }
 
 // Instead of two vectors, use only one
 class AnotherUDSEntry
 {
 private:
     struct Field {
         inline Field()
         {
         }
         inline Field(const uint index, const QString &value)
             : m_str(value)
             , m_index(index)
         {
         }
         inline Field(const uint index, long long value = 0)
             : m_long(value)
             , m_index(index)
         {
         }
         // This operator helps to gain 1ms just comparing the key
         inline bool operator==(const Field &other) const
         {
             return m_index == other.m_index;
         }
 
         QString m_str;
         long long m_long = LLONG_MIN;
         uint m_index = 0;
     };
     std::vector<Field> storage;
 
 public:
     void reserve(int size)
     {
         storage.reserve(size);
     }
     void insert(uint udsField, const QString &value)
     {
         Q_ASSERT(udsField & KIO::UDSEntry::UDS_STRING);
         Q_ASSERT(std::find_if(storage.cbegin(),
                               storage.cend(),
                               [udsField](const Field &entry) {
                                   return entry.m_index == udsField;
                               })
                  == storage.cend());
         storage.emplace_back(udsField, value);
     }
     void replaceOrInsert(uint udsField, const QString &value)
     {
         Q_ASSERT(udsField & KIO::UDSEntry::UDS_STRING);
         auto it = std::find_if(storage.begin(), storage.end(), [udsField](const Field &entry) {
             return entry.m_index == udsField;
         });
         if (it != storage.end()) {
             it->m_str = value;
             return;
         }
         storage.emplace_back(udsField, value);
     }
     void insert(uint udsField, long long value)
     {
         Q_ASSERT(udsField & KIO::UDSEntry::UDS_NUMBER);
         Q_ASSERT(std::find_if(storage.cbegin(),
                               storage.cend(),
                               [udsField](const Field &entry) {
                                   return entry.m_index == udsField;
                               })
                  == storage.cend());
         storage.emplace_back(udsField, value);
     }
     void replaceOrInsert(uint udsField, long long value)
     {
         Q_ASSERT(udsField & KIO::UDSEntry::UDS_NUMBER);
         auto it = std::find_if(storage.begin(), storage.end(), [udsField](const Field &entry) {
             return entry.m_index == udsField;
         });
         if (it != storage.end()) {
             it->m_long = value;
             return;
         }
         storage.emplace_back(udsField, value);
     }
     int count() const
     {
         return storage.size();
     }
     QString stringValue(uint udsField) const
     {
         auto it = std::find_if(storage.cbegin(), storage.cend(), [udsField](const Field &entry) {
             return entry.m_index == udsField;
         });
         if (it != storage.cend()) {
             return it->m_str;
         }
         return QString();
     }
     long long numberValue(uint udsField, long long defaultValue = -1) const
     {
         auto it = std::find_if(storage.cbegin(), storage.cend(), [udsField](const Field &entry) {
             return entry.m_index == udsField;
         });
         if (it != storage.cend()) {
             return it->m_long;
         }
         return defaultValue;
     }
 };
 Q_DECLARE_TYPEINFO(AnotherUDSEntry, Q_RELOCATABLE_TYPE);
 
 void UdsEntryBenchmark::testAnotherSlaveFill()
 {
     testFill<AnotherUDSEntry>(now_time_t, nameStr);
 }
 void UdsEntryBenchmark::testAnotherSlaveCompare()
 {
     testCompare<AnotherUDSEntry>(now_time_t, nameStr);
 }
 void UdsEntryBenchmark::testAnotherApp()
 {
     testApp<AnotherUDSEntry>(now_time_t, nameStr);
 }
 
 // Instead of two vectors, use only one sorted by index and accessed using a binary search.
 class AnotherV2UDSEntry
 {
 private:
     struct Field {
         inline Field()
         {
         }
         inline Field(const uint index, const QString &value)
             : m_str(value)
             , m_index(index)
         {
         }
         inline Field(const uint index, long long value = 0)
             : m_long(value)
             , m_index(index)
         {
         }
         // This operator helps to gain 1ms just comparing the key
         inline bool operator==(const Field &other) const
         {
             return m_index == other.m_index;
         }
 
         QString m_str;
         long long m_long = LLONG_MIN;
         uint m_index = 0;
     };
     std::vector<Field> storage;
 
 private:
     static inline bool less(const Field &other, const uint index)
     {
         return other.m_index < index;
     }
 
 public:
     void reserve(int size)
     {
         storage.reserve(size);
     }
     void insert(uint udsField, const QString &value)
     {
         Q_ASSERT(udsField & KIO::UDSEntry::UDS_STRING);
         auto it = std::lower_bound(storage.cbegin(), storage.cend(), udsField, less);
         Q_ASSERT(it == storage.cend() || it->m_index != udsField);
         storage.insert(it, Field(udsField, value));
     }
     void replaceOrInsert(uint udsField, const QString &value)
     {
         Q_ASSERT(udsField & KIO::UDSEntry::UDS_STRING);
         auto it = std::lower_bound(storage.begin(), storage.end(), udsField, less);
         if (it != storage.end() && it->m_index == udsField) {
             it->m_str = value;
             return;
         }
         storage.insert(it, Field(udsField, value));
     }
     void insert(uint udsField, long long value)
     {
         Q_ASSERT(udsField & KIO::UDSEntry::UDS_NUMBER);
         auto it = std::lower_bound(storage.cbegin(), storage.cend(), udsField, less);
         Q_ASSERT(it == storage.end() || it->m_index != udsField);
         storage.insert(it, Field(udsField, value));
     }
     void replaceOrInsert(uint udsField, long long value)
     {
         Q_ASSERT(udsField & KIO::UDSEntry::UDS_NUMBER);
         auto it = std::lower_bound(storage.begin(), storage.end(), udsField, less);
         if (it != storage.end() && it->m_index == udsField) {
             it->m_long = value;
             return;
         }
         storage.insert(it, Field(udsField, value));
     }
     int count() const
     {
         return storage.size();
     }
     QString stringValue(uint udsField) const
     {
         auto it = std::lower_bound(storage.cbegin(), storage.cend(), udsField, less);
         if (it != storage.end() && it->m_index == udsField) {
             return it->m_str;
         }
         return QString();
     }
     long long numberValue(uint udsField, long long defaultValue = -1) const
     {
         auto it = std::lower_bound(storage.cbegin(), storage.cend(), udsField, less);
         if (it != storage.end() && it->m_index == udsField) {
             return it->m_long;
         }
         return defaultValue;
     }
 };
 Q_DECLARE_TYPEINFO(AnotherV2UDSEntry, Q_RELOCATABLE_TYPE);
 
 void UdsEntryBenchmark::testAnotherV2SlaveFill()
 {
     testFill<AnotherV2UDSEntry>(now_time_t, nameStr);
 }
 void UdsEntryBenchmark::testAnotherV2SlaveCompare()
 {
     testCompare<AnotherV2UDSEntry>(now_time_t, nameStr);
 }
 void UdsEntryBenchmark::testAnotherV2App()
 {
     testApp<AnotherV2UDSEntry>(now_time_t, nameStr);
 }
 
 QTEST_MAIN(UdsEntryBenchmark)
 
 #include "udsentry_api_comparison_benchmark.moc"