From 44b3bb9bcb34fc8ebed0b04f667fecef15d7bc82 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Sun, 28 Dec 2025 11:00:41 +0100 Subject: memmem, memcasemem: use kmp algorithm MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- memcasemem.c | 27 +++++++++++++++++++++++---- 1 file changed, 23 insertions(+), 4 deletions(-) (limited to 'memcasemem.c') diff --git a/memcasemem.c b/memcasemem.c index 6be8adc..d883b62 100644 --- a/memcasemem.c +++ b/memcasemem.c @@ -8,7 +8,7 @@ libsimple_memcasemem(const void *hay_, size_t hayn, const void *sub_, size_t sub { const char *hay = hay_; const char *sub = sub_; - const char *end; + size_t *next, i, j; if (!subn) return REMOVE_CONST(hay, char *); @@ -17,10 +17,29 @@ libsimple_memcasemem(const void *hay_, size_t hayn, const void *sub_, size_t sub if (subn == 1) return libsimple_memcasechr(hay, *sub, hayn); - /* TODO optimise */ - for (end = &hay[hayn - subn + 1]; hay != end; hay++) - if (tolower(*hay) == tolower(*sub) && !libsimple_memcasecmp(hay, sub, subn)) + next = alloca((subn + 1U) * sizeof(*next)); + i = 0, j = SIZE_MAX; + goto beginning; + for (; i < subn; i++, j++) { + if (tolower(sub[i]) == tolower(sub[j])) { + next[i] = next[j]; + } else { + beginning: + next[i] = j; + while (j != SIZE_MAX && tolower(sub[i]) != tolower(sub[j])) + j = next[j]; + } + } + + for (i = j = 0; i < hayn;) { + while (j != SIZE_MAX && tolower(sub[j]) != tolower(hay[i])) + j = next[j]; + i++; + if (++j == subn) { + hay = &hay[i - j]; return REMOVE_CONST(hay, char *); + } + } return NULL; } -- cgit v1.2.3-70-g09d2