FilesExpand file tree

 master

/

fastsearch.h

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

104 lines (90 loc) · 2.78 KB

 master

/

fastsearch.h

Copy path

Top

File metadata and controls

• Code
• Blame

104 lines (90 loc) · 2.78 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

/* stringlib: fastsearch implementation */

#ifndef STRINGLIB_FASTSEARCH_H

#define STRINGLIB_FASTSEARCH_H

/* fast search/count implementation, based on a mix between boyer-

moore and horspool, with a few more bells and whistles on the top.

for some more background, see: http://effbot.org/stringlib.htm */

/* note: fastsearch may access s[n], which isn't a problem when using

Python's ordinary string types, but may cause problems if you're

using this code in other contexts. also, the count mode returns -1

if there cannot possible be a match in the target string, and 0 if

it has actually checked for matches, but didn't find any. callers

beware! */

#define FAST_COUNT 0

#define FAST_SEARCH 1

Py_LOCAL_INLINE(Py_ssize_t)

fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n,

const STRINGLIB_CHAR* p, Py_ssize_t m,

int mode)

{

long mask;

Py_ssize_t skip, count = 0;

Py_ssize_t i, j, mlast, w;

w = n - m;

if (w < 0)

return -1;

/* look for special cases */

if (m <= 1) {

if (m <= 0)

return -1;

/* use special case for 1-character strings */

if (mode == FAST_COUNT) {

for (i = 0; i < n; i++)

if (s[i] == p[0])

count++;

return count;

} else {

for (i = 0; i < n; i++)

if (s[i] == p[0])

return i;

}

return -1;

}

mlast = m - 1;

/* create compressed boyer-moore delta 1 table */

skip = mlast - 1;

/* process pattern[:-1] */

for (mask = i = 0; i < mlast; i++) {

mask |= (1 << (p[i] & 0x1F));

if (p[i] == p[mlast])

skip = mlast - i - 1;

}

/* process pattern[-1] outside the loop */

mask |= (1 << (p[mlast] & 0x1F));

for (i = 0; i <= w; i++) {

/* note: using mlast in the skip path slows things down on x86 */

if (s[i+m-1] == p[m-1]) {

/* candidate match */

for (j = 0; j < mlast; j++)

if (s[i+j] != p[j])

break;

if (j == mlast) {

/* got a match! */

if (mode != FAST_COUNT)

return i;

count++;

i = i + mlast;

continue;

}

/* miss: check if next character is part of pattern */

if (!(mask & (1 << (s[i+m] & 0x1F))))

i = i + m;

else

i = i + skip;

} else {

/* skip: check if next character is part of pattern */

if (!(mask & (1 << (s[i+m] & 0x1F))))

i = i + m;

}

}

if (mode != FAST_COUNT)

return -1;

return count;

}

#endif

/*

Local variables:

c-basic-offset: 4

indent-tabs-mode: nil

End:

*/