|
c358da1e
|
2008-01-10T12:06:35
|
|
Share two-way algorithm.
* lib/str-two-way.h: New file, merged from...
* lib/memmem.c: ...here...
* lib/strstr.c: ...and here.
* modules/memmem (Files): Use it.
* modules/strstr (Files): Likewise.
Signed-off-by: Eric Blake <ebb9@byu.net>
|
|
|
9d8d6cd7
|
2008-01-05T14:09:11
|
|
Rewrite memmem to guarantee linear complexity without malloc.
* lib/memmem.c (memmem): Use Two-Way rather than
Knuth-Morris-Pratt, to allow O(1) space usage.
(critical_factorization, two_way_short_needle)
(two_way_long_needle): New functions.
(knuth_morris_pratt): Delete.
* modules/memmem (Depends-on): No longer need malloca or stdbool.
Add stdint.
* tests/test-memmem.c (main): Add tests for periodic needle and
sublinear performance.
* doc/functions/memmem.texi (memmem): Document other deficiencies
in cygwin and older glibc.
Signed-off-by: Eric Blake <ebb9@byu.net>
|
|
e883a11c
|
2008-01-04T00:24:10
|
|
Treat untyped memory as an 'unsigned char' array.
|
|
|
bffe05f4
|
2007-12-31T11:53:40
|
|
Protect against integer overflow in malloca() calls.
|
|
f1c88d2e
|
2007-12-29T01:17:08
|
|
* lib/memmem.c (knuth_morris_pratt): Check for size_t overflow
when multiplying M by sizeof (size_t).
|
|
|
4a64397b
|
2007-12-26T16:13:28
|
|
Use GNU style coding conventions.
|
|
|
075c5c89
|
2007-12-26T16:10:15
|
|
Add more comments about Knuth-Morris-Pratt algorithm.
|
|
|
fc068cf4
|
2007-12-19T16:09:03
|
|
Fix memmem to avoid O(n^2) worst-case complexity.
* lib/memmem.c (knuth_morris_pratt): New function.
(memmem): Use it if first few naive iterations fail.
* m4/memmem.m4 (gl_FUNC_MEMMEM): Detect cygwin bug.
* modules/memcmp (License): Set to LGPLv2+, not LGPL.
* modules/memchr (License): Likewise.
* modules/memmem (Depends-on): Add memcmp, memchr, stdbool, and
malloca.
* tests/test-memmem.c: Rewrite, borrowing ideas from
test-mbsstr1.c; the old version wouldn't even compile!
* modules/memmem-tests: New file.
* lib/string.in.h (rpl_memmem): Add declaration.
* modules/string (Makefile.am): Substitute REPLACE_MEMMEM.
* m4/string_h.m4 (gl_HEADER_STRING_H_DEFAULTS): Default for
REPLACE_MEMMEM.
Signed-off-by: Eric Blake <ebb9@byu.net>
|
|
|
ed081024
|
2007-02-05T05:44:11
|
|
* lib/getsubopt.c [!_LIBC]: Include config.h and getsubopt.h.
* lib/memmem.c [!defined _LIBC]: Include config.h.
|
|
|
267a39ba
|
2005-05-14T06:03:57
|
|
*** empty log message ***
|
|
73d3a7a3
|
2004-10-04T13:33:49
|
|
Sync with glibc.
|
|
|
ec03ca35
|
2004-10-04T11:25:57
|
|
New module 'memmem', from Simon Josefsson.
|