File indexing completed on 2024-12-08 04:17:52

0001 /*
0002     SPDX-FileCopyrightText: 2020 Volker Krause <vkrause@kde.org>
0003 
0004     SPDX-License-Identifier: LGPL-2.0-or-later
0005 */
0006 
0007 #ifndef INDEXEDDATATABLE_H
0008 #define INDEXEDDATATABLE_H
0009 
0010 #include <QIODevice>
0011 
0012 #include <functional>
0013 #include <vector>
0014 
0015 class QByteArray;
0016 class QIODevice;
0017 class QString;
0018 
0019 /** Indexed data table, a generalized form of a string table.
0020  *  Entries are of varying length, so a terminating entry is required to separate them (such as a null byte in strings).
0021  *  Does suffix compression, ie. an entry "B" will be represented by pointing side another element "AB" if present.
0022  *  @tparam Entry must be iterable, element-wise comparable, copyable and have a size() method
0023  */
0024 template <typename Entry>
0025 class IndexedDataTable
0026 {
0027 public:
0028     inline void addEntry(const Entry &entry)
0029     {
0030         for (auto it = m_entries.begin(); it != m_entries.end(); ++it) {
0031             if (entry.size() <= (*it).size()) {
0032                 if (std::equal((*it).begin() + ((*it).size() - entry.size()), (*it).end(), entry.begin())) {
0033                     return; // new entry is a suffix of (or equal to) an existing element
0034                 }
0035             } else {
0036                 if (std::equal(entry.begin() + (entry.size() - (*it).size()), entry.end(), (*it).begin())) {
0037                     (*it) = entry; // an existing element is a suffix of the new element
0038                     return;
0039                 }
0040             }
0041         }
0042         m_entries.push_back(entry);
0043     }
0044 
0045     inline std::size_t entryOffset(const Entry &entry) const
0046     {
0047         std::size_t offset = 0;
0048         for (const auto &it : m_entries) {
0049             if (entry.size() <= it.size()) {
0050                 const auto subOffset = it.size() - entry.size();
0051                 if (std::equal(it.begin() + subOffset, it.end(), entry.begin())) {
0052                     return offset + subOffset;
0053                 }
0054             }
0055             offset += it.size() + 1;
0056         }
0057 
0058         return std::numeric_limits<std::size_t>::max();
0059     }
0060 
0061     /** @param entryWrite must write the terminating element at the end! */
0062     inline void writeCode(const char* type, const char *name, QIODevice *out, std::function<void(const Entry &entry, QIODevice *out)> entryWriter) const
0063     {
0064         out->write("static const ");
0065         out->write(type);
0066         out->write(" ");
0067         out->write(name);
0068         out->write("[] = {\n");
0069         for (const auto &it : m_entries) {
0070             out->write("    ");
0071             entryWriter(it, out);
0072             out->write("\n");
0073         }
0074         out->write("};\n\n");
0075     }
0076 
0077 private:
0078     std::vector<Entry> m_entries;
0079 };
0080 
0081 /** String table specialization. */
0082 class StringTable : IndexedDataTable<QByteArray>
0083 {
0084 public:
0085     void addString(const QString &s);
0086     std::size_t stringOffset(const QString &s) const;
0087     void writeCode(const char *name, QIODevice *out) const;
0088 };
0089 
0090 #endif // INDEXEDDATATABLE_H