1 /* 2 * Copyright 2020 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 <new> 22 #include <type_traits> 23 24 #define FTL_ARRAY_TRAIT(T, U) using U = typename details::ArrayTraits<T>::U 25 26 namespace android::ftl::details { 27 28 template <typename T> 29 struct ArrayTraits { 30 using value_type = T; 31 using size_type = std::size_t; 32 using difference_type = std::ptrdiff_t; 33 34 using pointer = value_type*; 35 using reference = value_type&; 36 using iterator = pointer; 37 using reverse_iterator = std::reverse_iterator<iterator>; 38 39 using const_pointer = const value_type*; 40 using const_reference = const value_type&; 41 using const_iterator = const_pointer; 42 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 43 44 template <typename... Args> construct_atArrayTraits45 static constexpr pointer construct_at(const_iterator it, Args&&... args) { 46 void* const ptr = const_cast<void*>(static_cast<const void*>(it)); 47 if constexpr (std::is_constructible_v<value_type, Args...>) { 48 // TODO: Replace with std::construct_at in C++20. 49 return new (ptr) value_type(std::forward<Args>(args)...); 50 } else { 51 // Fall back to list initialization. 52 return new (ptr) value_type{std::forward<Args>(args)...}; 53 } 54 } 55 56 // TODO: Make constexpr in C++20. 57 template <typename... Args> replace_atArrayTraits58 static reference replace_at(const_iterator it, Args&&... args) { 59 value_type element{std::forward<Args>(args)...}; 60 return replace_at(it, std::move(element)); 61 } 62 63 // TODO: Make constexpr in C++20. replace_atArrayTraits64 static reference replace_at(const_iterator it, value_type&& value) { 65 std::destroy_at(it); 66 // This is only safe because exceptions are disabled. 67 return *construct_at(it, std::move(value)); 68 } 69 70 // TODO: Make constexpr in C++20. in_place_swapArrayTraits71 static void in_place_swap(reference a, reference b) { 72 value_type c{std::move(a)}; 73 replace_at(&a, std::move(b)); 74 replace_at(&b, std::move(c)); 75 } 76 77 // TODO: Make constexpr in C++20. in_place_swap_rangesArrayTraits78 static void in_place_swap_ranges(iterator first1, iterator last1, iterator first2) { 79 while (first1 != last1) { 80 in_place_swap(*first1++, *first2++); 81 } 82 } 83 84 // TODO: Replace with std::uninitialized_copy in C++20. 85 template <typename Iterator> uninitialized_copyArrayTraits86 static void uninitialized_copy(Iterator first, Iterator last, const_iterator out) { 87 while (first != last) { 88 construct_at(out++, *first++); 89 } 90 } 91 }; 92 93 // CRTP mixin to define iterator functions in terms of non-const Self::begin and Self::end. 94 template <typename Self, typename T> 95 class ArrayIterators { 96 FTL_ARRAY_TRAIT(T, size_type); 97 98 FTL_ARRAY_TRAIT(T, reference); 99 FTL_ARRAY_TRAIT(T, iterator); 100 FTL_ARRAY_TRAIT(T, reverse_iterator); 101 102 FTL_ARRAY_TRAIT(T, const_reference); 103 FTL_ARRAY_TRAIT(T, const_iterator); 104 FTL_ARRAY_TRAIT(T, const_reverse_iterator); 105 self()106 Self& self() const { return *const_cast<Self*>(static_cast<const Self*>(this)); } 107 108 public: begin()109 const_iterator begin() const { return cbegin(); } cbegin()110 const_iterator cbegin() const { return self().begin(); } 111 end()112 const_iterator end() const { return cend(); } cend()113 const_iterator cend() const { return self().end(); } 114 rbegin()115 reverse_iterator rbegin() { return std::make_reverse_iterator(self().end()); } rbegin()116 const_reverse_iterator rbegin() const { return crbegin(); } crbegin()117 const_reverse_iterator crbegin() const { return self().rbegin(); } 118 rend()119 reverse_iterator rend() { return std::make_reverse_iterator(self().begin()); } rend()120 const_reverse_iterator rend() const { return crend(); } crend()121 const_reverse_iterator crend() const { return self().rend(); } 122 last()123 iterator last() { return self().end() - 1; } last()124 const_iterator last() const { return self().last(); } 125 front()126 reference front() { return *self().begin(); } front()127 const_reference front() const { return self().front(); } 128 back()129 reference back() { return *last(); } back()130 const_reference back() const { return self().back(); } 131 132 reference operator[](size_type i) { return *(self().begin() + i); } 133 const_reference operator[](size_type i) const { return self()[i]; } 134 }; 135 136 // Mixin to define comparison operators for an array-like template. 137 // TODO: Replace with operator<=> in C++20. 138 template <template <typename, std::size_t> class Array> 139 struct ArrayComparators { 140 template <typename T, typename U, std::size_t N, std::size_t M> 141 friend bool operator==(const Array<T, N>& lhs, const Array<U, M>& rhs) { 142 return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin()); 143 } 144 145 template <typename T, typename U, std::size_t N, std::size_t M> 146 friend bool operator<(const Array<T, N>& lhs, const Array<U, M>& rhs) { 147 return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); 148 } 149 150 template <typename T, typename U, std::size_t N, std::size_t M> 151 friend bool operator>(const Array<T, N>& lhs, const Array<U, M>& rhs) { 152 return rhs < lhs; 153 } 154 155 template <typename T, typename U, std::size_t N, std::size_t M> 156 friend bool operator!=(const Array<T, N>& lhs, const Array<U, M>& rhs) { 157 return !(lhs == rhs); 158 } 159 160 template <typename T, typename U, std::size_t N, std::size_t M> 161 friend bool operator>=(const Array<T, N>& lhs, const Array<U, M>& rhs) { 162 return !(lhs < rhs); 163 } 164 165 template <typename T, typename U, std::size_t N, std::size_t M> 166 friend bool operator<=(const Array<T, N>& lhs, const Array<U, M>& rhs) { 167 return !(lhs > rhs); 168 } 169 }; 170 171 } // namespace android::ftl::details 172