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