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