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