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