]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |