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