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

   1 #ifndef __DALI_VECTOR_H__
   2 #define __DALI_VECTOR_H__
   3
   4 /*
   5  * Copyright (c) 2015 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 // EXTERNAL INCLUDES
  22 #include <cstddef>
  23 #include <algorithm>
  24
  25 // INTERNAL INCLUDES
  26 #include <dali/public-api/common/dali-common.h>
  27 #include <dali/public-api/common/type-traits.h>
  28 #include <dali/public-api/math/math-utils.h>
  29
  30 /**
  31  * @brief For DALi internal use asserts are enabled in debug builds.
  32  *
  33  * For Application use asserts can be enabled manually.
  34  * @since_tizen 2.4
  35  */
  36 #if defined( DEBUG_ENABLED )
  37 #define ENABLE_VECTOR_ASSERTS
  38 #endif
  39
  40 #if defined( ENABLE_VECTOR_ASSERTS )
  41 #define DALI_ASSERT_VECTOR(cond) DALI_ASSERT_ALWAYS(cond)
  42 #else
  43 #define DALI_ASSERT_VECTOR(cond)
  44 #endif
  45
  46 namespace Dali
  47 {
  48 /**
  49  * @addtogroup dali_core_common
  50  * @{
  51  */
  52
  53 /**
  54  * @brief Base class to handle the memory of simple vector.
  55  *
  56  * Memory layout is such that it has two std::size_t to hold the count
  57  * and capacity of the vector. VectorBase::mData is adjusted so that it points to the
  58  * beginning of the first real item so that iterating the items is quick.
  59  * @since_tizen 2.4
  60  */
  61 class DALI_IMPORT_API VectorBase
  62 {
  63 public: // Typedefs
  64
  65   typedef std::size_t SizeType; ///< Size type @since_tizen 2.4
  66
  67 protected: // Construction
  68
  69   /**
  70    * @brief Default constructor. Does not allocate space.
  71    * @since_tizen 2.4
  72    */
  73   VectorBase();
  74
  75   /**
  76    * @brief Destructor.
  77    *
  78    * Does not release the space. Derived class needs to call Release.
  79    * Not virtual as should not be called directly and we do not want
  80    * a vtable for this class as it would unnecessarily increase size.
  81    * @since_tizen 2.4
  82    */
  83   ~VectorBase();
  84
  85 public: // API
  86
  87   /**
  88    * @brief This method is inlined as its needed frequently for Vector::End() iterator.
  89    *
  90    * @since_tizen 2.4
  91    * @return The count of elements in this vector.
  92    */
  93   SizeType Count() const
  94   {
  95     SizeType items = 0u;
  96     if( mData )
  97     {
  98       SizeType* metadata = reinterpret_cast< SizeType* >( mData );
  99       items = *(metadata - 1u);
 100     }
 101     return items;
 102   }
 103
 104   /**
 105    * @brief Gets the count of elements in this vector.
 106    * @since_tizen 2.4
 107    * @return The count of elements in this vector.
 108    */
 109   SizeType Size() const
 110   {
 111     return Count();
 112   }
 113
 114   /**
 115    * @brief Gets the capacity of this vector.
 116    * @since_tizen 2.4
 117    * @return The capacity of this vector.
 118    */
 119   SizeType Capacity() const;
 120
 121   /**
 122    * @brief Release the data.
 123    *
 124    * Does not call destructors on objects held.
 125    * @since_tizen 2.4
 126    */
 127   void Release();
 128
 129 protected: // for Derived classes
 130
 131   /**
 132    * @brief Helper to set the count.
 133    *
 134    * @since_tizen 2.4
 135    * @param[in] count Number of elements in the vector.
 136    */
 137   void SetCount( SizeType count );
 138
 139   /**
 140    * @brief Reserve space in the vector.
 141    *
 142    * @since_tizen 2.4
 143    * @param[in] count Count of elements to reserve.
 144    * @param[in] elementSize Size of a single element.
 145    */
 146   void Reserve( SizeType count, SizeType elementSize );
 147
 148   /**
 149    * @brief Copy a vector.
 150    *
 151    * @since_tizen 2.4
 152    * @param[in] vector Vector to copy from.
 153    * @param[in] elementSize Size of a single element.
 154    */
 155   void Copy( const VectorBase& vector, SizeType elementSize );
 156
 157   /**
 158    * @brief Swap the contents of two vectors.
 159    *
 160    * @since_tizen 2.4
 161    * @param[in] vector Vector to swap with.
 162    */
 163   void Swap( VectorBase& vector );
 164
 165   /**
 166    * @brief Erase an element.
 167    *
 168    * Does not change capacity.
 169    * @since_tizen 2.4
 170    * @param[in] address Adress to erase from.
 171    * @param[in] elementSize Size to erase.
 172    * @pre Last element cannot be erased as there is nothing to move.
 173    */
 174   void Erase( char* address, SizeType elementSize );
 175
 176   /**
 177    * @brief Erase a range of elements.
 178    *
 179    * Does not change capacity.
 180    * @since_tizen 2.4
 181    * @param[in] first Address to the first element to be erased.
 182    * @param[in] last Address to the last element to be erased.
 183    * @param[in] elementSize Size of one of the elements to be erased.
 184    * @return Address pointing to the next element of the last one.
 185    */
 186   char* Erase( char* first, char* last, SizeType elementSize );
 187
 188   /**
 189    * @brief Copies a number of bytes from \e source to \e destination.
 190    *
 191    * \e source and \e destination must not overlap.
 192    *
 193    * @since_tizen 2.4
 194    * @param[in] destination Pointer to the destination address.
 195    * @param[in] source Pointer to the source address.
 196    * @param[in] numberOfBytes The number of bytes to be copied.
 197    */
 198   void CopyMemory( char* destination, const char* source, size_t numberOfBytes );
 199
 200 private:
 201
 202   // not copiable as it does not know the size of elements
 203   VectorBase( const VectorBase& ); ///< Undefined @since_tizen 2.4
 204   VectorBase& operator=( const VectorBase& ); ///< Undefined @since_tizen 2.4
 205
 206 protected: // Data
 207
 208   void* mData; ///< Pointer to the data.
 209
 210 };
 211
 212 /**
 213  * @brief Vector algorithm variant for trivial types.
 214  *
 215  * Trivial types do not need destructor or copy constructor called.
 216  * @since_tizen 2.4
 217  */
 218 template< bool IsTrivial >
 219 class VectorAlgorithms : public VectorBase
 220 {
 221 protected: // API for deriving classes
 222
 223   typedef VectorBase::SizeType SizeType; ///< Size type @since_tizen 2.4
 224
 225   /**
 226    * @brief Empty constructor.
 227    * @since_tizen 2.4
 228    */
 229   VectorAlgorithms()
 230   { }
 231
 232   /**
 233    * @brief Empty destructor.
 234    * @since_tizen 2.4
 235    */
 236   ~VectorAlgorithms()
 237   { }
 238
 239   /**
 240    * @brief Copy vector contents.
 241    *
 242    * @since_tizen 2.4
 243    * @param[in] rhs VectorBase object to copy from.
 244    * @param[in] elementSize Size of the content.
 245    */
 246   void Copy( const VectorBase& rhs, SizeType elementSize )
 247   {
 248     if( rhs.Capacity() > 0u )
 249     {
 250       VectorBase::Copy( rhs, elementSize );
 251     }
 252     else
 253     {
 254       VectorBase::Release();
 255     }
 256   }
 257
 258   /**
 259    * @brief Reserve space in the vector.
 260    *
 261    * @since_tizen 2.4
 262    * @param[in] count Count of elements to reserve.
 263    * @param[in] elementSize Size of a single element.
 264    */
 265   void Reserve( SizeType count, SizeType elementSize )
 266   {
 267     VectorBase::Reserve( count, elementSize );
 268   }
 269
 270   /**
 271    * @brief Resize the vector. Does not change capacity.
 272    *
 273    * @since_tizen 2.4
 274    * @param[in] count Count to resize to.
 275    * @param[in] elementSize Size of a single element.
 276    */
 277   void Resize( SizeType count, SizeType elementSize )
 278   {
 279     // reserve will copy old elements as well
 280     Reserve( count, elementSize );
 281   }
 282
 283   /**
 284    * @brief Clear the contents.
 285    *
 286    * For simple types nothing to do.
 287    * @since_tizen 2.4
 288    */
 289   void Clear()
 290   {
 291     if( mData )
 292     {
 293       VectorBase::SetCount( 0u );
 294     }
 295   }
 296
 297   /**
 298    * @brief Release the vector.
 299    * @since_tizen 2.4
 300    */
 301   void Release()
 302   {
 303     VectorBase::Release();
 304   }
 305
 306   /**
 307    * @brief Erase an element. Does not change capacity.
 308    *
 309    * @since_tizen 2.4
 310    * @param[in] address Address to erase from.
 311    * @param[in] elementSize Size to erase.
 312    */
 313   void Erase( char* address, SizeType elementSize )
 314   {
 315     VectorBase::Erase( address, elementSize );
 316   }
 317
 318   /**
 319    * @brief Erase a range of elements. Does not change capacity.
 320    *
 321    * @since_tizen 2.4
 322    * @param[in] first Address to the first element to be erased.
 323    * @param[in] last Address to the last element to be erased.
 324    * @param[in] elementSize Size of one of the elements to be erased.
 325    * @return Address pointing to the next element of the last one.
 326    */
 327   char* Erase( char* first, char* last, SizeType elementSize )
 328   {
 329     return VectorBase::Erase( first, last, elementSize );
 330   }
 331
 332   /**
 333    * @brief Inserts the given elements into the vector.
 334    *
 335    * @since_tizen 2.4
 336    * @param[in] at Address where to insert the elements into the vector.
 337    * @param[in] from Address to the first element to be inserted.
 338    * @param[in] to Address to the last element to be inserted.
 339    * @param[in] elementSize Size of one of the elements to be inserted.
 340    */
 341   void Insert( char* at, char* from, char* to, SizeType elementSize )
 342   {
 343     const SizeType size = to - from;
 344     const SizeType count = Count();
 345     const SizeType newCount = count + size / elementSize;
 346
 347     if( newCount > Capacity() )
 348     {
 349       // Calculate the at offset as the pointer is invalid after the Reserve() call.
 350       std::size_t offset = at - reinterpret_cast<char*>( mData );
 351
 352       // need more space
 353       Reserve( NextPowerOfTwo( newCount ), elementSize ); // reserve enough space to store at least the next power of two elements of the new required size.
 354
 355       // Set the new at pointer.
 356       at = reinterpret_cast<char*>( mData ) + offset;
 357     }
 358     // set new count first as otherwise the debug assert will hit us
 359     SetCount( newCount );
 360
 361     // Move current items to a new position inside the vector.
 362     CopyMemory( at + size,
 363                 at,
 364                 ( reinterpret_cast<char*>( mData ) + count * elementSize ) - at );
 365
 366     // Copy the given items.
 367     CopyMemory( at, from, size );
 368   }
 369 };
 370
 371 /**
 372  * @brief Vector algorithm variant for complex types.
 373  *
 374  * Not yet supported so will lead to compile error
 375  * as constructor and destructor are private.
 376  * TODO add support for this variant.
 377  * @since_tizen 2.4
 378  */
 379 template<>
 380 class VectorAlgorithms< false > : public VectorBase
 381 {
 382 private:
 383   VectorAlgorithms()
 384   { }
 385   ~VectorAlgorithms()
 386   { }
 387 };
 388
 389 /**
 390  * @brief Vector class with minimum space allocation when its empty.
 391  *
 392  * @since_tizen 2.4
 393  * @param[in] type of the data that the vector holds.
 394  */
 395 template< class T, bool IsTrivialType = TypeTraits<T>::IS_TRIVIAL_TYPE == true >
 396 class Vector : public VectorAlgorithms< IsTrivialType >
 397 {
 398 public: // API
 399
 400   /**
 401    * @brief Type definitions.
 402    * @since_tizen 2.4
 403    */
 404   typedef VectorBase::SizeType SizeType; ///< Size type @since_tizen 2.4
 405   typedef T* Iterator;  ///< Most simple Iterator is a pointer @since_tizen 2.4
 406   typedef const T* ConstIterator; ///< Const iterator @since_tizen 2.4
 407   typedef T  ItemType; ///< Item type @since_tizen 2.4
 408
 409   enum
 410   {
 411     BaseType = IsTrivialType
 412   };
 413
 414   /**
 415    * @brief Default constructor. Does not allocate any space.
 416    * @since_tizen 2.4
 417    */
 418   Vector()
 419   { }
 420
 421   /**
 422    * @brief Destructor. Releases the allocated space.
 423    * @since_tizen 2.4
 424    */
 425   ~Vector()
 426   {
 427     Release();
 428   }
 429
 430   /**
 431    * @brief Copy constructor.
 432    *
 433    * @since_tizen 2.4
 434    * @param[in] vector Vector to copy from.
 435    */
 436   Vector( const Vector& vector )
 437   {
 438     // reuse assignment
 439     operator=( vector );
 440   }
 441
 442   /**
 443    * @brief Assignment operator.
 444    *
 445    * @since_tizen 2.4
 446    * @param[in]  vector Vector to assign from.
 447    * @return Reference to self for chaining.
 448    */
 449   Vector& operator=( const Vector& vector )
 450   {
 451     if( this != &vector )
 452     {
 453       VectorAlgorithms<BaseType>::Copy( vector, sizeof( ItemType ) );
 454     }
 455     return *this;
 456   }
 457
 458   /**
 459    * @brief Iterator to the beginning of the data.
 460    * @since_tizen 2.4
 461    * @return Iterator to the beginning of the data.
 462    */
 463   Iterator Begin() const
 464   {
 465     ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
 466     return address;
 467   }
 468
 469   /**
 470    * @brief Iterator to the end of the data (one past last element).
 471    * @since_tizen 2.4
 472    * @return Iterator to the end of the data (one past last element).
 473    */
 474   Iterator End() const
 475   {
 476     ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
 477     address += VectorBase::Count();
 478     return address;
 479   }
 480
 481   /**
 482    * @brief Subscript operator.
 483    * @since_tizen 2.4
 484    * @param[in]  index Index of the element.
 485    * @return Reference to the element for given index.
 486    * @pre Index must be in the vector's range.
 487    */
 488   ItemType& operator[]( SizeType index )
 489   {
 490     // reuse the const version
 491     return const_cast< ItemType& >( const_cast< const Vector< ItemType >& >( *this )[ index ] );
 492   }
 493
 494   /**
 495    * @brief Subscript operator.
 496    * @since_tizen 2.4
 497    * @param[in]  index of the element.
 498    * @return reference to the element for given index.
 499    * @pre index must be in the vector's range.
 500    */
 501   const ItemType& operator[]( SizeType index ) const
 502   {
 503     DALI_ASSERT_VECTOR( VectorBase::mData && "Vector is empty" );
 504     DALI_ASSERT_VECTOR( index < VectorBase::Count() && "Index out of bounds" );
 505     ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
 506     address += index;
 507     return *address;
 508   }
 509
 510   /**
 511    * @brief Push back an element to the vector.
 512    *
 513    * The underlying storage may be reallocated to provide space.
 514    * If this occurs, all pre-existing pointers into the vector will
 515    * become invalid.
 516    *
 517    * @since_tizen 2.4
 518    * @param[in] element Element to be added.
 519    */
 520   void PushBack( const ItemType& element )
 521   {
 522     const SizeType count = VectorBase::Count();
 523     const SizeType newCount = count + 1u;
 524     const SizeType capacity = VectorBase::Capacity();
 525     if( newCount > capacity )
 526     {
 527       // need more space
 528       Reserve( newCount << 1u ); // reserve double the current count
 529     }
 530     // set new count first as otherwise the debug assert will hit us
 531     VectorBase::SetCount( newCount );
 532     operator[]( count ) = element;
 533   }
 534
 535   /**
 536    *@brief Insert an element to the vector.
 537    *
 538    * Elements after \e at are moved one position to the right.
 539    *
 540    * The underlying storage may be reallocated to provide space.
 541    * If this occurs, all pre-existing pointers into the vector will
 542    * become invalid.
 543    *
 544    * @pre Iterator at must be in the vector's range ( Vector::Begin(), Vector::End() ).
 545    *
 546    * @param[in] at Iterator where to insert the elements into the vector.
 547    * @param[in] element An element to be added.
 548    *@since_tizen 2.4
 549    */
 550   void Insert( Iterator at, const ItemType& element )
 551   {
 552     DALI_ASSERT_VECTOR( ( at <= End() ) && ( at >= Begin() ) && "Iterator not inside vector" );
 553     const SizeType size = sizeof( ItemType );
 554     char* address = const_cast<char*>( reinterpret_cast<const char*>( &element ) );
 555     VectorAlgorithms<BaseType>::Insert( reinterpret_cast< char* >( at ),
 556                                         address,
 557                                         address + size,
 558                                         size );
 559   }
 560
 561   /**
 562    * @brief Inserts the given elements into the vector.
 563    *
 564    * Elements after \e at are moved the number of given elements positions to the right.
 565    *
 566    * The underlying storage may be reallocated to provide space.
 567    * If this occurs, all pre-existing pointers into the vector will
 568    * become invalid.
 569    *
 570    * @since_tizen 2.4
 571    * @param[in] at Iterator where to insert the elements into the vector.
 572    * @param[in] from Iterator to the first element to be inserted.
 573    * @param[in] to Iterator to the last element to be inserted.
 574    * @pre Iterator \e at must be in the vector's range ( Vector::Begin(), Vector::End() ).
 575    * @pre Iterators \e from and \e to must be valid iterators.
 576    * @pre Iterator \e from must not be grater than Iterator \e to.
 577    *
 578    */
 579   void Insert( Iterator at, Iterator from, Iterator to )
 580   {
 581     DALI_ASSERT_VECTOR( ( at <= End() ) && ( at >= Begin() ) && "Iterator not inside vector" );
 582     DALI_ASSERT_VECTOR( ( from <= to ) && "from address can't be greater than to" );
 583
 584     if( from == to )
 585     {
 586       // nothing to copy.
 587       return;
 588     }
 589
 590     VectorAlgorithms<BaseType>::Insert( reinterpret_cast< char* >( at ),
 591                                         reinterpret_cast< char* >( from ),
 592                                         reinterpret_cast< char* >( to ),
 593                                         sizeof( ItemType ) );
 594   }
 595
 596   /**
 597    * @brief Reserve space in the vector.
 598    *
 599    * Reserving less than current Capacity is a no-op.
 600    * @since_tizen 2.4
 601    * @param[in] count Count of elements to reserve.
 602    */
 603   void Reserve( SizeType count )
 604   {
 605     VectorAlgorithms<BaseType>::Reserve( count, sizeof( ItemType ) );
 606   }
 607
 608   /**
 609    * @brief Resize the vector. Does not change capacity.
 610    *
 611    * @since_tizen 2.4
 612    * @param[in] count Count to resize to.
 613    * @param[in] item An item to insert to the new indices.
 614    */
 615   void Resize( SizeType count, ItemType item = ItemType() )
 616   {
 617     const SizeType oldCount = VectorBase::Count();
 618     if( count <= oldCount )
 619     {
 620       // getting smaller so just set count
 621       VectorBase::SetCount( count );
 622     }
 623     else
 624     {
 625       // remember how many new items get added
 626       SizeType newItems = count - oldCount;
 627       Reserve( count );
 628       for( ; newItems > 0u; --newItems )
 629       {
 630         PushBack( item );
 631       }
 632     }
 633   }
 634
 635   /**
 636    * @brief Erase an element.
 637    *
 638    * Does not change capacity. Other elements get moved.
 639    *
 640    * @since_tizen 2.4
 641    * @param[in] iterator Iterator pointing to item to remove.
 642    * @return Iterator pointing to next element.
 643    * @pre Iterator \e iterator must be within the vector's range ( Vector::Begin(), Vector::End() - 1 ).
 644    *
 645    */
 646   Iterator Erase( Iterator iterator )
 647   {
 648     DALI_ASSERT_VECTOR( (iterator < End()) && (iterator >= Begin()) && "Iterator not inside vector" );
 649     if( iterator < ( End() - 1u ) )
 650     {
 651       VectorAlgorithms<BaseType>::Erase( reinterpret_cast< char* >( iterator ), sizeof( ItemType ) );
 652     }
 653     else
 654     {
 655       // just remove the element
 656       Remove( iterator );
 657     }
 658     return iterator;
 659   }
 660
 661   /**
 662    * @brief Erase a range of elements.
 663    *
 664    * Does not change capacity. Other elements get moved.
 665    *
 666    * @since_tizen 2.4
 667    * @param[in] first Iterator to the first element to be erased.
 668    * @param[in] last Iterator to the last element to be erased.
 669    *
 670    * @return Iterator pointing to the next element of the last one.
 671    * @pre Iterator \e first must be in the vector's range ( Vector::Begin(), Vector::End() ).
 672    * @pre Iterator \e last must be in the vector's range ( Vector::Begin(), Vector::End() ).
 673    * @pre Iterator \e first must not be grater than Iterator \e last.
 674    *
 675    */
 676   Iterator Erase( Iterator first, Iterator last )
 677   {
 678     DALI_ASSERT_VECTOR( ( first <= End() ) && ( first >= Begin() ) && "Iterator not inside vector" );
 679     DALI_ASSERT_VECTOR( ( last <= End() ) && ( last >= Begin() ) && "Iterator not inside vector" );
 680     DALI_ASSERT_VECTOR( ( first <= last ) && "first iterator greater than last" );
 681
 682     Iterator nextElement;
 683
 684     if( last == End() )
 685     {
 686       // Erase up to the end.
 687       VectorBase::SetCount( VectorBase::Count() - ( last - first ) );
 688       nextElement = End();
 689     }
 690     else
 691     {
 692       nextElement = reinterpret_cast<Iterator>( VectorAlgorithms<BaseType>::Erase( reinterpret_cast< char* >( first ),
 693                                                                                    reinterpret_cast< char* >( last ),
 694                                                                                    sizeof( ItemType ) ) );
 695     }
 696
 697     return nextElement;
 698   }
 699
 700   /**
 701    * @brief Removes an element.
 702    *
 703    * Does not maintain order.  Swaps the element with end and
 704    * decreases size by one.  This is much faster than Erase so use
 705    * this in case order does not matter. Does not change capacity.
 706    *
 707    * @since_tizen 2.4
 708    * @param[in] iterator Iterator pointing to item to remove.
 709    * @pre Iterator \e iterator must be in the vector's range ( Vector::Begin(), Vector::End() - 1 ).
 710    *
 711    */
 712   void Remove( Iterator iterator )
 713   {
 714     DALI_ASSERT_VECTOR( (iterator < End()) && (iterator >= Begin()) && "Iterator not inside vector" );
 715
 716     Iterator last = End() - 1u;
 717     if( last > iterator )
 718     {
 719       std::swap( *iterator, *last );
 720     }
 721     VectorBase::SetCount( VectorBase::Count() - 1u );
 722   }
 723
 724   /**
 725    * @brief Swap the contents of two vectors.
 726    *
 727    * @since_tizen 2.4
 728    * @param[in] vector Vector to swap with.
 729    */
 730   void Swap( Vector& vector )
 731   {
 732     VectorBase::Swap( vector );
 733   }
 734
 735   /**
 736    * @brief Clear the contents of the vector. Keeps its capacity.
 737    * @since_tizen 2.4
 738    */
 739   void Clear()
 740   {
 741     VectorAlgorithms<BaseType>::Clear();
 742   }
 743
 744   /**
 745    * @brief Release the memory that the vector holds.
 746    * @since_tizen 2.4
 747    */
 748   void Release()
 749   {
 750     VectorAlgorithms<BaseType>::Release();
 751   }
 752 };
 753
 754 /**
 755  * @}
 756  */
 757 } // namespace Dali
 758
 759 #endif /* __DALI_VECTOR_H__ */