From 78e49a27cc1f5572ecffaca16688aebe823504a6 Mon Sep 17 00:00:00 2001
From: dt
Date: Sun, 12 Sep 1999 19:42:38 +0000
Subject: 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.
---
lib/libc/locale/collate.c | 19 +++++++++++--------
1 file 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;
}
--
cgit v1.1