include/utils/Vector.h

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