boost/boost/regex/v4/regex_kmp.hpp

   1 /*
   2  *
   3  * Copyright (c) 1998-2002
   4  * John Maddock
   5  *
   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)
   9  *
  10  */
  11
  12  /*
  13   *   LOCATION:    see http://www.boost.org for most recent version.
  14   *   FILE         regex_kmp.hpp
  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.
  19   */
  20
  21 #ifndef BOOST_REGEX_KMP_HPP
  22 #define BOOST_REGEX_KMP_HPP
  23
  24 #ifdef BOOST_REGEX_CONFIG_HPP
  25 #include <boost/regex/config.hpp>
  26 #endif
  27
  28
  29 namespace boost{
  30    namespace re_detail{
  31
  32 #ifdef BOOST_HAS_ABI_HEADERS
  33 #  include BOOST_ABI_PREFIX
  34 #endif
  35
  36 template <class charT>
  37 struct kmp_info
  38 {
  39    unsigned int size;
  40    unsigned int len;
  41    const charT* pstr;
  42    int kmp_next[1];
  43 };
  44
  45 template <class charT, class Allocator>
  46 void kmp_free(kmp_info<charT>* pinfo, const Allocator& a)
  47 {
  48    typedef typename boost::detail::rebind_allocator<char, Allocator>::type atype;
  49    atype(a).deallocate(reinterpret_cast<char*>(pinfo), pinfo->size);
  50 }
  51
  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)
  54 {
  55    typedef typename boost::detail::rebind_allocator<char, Allocator>::type atype;
  56    int i, j, m;
  57    i = 0;
  58    m = static_cast<int>(::boost::re_detail::distance(first, last));
  59    ++m;
  60    unsigned int size = sizeof(kmp_info<charT>) + sizeof(int)*m + sizeof(charT)*m;
  61    --m;
  62    //
  63    // allocate struct and fill it in:
  64    //
  65    kmp_info<charT>* pinfo = reinterpret_cast<kmp_info<charT>*>(atype(a).allocate(size));
  66    BOOST_REGEX_NOEH_ASSERT(pinfo)
  67    pinfo->size = size;
  68    pinfo->len = m;
  69    charT* p = reinterpret_cast<charT*>(reinterpret_cast<char*>(pinfo) + sizeof(kmp_info<charT>) + sizeof(int)*(m+1));
  70    pinfo->pstr = p;
  71    while(first != last)
  72    {
  73       *p = translate(*first);
  74       ++first;
  75       ++p;
  76    }
  77    *p = 0;
  78    //
  79    // finally do regular kmp compile:
  80    //
  81    j = pinfo->kmp_next[0] = -1;
  82    while (i < m)
  83    {
  84       while ((j > -1) && (pinfo->pstr[i] != pinfo->pstr[j]))
  85          j = pinfo->kmp_next[j];
  86       ++i;
  87       ++j;
  88       if (pinfo->pstr[i] == pinfo->pstr[j])
  89          pinfo->kmp_next[i] = pinfo->kmp_next[j];
  90       else
  91          pinfo->kmp_next[i] = j;
  92    }
  93
  94    return pinfo;
  95 }
  96
  97 #ifdef BOOST_HAS_ABI_HEADERS
  98 #  include BOOST_ABI_SUFFIX
  99 #endif
 100
 101    } // namepsace re_detail
 102 } // namespace boost
 103
 104 #endif   // BOOST_REGEX_KMP_HPP
 105
 106
 107
 108