dali/public-api/common/dali-vector.h

   1 #ifndef __DALI_VECTOR_H__
   2 #define __DALI_VECTOR_H__
   3
   4 /*
   5  * Copyright (c) 2014 Samsung Electronics Co., Ltd.
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  * http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  *
  19  */
  20
  21
  22 // EXTERNAL INCLUDES
  23 #include <cstddef>
  24
  25 // INTERNAL INCLUDES
  26 #include <dali/public-api/common/dali-common.h>
  27
  28 /**
  29  * @brief For DALi internal use asserts are enabled in debug builds.
  30  *
  31  * For Application use asserts can be enabled manually.
  32  */
  33 #if defined( DEBUG_ENABLED )
  34 #define ENABLE_VECTOR_ASSERTS
  35 #endif
  36
  37 #if defined( ENABLE_VECTOR_ASSERTS )
  38 #define DALI_ASSERT_VECTOR(cond) DALI_ASSERT_ALWAYS(cond)
  39 #else
  40 #define DALI_ASSERT_VECTOR(cond)
  41 #endif
  42
  43 namespace Dali DALI_IMPORT_API
  44 {
  45
  46 /**
  47  * @brief Base class to handle the memory of simple vector.
  48  *
  49  * Memory layout is such that it has two std::size_t to hold the count
  50  * and capacity of the vector. mData is adjusted so that it points to the
  51  * beginning of the first real item so that iterating the items is quick.
  52  */
  53 class VectorBase
  54 {
  55 public: // Typedefs
  56
  57   typedef std::size_t SizeType;
  58
  59 protected: // Construction
  60
  61   /**
  62    * @brief Default constructor. Does not allocate space.
  63    */
  64   VectorBase();
  65
  66   /**
  67    * @brief Destructor.
  68    *
  69    * Does not release the space. Derived class needs to call Release.
  70    * Not virtual as should not be called directly and we do not want
  71    * a vtable for this class as it would unnecessarily increase size.
  72    */
  73   ~VectorBase();
  74
  75 public: // API
  76
  77   /**
  78    * @brief This method is inlined as its needed frequently for End() iterator.
  79    *
  80    * @return The count of elements in this vector.
  81    */
  82   SizeType Count() const
  83   {
  84     SizeType items = 0;
  85     if( mData )
  86     {
  87       SizeType* metadata = reinterpret_cast< SizeType* >( mData );
  88       items = *(metadata - 1);
  89     }
  90     return items;
  91   }
  92
  93
  94   /**
  95    * @return The count of elements in this vector.
  96    */
  97   SizeType Size() const
  98   {
  99     return Count();
 100   }
 101
 102   /**
 103    * @return The capacity of this vector.
 104    */
 105   SizeType Capacity() const;
 106
 107   /**
 108    * @brief Release the data.
 109    *
 110    * Does not call destructors on objects held.
 111    */
 112   void Release();
 113
 114 protected: // for Derived classes
 115
 116   /**
 117    * @brief Helper to set the count.
 118    *
 119    * @param count Number of elements in the vector.
 120    */
 121   void SetCount( SizeType count );
 122
 123   /**
 124    * @brief Reserve space in the vector.
 125    *
 126    * @param count of elements to reserve.
 127    * @param elementSize of a single element.
 128    */
 129   void Reserve( SizeType count, SizeType elementSize );
 130
 131   /**
 132    * @brief Copy a vector.
 133    *
 134    * @param vector Vector to copy from.
 135    * @param elementSize of a single element.
 136    */
 137   void Copy( const VectorBase& vector, SizeType elementSize );
 138
 139   /**
 140    * @brief Swap the contents of two vectors.
 141    *
 142    * @param vector Vector to swap with.
 143    */
 144   void Swap( VectorBase& vector );
 145
 146   /**
 147    * @brief Erase an element.
 148    *
 149    * Does not change capacity.
 150    * @pre last element cannot be erased as there is nothing to move.
 151    * @param address to erase from.
 152    * @param elementSize to erase.
 153    */
 154   void Erase( char* address, SizeType elementSize );
 155
 156 private:
 157
 158   // not copiable as it does not know the size of elements
 159   VectorBase( const VectorBase& ); ///< Undefined
 160   VectorBase& operator=( const VectorBase& ); ///< Undefined
 161
 162 protected: // Data
 163
 164   void* mData; ///< Pointer to the data.
 165
 166 };
 167
 168 /**
 169  * @brief Vector algorithm variant for trivial types.
 170  *
 171  * Trivial types do not need destructor or copy constructor called.
 172  */
 173 template< bool IsTrivial >
 174 class VectorAlgorithms : public VectorBase
 175 {
 176 protected: // API for deriving classes
 177
 178   typedef VectorBase::SizeType SizeType;
 179
 180   /**
 181    * @brief Empty constructor.
 182    */
 183   VectorAlgorithms()
 184   { }
 185
 186   /**
 187    * @brief Empty destructor.
 188    */
 189   ~VectorAlgorithms()
 190   { }
 191
 192   /**
 193    * @brief Copy vector contents.
 194    *
 195    * @param rhs to copy from.
 196    * @param elementSize of the content.
 197    */
 198   void Copy( const VectorBase& rhs, SizeType elementSize )
 199   {
 200     if( rhs.Capacity() > 0u )
 201     {
 202       VectorBase::Copy( rhs, elementSize );
 203     }
 204     else
 205     {
 206       VectorBase::Release();
 207     }
 208   }
 209
 210   /**
 211    * @brief Reserve space in the vector.
 212    *
 213    * @param count of elements to reserve.
 214    * @param elementSize of a single element.
 215    */
 216   void Reserve( SizeType count, SizeType elementSize )
 217   {
 218     VectorBase::Reserve( count, elementSize );
 219   }
 220
 221   /**
 222    * @brief Resize the vector. Does not change capacity.
 223    *
 224    * @param count to resize to.
 225    * @param elementSize of a single element.
 226    */
 227   void Resize( SizeType count, SizeType elementSize )
 228   {
 229     // reserve will copy old elements as well
 230     Reserve( count, elementSize );
 231   }
 232
 233   /**
 234    * @brief Clear the contents.
 235    *
 236    * For simple types nothing to do.
 237    */
 238   void Clear()
 239   {
 240     if( mData )
 241     {
 242       VectorBase::SetCount( 0u );
 243     }
 244   }
 245
 246   /**
 247    * @brief Release the vector.
 248    */
 249   void Release()
 250   {
 251     VectorBase::Release();
 252   }
 253
 254   /**
 255    * @brief Erase an element. Does not change capacity.
 256    *
 257    * @param address to erase from.
 258    * @param elementSize to erase.
 259    */
 260   void Erase( char* address, SizeType elementSize )
 261   {
 262     VectorBase::Erase( address, elementSize );
 263   }
 264
 265 };
 266
 267 /**
 268  * @brief Vector algorithm variant for complex types.
 269  *
 270  * Not yet supported so will lead to compile error
 271  * as constructor and destructor are private.
 272  * TODO add support for this variant.
 273  */
 274 template<>
 275 class VectorAlgorithms< false > : public VectorBase
 276 {
 277 private:
 278   VectorAlgorithms()
 279   { }
 280   ~VectorAlgorithms()
 281   { }
 282 };
 283
 284 /**
 285  * @brief Vector class with minimum space allocation when its empty.
 286  *
 287  * @param type of the data that the vector holds.
 288  */
 289 template< class T, bool IsTrivialType = __has_trivial_destructor(T) && __has_trivial_copy(T) >
 290 class Vector : public VectorAlgorithms< IsTrivialType >
 291 {
 292 public: // API
 293
 294   /**
 295    * @brief Type definitions.
 296    */
 297   typedef VectorBase::SizeType SizeType;
 298   typedef T* Iterator;  ///< Most simple Iterator is a pointer
 299   typedef const T* ConstIterator;
 300   typedef T  ItemType;
 301
 302   enum
 303   {
 304     BaseType = IsTrivialType
 305   };
 306
 307   /**
 308    * @brief Default constructor. Does not allocate any space.
 309    */
 310   Vector()
 311   { }
 312
 313   /**
 314    * @brief Destructor. Releases the allocated space.
 315    */
 316   ~Vector()
 317   {
 318     Release();
 319   }
 320
 321   /**
 322    * @brief Copy constructor.
 323    *
 324    * @param vector Vector to copy from.
 325    */
 326   Vector( const Vector& vector )
 327   {
 328     // reuse assignment
 329     operator=( vector );
 330   }
 331
 332   /**
 333    * @brief Assignment operator.
 334    *
 335    * @param  vector Vector to assign from.
 336    * @return reference to self for chaining.
 337    */
 338   Vector& operator=( const Vector& vector )
 339   {
 340     if( this != &vector )
 341     {
 342       VectorAlgorithms<BaseType>::Copy( vector, sizeof( ItemType ) );
 343     }
 344     return *this;
 345   }
 346
 347   /**
 348    * @return Iterator to the beginning of the data.
 349    */
 350   Iterator Begin() const
 351   {
 352     ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
 353     return address;
 354   }
 355
 356   /**
 357    * @return Iterator to the end of the data (one past last element).
 358    */
 359   Iterator End() const
 360   {
 361     ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
 362     address += VectorBase::Count();
 363     return address;
 364   }
 365
 366   /**
 367    * @param  index of the element.
 368    * @return reference to the element for given index.
 369    */
 370   ItemType& operator[]( SizeType index )
 371   {
 372     // reuse the const version
 373     return const_cast< ItemType& >( const_cast< const Vector< ItemType >& >( *this )[ index ] );
 374   }
 375
 376   /**
 377    * @param  index of the element.
 378    * @return reference to the element for given index.
 379    */
 380   const ItemType& operator[]( SizeType index ) const
 381   {
 382     DALI_ASSERT_VECTOR( VectorBase::mData && "Vector is empty" );
 383     DALI_ASSERT_VECTOR( index < VectorBase::Count() && "Index out of bounds" );
 384     ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
 385     address += index;
 386     return *address;
 387   }
 388
 389   /**
 390    * @brief Push back an element to the vector.
 391    *
 392    * @param element to be added.
 393    */
 394   void PushBack( const ItemType& element )
 395   {
 396     const SizeType count = VectorBase::Count();
 397     const SizeType newCount = count + 1u;
 398     const SizeType capacity = VectorBase::Capacity();
 399     if( newCount > capacity )
 400     {
 401       // need more space
 402       Reserve( newCount << 1 ); // reserve double the current count
 403     }
 404     // set new count first as otherwise the debug assert will hit us
 405     VectorBase::SetCount( newCount );
 406     operator[]( count ) = element;
 407   }
 408
 409   /**
 410    * @brief Reserve space in the vector.
 411    *
 412    * Reserving less than current Capacity is a no-op.
 413    * @param count of elements to reserve.
 414    */
 415   void Reserve( SizeType count )
 416   {
 417     VectorAlgorithms<BaseType>::Reserve( count, sizeof( ItemType ) );
 418   }
 419
 420   /**
 421    * @brief Resize the vector. Does not change capacity.
 422    *
 423    * @param count to resize to.
 424    * @param item to insert to the new indeces.
 425    */
 426   void Resize( SizeType count, ItemType item = ItemType() )
 427   {
 428     const SizeType oldCount = VectorBase::Count();
 429     if( count <= oldCount )
 430     {
 431       // getting smaller so just set count
 432       VectorBase::SetCount( count );
 433     }
 434     else
 435     {
 436       // remember how many new items get added
 437       SizeType newItems = count - oldCount;
 438       Reserve( count );
 439       for( ; newItems > 0; --newItems )
 440       {
 441         PushBack( item );
 442       }
 443     }
 444   }
 445
 446   /**
 447    * @brief Erase an element.
 448    *
 449    * Does not change capacity. Other elements get moved.
 450    * @param iterator Iterator pointing to item to remove.
 451    * @return Iterator pointing to next element.
 452    */
 453   Iterator Erase( Iterator iterator )
 454   {
 455     DALI_ASSERT_VECTOR( VectorBase::mData && "Vector is empty" );
 456     DALI_ASSERT_VECTOR( (iterator < End()) && (iterator >= Begin() ) && "Iterator not inside vector" );
 457     if( iterator < ( End() - 1 ) )
 458     {
 459       VectorAlgorithms<BaseType>::Erase( reinterpret_cast< char* >( iterator ), sizeof( ItemType ) );
 460     }
 461     else
 462     {
 463       // just remove the element
 464       Remove( iterator );
 465     }
 466     return iterator;
 467   }
 468
 469   /**
 470    * @brief Removes an element.
 471    *
 472    * Does not maintain order.  Swaps the element with end and
 473    * decreases size by one.  This is much faster than Erase so use
 474    * this in case order does not matter. Does not change capacity.
 475    *
 476    * @param iterator Iterator pointing to item to remove.
 477    */
 478   void Remove( Iterator iterator )
 479   {
 480     DALI_ASSERT_VECTOR( VectorBase::mData && "Vector is empty" );
 481     Iterator end = End();
 482     DALI_ASSERT_VECTOR( (iterator < end) && (iterator >= Begin() ) && "Iterator not inside vector" );
 483     Iterator last = end - 1;
 484     if( last != iterator )
 485     {
 486       std::swap( *iterator, *last );
 487     }
 488     VectorBase::SetCount( VectorBase::Count() - 1 );
 489   }
 490
 491   /**
 492    * @brief Swap the contents of two vectors.
 493    *
 494    * @param vector Vector to swap with.
 495    */
 496   void Swap( Vector& vector )
 497   {
 498     VectorBase::Swap( vector );
 499   }
 500
 501   /**
 502    * @brief Clear the contents of the vector. Keeps its capacity.
 503    */
 504   void Clear()
 505   {
 506     VectorAlgorithms<BaseType>::Clear();
 507   }
 508
 509   /**
 510    * @brief Release the memory that the vector holds.
 511    */
 512   void Release()
 513   {
 514     VectorAlgorithms<BaseType>::Release();
 515   }
 516
 517 };
 518
 519 } // namespace Dali
 520
 521 #endif /* __DALI_VECTOR_H__ */