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