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