3 * Copyright (c) 1998-2002
6 * Use, modification and distribution are subject to the
7 * Boost Software License, Version 1.0. (See accompanying file
8 * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
13 * LOCATION: see http://www.boost.org for most recent version.
15 * VERSION see <boost/version.hpp>
16 * DESCRIPTION: Provides Knuth Morris Pratt search operations.
17 * Note this is an internal header file included
18 * by regex.hpp, do not include on its own.
21 #ifndef BOOST_REGEX_KMP_HPP
22 #define BOOST_REGEX_KMP_HPP
24 #ifdef BOOST_REGEX_CONFIG_HPP
25 #include <boost/regex/config.hpp>
32 #ifdef BOOST_HAS_ABI_HEADERS
33 # include BOOST_ABI_PREFIX
36 template <class charT>
45 template <class charT, class Allocator>
46 void kmp_free(kmp_info<charT>* pinfo, const Allocator& a)
48 typedef typename boost::detail::rebind_allocator<char, Allocator>::type atype;
49 atype(a).deallocate(reinterpret_cast<char*>(pinfo), pinfo->size);
52 template <class iterator, class charT, class Trans, class Allocator>
53 kmp_info<charT>* kmp_compile(iterator first, iterator last, charT, Trans translate, const Allocator& a)
55 typedef typename boost::detail::rebind_allocator<char, Allocator>::type atype;
58 m = static_cast<int>(::boost::re_detail::distance(first, last));
60 unsigned int size = sizeof(kmp_info<charT>) + sizeof(int)*m + sizeof(charT)*m;
63 // allocate struct and fill it in:
65 kmp_info<charT>* pinfo = reinterpret_cast<kmp_info<charT>*>(atype(a).allocate(size));
66 BOOST_REGEX_NOEH_ASSERT(pinfo)
69 charT* p = reinterpret_cast<charT*>(reinterpret_cast<char*>(pinfo) + sizeof(kmp_info<charT>) + sizeof(int)*(m+1));
73 *p = translate(*first);
79 // finally do regular kmp compile:
81 j = pinfo->kmp_next[0] = -1;
84 while ((j > -1) && (pinfo->pstr[i] != pinfo->pstr[j]))
85 j = pinfo->kmp_next[j];
88 if (pinfo->pstr[i] == pinfo->pstr[j])
89 pinfo->kmp_next[i] = pinfo->kmp_next[j];
91 pinfo->kmp_next[i] = j;
97 #ifdef BOOST_HAS_ABI_HEADERS
98 # include BOOST_ABI_SUFFIX
101 } // namepsace re_detail
104 #endif // BOOST_REGEX_KMP_HPP