diff options
| -rw-r--r-- | include/string.h | 125 | ||||
| -rw-r--r-- | include/wchar.h | 134 | ||||
| -rw-r--r-- | src/string/strchr.c | 15 | ||||
| -rw-r--r-- | src/string/strstr.c | 179 | ||||
| -rw-r--r-- | src/string/substring.h | 70 | ||||
| -rw-r--r-- | src/wchar/wcschr.c | 15 | ||||
| -rw-r--r-- | src/wchar/wcsstr.c | 189 |
7 files changed, 715 insertions, 12 deletions
diff --git a/include/string.h b/include/string.h index f1cc0c1..8034973 100644 --- a/include/string.h +++ b/include/string.h @@ -848,6 +848,131 @@ char* strrchr(const char*, int) /* TODO Add case insensitive character searching functions. */ +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +char* strstr(const char*, const char*) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull))); + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +char* strcasestr(const char*, const char*) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull))); + +#if defined(_SLIBC_SOURCE) && !defined(__PORTABLE) +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * + * This is a slibc extension added for because it was useful + * in implementing slibc itself. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @param maxlen The maximum number of character to search. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +char* strnstr(const char*, const char*, size_t) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull))); + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * + * This is a slibc extension added for completeness. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @param maxlen The maximum number of character to search. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +char* strncasestr(const char*, const char*, size_t) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull))); + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * It must already be known that such a substring exists. + * + * This is a slibc extension. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the substring. + */ +char* rawstrstr(const char*, const char*) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull, returns_nonnull))); + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * It must already be known that such a substring exists. + * + * This is a slibc extension. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the substring. + */ +char* rawstrcasestr(const char*, const char*) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull, returns_nonnull))); + +/** + * 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*, size_t, const void*, size_t) + __GCC_ONLY(__attribute__((warn_unused_result))); +#endif + +#if (defined(_GNU_SOURCE) || defined(_SLIBC_SOURCE)) && !defined(__PORTABLE) +/** + * 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*, size_t, const void*, size_t) + __GCC_ONLY(__attribute__((warn_unused_result))); +#endif + + +/* TODO Add case right-to-left substring searching functions. */ + + #endif diff --git a/include/wchar.h b/include/wchar.h index 66c4127..16644c8 100644 --- a/include/wchar.h +++ b/include/wchar.h @@ -804,6 +804,140 @@ wchar_t* wcsrchr(const wchar_t*, wchar_t) /* TODO Add case insensitive character searching functions. */ +/** + * This function is identical to `wcsstr`. + */ +wchar_t* wcswcs(const wchar_t*, const wchar_t*) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull))) + __deprecated("Use 'wcsstr' instead."); + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +wchar_t* wcsstr(const wchar_t*, const wchar_t*) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull))); + +#if defined(_SLIBC_SOURCE) && !defined(__PORTABLE) +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * + * This is a slibc extension. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +wchar_t* wcscasestr(const wchar_t*, const wchar_t*) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull))); + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * + * This is a slibc extension added for because it was useful + * in implementing slibc itself. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @param maxlen The maximum number of character to search. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +wchar_t* wcsnstr(const wchar_t*, const wchar_t*, size_t) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull))); + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * + * This is a slibc extension added for completeness. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @param maxlen The maximum number of character to search. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +wchar_t* wcsncasestr(const wchar_t*, const wchar_t*, size_t) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull))); + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * It must already be known that such a substring exists. + * + * This is a slibc extension. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the substring. + */ +wchar_t* rawwcsstr(const wchar_t*, const wchar_t*) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull, returns_nonnull))); + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * It must already be known that such a substring exists. + * + * This is a slibc extension. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the substring. + */ +wchar_t* rawwcscasestr(const wchar_t*, const wchar_t*) + __GCC_ONLY(__attribute__((warn_unused_result, nonnull, returns_nonnull))); + +/** + * 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. + */ +wchar_t* wmemcasemem(const wchar_t*, size_t, const wchar_t*, size_t); +#endif + +#if (defined(_GNU_SOURCE) || defined(_SLIBC_SOURCE)) && !defined(__PORTABLE) +/** + * Finds the first occurrence of a substring + * This search is case sensitive. + * + * This is a slibc extension added for completeness, + * and because it was 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. + */ +wchar_t* wmemmem(const wchar_t*, size_t, const wchar_t*, size_t) + __GCC_ONLY(__attribute__((warn_unused_result))); +#endif + + +/* TODO Add case right-to-left substring searching functions. */ + + #endif #endif diff --git a/src/string/strchr.c b/src/string/strchr.c index 6a25f78..21345d4 100644 --- a/src/string/strchr.c +++ b/src/string/strchr.c @@ -93,10 +93,11 @@ void* memrchr(const void* segment, int c, size_t size) */ char* strchr(const char* string, int c) { - while (; *string; string++) + for (;;) if (*string == c) return string; - return NULL; + else if (!*string++) + return NULL; } /* TODO Ensure that `s = strchr(s, 0)` is faster than `s = s + strlen(s)`. */ @@ -117,10 +118,11 @@ char* strchr(const char* string, int c) */ char* strchrnul(const char* string, int c) { - while (; *string; string++) + for (;; string++) if (*string == c) return string; - return string; + else if (!*string) + return string; } @@ -141,9 +143,10 @@ char* strchrnul(const char* string, int c) char* strrchr(const char* string, int c) { char* r = NULL; - while (; *string; string++) + for (;;) if (*string == c) r = string; - return r; + else if (!*string++) + return r; } diff --git a/src/string/strstr.c b/src/string/strstr.c new file mode 100644 index 0000000..a7e490a --- /dev/null +++ b/src/string/strstr.c @@ -0,0 +1,179 @@ +/** + * 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 <stddef.h> +#include <inttypes.h> + + + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +char* strstr(const char* haystack, const char* needle) +{ + return memmem(haystack, strlen(haystack), needle, strlen(needle)); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +char* strcasestr(const char* haystack, const char* needle) +{ + return memcasemem(haystack, strlen(haystack), needle, strlen(needle)); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * + * This is a slibc extension added for because it was useful + * in implementing slibc itself. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @param maxlen The maximum number of character to search. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +char* strnstr(const char* haystack, const char* needle, size_t maxlen) +{ + return memmem(haystack, strnlen(haystack, maxlen), needle, strlen(needle)); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * + * This is a slibc extension added for completeness. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @param maxlen The maximum number of character to search. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +char* strncasestr(const char* haystack, const char* needle, size_t maxlen) +{ + return memcasemem(haystack, strnlen(haystack, maxlen), needle, strlen(needle)); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * It must already be known that such a substring exists. + * + * This is a slibc extension. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the substring. + */ +char* rawstrstr(const char* haystack, const char* needle) +{ + return memmem(haystack, SIZE_MAX, needle, strlen(needle)); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * It must already be known that such a substring exists. + * + * This is a slibc extension. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the substring. + */ +char* rawstrcasestr(const char* haystack, const char* needle) +{ + return memcasemem(haystack, SIZE_MAX, needle, strlen(needle)); +} + + +/** + * 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, haystack_length, haystack_length) ? haystack : NULL; +#include "substring.h" +} + + +/** + * 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, haystack_length, haystack_length) ? haystack : NULL; +#define CASE +#include "substring.h" +#undef CASE +} + diff --git a/src/string/substring.h b/src/string/substring.h new file mode 100644 index 0000000..10e4a7d --- /dev/null +++ b/src/string/substring.h @@ -0,0 +1,70 @@ +/** + * 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. */ + + +#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 */ + + +{ + 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 < 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 < haystack_length) + { + while ((ned > -1) && !CHREQ(haystack[hay], needle[ned])) + ned = next_map[ned]; + hay++, ned++; + if (ned >= needle_length) + return needle + (hay - ned); + } + + return NULL; +} + diff --git a/src/wchar/wcschr.c b/src/wchar/wcschr.c index e96a90a..493f0a7 100644 --- a/src/wchar/wcschr.c +++ b/src/wchar/wcschr.c @@ -95,10 +95,11 @@ wchar_t* wmemrchr(const wchar_t* segment, wchar_t c, size_t size) */ wchar_t* wcschr(const wchar_t* string, wchar_t c) { - while (; *string; string++) + for (;;) if (*string == c) return string; - return NULL; + else if (!*string++) + return NULL; } @@ -119,10 +120,11 @@ wchar_t* wcschr(const wchar_t* string, wchar_t c) */ wchar_t* wcschrnul(const wchar_t* string, wchar_t c) { - while (; *string; string++) + for (;; string++) if (*string == c) return string; - return string; + else if (!*string) + return string; } @@ -143,9 +145,10 @@ wchar_t* wcschrnul(const wchar_t* string, wchar_t c) wchar_t* wcsrchr(const wchar_t* string, wchar_t c) { wchar_t* r = NULL; - while (; *string; string++) + for (;;) if (*string == c) r = string; - return r; + else if (!*string++) + return r; } diff --git a/src/wchar/wcsstr.c b/src/wchar/wcsstr.c new file mode 100644 index 0000000..bba7d96 --- /dev/null +++ b/src/wchar/wcsstr.c @@ -0,0 +1,189 @@ +/** + * 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 <wchar.h> +#include <stddef.h> +#include <inttypes.h> + +#define WIDE + + + +/** + * This function is identical to `wcsstr`. + */ +wchar_t* wcswcs(const wchar_t* haystack, const wchar_t* needle) +{ + return wcsstr(haystack, needle); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +wchar_t* wcsstr(const wchar_t* haystack, const wchar_t* needle) +{ + return wmemmem(haystack, wcslen(haystack), needle, wcslen(needle)); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * + * This is a slibc extension. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +wchar_t* wcscasestr(const wchar_t* haystack, const wchar_t* needle) +{ + return wmemcasemem(haystack, wcslen(haystack), needle, wcslen(needle)); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * + * This is a slibc extension added for because it was useful + * in implementing slibc itself. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @param maxlen The maximum number of character to search. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +wchar_t* wcsnstr(const wchar_t* haystack, const wchar_t* needle, size_t maxlen) +{ + return wmemmem(haystack, wcsnlen(haystack, maxlen), needle, wcslen(needle)); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * + * This is a slibc extension added for completeness. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @param maxlen The maximum number of character to search. + * @return Pointer to the first occurrence of the + * substring, `NULL` if not found. + */ +wchar_t* wcsncasestr(const wchar_t* haystack, const wchar_t* needle, size_t maxlen) +{ + return wmemcasemem(haystack, wcsnlen(haystack, maxlen), needle, wcslen(needle)); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case sensitive. + * It must already be known that such a substring exists. + * + * This is a slibc extension. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the substring. + */ +wchar_t* rawwcsstr(const wchar_t* haystack, const wchar_t* needle) +{ + return wmemmem(haystack, SIZE_MAX, needle, wcslen(needle)); +} + + +/** + * Finds the first occurrence of a substring. + * This search is case insensitive. + * It must already be known that such a substring exists. + * + * This is a slibc extension. + * + * @param haystack The string to search. + * @param needle The sought after substring. + * @return Pointer to the first occurrence of the substring. + */ +wchar_t* rawwcscasestr(const wchar_t* haystack, const wchar_t* needle) +{ + return wmemcasemem(haystack, SIZE_MAX, needle, wcslen(needle)); +} + + +/** + * Finds the first occurrence of a substring + * This search is case sensitive. + * + * This is a slibc extension added for completeness, + * and because it was 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. + */ +wchar_t* wmemmem(const wchar_t* haystack, size_t haystack_length, + const wchar_t* needle, size_t needle_length) +{ + if (haystack_length < needle_length) + return NULL; + if (haystack_length == needle_length) + return !wmemcmp(haystack, haystack_length, haystack_length) ? haystack : NULL; +#include "../string/substring.h" +} + + +/** + * 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. + */ +wchar_t* wmemcasemem(const wchar_t* haystack, size_t haystack_length, + const wchar_t* needle, size_t needle_length) +{ + if (haystack_length < needle_length) + return NULL; + if (haystack_length == needle_length) + return !wmemcasecmp(haystack, haystack_length, haystack_length) ? haystack : NULL; +#define CASE +#include "../string/substring.h" +#undef CASE +} + |