Optimize latin_tolower(). Marge from master: https://android-git.corp.google.com/g/#change,49214
Change-Id: Ib1d7711aca533c21e5179b557a3ed806ac3fbdc6
diff --git a/native/src/char_utils.cpp b/native/src/char_utils.cpp
index 3cacc9e..c9204df 100644
--- a/native/src/char_utils.cpp
+++ b/native/src/char_utils.cpp
@@ -14,7 +14,7 @@
* limitations under the License.
*/
-#include <stdlib.h>
+#include <sys/types.h>
namespace latinime {
@@ -882,18 +882,25 @@
{ 0xFF3A, 0xFF5A } // FULLWIDTH LATIN CAPITAL LETTER Z
};
-static int compare_pair_capital(const void *a, const void *b) {
- return (int)((struct LatinCapitalSmallPair*)a)->capital
- - (int)((struct LatinCapitalSmallPair*)b)->capital;
-}
+unsigned short latin_tolower(unsigned short c0) {
+ const struct LatinCapitalSmallPair *p;
+ const struct LatinCapitalSmallPair *base = SORTED_CHAR_MAP;
+ int c = c0;
+ int lim, cmp;
+ const size_t nmemb = sizeof(SORTED_CHAR_MAP) / sizeof(SORTED_CHAR_MAP[0]);
-unsigned short latin_tolower(unsigned short c) {
- struct LatinCapitalSmallPair *p =
- (struct LatinCapitalSmallPair *)bsearch(&c, SORTED_CHAR_MAP,
- sizeof(SORTED_CHAR_MAP) / sizeof(SORTED_CHAR_MAP[0]),
- sizeof(SORTED_CHAR_MAP[0]),
- compare_pair_capital);
- return p ? p->small : c;
+ // Binary search: Taken from bionic
+ for (lim = nmemb; lim != 0; lim >>= 1) {
+ p = base + (lim >> 1);
+ cmp = c - (int)p->capital;
+ if (cmp == 0)
+ return p->small;
+ if (cmp > 0) { /* key > p: move right */
+ base = p + 1;
+ lim--;
+ } /* else move left */
+ }
+ return c0;
}
} // namespace latinime