Skip to content

Exclude deleted groups from groupList()

Igor Kushnir requested to merge work/fix-group-list into master

This commit is an alternative to the earlier incorrect and reverted b3dc879e. 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 mGroups of non-deleted key entries instead of mGroups 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.

BUG: 384039
FIXED-IN: 5.90

Merge request reports