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