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