1 /* 2 * Copyright (C) 2015 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 #ifndef ART_RUNTIME_BASE_DCHECKED_VECTOR_H_ 18 #define ART_RUNTIME_BASE_DCHECKED_VECTOR_H_ 19 20 #include <algorithm> 21 #include <type_traits> 22 #include <vector> 23 24 #include "base/logging.h" 25 26 namespace art { 27 28 // Template class serving as a replacement for std::vector<> but adding 29 // DCHECK()s for the subscript operator, front(), back(), pop_back(), 30 // and for insert()/emplace()/erase() positions. 31 // 32 // Note: The element accessor at() is specified as throwing std::out_of_range 33 // but we do not use exceptions, so this accessor is deliberately hidden. 34 // Note: The common pattern &v[0] used to retrieve pointer to the data is not 35 // valid for an empty dchecked_vector<>. Use data() to avoid checking empty(). 36 template <typename T, typename Alloc = std::allocator<T>> 37 class dchecked_vector : private std::vector<T, Alloc> { 38 private: 39 // std::vector<> has a slightly different specialization for bool. We don't provide that. 40 static_assert(!std::is_same<T, bool>::value, "Not implemented for bool."); 41 using Base = std::vector<T, Alloc>; 42 43 public: 44 using typename Base::value_type; 45 using typename Base::allocator_type; 46 using typename Base::reference; 47 using typename Base::const_reference; 48 using typename Base::pointer; 49 using typename Base::const_pointer; 50 using typename Base::iterator; 51 using typename Base::const_iterator; 52 using typename Base::reverse_iterator; 53 using typename Base::const_reverse_iterator; 54 using typename Base::size_type; 55 using typename Base::difference_type; 56 57 // Construct/copy/destroy. 58 dchecked_vector() 59 : Base() { } 60 explicit dchecked_vector(const allocator_type& alloc) 61 : Base(alloc) { } 62 explicit dchecked_vector(size_type n, const allocator_type& alloc = allocator_type()) 63 : Base(n, alloc) { } 64 dchecked_vector(size_type n, 65 const value_type& value, 66 const allocator_type& alloc = allocator_type()) 67 : Base(n, value, alloc) { } 68 template <typename InputIterator> 69 dchecked_vector(InputIterator first, 70 InputIterator last, 71 const allocator_type& alloc = allocator_type()) 72 : Base(first, last, alloc) { } 73 dchecked_vector(const dchecked_vector& src) 74 : Base(src) { } 75 dchecked_vector(const dchecked_vector& src, const allocator_type& alloc) 76 : Base(src, alloc) { } 77 dchecked_vector(dchecked_vector&& src) 78 : Base(std::move(src)) { } 79 dchecked_vector(dchecked_vector&& src, const allocator_type& alloc) 80 : Base(std::move(src), alloc) { } 81 dchecked_vector(std::initializer_list<value_type> il, 82 const allocator_type& alloc = allocator_type()) 83 : Base(il, alloc) { } 84 ~dchecked_vector() = default; 85 dchecked_vector& operator=(const dchecked_vector& src) { 86 Base::operator=(src); 87 return *this; 88 } 89 dchecked_vector& operator=(dchecked_vector&& src) { 90 Base::operator=(std::move(src)); 91 return *this; 92 } 93 dchecked_vector& operator=(std::initializer_list<value_type> il) { 94 Base::operator=(il); 95 return *this; 96 } 97 98 // Iterators. 99 using Base::begin; 100 using Base::end; 101 using Base::rbegin; 102 using Base::rend; 103 using Base::cbegin; 104 using Base::cend; 105 using Base::crbegin; 106 using Base::crend; 107 108 // Capacity. 109 using Base::size; 110 using Base::max_size; 111 using Base::resize; 112 using Base::capacity; 113 using Base::empty; 114 using Base::reserve; 115 using Base::shrink_to_fit; 116 117 // Element access: inherited. 118 // Note: Deliberately not providing at(). 119 using Base::data; 120 121 // Element access: subscript operator. Check index. 122 reference operator[](size_type n) { 123 DCHECK_LT(n, size()); 124 return Base::operator[](n); 125 } 126 const_reference operator[](size_type n) const { 127 DCHECK_LT(n, size()); 128 return Base::operator[](n); 129 } 130 131 // Element access: front(), back(). Check not empty. 132 reference front() { DCHECK(!empty()); return Base::front(); } 133 const_reference front() const { DCHECK(!empty()); return Base::front(); } 134 reference back() { DCHECK(!empty()); return Base::back(); } 135 const_reference back() const { DCHECK(!empty()); return Base::back(); } 136 137 // Modifiers: inherited. 138 using Base::assign; 139 using Base::push_back; 140 using Base::clear; 141 using Base::emplace_back; 142 143 // Modifiers: pop_back(). Check not empty. 144 void pop_back() { DCHECK(!empty()); Base::pop_back(); } 145 146 // Modifiers: swap(). Swap only with another dchecked_vector instead of a plain vector. 147 void swap(dchecked_vector& other) { Base::swap(other); } 148 149 // Modifiers: insert(). Check position. 150 iterator insert(const_iterator position, const value_type& value) { 151 DCHECK(cbegin() <= position && position <= cend()); 152 return Base::insert(position, value); 153 } 154 iterator insert(const_iterator position, size_type n, const value_type& value) { 155 DCHECK(cbegin() <= position && position <= cend()); 156 return Base::insert(position, n, value); 157 } 158 template <typename InputIterator> 159 iterator insert(const_iterator position, InputIterator first, InputIterator last) { 160 DCHECK(cbegin() <= position && position <= cend()); 161 return Base::insert(position, first, last); 162 } 163 iterator insert(const_iterator position, value_type&& value) { 164 DCHECK(cbegin() <= position && position <= cend()); 165 return Base::insert(position, std::move(value)); 166 } 167 iterator insert(const_iterator position, std::initializer_list<value_type> il) { 168 DCHECK(cbegin() <= position && position <= cend()); 169 return Base::insert(position, il); 170 } 171 172 // Modifiers: erase(). Check position. 173 iterator erase(const_iterator position) { 174 DCHECK(cbegin() <= position && position < cend()); 175 return Base::erase(position); 176 } 177 iterator erase(const_iterator first, const_iterator last) { 178 DCHECK(cbegin() <= first && first <= cend()); 179 DCHECK(first <= last && last <= cend()); 180 return Base::erase(first, last); 181 } 182 183 // Modifiers: emplace(). Check position. 184 template <typename... Args> 185 iterator emplace(const_iterator position, Args&&... args) { 186 DCHECK(cbegin() <= position && position <= cend()); 187 Base::emplace(position, std::forward(args...)); 188 } 189 190 // Allocator. 191 using Base::get_allocator; 192 }; 193 194 // Non-member swap(), found by argument-dependent lookup for an unqualified call. 195 template <typename T, typename Alloc> 196 void swap(dchecked_vector<T, Alloc>& lhs, dchecked_vector<T, Alloc>& rhs) { 197 lhs.swap(rhs); 198 } 199 200 // Non-member relational operators. 201 template <typename T, typename Alloc> 202 bool operator==(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) { 203 return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin()); 204 } 205 template <typename T, typename Alloc> 206 bool operator!=(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) { 207 return !(lhs == rhs); 208 } 209 template <typename T, typename Alloc> 210 bool operator<(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) { 211 return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); 212 } 213 template <typename T, typename Alloc> 214 bool operator<=(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) { 215 return !(rhs < lhs); 216 } 217 template <typename T, typename Alloc> 218 bool operator>(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) { 219 return rhs < lhs; 220 } 221 template <typename T, typename Alloc> 222 bool operator>=(const dchecked_vector<T, Alloc>& lhs, const dchecked_vector<T, Alloc>& rhs) { 223 return !(lhs < rhs); 224 } 225 226 } // namespace art 227 228 #endif // ART_RUNTIME_BASE_DCHECKED_VECTOR_H_ 229