CVS commit: src/lib/libc/string

["Joerg Sonnenberger" <joerg%netbsd.org@localhost>]

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.