Exclude deleted groups from groupList()

This commit is an alternative to the earlier incorrect and reverted
b3dc879e8b108c26c929bfbe551bcdf77f140e94. That commit contained several
mistakes and an algorithmic complexity increase:
1) the added conditions were inverted: should have been
   `hasNonDeletedEntries` (without `!`);
2) KConfigPrivate::groupList() passed group instead of key.mGroup to
   hasNonDeletedEntries();
3) The complexity of hasNonDeletedEntries() is O(entryMap.size()). Calls
   to this function were added into loops that iterated entryMap.size()
   times. So the overall complexity of groupList() increased from linear
   to quadratic.

This fix collects `mGroup`s of non-deleted key entries instead of
`mGroup`s of group entries. The number of key entries can be much
greater than the number of group entries, so this fix hurts performance.
But at least the algorithmic complexity of groupList() stays linear.
Future commits can optimize the loops and make them almost as fast or
even faster than before this fix.

The `!key.mKey.isNull() && !entryMapIt->bDeleted` checks added in this
commit are consistent with the check in
KConfigPrivate::hasNonDeletedEntries(). KConfig::hasGroupImpl() forwards
its argument to hasNonDeletedEntries() with the following comment:
// No need to look for the actual group entry anymore, or for subgroups:
// a group exists if it contains any non-deleted entry.

BUG: 384039
FIXED-IN: 5.90

1 files changed, 2 insertions, 2 deletions

diff --git a/src/core/kconfig.cpp b/src/core/kconfig.cpp
index ed45d1dd..0b890132 100644
--- a/src/core/kconfig.cpp
+++ b/src/core/kconfig.cpp
@@ -281,7 +281,7 @@ QStringList KConfig::groupList() const
     for (auto entryMapIt = d->entryMap.cbegin(); entryMapIt != d->entryMap.cend(); ++entryMapIt) {
         const KEntryKey &key = entryMapIt.key();
         const QByteArray &group = key.mGroup;
-        if (key.mKey.isNull() && !group.isEmpty() && group != "<default>" && group != "$Version") {
+        if (!key.mKey.isNull() && !entryMapIt->bDeleted && !group.isEmpty() && group != "<default>" && group != "$Version") {
             const QString groupname = QString::fromUtf8(group);
             groups << groupname.left(groupname.indexOf(QLatin1Char('\x1d')));
         }
@@ -297,7 +297,7 @@ QStringList KConfigPrivate::groupList(const QByteArray &group) const
 
     for (auto entryMapIt = entryMap.cbegin(); entryMapIt != entryMap.cend(); ++entryMapIt) {
         const KEntryKey &key = entryMapIt.key();
-        if (key.mKey.isNull() && key.mGroup.startsWith(theGroup)) {
+        if (!key.mKey.isNull() && !entryMapIt->bDeleted && key.mGroup.startsWith(theGroup)) {
             const QString groupname = QString::fromUtf8(key.mGroup.mid(theGroup.length()));
             groups << groupname.left(groupname.indexOf(QLatin1Char('\x1d')));
         }