1 /* 2 * Copyright (C) 2022 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #pragma once 18 19 #include <algorithm> 20 #include <iterator> 21 #include <string> 22 #include <string_view> 23 #include <type_traits> 24 25 /** 26 * @file: Implement Contains(container, key) 27 * 28 * The function returns true if container has the key, or false. 29 * 30 * If the container has a find(key) method (e.g. set, unordered_set, std::map, 31 * etc), the find method is used. Otherwise, the std::find function from 32 * algorithm is used, which may result in a linear search. 33 * 34 * See go/cf-utils-contains for more details. 35 */ 36 namespace cuttlefish { 37 namespace contains_internal_impl { 38 39 /* 40 * If Container does not have find key, will be a compiler error used 41 * by SFINAE. If it does have one, this is equivalent to the "void" type. 42 */ 43 template <typename Container, typename Key> 44 using VoidTypeIfHasFind = 45 decltype(void(std::declval<Container&>().find(std::declval<Key&>()))); 46 47 /* 48 * Here is how this works: 49 * 50 * Given that 51 * HasFindImpl<Container, T> is used in the code 52 * 53 * 1. The input is effectively regarded as HasFindImpl<Container, T, void>. 54 * The specialized version below isn't looked up yet; whether the specialized 55 * version below is used or not, the compiler front-end needs all three 56 * template parameters to match against either special or generic version. 57 * When obtaining "all three," the front-end only looks up the base template 58 * definition. The default type of the third template parameter is void, so 59 * the given type is expanded/deduced to HasFindImpl<Container, T, void>. 60 * 61 * 2. Now, given HasFindImpl<Container, T, void>, the compiler front-end 62 * tries matching against the specialized and generic/original versions. If 63 * the input could matches both a generic and a specialized one, the compiler 64 * chooses the specialized one. Thus, particularly, HasFindImpl 65 * implementation's third parameter in the specialized version must be the 66 * same as the default type of the third template parameter to the original/ 67 * generic version, which is "void." 68 */ 69 template <typename Container, typename T, typename = void> 70 struct HasFindImpl : std::false_type {}; 71 72 template <typename Container, typename T> 73 struct HasFindImpl<Container, T, VoidTypeIfHasFind<Container, T>> 74 : std::true_type {}; 75 76 template <typename T> 77 using RemoveCvref = 78 typename std::remove_cv_t<typename std::remove_reference_t<T>>; 79 80 template <typename T, typename U> 81 using IsSame = typename std::is_same<RemoveCvref<T>, RemoveCvref<U>>; 82 83 template <typename T> 84 struct IsString : IsSame<std::string, T> {}; 85 86 template <typename T> 87 struct IsStringView : IsSame<std::string_view, T> {}; 88 89 } // namespace contains_internal_impl 90 91 // TODO(kwstephenkim): Replace these when C++20 starts to be used. 92 template <typename Container, typename U, 93 typename = std::enable_if_t< 94 contains_internal_impl::HasFindImpl<Container, U>::value && 95 (!contains_internal_impl::IsString<Container>::value && 96 !contains_internal_impl::IsStringView<Container>::value), 97 void>> 98 constexpr bool Contains(Container&& container, U&& u) { 99 // using O(1) or O(lgN) find() 100 return container.find(std::forward<U>(u)) != container.end(); 101 } 102 103 template < 104 typename Container, typename U, 105 std::enable_if_t<!contains_internal_impl::HasFindImpl<Container, U>::value, 106 int> = 0> 107 constexpr bool Contains(Container&& container, U&& u) { 108 // falls back to a generic, likely linear search 109 const auto itr = 110 std::find(std::begin(container), std::end(container), std::forward<U>(u)); 111 return itr != std::end(container); 112 } 113 114 // std::string:: or std::string_view::find() returns index, not iterator 115 template <typename T> 116 constexpr bool Contains(const std::string& s, T&& t) { 117 return s.find(std::forward<T>(t)) != std::string::npos; 118 } 119 120 template <typename T> 121 constexpr bool Contains(const std::string_view& s, T&& t) { 122 return s.find(std::forward<T>(t)) != std::string_view::npos; 123 } 124 125 } // namespace cuttlefish 126