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 ArrayTraits<T>::U 25 26 namespace android::ftl { 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 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 57 // CRTP mixin to define iterator functions in terms of non-const Self::begin and Self::end. 58 template <typename Self, typename T> 59 class ArrayIterators { 60 FTL_ARRAY_TRAIT(T, size_type); 61 62 FTL_ARRAY_TRAIT(T, reference); 63 FTL_ARRAY_TRAIT(T, iterator); 64 FTL_ARRAY_TRAIT(T, reverse_iterator); 65 66 FTL_ARRAY_TRAIT(T, const_reference); 67 FTL_ARRAY_TRAIT(T, const_iterator); 68 FTL_ARRAY_TRAIT(T, const_reverse_iterator); 69 self()70 Self& self() const { return *const_cast<Self*>(static_cast<const Self*>(this)); } 71 72 public: begin()73 const_iterator begin() const { return cbegin(); } cbegin()74 const_iterator cbegin() const { return self().begin(); } 75 end()76 const_iterator end() const { return cend(); } cend()77 const_iterator cend() const { return self().end(); } 78 rbegin()79 reverse_iterator rbegin() { return std::make_reverse_iterator(self().end()); } rbegin()80 const_reverse_iterator rbegin() const { return crbegin(); } crbegin()81 const_reverse_iterator crbegin() const { return self().rbegin(); } 82 rend()83 reverse_iterator rend() { return std::make_reverse_iterator(self().begin()); } rend()84 const_reverse_iterator rend() const { return crend(); } crend()85 const_reverse_iterator crend() const { return self().rend(); } 86 last()87 iterator last() { return self().end() - 1; } last()88 const_iterator last() const { return self().last(); } 89 front()90 reference front() { return *self().begin(); } front()91 const_reference front() const { return self().front(); } 92 back()93 reference back() { return *last(); } back()94 const_reference back() const { return self().back(); } 95 96 reference operator[](size_type i) { return *(self().begin() + i); } 97 const_reference operator[](size_type i) const { return self()[i]; } 98 }; 99 100 // Mixin to define comparison operators for an array-like template. 101 // TODO: Replace with operator<=> in C++20. 102 template <template <typename, std::size_t> class Array> 103 struct ArrayComparators { 104 template <typename T, std::size_t N, std::size_t M> 105 friend bool operator==(const Array<T, N>& lhs, const Array<T, M>& rhs) { 106 return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin()); 107 } 108 109 template <typename T, std::size_t N, std::size_t M> 110 friend bool operator<(const Array<T, N>& lhs, const Array<T, M>& rhs) { 111 return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); 112 } 113 114 template <typename T, std::size_t N, std::size_t M> 115 friend bool operator>(const Array<T, N>& lhs, const Array<T, M>& rhs) { 116 return rhs < lhs; 117 } 118 119 template <typename T, std::size_t N, std::size_t M> 120 friend bool operator!=(const Array<T, N>& lhs, const Array<T, M>& rhs) { 121 return !(lhs == rhs); 122 } 123 124 template <typename T, std::size_t N, std::size_t M> 125 friend bool operator>=(const Array<T, N>& lhs, const Array<T, M>& rhs) { 126 return !(lhs < rhs); 127 } 128 129 template <typename T, std::size_t N, std::size_t M> 130 friend bool operator<=(const Array<T, N>& lhs, const Array<T, M>& rhs) { 131 return !(lhs > rhs); 132 } 133 }; 134 135 } // namespace android::ftl 136