Chris@16: // scan_keyword.hpp --------------------------------------------------------------// Chris@16: //===----------------------------------------------------------------------===// Chris@16: // Chris@16: // The LLVM Compiler Infrastructure Chris@16: // Chris@16: // This file is dual licensed under the MIT and the University of Illinois Open Chris@16: // Source Licenses. See LICENSE.TXT for details. Chris@16: // Chris@16: //===----------------------------------------------------------------------===// Chris@16: // Adaptation to Boost of the libcxx Chris@16: Chris@16: // Copyright 2010 Vicente J. Botet Escriba Chris@16: Chris@16: // Distributed under the Boost Software License, Version 1.0. Chris@16: // See http://www.boost.org/LICENSE_1_0.txt Chris@16: Chris@16: #ifndef BOOST_CHRONO_DETAIL_SCAN_KEYWORD_HPP Chris@16: #define BOOST_CHRONO_DETAIL_SCAN_KEYWORD_HPP Chris@16: Chris@16: #include Chris@16: Chris@101: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: namespace boost { Chris@101: using movelib::unique_ptr; Chris@16: Chris@16: namespace chrono { Chris@16: namespace chrono_detail { Chris@16: Chris@16: inline void free_aux(void* ptr) { free(ptr); } Chris@16: Chris@16: // scan_keyword Chris@16: // Scans [b, e) until a match is found in the basic_strings range Chris@16: // [kb, ke) or until it can be shown that there is no match in [kb, ke). Chris@16: // b will be incremented (visibly), consuming CharT until a match is found Chris@16: // or proved to not exist. A keyword may be "", in which will match anything. Chris@16: // If one keyword is a prefix of another, and the next CharT in the input Chris@16: // might match another keyword, the algorithm will attempt to find the longest Chris@16: // matching keyword. If the longer matching keyword ends up not matching, then Chris@16: // no keyword match is found. If no keyword match is found, ke is returned Chris@16: // and failbit is set in err. Chris@16: // Else an iterator pointing to the matching keyword is found. If more than Chris@16: // one keyword matches, an iterator to the first matching keyword is returned. Chris@16: // If on exit b == e, eofbit is set in err. Chris@16: // Examples: Chris@16: // Keywords: "a", "abb" Chris@16: // If the input is "a", the first keyword matches and eofbit is set. Chris@16: // If the input is "abc", no match is found and "ab" are consumed. Chris@16: Chris@16: template Chris@16: ForwardIterator Chris@16: scan_keyword(InputIterator& b, InputIterator e, Chris@16: ForwardIterator kb, ForwardIterator ke, Chris@16: std::ios_base::iostate& err Chris@16: ) Chris@16: { Chris@16: typedef typename std::iterator_traits::value_type CharT; Chris@16: size_t nkw = std::distance(kb, ke); Chris@16: const unsigned char doesnt_match = '\0'; Chris@16: const unsigned char might_match = '\1'; Chris@16: const unsigned char does_match = '\2'; Chris@16: unsigned char statbuf[100]; Chris@16: unsigned char* status = statbuf; Chris@16: // Change free by free_aux to avoid Chris@16: // Error: Could not find a match for boost::interprocess::unique_ptr::unique_ptr(int, extern "C" void(void*)) Chris@16: unique_ptr stat_hold(0, free_aux); Chris@16: if (nkw > sizeof(statbuf)) Chris@16: { Chris@16: status = (unsigned char*)malloc(nkw); Chris@16: if (status == 0) Chris@16: throw_exception(std::bad_alloc()); Chris@16: stat_hold.reset(status); Chris@16: } Chris@16: size_t n_might_match = nkw; // At this point, any keyword might match Chris@16: size_t n_does_match = 0; // but none of them definitely do Chris@16: // Initialize all statuses to might_match, except for "" keywords are does_match Chris@16: unsigned char* st = status; Chris@16: for (ForwardIterator ky = kb; ky != ke; ++ky, ++st) Chris@16: { Chris@16: if (!ky->empty()) Chris@16: *st = might_match; Chris@16: else Chris@16: { Chris@16: *st = does_match; Chris@16: --n_might_match; Chris@16: ++n_does_match; Chris@16: } Chris@16: } Chris@16: // While there might be a match, test keywords against the next CharT Chris@16: for (size_t indx = 0; b != e && n_might_match > 0; ++indx) Chris@16: { Chris@16: // Peek at the next CharT but don't consume it Chris@16: CharT c = *b; Chris@16: bool consume = false; Chris@16: // For each keyword which might match, see if the indx character is c Chris@16: // If a match if found, consume c Chris@16: // If a match is found, and that is the last character in the keyword, Chris@16: // then that keyword matches. Chris@16: // If the keyword doesn't match this character, then change the keyword Chris@16: // to doesn't match Chris@16: st = status; Chris@16: for (ForwardIterator ky = kb; ky != ke; ++ky, ++st) Chris@16: { Chris@16: if (*st == might_match) Chris@16: { Chris@16: CharT kc = (*ky)[indx]; Chris@16: if (c == kc) Chris@16: { Chris@16: consume = true; Chris@16: if (ky->size() == indx+1) Chris@16: { Chris@16: *st = does_match; Chris@16: --n_might_match; Chris@16: ++n_does_match; Chris@16: } Chris@16: } Chris@16: else Chris@16: { Chris@16: *st = doesnt_match; Chris@16: --n_might_match; Chris@16: } Chris@16: } Chris@16: } Chris@16: // consume if we matched a character Chris@16: if (consume) Chris@16: { Chris@16: ++b; Chris@16: // If we consumed a character and there might be a matched keyword that Chris@16: // was marked matched on a previous iteration, then such keywords Chris@16: // which are now marked as not matching. Chris@16: if (n_might_match + n_does_match > 1) Chris@16: { Chris@16: st = status; Chris@16: for (ForwardIterator ky = kb; ky != ke; ++ky, ++st) Chris@16: { Chris@16: if (*st == does_match && ky->size() != indx+1) Chris@16: { Chris@16: *st = doesnt_match; Chris@16: --n_does_match; Chris@16: } Chris@16: } Chris@16: } Chris@16: } Chris@16: } Chris@16: // We've exited the loop because we hit eof and/or we have no more "might matches". Chris@16: if (b == e) Chris@16: err |= std::ios_base::eofbit; Chris@16: // Return the first matching result Chris@16: for (st = status; kb != ke; ++kb, ++st) Chris@16: if (*st == does_match) Chris@16: break; Chris@16: if (kb == ke) Chris@16: err |= std::ios_base::failbit; Chris@16: return kb; Chris@16: } Chris@16: } Chris@16: } Chris@16: } Chris@16: #endif // BOOST_CHRONO_DETAIL_SCAN_KEYWORD_HPP