1 /*
2 * Copyright (C) 2005 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 ANDROID_VECTOR_H
18 #define ANDROID_VECTOR_H
19
20 #include <stdint.h>
21 #include <sys/types.h>
22
23 #include <log/log.h>
24 #include <utils/TypeHelpers.h>
25 #include <utils/VectorImpl.h>
26 #ifndef __has_attribute
27 #define __has_attribute(x) 0
28 #endif
29
30 /*
31 * Used to exclude some functions from CFI.
32 */
33 #if __has_attribute(no_sanitize)
34 #define UTILS_VECTOR_NO_CFI __attribute__((no_sanitize("cfi")))
35 #else
36 #define UTILS_VECTOR_NO_CFI
37 #endif
38
39 // ---------------------------------------------------------------------------
40
41 namespace android {
42
43 template <typename TYPE>
44 class SortedVector;
45
46 /*!
47 * The main templated vector class ensuring type safety
48 * while making use of VectorImpl.
49 * This is the class users want to use.
50 *
51 * DO NOT USE: please use std::vector
52 */
53
54 template <class TYPE>
55 class Vector : private VectorImpl
56 {
57 public:
58 typedef TYPE value_type;
59
60 /*!
61 * Constructors and destructors
62 */
63
64 Vector();
65 Vector(const Vector<TYPE>& rhs);
66 explicit Vector(const SortedVector<TYPE>& rhs);
67 virtual ~Vector();
68
69 /*! copy operator */
70 Vector<TYPE>& operator=(const Vector<TYPE>& rhs); // NOLINT(cert-oop54-cpp)
71 Vector<TYPE>& operator=(const SortedVector<TYPE>& rhs); // NOLINT(cert-oop54-cpp)
72
73 /*
74 * empty the vector
75 */
76
clear()77 inline void clear() { VectorImpl::clear(); }
78
79 /*!
80 * vector stats
81 */
82
83 //! returns number of items in the vector
size()84 inline size_t size() const { return VectorImpl::size(); }
85 //! returns whether or not the vector is empty
isEmpty()86 inline bool isEmpty() const { return VectorImpl::isEmpty(); }
87 //! returns how many items can be stored without reallocating the backing store
capacity()88 inline size_t capacity() const { return VectorImpl::capacity(); }
89 //! sets the capacity. capacity can never be reduced less than size()
setCapacity(size_t size)90 inline ssize_t setCapacity(size_t size) { return VectorImpl::setCapacity(size); }
91
92 /*!
93 * set the size of the vector. items are appended with the default
94 * constructor, or removed from the end as needed.
95 */
resize(size_t size)96 inline ssize_t resize(size_t size) { return VectorImpl::resize(size); }
97
98 /*!
99 * C-style array access
100 */
101
102 //! read-only C-style access
103 inline const TYPE* array() const;
104 //! read-write C-style access
105 TYPE* editArray();
106
107 /*!
108 * accessors
109 */
110
111 //! read-only access to an item at a given index
112 inline const TYPE& operator [] (size_t index) const;
113 //! alternate name for operator []
114 inline const TYPE& itemAt(size_t index) const;
115 //! stack-usage of the vector. returns the top of the stack (last element)
116 const TYPE& top() const;
117
118 /*!
119 * modifying the array
120 */
121
122 //! copy-on write support, grants write access to an item
123 TYPE& editItemAt(size_t index);
124 //! grants right access to the top of the stack (last element)
125 TYPE& editTop();
126
127 /*!
128 * append/insert another vector
129 */
130
131 //! insert another vector at a given index
132 ssize_t insertVectorAt(const Vector<TYPE>& vector, size_t index);
133
134 //! append another vector at the end of this one
135 ssize_t appendVector(const Vector<TYPE>& vector);
136
137
138 //! insert an array at a given index
139 ssize_t insertArrayAt(const TYPE* array, size_t index, size_t length);
140
141 //! append an array at the end of this vector
142 ssize_t appendArray(const TYPE* array, size_t length);
143
144 /*!
145 * add/insert/replace items
146 */
147
148 //! insert one or several items initialized with their default constructor
149 inline ssize_t insertAt(size_t index, size_t numItems = 1);
150 //! insert one or several items initialized from a prototype item
151 ssize_t insertAt(const TYPE& prototype_item, size_t index, size_t numItems = 1);
152 //! pop the top of the stack (removes the last element). No-op if the stack's empty
153 inline void pop();
154 //! pushes an item initialized with its default constructor
155 inline void push();
156 //! pushes an item on the top of the stack
157 void push(const TYPE& item);
158 //! same as push() but returns the index the item was added at (or an error)
159 inline ssize_t add();
160 //! same as push() but returns the index the item was added at (or an error)
161 ssize_t add(const TYPE& item);
162 //! replace an item with a new one initialized with its default constructor
163 inline ssize_t replaceAt(size_t index);
164 //! replace an item with a new one
165 ssize_t replaceAt(const TYPE& item, size_t index);
166
167 /*!
168 * remove items
169 */
170
171 //! remove several items
172 inline ssize_t removeItemsAt(size_t index, size_t count = 1);
173 //! remove one item
removeAt(size_t index)174 inline ssize_t removeAt(size_t index) { return removeItemsAt(index); }
175
176 /*!
177 * sort (stable) the array
178 */
179
180 typedef int (*compar_t)(const TYPE* lhs, const TYPE* rhs);
181 typedef int (*compar_r_t)(const TYPE* lhs, const TYPE* rhs, void* state);
182
183 inline status_t sort(compar_t cmp);
184 inline status_t sort(compar_r_t cmp, void* state);
185
186 // for debugging only
getItemSize()187 inline size_t getItemSize() const { return itemSize(); }
188
189
190 /*
191 * these inlines add some level of compatibility with STL. eventually
192 * we should probably turn things around.
193 */
194 typedef TYPE* iterator;
195 typedef TYPE const* const_iterator;
196
begin()197 inline iterator begin() { return editArray(); }
end()198 inline iterator end() { return editArray() + size(); }
begin()199 inline const_iterator begin() const { return array(); }
end()200 inline const_iterator end() const { return array() + size(); }
reserve(size_t n)201 inline void reserve(size_t n) { setCapacity(n); }
empty()202 inline bool empty() const{ return isEmpty(); }
push_back(const TYPE & item)203 inline void push_back(const TYPE& item) { insertAt(item, size(), 1); }
push_front(const TYPE & item)204 inline void push_front(const TYPE& item) { insertAt(item, 0, 1); }
erase(iterator pos)205 inline iterator erase(iterator pos) {
206 ssize_t index = removeItemsAt(static_cast<size_t>(pos-array()));
207 return begin() + index;
208 }
209
210 protected:
211 virtual void do_construct(void* storage, size_t num) const;
212 virtual void do_destroy(void* storage, size_t num) const;
213 virtual void do_copy(void* dest, const void* from, size_t num) const;
214 virtual void do_splat(void* dest, const void* item, size_t num) const;
215 virtual void do_move_forward(void* dest, const void* from, size_t num) const;
216 virtual void do_move_backward(void* dest, const void* from, size_t num) const;
217 };
218
219 // ---------------------------------------------------------------------------
220 // No user serviceable parts from here...
221 // ---------------------------------------------------------------------------
222
223 template<class TYPE> inline
Vector()224 Vector<TYPE>::Vector()
225 : VectorImpl(sizeof(TYPE),
226 ((traits<TYPE>::has_trivial_ctor ? HAS_TRIVIAL_CTOR : 0)
227 |(traits<TYPE>::has_trivial_dtor ? HAS_TRIVIAL_DTOR : 0)
228 |(traits<TYPE>::has_trivial_copy ? HAS_TRIVIAL_COPY : 0))
229 )
230 {
231 }
232
233 template<class TYPE> inline
Vector(const Vector<TYPE> & rhs)234 Vector<TYPE>::Vector(const Vector<TYPE>& rhs)
235 : VectorImpl(rhs) {
236 }
237
238 template<class TYPE> inline
Vector(const SortedVector<TYPE> & rhs)239 Vector<TYPE>::Vector(const SortedVector<TYPE>& rhs)
240 : VectorImpl(static_cast<const VectorImpl&>(rhs)) {
241 }
242
243 template<class TYPE> inline
~Vector()244 Vector<TYPE>::~Vector() {
245 finish_vector();
246 }
247
248 template <class TYPE>
249 inline Vector<TYPE>& Vector<TYPE>::operator=(const Vector<TYPE>& rhs) // NOLINT(cert-oop54-cpp)
250 {
251 VectorImpl::operator=(rhs);
252 return *this;
253 }
254
255 template <class TYPE>
256 inline Vector<TYPE>& Vector<TYPE>::operator=(
257 const SortedVector<TYPE>& rhs) // NOLINT(cert-oop54-cpp)
258 {
259 VectorImpl::operator=(static_cast<const VectorImpl&>(rhs));
260 return *this;
261 }
262
263 template<class TYPE> inline
array()264 const TYPE* Vector<TYPE>::array() const {
265 return static_cast<const TYPE *>(arrayImpl());
266 }
267
268 template<class TYPE> inline
editArray()269 TYPE* Vector<TYPE>::editArray() {
270 return static_cast<TYPE *>(editArrayImpl());
271 }
272
273
274 template<class TYPE> inline
275 const TYPE& Vector<TYPE>::operator[](size_t index) const {
276 LOG_FATAL_IF(index>=size(),
277 "%s: index=%u out of range (%u)", __PRETTY_FUNCTION__,
278 int(index), int(size()));
279 return *(array() + index);
280 }
281
282 template<class TYPE> inline
itemAt(size_t index)283 const TYPE& Vector<TYPE>::itemAt(size_t index) const {
284 return operator[](index);
285 }
286
287 template<class TYPE> inline
top()288 const TYPE& Vector<TYPE>::top() const {
289 return *(array() + size() - 1);
290 }
291
292 template<class TYPE> inline
editItemAt(size_t index)293 TYPE& Vector<TYPE>::editItemAt(size_t index) {
294 return *( static_cast<TYPE *>(editItemLocation(index)) );
295 }
296
297 template<class TYPE> inline
editTop()298 TYPE& Vector<TYPE>::editTop() {
299 return *( static_cast<TYPE *>(editItemLocation(size()-1)) );
300 }
301
302 template<class TYPE> inline
insertVectorAt(const Vector<TYPE> & vector,size_t index)303 ssize_t Vector<TYPE>::insertVectorAt(const Vector<TYPE>& vector, size_t index) {
304 return VectorImpl::insertVectorAt(reinterpret_cast<const VectorImpl&>(vector), index);
305 }
306
307 template<class TYPE> inline
appendVector(const Vector<TYPE> & vector)308 ssize_t Vector<TYPE>::appendVector(const Vector<TYPE>& vector) {
309 return VectorImpl::appendVector(reinterpret_cast<const VectorImpl&>(vector));
310 }
311
312 template<class TYPE> inline
insertArrayAt(const TYPE * array,size_t index,size_t length)313 ssize_t Vector<TYPE>::insertArrayAt(const TYPE* array, size_t index, size_t length) {
314 return VectorImpl::insertArrayAt(array, index, length);
315 }
316
317 template<class TYPE> inline
appendArray(const TYPE * array,size_t length)318 ssize_t Vector<TYPE>::appendArray(const TYPE* array, size_t length) {
319 return VectorImpl::appendArray(array, length);
320 }
321
322 template<class TYPE> inline
insertAt(const TYPE & item,size_t index,size_t numItems)323 ssize_t Vector<TYPE>::insertAt(const TYPE& item, size_t index, size_t numItems) {
324 return VectorImpl::insertAt(&item, index, numItems);
325 }
326
327 template<class TYPE> inline
push(const TYPE & item)328 void Vector<TYPE>::push(const TYPE& item) {
329 return VectorImpl::push(&item);
330 }
331
332 template<class TYPE> inline
add(const TYPE & item)333 ssize_t Vector<TYPE>::add(const TYPE& item) {
334 return VectorImpl::add(&item);
335 }
336
337 template<class TYPE> inline
replaceAt(const TYPE & item,size_t index)338 ssize_t Vector<TYPE>::replaceAt(const TYPE& item, size_t index) {
339 return VectorImpl::replaceAt(&item, index);
340 }
341
342 template<class TYPE> inline
insertAt(size_t index,size_t numItems)343 ssize_t Vector<TYPE>::insertAt(size_t index, size_t numItems) {
344 return VectorImpl::insertAt(index, numItems);
345 }
346
347 template<class TYPE> inline
pop()348 void Vector<TYPE>::pop() {
349 VectorImpl::pop();
350 }
351
352 template<class TYPE> inline
push()353 void Vector<TYPE>::push() {
354 VectorImpl::push();
355 }
356
357 template<class TYPE> inline
add()358 ssize_t Vector<TYPE>::add() {
359 return VectorImpl::add();
360 }
361
362 template<class TYPE> inline
replaceAt(size_t index)363 ssize_t Vector<TYPE>::replaceAt(size_t index) {
364 return VectorImpl::replaceAt(index);
365 }
366
367 template<class TYPE> inline
removeItemsAt(size_t index,size_t count)368 ssize_t Vector<TYPE>::removeItemsAt(size_t index, size_t count) {
369 return VectorImpl::removeItemsAt(index, count);
370 }
371
372 template<class TYPE> inline
sort(Vector<TYPE>::compar_t cmp)373 status_t Vector<TYPE>::sort(Vector<TYPE>::compar_t cmp) {
374 return VectorImpl::sort(reinterpret_cast<VectorImpl::compar_t>(cmp));
375 }
376
377 template<class TYPE> inline
sort(Vector<TYPE>::compar_r_t cmp,void * state)378 status_t Vector<TYPE>::sort(Vector<TYPE>::compar_r_t cmp, void* state) {
379 return VectorImpl::sort(reinterpret_cast<VectorImpl::compar_r_t>(cmp), state);
380 }
381
382 // ---------------------------------------------------------------------------
383
384 template<class TYPE>
do_construct(void * storage,size_t num)385 UTILS_VECTOR_NO_CFI void Vector<TYPE>::do_construct(void* storage, size_t num) const {
386 construct_type( reinterpret_cast<TYPE*>(storage), num );
387 }
388
389 template<class TYPE>
do_destroy(void * storage,size_t num)390 void Vector<TYPE>::do_destroy(void* storage, size_t num) const {
391 destroy_type( reinterpret_cast<TYPE*>(storage), num );
392 }
393
394 template<class TYPE>
do_copy(void * dest,const void * from,size_t num)395 UTILS_VECTOR_NO_CFI void Vector<TYPE>::do_copy(void* dest, const void* from, size_t num) const {
396 copy_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
397 }
398
399 template<class TYPE>
do_splat(void * dest,const void * item,size_t num)400 UTILS_VECTOR_NO_CFI void Vector<TYPE>::do_splat(void* dest, const void* item, size_t num) const {
401 splat_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(item), num );
402 }
403
404 template<class TYPE>
do_move_forward(void * dest,const void * from,size_t num)405 UTILS_VECTOR_NO_CFI void Vector<TYPE>::do_move_forward(void* dest, const void* from, size_t num) const {
406 move_forward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
407 }
408
409 template<class TYPE>
do_move_backward(void * dest,const void * from,size_t num)410 UTILS_VECTOR_NO_CFI void Vector<TYPE>::do_move_backward(void* dest, const void* from, size_t num) const {
411 move_backward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
412 }
413
414 } // namespace android
415
416 // ---------------------------------------------------------------------------
417
418 #endif // ANDROID_VECTOR_H
419