QLocale/Win: replace hand-written binary search with a call to lower_bound()

Binary search is notoriously hard to implement, and, while I didn't
spend time to prove it, this implementation was probably buggy, too
(any implementation which is missing a ±1 in the loop body is
suspicious).

Replace with a call to std::lower_bound(), which has precise semantics
and no bugs.

Task-number: QTBUG-103721
Change-Id: Ibe12c7d20b8c01e19a6f294f6c1b564b6b484b07
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>

1 files changed, 10 insertions, 18 deletions

diff --git a/src/corelib/text/qlocale_win.cpp b/src/corelib/text/qlocale_win.cpp
index 97ef7a3970..338d18bdcb 100644
--- a/src/corelib/text/qlocale_win.cpp
+++ b/src/corelib/text/qlocale_win.cpp
@@ -892,6 +892,10 @@ struct WindowsToISOListElt {
 
 namespace {
 struct ByWindowsCode {
+    constexpr bool operator()(int lhs, WindowsToISOListElt rhs) const noexcept
+    { return lhs < int(rhs.windows_code); }
+    constexpr bool operator()(WindowsToISOListElt lhs, int rhs) const noexcept
+    { return int(lhs.windows_code) < rhs; }
     constexpr bool operator()(WindowsToISOListElt lhs, WindowsToISOListElt rhs) const noexcept
     { return lhs.windows_code < rhs.windows_code; }
 };
@@ -1008,9 +1012,6 @@ static constexpr WindowsToISOListElt windows_to_iso_list[] = {
     { 0x500a, "es_PR" }
 };
 
-static const int windows_to_iso_count
-    = sizeof(windows_to_iso_list)/sizeof(WindowsToISOListElt);
-
 static_assert(q20::is_sorted(std::begin(windows_to_iso_list), std::end(windows_to_iso_list),
                              ByWindowsCode{}));
 
@@ -1023,21 +1024,12 @@ static const char *winLangCodeToIsoName(int code)
     if (cmp == 0)
         return windows_to_iso_list[0].iso_name;
 
-    int begin = 0;
-    int end = windows_to_iso_count;
-
-    while (end - begin > 1) {
-        uint mid = (begin + end)/2;
-
-        const WindowsToISOListElt *elt = windows_to_iso_list + mid;
-        int cmp = code - elt->windows_code;
-        if (cmp < 0)
-            end = mid;
-        else if (cmp > 0)
-            begin = mid;
-        else
-            return elt->iso_name;
-    }
+    const auto it = std::lower_bound(std::begin(windows_to_iso_list),
+                                     std::end(windows_to_iso_list),
+                                     code,
+                                     ByWindowsCode{});
+    if (it != std::end(windows_to_iso_list) && !ByWindowsCode{}(code, *it))
+        return it->iso_name;
 
     return 0;