From 8bccf93300a4fb921fd9b59bf346f6a6b08dfe53 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Morten=20Johan=20S=C3=B8rvig?= Date: Thu, 3 Apr 2014 12:40:45 +0200 Subject: Make the QPlatformTheme::keyBindings() search deterministic MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit QPlatformTheme::keyBindings() performs a binary search into an ordered list of StandardKey -> Key Sequence mappings where each StandardKey can have multiple key sequences. Previously the order of the Key Sequences in the returned list would be indeterministic and, except for the designated pri-1 key sequence, would not necessarily correspond to the list order. (The ordering was dependent on where the binary search "hits", which again depends on the size of the list.) This caused trouble when adding mappings, since it would change the order in the returned key sequence list for existing mappings and confusingly cause (apparently) unrelated test failures. Fix this by replacing the manually coded binary search with std::equal_range. One test case needed to be fixed up because it had the result in the wrong order (verified by looking at QPlatformTheme::keyBindings). Change-Id: I555ca2736b1a8e6454dc79645a8246f80119cfc2 Done-with: Marc Mutz Reviewed-by: Marc Mutz Reviewed-by: Morten Johan Sørvig --- src/gui/kernel/qplatformtheme.cpp | 83 +++++++++------------- .../gui/kernel/qkeysequence/tst_qkeysequence.cpp | 2 +- 2 files changed, 34 insertions(+), 51 deletions(-) diff --git a/src/gui/kernel/qplatformtheme.cpp b/src/gui/kernel/qplatformtheme.cpp index 3e48c48c2c..c53b71eafc 100644 --- a/src/gui/kernel/qplatformtheme.cpp +++ b/src/gui/kernel/qplatformtheme.cpp @@ -45,6 +45,7 @@ #include #include +#include QT_BEGIN_NAMESPACE @@ -569,6 +570,23 @@ static inline int maybeSwapShortcut(int shortcut) } #endif +// mixed-mode predicate: all of these overloads are actually needed (but not all for every compiler) +struct ByStandardKey { + typedef bool result_type; + + bool operator()(QKeySequence::StandardKey lhs, QKeySequence::StandardKey rhs) const + { return lhs < rhs; } + + bool operator()(const QKeyBinding& lhs, const QKeyBinding& rhs) const + { return operator()(lhs.standardKey, rhs.standardKey); } + + bool operator()(QKeySequence::StandardKey lhs, const QKeyBinding& rhs) const + { return operator()(lhs, rhs.standardKey); } + + bool operator()(const QKeyBinding& lhs, QKeySequence::StandardKey rhs) const + { return operator()(lhs.standardKey, rhs); } +}; + /*! Returns the key sequence that should be used for a standard action. @@ -579,62 +597,27 @@ QList QPlatformTheme::keyBindings(QKeySequence::StandardKey key) c const uint platform = QPlatformThemePrivate::currentKeyPlatforms(); QList list; - uint N = QPlatformThemePrivate::numberOfKeyBindings; - int first = 0; - int last = N - 1; + std::pair range = + std::equal_range(QPlatformThemePrivate::keyBindings, + QPlatformThemePrivate::keyBindings + QPlatformThemePrivate::numberOfKeyBindings, + key, ByStandardKey()); - while (first <= last) { - int mid = (first + last) / 2; - const QKeyBinding &midVal = QPlatformThemePrivate::keyBindings[mid]; + for (const QKeyBinding *it = range.first; it < range.second; ++it) { + if (!(it->platform & platform)) + continue; - if (key > midVal.standardKey){ - first = mid + 1; // Search in top half - } - else if (key < midVal.standardKey){ - last = mid - 1; // Search in bottom half - } - else { - //We may have several equal values for different platforms, so we must search in both directions - //search forward including current location - for (unsigned int i = mid; i < N ; ++i) { - QKeyBinding current = QPlatformThemePrivate::keyBindings[i]; - if (current.standardKey != key) - break; - else if (current.platform & platform && current.standardKey == key) { - uint shortcut = -#if defined(Q_OS_MACX) - maybeSwapShortcut(current.shortcut); -#else - current.shortcut; -#endif - if (current.priority > 0) - list.prepend(QKeySequence(shortcut)); - else - list.append(QKeySequence(shortcut)); - } - } - - //search back - for (int i = mid - 1 ; i >= 0 ; --i) { - QKeyBinding current = QPlatformThemePrivate::keyBindings[i]; - if (current.standardKey != key) - break; - else if (current.platform & platform && current.standardKey == key) { - uint shortcut = + uint shortcut = #if defined(Q_OS_MACX) - maybeSwapShortcut(current.shortcut); + maybeSwapShortcut(it->shortcut); #else - current.shortcut; + it->shortcut; #endif - if (current.priority > 0) - list.prepend(QKeySequence(shortcut)); - else - list.append(QKeySequence(shortcut)); - } - } - break; - } + if (it->priority > 0) + list.prepend(QKeySequence(shortcut)); + else + list.append(QKeySequence(shortcut)); } + return list; } diff --git a/tests/auto/gui/kernel/qkeysequence/tst_qkeysequence.cpp b/tests/auto/gui/kernel/qkeysequence/tst_qkeysequence.cpp index b6ce2fb4b7..2edfddf6dd 100644 --- a/tests/auto/gui/kernel/qkeysequence/tst_qkeysequence.cpp +++ b/tests/auto/gui/kernel/qkeysequence/tst_qkeysequence.cpp @@ -391,7 +391,7 @@ void tst_QKeySequence::keyBindings() expected << ctrlC << ctrlInsert; break; default: // X11 - expected << ctrlC << QKeySequence(QStringLiteral("F16")) << ctrlInsert; + expected << ctrlC << ctrlInsert << QKeySequence(QStringLiteral("F16")); break; } QCOMPARE(bindings, expected); -- cgit v1.2.3