boost/chrono/detail/scan_keyword.hpp

   1 //  scan_keyword.hpp  --------------------------------------------------------------//
   2 //===----------------------------------------------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10 //  Adaptation to Boost of the libcxx
  11
  12 //  Copyright 2010 Vicente J. Botet Escriba
  13
  14 //  Distributed under the Boost Software License, Version 1.0.
  15 //  See http://www.boost.org/LICENSE_1_0.txt
  16
  17 #ifndef BOOST_CHRONO_DETAIL_SCAN_KEYWORD_HPP
  18 #define BOOST_CHRONO_DETAIL_SCAN_KEYWORD_HPP
  19
  20 #include <boost/chrono/config.hpp>
  21
  22 #include <boost/interprocess/smart_ptr/unique_ptr.hpp>
  23 #include <ios>
  24 #include <exception>
  25 #include <stdlib.h>
  26
  27 namespace boost {
  28     using interprocess::unique_ptr;
  29
  30 namespace chrono {
  31 namespace chrono_detail {
  32
  33 inline void free_aux(void* ptr) { free(ptr); }
  34
  35 // scan_keyword
  36 // Scans [b, e) until a match is found in the basic_strings range
  37 //  [kb, ke) or until it can be shown that there is no match in [kb, ke).
  38 //  b will be incremented (visibly), consuming CharT until a match is found
  39 //  or proved to not exist.  A keyword may be "", in which will match anything.
  40 //  If one keyword is a prefix of another, and the next CharT in the input
  41 //  might match another keyword, the algorithm will attempt to find the longest
  42 //  matching keyword.  If the longer matching keyword ends up not matching, then
  43 //  no keyword match is found.  If no keyword match is found, ke is returned
  44 //  and failbit is set in err.
  45 //  Else an iterator pointing to the matching keyword is found.  If more than
  46 //  one keyword matches, an iterator to the first matching keyword is returned.
  47 //  If on exit b == e, eofbit is set in err.
  48 //  Examples:
  49 //  Keywords:  "a", "abb"
  50 //  If the input is "a", the first keyword matches and eofbit is set.
  51 //  If the input is "abc", no match is found and "ab" are consumed.
  52
  53 template <class InputIterator, class ForwardIterator>
  54 ForwardIterator
  55 scan_keyword(InputIterator& b, InputIterator e,
  56                ForwardIterator kb, ForwardIterator ke,
  57                std::ios_base::iostate& err
  58                )
  59 {
  60     typedef typename std::iterator_traits<InputIterator>::value_type CharT;
  61     size_t nkw = std::distance(kb, ke);
  62     const unsigned char doesnt_match = '\0';
  63     const unsigned char might_match = '\1';
  64     const unsigned char does_match = '\2';
  65     unsigned char statbuf[100];
  66     unsigned char* status = statbuf;
  67     //  Change free by free_aux to avoid
  68     // Error: Could not find a match for boost::interprocess::unique_ptr<unsigned char, void(*)(void*)>::unique_ptr(int, extern "C" void(void*))
  69     unique_ptr<unsigned char, void(*)(void*)> stat_hold(0, free_aux);
  70     if (nkw > sizeof(statbuf))
  71     {
  72         status = (unsigned char*)malloc(nkw);
  73         if (status == 0)
  74             throw std::bad_alloc();
  75         stat_hold.reset(status);
  76     }
  77     size_t n_might_match = nkw;  // At this point, any keyword might match
  78     size_t n_does_match = 0;       // but none of them definitely do
  79     // Initialize all statuses to might_match, except for "" keywords are does_match
  80     unsigned char* st = status;
  81     for (ForwardIterator ky = kb; ky != ke; ++ky, ++st)
  82     {
  83         if (!ky->empty())
  84             *st = might_match;
  85         else
  86         {
  87             *st = does_match;
  88             --n_might_match;
  89             ++n_does_match;
  90         }
  91     }
  92     // While there might be a match, test keywords against the next CharT
  93     for (size_t indx = 0; b != e && n_might_match > 0; ++indx)
  94     {
  95         // Peek at the next CharT but don't consume it
  96         CharT c = *b;
  97         bool consume = false;
  98         // For each keyword which might match, see if the indx character is c
  99         // If a match if found, consume c
 100         // If a match is found, and that is the last character in the keyword,
 101         //    then that keyword matches.
 102         // If the keyword doesn't match this character, then change the keyword
 103         //    to doesn't match
 104         st = status;
 105         for (ForwardIterator ky = kb; ky != ke; ++ky, ++st)
 106         {
 107             if (*st == might_match)
 108             {
 109                 CharT kc = (*ky)[indx];
 110                 if (c == kc)
 111                 {
 112                     consume = true;
 113                     if (ky->size() == indx+1)
 114                     {
 115                         *st = does_match;
 116                         --n_might_match;
 117                         ++n_does_match;
 118                     }
 119                 }
 120                 else
 121                 {
 122                     *st = doesnt_match;
 123                     --n_might_match;
 124                 }
 125             }
 126         }
 127         // consume if we matched a character
 128         if (consume)
 129         {
 130             ++b;
 131             // If we consumed a character and there might be a matched keyword that
 132             //   was marked matched on a previous iteration, then such keywords
 133             //   which are now marked as not matching.
 134             if (n_might_match + n_does_match > 1)
 135             {
 136                 st = status;
 137                 for (ForwardIterator ky = kb; ky != ke; ++ky, ++st)
 138                 {
 139                     if (*st == does_match && ky->size() != indx+1)
 140                     {
 141                         *st = doesnt_match;
 142                         --n_does_match;
 143                     }
 144                 }
 145             }
 146         }
 147     }
 148     // We've exited the loop because we hit eof and/or we have no more "might matches".
 149     if (b == e)
 150         err |= std::ios_base::eofbit;
 151     // Return the first matching result
 152     for (st = status; kb != ke; ++kb, ++st)
 153         if (*st == does_match)
 154             break;
 155     if (kb == ke)
 156         err |= std::ios_base::failbit;
 157     return kb;
 158 }
 159 }
 160 }
 161 }
 162 #endif // BOOST_CHRONO_DETAIL_SCAN_KEYWORD_HPP