Module Name: src
Committed By: joerg
Date: Thu Nov 24 18:44:25 UTC 2011
Modified Files:
src/lib/libc/string: wcscspn.c wcspbrk.c
Added Files:
src/lib/libc/string: wcscspn_bloom.h
Log Message:
In wcscspn and wcspbrk, handle set size of 0 and 1 explicitly.
For larger sets, use a bloom filter to avoid the inner loop for most of
the input. The current implementation uses a simple modular hash as
first function (well suited for input e.g. in ISO Latin character sets)
and a more complex multiplicative hash as second function with a filter
size of 512 Bit. This reduces the typical run time to O(n+m).
To generate a diff of this commit:
cvs rdiff -u -r1.3 -r1.4 src/lib/libc/string/wcscspn.c
cvs rdiff -u -r0 -r1.1 src/lib/libc/string/wcscspn_bloom.h
cvs rdiff -u -r1.4 -r1.5 src/lib/libc/string/wcspbrk.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
