Reduce time of __collate_substitute() from O(strlen(s)^2) to O(strlen(s)).

Other minor optimizations. I got ~30% speedup in strcoll() for 50 char strings,
~40% speedup for 100 char strings, and unmeasurable speedup for 1M strings.

Collates are still terribly slow. To make them reasonable fast,
__collate_substitute() should be killed.

1 files changed, 11 insertions, 8 deletions

diff --git a/lib/libc/locale/collate.c b/lib/libc/locale/collate.c
index f71870c..a73e4f1 100644
--- a/lib/libc/locale/collate.c
+++ b/lib/libc/locale/collate.c
@@ -102,23 +102,26 @@ u_char *
 __collate_substitute(s)
 	const u_char *s;
 {
-	int dest_len = 0, len = 0;
+	int dest_len, len, nlen;
 	int delta = strlen(s);
 	u_char *dest_str = NULL;
 
 	if(s == NULL || *s == '\0')
 		return __collate_strdup("");
+	delta += delta / 8;
+	dest_str = malloc(dest_len = delta);
+	if(dest_str == NULL)
+		__collate_err(EX_OSERR, __FUNCTION__);
+	len = 0;
 	while(*s) {
-		len += strlen(__collate_substitute_table[*s]);
-		while(dest_len <= len) {
-			if(!dest_str)
-				dest_str = calloc(dest_len = delta, 1);
-			else
-				dest_str = reallocf(dest_str, dest_len += delta);
+		nlen = len + strlen(__collate_substitute_table[*s]);
+		if (dest_len <= nlen) {
+			dest_str = reallocf(dest_str, dest_len = nlen + delta);
 			if(dest_str == NULL)
 				__collate_err(EX_OSERR, __FUNCTION__);
 		}
-		strcat(dest_str, __collate_substitute_table[*s++]);
+		strcpy(dest_str + len, __collate_substitute_table[*s++]);
+		len = nlen;
 	}
 	return dest_str;
 }