diff options
| -rw-r--r-- | memcasemem.c | 27 | ||||
| -rw-r--r-- | memmem.c | 34 |
2 files changed, 50 insertions, 11 deletions
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; } @@ -6,20 +6,40 @@ void * libsimple_memmem(const void *hay_, size_t hayn, const void *sub_, size_t subn) { - const char *hay = hay_, *end; - const char *sub = sub_; + const unsigned char *hay = hay_; + const unsigned char *sub = sub_; + size_t *next, i, j; if (!subn) - return REMOVE_CONST(hay, char *); + return REMOVE_CONST(hay, unsigned char *); if (hayn < subn) return NULL; if (subn == 1) return memchr(hay, *sub, hayn); - /* TODO optimise */ - for (end = &hay[hayn - subn + 1]; hay != end; hay++) - if (*hay == *sub && !memcmp(hay, sub, subn)) - return REMOVE_CONST(hay, char *); + next = alloca((subn + 1U) * sizeof(*next)); + i = 0, j = SIZE_MAX; + goto beginning; + for (; i < subn; i++, j++) { + if (sub[i] == sub[j]) { + next[i] = next[j]; + } else { + beginning: + next[i] = j; + while (j != SIZE_MAX && sub[i] != sub[j]) + j = next[j]; + } + } + + for (i = j = 0; i < hayn;) { + while (j != SIZE_MAX && sub[j] != hay[i]) + j = next[j]; + i++; + if (++j == subn) { + hay = &hay[i - j]; + return REMOVE_CONST(hay, unsigned char *); + } + } return NULL; } |