From acccefbc667e7ee2c481b2fd0b45ba2f12e9237a Mon Sep 17 00:00:00 2001 From: Igor Kushnir Date: Sat, 25 Dec 2021 09:46:44 +0200 Subject: Look for entries with common group prefix in entryMap's subrange entryMap is ordered by the group name first. So there is no need to iterate over the entire map to process entries whose group names start with some prefix. Find the group name prefix's lower bound and iterate over the proper subrange instead. This should be much faster, especially if the subrange's size is much less than the entryMap's size. Adjust isGroupOrSubGroupMatch() helper function to assert the extracted startsWith() condition instead of rechecking it. Pass KEntryMapConstIterator in place of the group name to this function in order to simplify its callers' code. Reuse this helper function in KConfigPrivate::copyGroup(). --- src/core/kconfig.cpp | 56 +++++++++++++++++++----------------------------- src/core/kconfigdata_p.h | 30 ++++++++++++++++++++++++++ 2 files changed, 52 insertions(+), 34 deletions(-) (limited to 'src') diff --git a/src/core/kconfig.cpp b/src/core/kconfig.cpp index 4bbceeda..9e62c167 100644 --- a/src/core/kconfig.cpp +++ b/src/core/kconfig.cpp @@ -130,10 +130,16 @@ bool KConfigPrivate::lockLocal() return true; } +static bool isGroupOrSubGroupMatch(KEntryMapConstIterator entryMapIt, const QByteArray &group) +{ + const QByteArray &entryGroup = entryMapIt.key().mGroup; + Q_ASSERT_X(entryGroup.startsWith(group), Q_FUNC_INFO, "Precondition"); + return entryGroup.size() == group.size() || entryGroup[group.size()] == '\x1d'; +} + void KConfigPrivate::copyGroup(const QByteArray &source, const QByteArray &destination, KConfigGroup *otherGroup, KConfigBase::WriteConfigFlags flags) const { KEntryMap &otherMap = otherGroup->config()->d_ptr->entryMap; - const int len = source.length(); const bool sameName = (destination == source); // we keep this bool outside the for loop so that if @@ -141,16 +147,10 @@ void KConfigPrivate::copyGroup(const QByteArray &source, const QByteArray &desti // as dirty erroneously bool dirtied = false; - for (auto entryMapIt = entryMap.cbegin(); entryMapIt != entryMap.cend(); ++entryMapIt) { - const QByteArray &group = entryMapIt.key().mGroup; - - if (!group.startsWith(source)) { // nothing to do - continue; - } - + entryMap.forEachEntryWhoseGroupStartsWith(source, [&source, &destination, flags, &otherMap, sameName, &dirtied](KEntryMapConstIterator entryMapIt) { // don't copy groups that start with the same prefix, but are not sub-groups - if (group.length() > len && group[len] != '\x1d') { - continue; + if (!isGroupOrSubGroupMatch(entryMapIt, source)) { + return; } KEntryKey newKey = entryMapIt.key(); @@ -160,7 +160,7 @@ void KConfigPrivate::copyGroup(const QByteArray &source, const QByteArray &desti } if (!sameName) { - newKey.mGroup.replace(0, len, destination); + newKey.mGroup.replace(0, source.size(), destination); } KEntry entry = entryMapIt.value(); @@ -175,7 +175,7 @@ void KConfigPrivate::copyGroup(const QByteArray &source, const QByteArray &desti } otherMap[newKey] = entry; - } + }); if (dirtied) { otherGroup->config()->d_ptr->bDirty = true; @@ -318,50 +318,38 @@ QStringList KConfigPrivate::groupList(const QByteArray &group) const const QByteArray theGroup = group + '\x1d'; ByteArrayViewSet groups; - for (auto entryMapIt = entryMap.cbegin(); entryMapIt != entryMap.cend(); ++entryMapIt) { + entryMap.forEachEntryWhoseGroupStartsWith(theGroup, [&theGroup, &groups](KEntryMapConstIterator entryMapIt) { const KEntryKey &key = entryMapIt.key(); - if (!key.mKey.isNull() && !entryMapIt->bDeleted && key.mGroup.startsWith(theGroup)) { + if (!key.mKey.isNull() && !entryMapIt->bDeleted) { const auto subgroupStartPos = theGroup.size(); const auto subgroupEndPos = findFirstGroupEndPos(key.mGroup, subgroupStartPos); groups.emplace(key.mGroup.constData() + subgroupStartPos, subgroupEndPos - subgroupStartPos); } - } + }); return stringListFromUtf8Collection(groups); } -static bool isGroupOrSubGroupMatch(const QByteArray &potentialGroup, const QByteArray &group) -{ - if (!potentialGroup.startsWith(group)) { - return false; - } - return potentialGroup.length() == group.length() || potentialGroup[group.length()] == '\x1d'; -} - /// Returns @p parentGroup itself, all its subgroups, subsubgroups, and so on, including deleted groups. QSet KConfigPrivate::allSubGroups(const QByteArray &parentGroup) const { QSet groups; - for (KEntryMap::const_iterator entryMapIt = entryMap.begin(); entryMapIt != entryMap.end(); ++entryMapIt) { + entryMap.forEachEntryWhoseGroupStartsWith(parentGroup, [&parentGroup, &groups](KEntryMapConstIterator entryMapIt) { const KEntryKey &key = entryMapIt.key(); - if (key.mKey.isNull() && isGroupOrSubGroupMatch(key.mGroup, parentGroup)) { + if (key.mKey.isNull() && isGroupOrSubGroupMatch(entryMapIt, parentGroup)) { groups << key.mGroup; } - } + }); + return groups; } bool KConfigPrivate::hasNonDeletedEntries(const QByteArray &group) const { - for (KEntryMap::const_iterator it = entryMap.begin(); it != entryMap.end(); ++it) { - const KEntryKey &key = it.key(); - // Check for any non-deleted entry - if (isGroupOrSubGroupMatch(key.mGroup, group) && !key.mKey.isNull() && !it->bDeleted) { - return true; - } - } - return false; + return entryMap.anyEntryWhoseGroupStartsWith(group, [&group](KEntryMapConstIterator entryMapIt) { + return isGroupOrSubGroupMatch(entryMapIt, group) && !entryMapIt.key().mKey.isNull() && !entryMapIt->bDeleted; + }); } QStringList KConfigPrivate::keyListImpl(const QByteArray &theGroup) const diff --git a/src/core/kconfigdata_p.h b/src/core/kconfigdata_p.h index 5e5246f3..beb18f45 100644 --- a/src/core/kconfigdata_p.h +++ b/src/core/kconfigdata_p.h @@ -155,6 +155,17 @@ inline bool operator<(const KEntryKey &k1, const KEntryKey &k2) return (!k1.bDefault && k2.bDefault); } +/** + * Returns the minimum key that has @a mGroup == @p group. + * + * @note The returned "minimum key" is consistent with KEntryKey's operator<(). + * The return value of this function can be passed to KEntryMap::lowerBound(). + */ +inline KEntryKey minimumGroupKey(const QByteArray &group) +{ + return KEntryKey(group, QByteArray{}, true, false); +} + QDebug operator<<(QDebug dbg, const KEntryKey &key); QDebug operator<<(QDebug dbg, const KEntry &entry); @@ -230,6 +241,25 @@ public: } bool revertEntry(const QByteArray &group, const QByteArray &key, EntryOptions options, SearchFlags flags = SearchFlags()); + + template + void forEachEntryWhoseGroupStartsWith(const QByteArray &groupPrefix, ConstIteratorUser callback) const + { + for (auto it = lowerBound(minimumGroupKey(groupPrefix)), end = cend(); it != end && it.key().mGroup.startsWith(groupPrefix); ++it) { + callback(it); + } + } + + template + bool anyEntryWhoseGroupStartsWith(const QByteArray &groupPrefix, ConstIteratorPredicate predicate) const + { + for (auto it = lowerBound(minimumGroupKey(groupPrefix)), end = cend(); it != end && it.key().mGroup.startsWith(groupPrefix); ++it) { + if (predicate(it)) { + return true; + } + } + return false; + } }; Q_DECLARE_OPERATORS_FOR_FLAGS(KEntryMap::SearchFlags) Q_DECLARE_OPERATORS_FOR_FLAGS(KEntryMap::EntryOptions) -- cgit v1.2.1