diff options
author | Mattias Andrée <maandree@operamail.com> | 2015-11-17 05:50:23 +0100 |
---|---|---|
committer | Mattias Andrée <maandree@operamail.com> | 2015-11-17 05:50:23 +0100 |
commit | c99cadbe02f659264cecb44c053d96383631147d (patch) | |
tree | baeb59b9b45e7ea798c92dc04af9ea55db8a3d2b /src/string/mem | |
parent | add strset (diff) | |
download | slibc-c99cadbe02f659264cecb44c053d96383631147d.tar.gz slibc-c99cadbe02f659264cecb44c053d96383631147d.tar.bz2 slibc-c99cadbe02f659264cecb44c053d96383631147d.tar.xz |
rearrange files
Signed-off-by: Mattias Andrée <maandree@operamail.com>
Diffstat (limited to 'src/string/mem')
-rw-r--r-- | src/string/mem/memcasecmp.c | 50 | ||||
-rw-r--r-- | src/string/mem/memcasemem.c | 55 | ||||
-rw-r--r-- | src/string/mem/memccpy.c | 45 | ||||
-rw-r--r-- | src/string/mem/memchr.c | 42 | ||||
-rw-r--r-- | src/string/mem/memcmove.c | 47 | ||||
-rw-r--r-- | src/string/mem/memcmp.c | 42 | ||||
-rw-r--r-- | src/string/mem/memcpy.c | 38 | ||||
-rw-r--r-- | src/string/mem/memdup.c | 40 | ||||
-rw-r--r-- | src/string/mem/memmem.c | 52 | ||||
-rw-r--r-- | src/string/mem/memmove.c | 42 | ||||
-rw-r--r-- | src/string/mem/mempcpy.c | 36 | ||||
-rw-r--r-- | src/string/mem/mempmove.c | 37 | ||||
-rw-r--r-- | src/string/mem/memrchr.c | 46 | ||||
-rw-r--r-- | src/string/mem/memset.c | 37 | ||||
-rw-r--r-- | src/string/mem/rawmemchr.c | 42 | ||||
-rw-r--r-- | src/string/mem/substring.h | 85 |
16 files changed, 736 insertions, 0 deletions
diff --git a/src/string/mem/memcasecmp.c b/src/string/mem/memcasecmp.c new file mode 100644 index 0000000..d8ea014 --- /dev/null +++ b/src/string/mem/memcasecmp.c @@ -0,0 +1,50 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> +#include <ctype.h> + + + +/** + * Compare two memory segments alphabetically in a case insensitive manner. + * + * This is a slibc extension added because it was useful + * in implementing slibc itself. + * + * @param a A negative value is returned if this is the lesser. + * @param b A positive value is returned if this is the lesser. + * @param size The size of the segments. + * @return Zero is returned if `a` and `b` are equal, otherwise, + * see the specifications for `a` and `b`. + */ +int memcasecmp(const void* a, const void* b, size_t size) +{ + const signed char* s1 = a; + const signed char* s2 = b; + int c1, c2; + for (; size--; s1++, s2++) + if (*s1 != *s2) + { + c1 = isalpha(*s1) ? tolower(*s1) : (int)*s1; + c2 = isalpha(*s2) ? tolower(*s2) : (int)*s2; + if ((c1 -= c2)) + return c1; + } + return 0; +} + diff --git a/src/string/mem/memcasemem.c b/src/string/mem/memcasemem.c new file mode 100644 index 0000000..3fb24dc --- /dev/null +++ b/src/string/mem/memcasemem.c @@ -0,0 +1,55 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> +#include <unistd.h> +#include <alloca.h> +#include <ctype.h> + + +# pragma GCC diagnostic ignored "-Wdiscarded-qualifiers" + + + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * + * This is a slibc extension added because it was useful + * in implementing slibc itself. + * + * @param haystack The string to search. + * @param haystack_length The number of character to search. + * @param needle The sought after substring. + * @param needle_length The length of `needle`. + * @return Pointer to the first occurrence of + * the substring, `NULL` if not found. + */ +void* (memcasemem)(const void* __haystack, size_t haystack_length, + const void* __needle, size_t needle_length) +{ + const char* haystack = __haystack; + const char* needle = __needle; + if (haystack_length < needle_length) + return NULL; + if (haystack_length == needle_length) + return !(memcasecmp)(haystack, needle, haystack_length) ? haystack : NULL; +#define CASE +#include "substring.h" +#undef CASE +} + diff --git a/src/string/mem/memccpy.c b/src/string/mem/memccpy.c new file mode 100644 index 0000000..18e423d --- /dev/null +++ b/src/string/mem/memccpy.c @@ -0,0 +1,45 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + + +/** + * Copy a memory segment to another, non-overlapping, segment, + * but stop if a specific byte is encountered. + * + * @param whither The destination memory segment. + * @param whence The source memory segment. + * @param c The byte to stop at if encountered. + * @param size The maximum number of bytes to copy. + * @return `NULL` if `c` was not encountered, otherwise + * the possition of `c` translated to `whither`, + * that is, the address of `whither` plus the + * number of copied characters; the address of + * one character passed the last written character. + */ +void* (memccpy)(void* restrict whither, const void* restrict whence, int c, size_t size) +{ + char* stop = (memchr)(whence, c, size); + void* r = NULL; + if (stop != NULL) + size = (size_t)(stop - (const char*)whence), r = whither + size; + memcpy(whither, whence, size); + return r; +} + diff --git a/src/string/mem/memchr.c b/src/string/mem/memchr.c new file mode 100644 index 0000000..380fa0f --- /dev/null +++ b/src/string/mem/memchr.c @@ -0,0 +1,42 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + +# pragma GCC diagnostic ignored "-Wdiscarded-qualifiers" + + + +/** + * Find the first occurrence of a byte in a memory segment. + * + * @param segment The memory segment to search. + * @param c The sought after character. + * @param size The size of the memory segment. + * @return Pointer to the first occurrence of `c`, + * `NULL` if none were found. + */ +void* (memchr)(const void* segment, int c, size_t size) +{ + char* s = segment; + while (size--) + if (*s++ == c) + return s - 1; + return NULL; +} + diff --git a/src/string/mem/memcmove.c b/src/string/mem/memcmove.c new file mode 100644 index 0000000..50ed1f9 --- /dev/null +++ b/src/string/mem/memcmove.c @@ -0,0 +1,47 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + + +/** + * Copy a memory segment to another, possibly overlapping, segment, + * but stop if a specific byte is encountered. + * + * This is a slibc extension added for completeness. + * + * @param whither The destination memory segment. + * @param whence The source memory segment. + * @param c The byte to stop at if encountered. + * @param size The maximum number of bytes to copy. + * @return `NULL` if `c` was not encountered, otherwise + * the possition of `c` translated to `whither`, + * that is, the address of `whither` plus the + * number of copied characters; the address of + * one character passed the last written character. + */ +void* (memcmove)(void* whither, const void* whence, int c, size_t size) +{ + char* stop = (memchr)(whence, c, size); + void* r = NULL; + if (stop != NULL) + size = (size_t)(stop - (const char*)whence), r = whither + size; + memmove(whither, whence, size); + return r; +} + diff --git a/src/string/mem/memcmp.c b/src/string/mem/memcmp.c new file mode 100644 index 0000000..112cdd1 --- /dev/null +++ b/src/string/mem/memcmp.c @@ -0,0 +1,42 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + + +/** + * Compare two memory segments alphabetically in a case sensitive manner. + * + * @param a A negative value is returned if this is the lesser. + * @param b A positive value is returned if this is the lesser. + * @param size The size of the segments. + * @return Zero is returned if `a` and `b` are equal, otherwise, + * see the specifications for `a` and `b`. + */ +int memcmp(const void* a, const void* b, size_t size) +{ + const signed char* s1 = a; + const signed char* s2 = b; + while (size--) + if (*s1 == *s2) + s1++, s2++; + else + return (int)(*s1 - *s2); + return 0; +} + diff --git a/src/string/mem/memcpy.c b/src/string/mem/memcpy.c new file mode 100644 index 0000000..fcda29d --- /dev/null +++ b/src/string/mem/memcpy.c @@ -0,0 +1,38 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + + +/** + * Copy a memory segment to another, non-overlapping, segment. + * + * @param whither The destination memory segment. + * @param whence The source memory segment. + * @param size The number of bytes to copy. + * @return `whither` is returned. + */ +void* memcpy(void* restrict whither, const void* restrict whence, size_t size) +{ + char* d = whither; + const char* s = whence; + while (size--) + *d++ = *s++; + return whither; +} + diff --git a/src/string/mem/memdup.c b/src/string/mem/memdup.c new file mode 100644 index 0000000..3b301dc --- /dev/null +++ b/src/string/mem/memdup.c @@ -0,0 +1,40 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> +#include <stdlib.h> + + + +/** + * Duplicate a memory segment. + * + * This is a slibc extension. + * + * @param segment The memory segment to duplicate. + * @param size The size of the memory segment. + * @return The new segment. `NULL` is returned on error + * and `errno` is set to indicate the error. + * + * @throws ENOMEM The process could not allocate sufficient amount of memory. + */ +void* memdup(const void* segment, size_t size) +{ + void* r = malloc(size); + return r == NULL ? NULL : memcpy(r, segment, size); +} + diff --git a/src/string/mem/memmem.c b/src/string/mem/memmem.c new file mode 100644 index 0000000..62739d4 --- /dev/null +++ b/src/string/mem/memmem.c @@ -0,0 +1,52 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> +#include <unistd.h> +#include <alloca.h> + + +# pragma GCC diagnostic ignored "-Wdiscarded-qualifiers" + + + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * + * This is a GNU-compliant slibc extension. It was useful + * in implementing slibc itself. + * + * @param haystack The string to search. + * @param haystack_length The number of character to search. + * @param needle The sought after substring. + * @param needle_length The length of `needle`. + * @return Pointer to the first occurrence of + * the substring, `NULL` if not found. + */ +void* (memmem)(const void* __haystack, size_t haystack_length, + const void* __needle, size_t needle_length) +{ + const char* haystack = __haystack; + const char* needle = __needle; + if (haystack_length < needle_length) + return NULL; + if (haystack_length == needle_length) + return !(memcmp)(haystack, needle, haystack_length) ? haystack : NULL; +#include "substring.h" +} + diff --git a/src/string/mem/memmove.c b/src/string/mem/memmove.c new file mode 100644 index 0000000..41871c6 --- /dev/null +++ b/src/string/mem/memmove.c @@ -0,0 +1,42 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + + +/** + * Copy a memory segment to another, possibly overlapping, segment. + * + * @param whither The destination memory segment. + * @param whence The source memory segment. + * @param size The number of bytes to copy. + * @return `whither` is returned. + */ +void* memmove(void* whither, const void* whence, size_t size) +{ + char* d = whither; + const char* s = whence; + if ((size_t)(d - s) < size) + while (size--) + d[size] = s[size]; + else + while (size--) + *d++ = *s++; + return whither; +} + diff --git a/src/string/mem/mempcpy.c b/src/string/mem/mempcpy.c new file mode 100644 index 0000000..2072dc3 --- /dev/null +++ b/src/string/mem/mempcpy.c @@ -0,0 +1,36 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + + +/** + * Copy a memory segment to another, non-overlapping, segment. + * + * This is a GNU extension. + * + * @param whither The destination memory segment. + * @param whence The source memory segment. + * @param size The number of bytes to copy. + * @return `whither + size` is returned. + */ +void* mempcpy(void* restrict whither, const void* restrict whence, size_t size) +{ + return (char*)memcpy(whither, whence, size) + size; +} + diff --git a/src/string/mem/mempmove.c b/src/string/mem/mempmove.c new file mode 100644 index 0000000..f837032 --- /dev/null +++ b/src/string/mem/mempmove.c @@ -0,0 +1,37 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + + +/** + * Copy a memory segment to another, possibly overlapping, segment. + * + * This is a slibc extension added for completeness. + * It is only available if GNU extensions are available. + * + * @param whither The destination memory segment. + * @param whence The source memory segment. + * @param size The number of bytes to copy. + * @return `whither + size` is returned. + */ +void* mempmove(void* whither, const void* whence, size_t size) +{ + return (char*)memmove(whither, whence, size) + size; +} + diff --git a/src/string/mem/memrchr.c b/src/string/mem/memrchr.c new file mode 100644 index 0000000..7325049 --- /dev/null +++ b/src/string/mem/memrchr.c @@ -0,0 +1,46 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + +# pragma GCC diagnostic ignored "-Wdiscarded-qualifiers" + + + +/** + * Find the last occurrence of a byte in a memory segment. + * + * For improved performace, use this function instead + * of `strrchr` if you already know the length of the + * string. + * + * @param segment The memory segment to search. + * @param c The sought after character. + * @param size The size of the memory segment. + * @return Pointer to the last occurrence of `c`, + * `NULL` if none were found. + */ +void* (memrchr)(const void* segment, int c, size_t size) +{ + char* s = segment; + while (size--) + if (s[size] == c) + return s + size; + return NULL; +} + diff --git a/src/string/mem/memset.c b/src/string/mem/memset.c new file mode 100644 index 0000000..df36052 --- /dev/null +++ b/src/string/mem/memset.c @@ -0,0 +1,37 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + + +/** + * Override a memory segment with a repeated character. + * + * @param segment The beginning of the memory segment. + * @param c The character (8 bits wide.) + * @param size The size of the memory segment. + * @return `segment` is returned. + */ +void* memset(void* segment, int c, size_t size) +{ + char* s = segment; + while (size--) + *s++ = (char)c; + return segment; +} + diff --git a/src/string/mem/rawmemchr.c b/src/string/mem/rawmemchr.c new file mode 100644 index 0000000..8f5c03e --- /dev/null +++ b/src/string/mem/rawmemchr.c @@ -0,0 +1,42 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#include <string.h> + + +# pragma GCC diagnostic ignored "-Wdiscarded-qualifiers" + + + +/** + * Find the first occurrence of a byte in a memory segment. + * The memory segment must be known to contain the sought after byte. + * + * This is a GNU-compliant slibc extension. + * + * @param segment The memory segment to search. + * @param c The sought after character. + * @return Pointer to the first occurrence of `c`. + */ +void* (rawmemchr)(const void* segment, int c) +{ + char* s = segment; + for (;;) + if (*s++ == c) + return s - 1; +} + diff --git a/src/string/mem/substring.h b/src/string/mem/substring.h new file mode 100644 index 0000000..05ef7cc --- /dev/null +++ b/src/string/mem/substring.h @@ -0,0 +1,85 @@ +/** + * slibc — Yet another C library + * Copyright © 2015 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/* This file is intended to be included inside a + * [w]mem[r][case]mem function. `haystack` and + * `needle` shall be defined the same pointer type, + * but not as `void*`. `haystack_length` and + * `needle_length` shall be defined in the `size_t` + * type. CASE shall be defined iff case insensitive + * search shall be used. RIGHT shall be defined iff + * the last occurrence shall be find. WIDE shall be + * defined iff wide characters are used. It is assumed + * that `needle_length` <= `haystack_length` */ + + +/* The Knuth–Morris–Pratt algorithm. */ + + +/** + * Test whether to characters are equal. + * Case-sensitivity depends on `CASE` being defined. + * + * @param a One of the characters. + * @param b The other character. + * @return 1 if `a` and `b` or equal, 0 otherwise. + * The comparison is case-insensitive if + * `CASE` is defined. + */ +#if !defined(CASE) +# define CHREQ(a, b) (a == b) +#elif !defined(WIDE) +# define CHREQ(a, b) ((islower(a) ? tolower(a) : (a)) == tolower(b)) +#else +# define CHREQ(a, b) ((iswlower(a) ? towlower(a) : (a)) == towlower(b)) +#endif + + +/* TODO add support for RIGHT */ + + +/* The implementation of the algorithm, read + * elsewhere for documentation/explanation. */ +{ + ssize_t* next_map = alloca((needle_length + 1) * sizeof(ssize_t)); + ssize_t hay, ned, skp; + + ned = 0, skp = next_map[0] = -1; + while (ned < (ssize_t)needle_length) + { + while ((skp > -1) && !CHREQ(needle[ned], needle[skp])) + skp = next_map[skp]; + ned++, skp++; + next_map[ned] = CHREQ(needle[ned], needle[skp]) ? next_map[skp] : skp; + } + + hay = ned = 0; + while (hay < (ssize_t)haystack_length) + { + while ((ned > -1) && !CHREQ(haystack[hay], needle[ned])) + ned = next_map[ned]; + hay++, ned++; + if (ned >= (ssize_t)needle_length) + return needle + (hay - ned); + } + + return NULL; +} + + +#undef CHREQ + |