diff options
author | dt <dt@FreeBSD.org> | 1999-09-12 19:42:38 +0000 |
---|---|---|
committer | dt <dt@FreeBSD.org> | 1999-09-12 19:42:38 +0000 |
commit | 78e49a27cc1f5572ecffaca16688aebe823504a6 (patch) | |
tree | 72fdf93da0c885eb65be3cc009e9a879ae291309 /lib/libc/locale/collate.c | |
parent | d9de85e5aa4a1241264ea9f89a866de7149f2b93 (diff) | |
download | FreeBSD-src-78e49a27cc1f5572ecffaca16688aebe823504a6.zip FreeBSD-src-78e49a27cc1f5572ecffaca16688aebe823504a6.tar.gz |
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.
Diffstat (limited to 'lib/libc/locale/collate.c')
-rw-r--r-- | lib/libc/locale/collate.c | 19 |
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; } |