1 #ifndef __DALI_VECTOR_H__
2 #define __DALI_VECTOR_H__
5 * Copyright (c) 2018 Samsung Electronics Co., Ltd.
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
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
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>
31 * @brief For DALi internal use, asserts are enabled in debug builds.
33 * For Application use, asserts can be enabled manually.
36 #if defined( DEBUG_ENABLED )
37 #define ENABLE_VECTOR_ASSERTS
40 #if defined( ENABLE_VECTOR_ASSERTS )
41 #define DALI_ASSERT_VECTOR(cond) DALI_ASSERT_ALWAYS(cond)
43 #define DALI_ASSERT_VECTOR(cond)
49 * @addtogroup dali_core_common
54 * @brief Base class to handle the memory of simple vector.
56 * Memory layout is such that it has two std::size_t to hold the count
57 * and capacity of the vector. VectorBase::mData is adjusted so that it points to the
58 * beginning of the first real item so that iterating the items is quick.
61 class DALI_CORE_API VectorBase
65 typedef std::size_t SizeType;
67 protected: // Construction
70 * @brief Default constructor. Does not allocate space.
78 * Does not release the space. Derived class needs to call Release.
79 * Not virtual as this should not be called directly and we do not want
80 * a vtable for this class as it would unnecessarily increase size.
88 * @brief This method is inlined as it's needed frequently for Vector::End() iterator.
91 * @return The count of elements in this vector
93 SizeType Count() const
98 SizeType* metadata = reinterpret_cast< SizeType* >( mData );
99 items = *(metadata - 1u);
105 * @brief Gets the count of elements in this vector.
107 * @return The count of elements in this vector
109 SizeType Size() const
115 * @brief @ return if the vector is empty.
117 * @return True if the count of elements is empty
121 return Count() == 0u;
125 * @brief Gets the capacity of this vector.
127 * @return The capacity of this vector
129 SizeType Capacity() const;
132 * @brief Releases the data.
134 * Does not call destructors on objects held.
139 protected: // for Derived classes
142 * @brief Helper to set the count.
145 * @param[in] count Number of elements in the vector
147 void SetCount( SizeType count );
150 * @brief Reserves space in the vector.
153 * @param[in] count Count of elements to reserve
154 * @param[in] elementSize Size of a single element
156 void Reserve( SizeType count, SizeType elementSize );
159 * @brief Copy a vector.
162 * @param[in] vector Vector to copy from
163 * @param[in] elementSize Size of a single element
165 void Copy( const VectorBase& vector, SizeType elementSize );
168 * @brief Swaps the contents of two vectors.
171 * @param[in] vector Vector to swap with
173 void Swap( VectorBase& vector );
176 * @brief Erases an element.
178 * Does not change capacity.
180 * @param[in] address Address to erase from
181 * @param[in] elementSize Size to erase
182 * @pre Last element cannot be erased as there is nothing to move.
184 void Erase( char* address, SizeType elementSize );
187 * @brief Erases a range of elements.
189 * Does not change capacity.
191 * @param[in] first Address to the first element to be erased
192 * @param[in] last Address to the last element to be erased
193 * @param[in] elementSize Size of one of the elements to be erased
194 * @return Address pointing to the next element of the last one
196 char* Erase( char* first, char* last, SizeType elementSize );
199 * @brief Copies a number of bytes from \e source to \e destination.
201 * \e source and \e destination must not overlap.
204 * @param[in] destination Pointer to the destination address
205 * @param[in] source Pointer to the source address
206 * @param[in] numberOfBytes The number of bytes to be copied
208 void CopyMemory( char* destination, const char* source, size_t numberOfBytes );
212 // not copiable as it does not know the size of elements
213 VectorBase( const VectorBase& ); ///< Undefined @SINCE_1_0.0
214 VectorBase& operator=( const VectorBase& ); ///< Undefined @SINCE_1_0.0
218 void* mData; ///< Pointer to the data.
223 * @brief Vector algorithm variant for trivial types.
225 * Trivial types do not need destructor or copy constructor called.
228 template< bool IsTrivial >
229 class VectorAlgorithms : public VectorBase
231 protected: // API for deriving classes
233 typedef VectorBase::SizeType SizeType;
236 * @brief Empty constructor.
243 * @brief Empty destructor.
250 * @brief Copy vector contents.
253 * @param[in] rhs VectorBase object to copy from
254 * @param[in] elementSize Size of the content
256 void Copy( const VectorBase& rhs, SizeType elementSize )
258 if( rhs.Capacity() > 0u )
260 VectorBase::Copy( rhs, elementSize );
264 VectorBase::Release();
269 * @brief Reserves space in the vector.
272 * @param[in] count Count of elements to reserve
273 * @param[in] elementSize Size of a single element
275 void Reserve( SizeType count, SizeType elementSize )
277 VectorBase::Reserve( count, elementSize );
281 * @brief Resizes the vector. Does not change capacity.
284 * @param[in] count Count to resize to
285 * @param[in] elementSize Size of a single element
287 void Resize( SizeType count, SizeType elementSize )
289 // reserve will copy old elements as well
290 Reserve( count, elementSize );
294 * @brief Clears the contents.
296 * For simple types, nothing to do.
303 VectorBase::SetCount( 0u );
308 * @brief Releases the vector.
313 VectorBase::Release();
317 * @brief Erases an element. Does not change capacity.
320 * @param[in] address Address to erase from
321 * @param[in] elementSize Size to erase
323 void Erase( char* address, SizeType elementSize )
325 VectorBase::Erase( address, elementSize );
329 * @brief Erases a range of elements. Does not change capacity.
332 * @param[in] first Address to the first element to be erased
333 * @param[in] last Address to the last element to be erased
334 * @param[in] elementSize Size of one of the elements to be erased
335 * @return Address pointing to the next element of the last one
337 char* Erase( char* first, char* last, SizeType elementSize )
339 return VectorBase::Erase( first, last, elementSize );
343 * @brief Inserts the given elements into the vector.
346 * @param[in] at Address where to insert the elements into the vector
347 * @param[in] from Address to the first element to be inserted
348 * @param[in] to Address to the last element to be inserted
349 * @param[in] elementSize Size of one of the elements to be inserted
351 void Insert( char* at, char* from, char* to, SizeType elementSize )
353 const SizeType size = to - from;
354 const SizeType count = Count();
355 const SizeType newCount = count + size / elementSize;
357 if( newCount > Capacity() )
359 // Calculate the at offset as the pointer is invalid after the Reserve() call.
360 std::size_t offset = at - reinterpret_cast<char*>( mData );
363 Reserve( NextPowerOfTwo( newCount ), elementSize ); // reserve enough space to store at least the next power of two elements of the new required size.
365 // Set the new at pointer.
366 at = reinterpret_cast<char*>( mData ) + offset;
368 // set new count first as otherwise the debug assert will hit us
369 SetCount( newCount );
371 // Move current items to a new position inside the vector.
372 CopyMemory( at + size,
374 ( reinterpret_cast<char*>( mData ) + count * elementSize ) - at );
376 // Copy the given items.
377 CopyMemory( at, from, size );
382 * @brief Vector algorithm variant for complex types.
384 * Not yet supported so will lead to compile error
385 * as constructor and destructor are private.
386 * TODO add support for this variant.
390 class VectorAlgorithms< false > : public VectorBase
400 * @brief Vector class with minimum space allocation when it's empty.
403 * @param type The type of the data that the vector holds
405 template< class T, bool IsTrivialType = TypeTraits<T>::IS_TRIVIAL_TYPE == true >
406 class Vector : public VectorAlgorithms< IsTrivialType >
411 * @brief Type definitions.
414 typedef VectorBase::SizeType SizeType; ///< Size type @SINCE_1_0.0
415 typedef T* Iterator; ///< Most simple Iterator is a pointer @SINCE_1_0.0
416 typedef const T* ConstIterator; ///< Const iterator @SINCE_1_0.0
417 typedef T ItemType; ///< Item type @SINCE_1_0.0
420 * @brief Enumeration for BaseType.
425 BaseType = IsTrivialType ///< @SINCE_1_0.0
429 * @brief Default constructor. Does not allocate any space.
436 * @brief Destructor. Releases the allocated space.
445 * @brief Copy constructor.
448 * @param[in] vector Vector to copy from
450 Vector( const Vector& vector )
457 * @brief Assignment operator.
460 * @param[in] vector Vector to assign from
461 * @return Reference to self for chaining
463 Vector& operator=( const Vector& vector )
465 if( this != &vector )
467 VectorAlgorithms<BaseType>::Copy( vector, sizeof( ItemType ) );
473 * @brief Iterator to the beginning of the data.
475 * @return Iterator to the beginning of the data
477 Iterator Begin() const
479 ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
484 * @brief Iterator to the end of the data (one past last element).
486 * @return Iterator to the end of the data (one past last element)
490 ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
491 address += VectorBase::Count();
496 * Support for C++11 Range-based for loop: for( item : container ).
498 * @return The start iterator
500 Iterator begin() const
506 * Support for C++11 Range-based for loop: for( item : container ).
508 * @return The end iterator
516 * @brief Subscript operator.
518 * @param[in] index Index of the element
519 * @return Reference to the element for given index
520 * @pre Index must be in the vector's range.
522 ItemType& operator[]( SizeType index )
524 // reuse the const version
525 return const_cast< ItemType& >( const_cast< const Vector< ItemType >& >( *this )[ index ] );
529 * @brief Subscript operator.
531 * @param[in] index Index of the element
532 * @return Reference to the element for given index
533 * @pre Index must be in the vector's range.
535 const ItemType& operator[]( SizeType index ) const
537 DALI_ASSERT_VECTOR( VectorBase::mData && "Vector is empty" );
538 DALI_ASSERT_VECTOR( index < VectorBase::Count() && "Index out of bounds" );
539 ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
545 * @brief Pushes back an element to the vector.
547 * The underlying storage may be reallocated to provide space.
548 * If this occurs, all pre-existing pointers into the vector will
552 * @param[in] element Element to be added
554 void PushBack( const ItemType& element )
556 const SizeType count = VectorBase::Count();
557 const SizeType newCount = count + 1u;
558 const SizeType capacity = VectorBase::Capacity();
559 if( newCount > capacity )
562 Reserve( newCount << 1u ); // reserve double the current count
564 // set new count first as otherwise the debug assert will hit us
565 VectorBase::SetCount( newCount );
566 operator[]( count ) = element;
570 * @brief Inserts an element to the vector.
572 * Elements after \e at are moved one position to the right.
574 * The underlying storage may be reallocated to provide space.
575 * If this occurs, all pre-existing pointers into the vector will
579 * @param[in] at Iterator where to insert the elements into the vector
580 * @param[in] element An element to be added
581 * @pre Iterator at must be in the vector's range ( Vector::Begin(), Vector::End() ).
583 void Insert( Iterator at, const ItemType& element )
585 DALI_ASSERT_VECTOR( ( at <= End() ) && ( at >= Begin() ) && "Iterator not inside vector" );
586 const SizeType size = sizeof( ItemType );
587 char* address = const_cast<char*>( reinterpret_cast<const char*>( &element ) );
588 VectorAlgorithms<BaseType>::Insert( reinterpret_cast< char* >( at ),
595 * @brief Inserts the given elements into the vector.
597 * Elements after \e at are moved the number of given elements positions to the right.
599 * The underlying storage may be reallocated to provide space.
600 * If this occurs, all pre-existing pointers into the vector will
604 * @param[in] at Iterator where to insert the elements into the vector
605 * @param[in] from Iterator to the first element to be inserted
606 * @param[in] to Iterator to the last element to be inserted
607 * @pre Iterator \e at must be in the vector's range ( Vector::Begin(), Vector::End() ).
608 * @pre Iterators \e from and \e to must be valid iterators.
609 * @pre Iterator \e from must not be grater than Iterator \e to.
612 void Insert( Iterator at, Iterator from, Iterator to )
614 DALI_ASSERT_VECTOR( ( at <= End() ) && ( at >= Begin() ) && "Iterator not inside vector" );
615 DALI_ASSERT_VECTOR( ( from <= to ) && "from address can't be greater than to" );
623 VectorAlgorithms<BaseType>::Insert( reinterpret_cast< char* >( at ),
624 reinterpret_cast< char* >( from ),
625 reinterpret_cast< char* >( to ),
626 sizeof( ItemType ) );
630 * @brief Reserves space in the vector.
632 * Reserving less than current Capacity is a no-op.
634 * @param[in] count Count of elements to reserve
636 void Reserve( SizeType count )
638 VectorAlgorithms<BaseType>::Reserve( count, sizeof( ItemType ) );
642 * @brief Resizes the vector. Does not change capacity.
645 * @param[in] count Count to resize to
647 void Resize( SizeType count )
649 ItemType item = ItemType();
654 * @brief Resizes the vector. Does not change capacity.
657 * @param[in] count Count to resize to
658 * @param[in] item An item to insert to the new indices
660 void Resize( SizeType count, const ItemType& item )
662 const SizeType oldCount = VectorBase::Count();
663 if( count <= oldCount )
665 // getting smaller so just set count
666 VectorBase::SetCount( count );
670 // remember how many new items get added
671 SizeType newItems = count - oldCount;
673 for( ; newItems > 0u; --newItems )
681 * @brief Erases an element.
683 * Does not change capacity. Other elements get moved.
686 * @param[in] iterator Iterator pointing to the item to remove
687 * @return Iterator pointing to next element
688 * @pre Iterator \e iterator must be within the vector's range ( Vector::Begin(), Vector::End() - 1 ).
691 Iterator Erase( Iterator iterator )
693 DALI_ASSERT_VECTOR( (iterator < End()) && (iterator >= Begin()) && "Iterator not inside vector" );
694 if( iterator < ( End() - 1u ) )
696 VectorAlgorithms<BaseType>::Erase( reinterpret_cast< char* >( iterator ), sizeof( ItemType ) );
700 // just remove the element
707 * @brief Erases a range of elements.
709 * Does not change capacity. Other elements get moved.
712 * @param[in] first Iterator to the first element to be erased
713 * @param[in] last Iterator to the last element to be erased
715 * @return Iterator pointing to the next element of the last one
716 * @pre Iterator \e first must be in the vector's range ( Vector::Begin(), Vector::End() ).
717 * @pre Iterator \e last must be in the vector's range ( Vector::Begin(), Vector::End() ).
718 * @pre Iterator \e first must not be grater than Iterator \e last.
721 Iterator Erase( Iterator first, Iterator last )
723 DALI_ASSERT_VECTOR( ( first <= End() ) && ( first >= Begin() ) && "Iterator not inside vector" );
724 DALI_ASSERT_VECTOR( ( last <= End() ) && ( last >= Begin() ) && "Iterator not inside vector" );
725 DALI_ASSERT_VECTOR( ( first <= last ) && "first iterator greater than last" );
727 Iterator nextElement;
731 // Erase up to the end.
732 VectorBase::SetCount( VectorBase::Count() - ( last - first ) );
737 nextElement = reinterpret_cast<Iterator>( VectorAlgorithms<BaseType>::Erase( reinterpret_cast< char* >( first ),
738 reinterpret_cast< char* >( last ),
739 sizeof( ItemType ) ) );
746 * @brief Removes an element.
748 * Does not maintain order. Swaps the element with end and
749 * decreases size by one. This is much faster than Erase so use
750 * this in case order does not matter. Does not change capacity.
753 * @param[in] iterator Iterator pointing to the item to remove
754 * @pre Iterator \e iterator must be in the vector's range ( Vector::Begin(), Vector::End() - 1 ).
757 void Remove( Iterator iterator )
759 DALI_ASSERT_VECTOR( (iterator < End()) && (iterator >= Begin()) && "Iterator not inside vector" );
761 Iterator last = End() - 1u;
762 if( last > iterator )
764 std::swap( *iterator, *last );
766 VectorBase::SetCount( VectorBase::Count() - 1u );
770 * @brief Swaps the contents of two vectors.
773 * @param[in] vector Vector to swap with
775 void Swap( Vector& vector )
777 VectorBase::Swap( vector );
781 * @brief Clears the contents of the vector. Keeps its capacity.
786 VectorAlgorithms<BaseType>::Clear();
790 * @brief Releases the memory that the vector holds.
795 VectorAlgorithms<BaseType>::Release();
804 #endif /* __DALI_VECTOR_H__ */