boost/boost/re_detail/regex_kmp.hpp

   1 /*
   2  *
   3  * Copyright (c) 1998-2000
   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      3.03
  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/re_detail/regex_config.hpp>
  30 #endif
  31
  32
  33 namespace boost{
  34    namespace re_detail{
  35
  36 #ifdef __BORLANDC__
  37    #if __BORLANDC__ == 0x530
  38     #pragma option push -a4 -b -Ve
  39    #elif __BORLANDC__ > 0x530
  40     #pragma option push -a8 -b -Ve
  41    #endif
  42 #endif
  43
  44 template <class charT>
  45 struct kmp_info
  46 {
  47    unsigned int size;
  48    unsigned int len;
  49    const charT* pstr;
  50    int kmp_next[1];
  51 };
  52
  53 template <class charT, class Allocator>
  54 void kmp_free(kmp_info<charT>* pinfo, Allocator a)
  55 {
  56    typedef BOOST_RE_MAYBE_TYPENAME REBIND_TYPE(char, Allocator) atype;
  57    atype(a).deallocate((char*)pinfo, pinfo->size);
  58 }
  59
  60 template <class iterator, class charT, class Trans, class Allocator>
  61 kmp_info<charT>* kmp_compile(iterator first, iterator last, charT, Trans translate, Allocator a)
  62 {
  63    typedef BOOST_RE_MAYBE_TYPENAME REBIND_TYPE(char, Allocator) atype;
  64    int i, j, m;
  65    i = 0;
  66    BOOST_RE_DISTANCE(first, last, m);
  67    ++m;
  68    unsigned int size = sizeof(kmp_info<charT>) + sizeof(int)*m + sizeof(charT)*m;
  69    --m;
  70    //
  71    // allocate struct and fill it in:
  72    //
  73    kmp_info<charT>* pinfo = (kmp_info<charT>*)atype(a).allocate(size);
  74    pinfo->size = size;
  75    pinfo->len = m;
  76    charT* p = (charT*)((char*)pinfo + sizeof(kmp_info<charT>) + sizeof(int)*(m+1));
  77    pinfo->pstr = p;
  78    while(first != last)
  79    {
  80       *p = translate(*first);
  81       ++first;
  82       ++p;
  83    }
  84    *p = 0;
  85    //
  86    // finally do regular kmp compile:
  87    //
  88    j = pinfo->kmp_next[0] = -1;
  89    while (i < m)
  90    {
  91       while ((j > -1) && (pinfo->pstr[i] != pinfo->pstr[j]))
  92          j = pinfo->kmp_next[j];
  93       ++i;
  94       ++j;
  95       if (pinfo->pstr[i] == pinfo->pstr[j])
  96          pinfo->kmp_next[i] = pinfo->kmp_next[j];
  97       else
  98          pinfo->kmp_next[i] = j;
  99    }
 100
 101    return pinfo;
 102 }
 103
 104 #ifdef __BORLANDC__
 105  #if __BORLANDC__ > 0x520
 106   #pragma option pop
 107  #endif
 108 #endif
 109
 110    } // namepsace re_detail
 111 } // namespace boost
 112
 113 #endif   // BOOST_REGEX_KMP_HPP
 114
 115
 116
 117
 118