Use a binary search to find the range containing a character in

RuneRange arrays. This is much faster when there are hundreds of
ranges (as is the case in UTF-8 locales) and was inspired by a
similar change made by Apple in Darwin.

3 files changed, 34 insertions, 20 deletions

diff --git a/lib/libc/locale/runetype.c b/lib/libc/locale/runetype.c
index ec1c2ec..def216c 100644
--- a/lib/libc/locale/runetype.c
+++ b/lib/libc/locale/runetype.c
@@ -44,21 +44,25 @@ unsigned long
 ___runetype(c)
 	__ct_rune_t c;
 {
-	int x;
+	size_t lim;
 	_RuneRange *rr = &_CurrentRuneLocale->runetype_ext;
-	_RuneEntry *re = rr->ranges;
+	_RuneEntry *base, *re;
 
 	if (c < 0 || c == EOF)
 		return(0L);
 
-	for (x = 0; x < rr->nranges; ++x, ++re) {
-		if (c < re->min)
-			return(0L);
-		if (c <= re->max) {
+	/* Binary search -- see bsearch.c for explanation. */
+	base = rr->ranges;
+	for (lim = rr->nranges; lim != 0; lim >>= 1) {
+		re = base + (lim >> 1);
+		if (re->min <= c && c <= re->max) {
 			if (re->types)
 			    return(re->types[c - re->min]);
 			else
 			    return(re->map);
+		} else if (c > re->max) {
+			base = re + 1;
+			lim--;
 		}
 	}
 
diff --git a/lib/libc/locale/tolower.c b/lib/libc/locale/tolower.c
index f8caecb..04f3992 100644
--- a/lib/libc/locale/tolower.c
+++ b/lib/libc/locale/tolower.c
@@ -44,18 +44,23 @@ __ct_rune_t
 ___tolower(c)
 	__ct_rune_t c;
 {
-	int x;
+	size_t lim;
 	_RuneRange *rr = &_CurrentRuneLocale->maplower_ext;
-	_RuneEntry *re = rr->ranges;
+	_RuneEntry *base, *re;
 
 	if (c < 0 || c == EOF)
 		return(c);
 
-	for (x = 0; x < rr->nranges; ++x, ++re) {
-		if (c < re->min)
-			return(c);
-		if (c <= re->max)
-			return(re->map + c - re->min);
+	/* Binary search -- see bsearch.c for explanation. */
+	base = rr->ranges;
+	for (lim = rr->nranges; lim != 0; lim >>= 1) {
+		re = base + (lim >> 1);
+		if (re->min <= c && c <= re->max)
+			return (re->map + c - re->min);
+		else if (c > re->max) {
+			base = re + 1;
+			lim--;
+		}
 	}
 
 	return(c);
diff --git a/lib/libc/locale/toupper.c b/lib/libc/locale/toupper.c
index 6ce6757..b83365d 100644
--- a/lib/libc/locale/toupper.c
+++ b/lib/libc/locale/toupper.c
@@ -44,18 +44,23 @@ __ct_rune_t
 ___toupper(c)
 	__ct_rune_t c;
 {
-	int x;
+	size_t lim;
 	_RuneRange *rr = &_CurrentRuneLocale->mapupper_ext;
-	_RuneEntry *re = rr->ranges;
+	_RuneEntry *base, *re;
 
 	if (c < 0 || c == EOF)
 		return(c);
 
-	for (x = 0; x < rr->nranges; ++x, ++re) {
-		if (c < re->min)
-			return(c);
-		if (c <= re->max)
-			return(re->map + c - re->min);
+	/* Binary search -- see bsearch.c for explanation. */
+	base = rr->ranges;
+	for (lim = rr->nranges; lim != 0; lim >>= 1) {
+		re = base + (lim >> 1);
+		if (re->min <= c && c <= re->max)
+			return (re->map + c - re->min);
+		else if (c > re->max) {
+			base = re + 1;
+			lim--;
+		}
 	}
 
 	return(c);