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