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