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
free_aux(void * ptr)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
scan_keyword(InputIterator & b,InputIterator e,ForwardIterator kb,ForwardIterator ke,std::ios_base::iostate & err)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
164