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