144 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___LOCALE_DIR_SCAN_KEYWORD_H10#define _LIBCPP___LOCALE_DIR_SCAN_KEYWORD_H11 12#include <__config>13#include <__memory/unique_ptr.h>14#include <ios>15 16#if _LIBCPP_HAS_LOCALIZATION17 18# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)19# pragma GCC system_header20# endif21 22_LIBCPP_BEGIN_NAMESPACE_STD23 24// __scan_keyword25// Scans [__b, __e) until a match is found in the basic_strings range26// [__kb, __ke) or until it can be shown that there is no match in [__kb, __ke).27// __b will be incremented (visibly), consuming CharT until a match is found28// or proved to not exist. A keyword may be "", in which will match anything.29// If one keyword is a prefix of another, and the next CharT in the input30// might match another keyword, the algorithm will attempt to find the longest31// matching keyword. If the longer matching keyword ends up not matching, then32// no keyword match is found. If no keyword match is found, __ke is returned33// and failbit is set in __err.34// Else an iterator pointing to the matching keyword is found. If more than35// one keyword matches, an iterator to the first matching keyword is returned.36// If on exit __b == __e, eofbit is set in __err. If __case_sensitive is false,37// __ct is used to force to lower case before comparing characters.38// Examples:39// Keywords: "a", "abb"40// If the input is "a", the first keyword matches and eofbit is set.41// If the input is "abc", no match is found and "ab" are consumed.42template <class _InputIterator, class _ForwardIterator, class _Ctype>43_LIBCPP_HIDE_FROM_ABI _ForwardIterator __scan_keyword(44 _InputIterator& __b,45 _InputIterator __e,46 _ForwardIterator __kb,47 _ForwardIterator __ke,48 const _Ctype& __ct,49 ios_base::iostate& __err,50 bool __case_sensitive = true) {51 typedef typename iterator_traits<_InputIterator>::value_type _CharT;52 size_t __nkw = static_cast<size_t>(std::distance(__kb, __ke));53 const unsigned char __doesnt_match = '\0';54 const unsigned char __might_match = '\1';55 const unsigned char __does_match = '\2';56 unsigned char __statbuf[100];57 unsigned char* __status = __statbuf;58 unique_ptr<unsigned char, void (*)(void*)> __stat_hold(nullptr, free);59 if (__nkw > sizeof(__statbuf)) {60 __status = (unsigned char*)malloc(__nkw);61 if (__status == nullptr)62 std::__throw_bad_alloc();63 __stat_hold.reset(__status);64 }65 size_t __n_might_match = __nkw; // At this point, any keyword might match66 size_t __n_does_match = 0; // but none of them definitely do67 // Initialize all statuses to __might_match, except for "" keywords are __does_match68 unsigned char* __st = __status;69 for (_ForwardIterator __ky = __kb; __ky != __ke; ++__ky, (void)++__st) {70 if (!__ky->empty())71 *__st = __might_match;72 else {73 *__st = __does_match;74 --__n_might_match;75 ++__n_does_match;76 }77 }78 // While there might be a match, test keywords against the next CharT79 for (size_t __indx = 0; __b != __e && __n_might_match > 0; ++__indx) {80 // Peek at the next CharT but don't consume it81 _CharT __c = *__b;82 if (!__case_sensitive)83 __c = __ct.toupper(__c);84 bool __consume = false;85 // For each keyword which might match, see if the __indx character is __c86 // If a match if found, consume __c87 // If a match is found, and that is the last character in the keyword,88 // then that keyword matches.89 // If the keyword doesn't match this character, then change the keyword90 // to doesn't match91 __st = __status;92 for (_ForwardIterator __ky = __kb; __ky != __ke; ++__ky, (void)++__st) {93 if (*__st == __might_match) {94 _CharT __kc = (*__ky)[__indx];95 if (!__case_sensitive)96 __kc = __ct.toupper(__kc);97 if (__c == __kc) {98 __consume = true;99 if (__ky->size() == __indx + 1) {100 *__st = __does_match;101 --__n_might_match;102 ++__n_does_match;103 }104 } else {105 *__st = __doesnt_match;106 --__n_might_match;107 }108 }109 }110 // consume if we matched a character111 if (__consume) {112 ++__b;113 // If we consumed a character and there might be a matched keyword that114 // was marked matched on a previous iteration, then such keywords115 // which are now marked as not matching.116 if (__n_might_match + __n_does_match > 1) {117 __st = __status;118 for (_ForwardIterator __ky = __kb; __ky != __ke; ++__ky, (void)++__st) {119 if (*__st == __does_match && __ky->size() != __indx + 1) {120 *__st = __doesnt_match;121 --__n_does_match;122 }123 }124 }125 }126 }127 // We've exited the loop because we hit eof and/or we have no more "might matches".128 if (__b == __e)129 __err |= ios_base::eofbit;130 // Return the first matching result131 for (__st = __status; __kb != __ke; ++__kb, (void)++__st)132 if (*__st == __does_match)133 break;134 if (__kb == __ke)135 __err |= ios_base::failbit;136 return __kb;137}138 139_LIBCPP_END_NAMESPACE_STD140 141#endif // _LIBCPP_HAS_LOCALIZATION142 143#endif // _LIBCPP___LOCALE_DIR_SCAN_KEYWORD_H144