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
105
106
107
108
109
110
111
112
|
//========= Copyright Valve Corporation, All rights reserved. ============//
//
// Purpose:
//
// $NoKeywords: $
//
//=============================================================================//
/*
*
* Copyright (c) 1998-9
* Dr John Maddock
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Dr John Maddock makes no representations
* about the suitability of this software for any purpose.
* It is provided "as is" without express or implied warranty.
*
*/
/*
* FILE re_kmp.h
* VERSION 2.12
* Knuth-Morris-Pratt search.
*/
#ifndef __RE_KMP_H
#define __RE_KMP_H
#ifdef JM_CFG_H
#include <jm/jm_cfg.h>
#endif
JM_NAMESPACE(__JM)
template <class charT>
struct kmp_info
{
unsigned int size;
unsigned int len;
const charT* pstr;
int kmp_next[1];
};
template <class charT, class Allocator>
void kmp_free(kmp_info<charT>* pinfo, Allocator a)
{
typedef JM_MAYBE_TYPENAME REBIND_TYPE(char, Allocator) atype;
atype(a).deallocate((char*)pinfo, pinfo->size);
}
template <class iterator, class charT, class Trans, class Allocator>
kmp_info<charT>* kmp_compile(iterator first, iterator last, charT, Trans translate, Allocator a
#ifdef RE_LOCALE_CPP
, const __JM_STD::locale& l
#endif
)
{
typedef JM_MAYBE_TYPENAME REBIND_TYPE(char, Allocator) atype;
int i, j, m;
i = 0;
m = 0;
JM_DISTANCE(first, last, m);
++m;
unsigned int size = sizeof(kmp_info<charT>) + sizeof(int)*m + sizeof(charT)*m;
--m;
//
// allocate struct and fill it in:
//
kmp_info<charT>* pinfo = (kmp_info<charT>*)atype(a).allocate(size);
pinfo->size = size;
pinfo->len = m;
charT* p = (charT*)((char*)pinfo + sizeof(kmp_info<charT>) + sizeof(int)*(m+1));
pinfo->pstr = p;
while(first != last)
{
*p = translate(*first MAYBE_PASS_LOCALE(l));
++first;
++p;
}
*p = 0;
//
// finally do regular kmp compile:
//
j = pinfo->kmp_next[0] = -1;
while (i < m)
{
while ((j > -1) && (pinfo->pstr[i] != pinfo->pstr[j]))
j = pinfo->kmp_next[j];
++i;
++j;
if (pinfo->pstr[i] == pinfo->pstr[j])
pinfo->kmp_next[i] = pinfo->kmp_next[j];
else
pinfo->kmp_next[i] = j;
}
return pinfo;
}
JM_END_NAMESPACE // namespace regex
#endif // __RE_KMP_H
|