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