boost/boost/regex/detail/regex_kmp.hpp

   1 /*
   2  *
   3  * Copyright (c) 1998-2002
   4  * Dr John Maddock
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Dr John Maddock makes no representations
  11  * about the suitability of this software for any purpose.
  12  * It is provided "as is" without express or implied warranty.
  13  *
  14  */
  15
  16  /*
  17   *   LOCATION:    see http://www.boost.org for most recent version.
  18   *   FILE         regex_kmp.hpp
  19   *   VERSION      see <boost/version.hpp>
  20   *   DESCRIPTION: Provides Knuth Morris Pratt search operations.
  21   *                Note this is an internal header file included
  22   *                by regex.hpp, do not include on its own.
  23   */
  24
  25 #ifndef BOOST_REGEX_KMP_HPP
  26 #define BOOST_REGEX_KMP_HPP
  27
  28 #ifdef BOOST_REGEX_CONFIG_HPP
  29 #include <boost/regex/config.hpp>
  30 #endif
  31
  32
  33 namespace boost{
  34    namespace re_detail{
  35
  36 #ifdef __BORLANDC__
  37    #pragma option push -a8 -b -Vx -Ve -pc
  38 #endif
  39
  40 template <class charT>
  41 struct kmp_info
  42 {
  43    unsigned int size;
  44    unsigned int len;
  45    const charT* pstr;
  46    int kmp_next[1];
  47 };
  48
  49 template <class charT, class Allocator>
  50 void kmp_free(kmp_info<charT>* pinfo, const Allocator& a)
  51 {
  52    typedef typename boost::detail::rebind_allocator<char, Allocator>::type atype;
  53    atype(a).deallocate(reinterpret_cast<char*>(pinfo), pinfo->size);
  54 }
  55
  56 template <class iterator, class charT, class Trans, class Allocator>
  57 kmp_info<charT>* kmp_compile(iterator first, iterator last, charT, Trans translate, const Allocator& a)
  58 {
  59    typedef typename boost::detail::rebind_allocator<char, Allocator>::type atype;
  60    int i, j, m;
  61    i = 0;
  62    m = static_cast<int>(boost::re_detail::distance(first, last));
  63    ++m;
  64    unsigned int size = sizeof(kmp_info<charT>) + sizeof(int)*m + sizeof(charT)*m;
  65    --m;
  66    //
  67    // allocate struct and fill it in:
  68    //
  69    kmp_info<charT>* pinfo = reinterpret_cast<kmp_info<charT>*>(atype(a).allocate(size));
  70    BOOST_REGEX_NOEH_ASSERT(pinfo)
  71    pinfo->size = size;
  72    pinfo->len = m;
  73    charT* p = reinterpret_cast<charT*>(reinterpret_cast<char*>(pinfo) + sizeof(kmp_info<charT>) + sizeof(int)*(m+1));
  74    pinfo->pstr = p;
  75    while(first != last)
  76    {
  77       *p = translate(*first);
  78       ++first;
  79       ++p;
  80    }
  81    *p = 0;
  82    //
  83    // finally do regular kmp compile:
  84    //
  85    j = pinfo->kmp_next[0] = -1;
  86    while (i < m)
  87    {
  88       while ((j > -1) && (pinfo->pstr[i] != pinfo->pstr[j]))
  89          j = pinfo->kmp_next[j];
  90       ++i;
  91       ++j;
  92       if (pinfo->pstr[i] == pinfo->pstr[j])
  93          pinfo->kmp_next[i] = pinfo->kmp_next[j];
  94       else
  95          pinfo->kmp_next[i] = j;
  96    }
  97
  98    return pinfo;
  99 }
 100
 101 #ifdef __BORLANDC__
 102   #pragma option pop
 103 #endif
 104
 105    } // namepsace re_detail
 106 } // namespace boost
 107
 108 #endif   // BOOST_REGEX_KMP_HPP
 109
 110
 111