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