1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
/**
* slibc — Yet another C library
* Copyright © 2015, 2016 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 */
/* TODO add [w]mem[r]{lower,upper}mem */
/* 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
|
