| 1 |
/* |
| 2 |
* SPDX-FileCopyrightText: 1998-2002 Pham Kim Long <[email protected]> |
| 3 |
* |
| 4 |
* SPDX-License-Identifier: GPL-2.0-or-later |
| 5 |
*/ |
| 6 |
|
| 7 |
#include "pattern.h" |
| 8 |
|
| 9 |
////////////////////////////////////////////////// |
| 10 |
// Pattern matching (based on KPM algorithm) |
| 11 |
////////////////////////////////////////////////// |
| 12 |
|
| 13 |
//---------------------------- |
| 14 |
void PatternState::reset() { |
| 15 |
m_pos = 0; |
| 16 |
m_found = 0; |
| 17 |
} |
| 18 |
|
| 19 |
//---------------------------- |
| 20 |
void PatternState::init(char *pattern) { |
| 21 |
m_pos = 0; |
| 22 |
m_found = 0; |
| 23 |
m_pattern = pattern; |
| 24 |
|
| 25 |
int i = 0, j = -1; |
| 26 |
m_border[i] = j; |
| 27 |
while (m_pattern[i]) { |
| 28 |
while (j >= 0 && m_pattern[i] != m_pattern[j]) |
| 29 |
j = m_border[j]; |
| 30 |
i++; |
| 31 |
j++; |
| 32 |
m_border[i] = j; |
| 33 |
} |
| 34 |
} |
| 35 |
|
| 36 |
//----------------------------------------------------- |
| 37 |
// get next input char, returns 1 if pattern is found. |
| 38 |
//----------------------------------------------------- |
| 39 |
int PatternState::foundAtNextChar(char ch) { |
| 40 |
int ret = 0; |
| 41 |
// int j = m_pos; |
| 42 |
while (m_pos >= 0 && ch != m_pattern[m_pos]) |
| 43 |
m_pos = m_border[m_pos]; |
| 44 |
m_pos++; |
| 45 |
if (m_pattern[m_pos] == 0) { |
| 46 |
m_found++; |
| 47 |
m_pos = m_border[m_pos]; |
| 48 |
ret = 1; |
| 49 |
} |
| 50 |
return ret; |
| 51 |
} |
| 52 |
|
| 53 |
//----------------------------------------------------- |
| 54 |
void PatternList::init(char **patterns, int count) { |
| 55 |
m_count = count; |
| 56 |
delete[] m_patterns; |
| 57 |
m_patterns = new PatternState[count]; |
| 58 |
for (int i = 0; i < count; i++) |
| 59 |
m_patterns[i].init(patterns[i]); |
| 60 |
} |
| 61 |
|
| 62 |
//----------------------------------------------------- |
| 63 |
// return the order number of the pattern that is found. |
| 64 |
// If more than 1 pattern is found, returns any pattern |
| 65 |
// Returns -1 if no pattern is found |
| 66 |
//----------------------------------------------------- |
| 67 |
int PatternList::foundAtNextChar(char ch) { |
| 68 |
int patternFound = -1; |
| 69 |
for (int i = 0; i < m_count; i++) { |
| 70 |
if (m_patterns[i].foundAtNextChar(ch)) |
| 71 |
patternFound = i; |
| 72 |
} |
| 73 |
return patternFound; |
| 74 |
} |
| 75 |
|
| 76 |
//----------------------------------------------------- |
| 77 |
void PatternList::reset() { |
| 78 |
for (int i = 0; i < m_count; i++) |
| 79 |
m_patterns[i].reset(); |
| 80 |
} |