From c99cadbe02f659264cecb44c053d96383631147d Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Tue, 17 Nov 2015 05:50:23 +0100 Subject: rearrange files MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/string/substring.h | 85 -------------------------------------------------- 1 file changed, 85 deletions(-) delete mode 100644 src/string/substring.h (limited to 'src/string/substring.h') diff --git a/src/string/substring.h b/src/string/substring.h deleted file mode 100644 index 05ef7cc..0000000 --- a/src/string/substring.h +++ /dev/null @@ -1,85 +0,0 @@ -/** - * 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 . - */ -/* 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 - -- cgit v1.3.1