5 * Copyright (c) 2020 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.
24 #include <cstdint> // uint32_t
27 #include <dali/public-api/common/dali-common.h>
28 #include <dali/public-api/common/type-traits.h>
29 #include <dali/public-api/math/math-utils.h>
32 * @brief For DALi internal use, asserts are enabled in debug builds.
34 * For Application use, asserts can be enabled manually.
37 #if defined( DEBUG_ENABLED )
38 #define ENABLE_VECTOR_ASSERTS
41 #if defined( ENABLE_VECTOR_ASSERTS )
42 #define DALI_ASSERT_VECTOR(cond) DALI_ASSERT_ALWAYS(cond)
44 #define DALI_ASSERT_VECTOR(cond)
50 * @addtogroup dali_core_common
55 * @brief Base class to handle the memory of simple vector.
57 * Memory layout is such that it has two std::size_t to hold the count
58 * and capacity of the vector. VectorBase::mData is adjusted so that it points to the
59 * beginning of the first real item so that iterating the items is quick.
62 class DALI_CORE_API VectorBase
66 typedef std::size_t SizeType;
68 protected: // Construction
71 * @brief Default constructor. Does not allocate space.
79 * Does not release the space. Derived class needs to call Release.
80 * Not virtual as this should not be called directly and we do not want
81 * a vtable for this class as it would unnecessarily increase size.
89 * @brief This method is inlined as it's needed frequently for Vector::End() iterator.
92 * @return The count of elements in this vector
94 SizeType Count() const
99 SizeType* metadata = reinterpret_cast< SizeType* >( mData );
100 items = *(metadata - 1u);
106 * @brief Gets the count of elements in this vector.
108 * @return The count of elements in this vector
110 SizeType Size() const
116 * @brief @ return if the vector is empty.
118 * @return True if the count of elements is empty
122 return Count() == 0u;
126 * @brief Gets the capacity of this vector.
128 * @return The capacity of this vector
130 SizeType Capacity() const;
133 * @brief Releases the data.
135 * Does not call destructors on objects held.
140 protected: // for Derived classes
143 * @brief Helper to set the count.
146 * @param[in] count Number of elements in the vector
148 void SetCount( SizeType count );
151 * @brief Reserves space in the vector.
154 * @param[in] count Count of elements to reserve
155 * @param[in] elementSize Size of a single element
157 void Reserve( SizeType count, SizeType elementSize );
160 * @brief Copy a vector.
163 * @param[in] vector Vector to copy from
164 * @param[in] elementSize Size of a single element
166 void Copy( const VectorBase& vector, SizeType elementSize );
169 * @brief Swaps the contents of two vectors.
172 * @param[in] vector Vector to swap with
174 void Swap( VectorBase& vector );
177 * @brief Erases an element.
179 * Does not change capacity.
181 * @param[in] address Address to erase from
182 * @param[in] elementSize Size to erase
183 * @pre Last element cannot be erased as there is nothing to move.
185 void Erase( char* address, SizeType elementSize );
188 * @brief Erases a range of elements.
190 * Does not change capacity.
192 * @param[in] first Address to the first element to be erased
193 * @param[in] last Address to the last element to be erased
194 * @param[in] elementSize Size of one of the elements to be erased
195 * @return Address pointing to the next element of the last one
197 char* Erase( char* first, char* last, SizeType elementSize );
200 * @brief Copies a number of bytes from \e source to \e destination.
202 * \e source and \e destination must not overlap.
205 * @param[in] destination Pointer to the destination address
206 * @param[in] source Pointer to the source address
207 * @param[in] numberOfBytes The number of bytes to be copied
209 void CopyMemory( char* destination, const char* source, size_t numberOfBytes );
213 // not copyable as it does not know the size of elements
214 VectorBase( const VectorBase& ) = delete; ///< Deleted copy constructor. @SINCE_1_0.0
215 VectorBase& operator=( const VectorBase& ) = delete; ///< Deleted copy assignment operator. @SINCE_1_0.0
217 // not movable as this is handled by deriving classes
218 VectorBase( VectorBase&& ) = delete; ///< Deleted move constructor. @SINCE_1_9.25
219 VectorBase& operator=( VectorBase&& ) = delete; ///< Deleted copy assignment operator. @SINCE_1_9.25
223 void* mData; ///< Pointer to the data.
229 * @brief Vector algorithm variant for trivial types.
231 * Trivial types do not need destructor or copy constructor called.
234 template< bool IsTrivial >
235 class VectorAlgorithms : public VectorBase
237 protected: // API for deriving classes
239 typedef VectorBase::SizeType SizeType;
242 * @brief Empty constructor.
249 * @brief Empty destructor.
256 * @brief Copy vector contents.
259 * @param[in] rhs VectorBase object to copy from
260 * @param[in] elementSize Size of the content
262 void Copy( const VectorBase& rhs, SizeType elementSize )
264 if( rhs.Capacity() > 0u )
266 VectorBase::Copy( rhs, elementSize );
270 VectorBase::Release();
275 * @brief Reserves space in the vector.
278 * @param[in] count Count of elements to reserve
279 * @param[in] elementSize Size of a single element
281 void Reserve( SizeType count, SizeType elementSize )
283 VectorBase::Reserve( count, elementSize );
287 * @brief Resizes the vector. Does not change capacity.
290 * @param[in] count Count to resize to
291 * @param[in] elementSize Size of a single element
293 void Resize( SizeType count, SizeType elementSize )
295 // reserve will copy old elements as well
296 Reserve( count, elementSize );
300 * @brief Clears the contents.
302 * For simple types, nothing to do.
309 VectorBase::SetCount( 0u );
314 * @brief Releases the vector.
319 VectorBase::Release();
323 * @brief Erases an element. Does not change capacity.
326 * @param[in] address Address to erase from
327 * @param[in] elementSize Size to erase
329 void Erase( uint8_t* address, SizeType elementSize )
331 VectorBase::Erase( reinterpret_cast< char* >( address ), elementSize );
335 * @brief Erases a range of elements. Does not change capacity.
338 * @param[in] first Address to the first element to be erased
339 * @param[in] last Address to the last element to be erased
340 * @param[in] elementSize Size of one of the elements to be erased
341 * @return Address pointing to the next element of the last one
343 uint8_t* Erase( uint8_t* first, uint8_t* last, SizeType elementSize )
345 return reinterpret_cast< uint8_t* >( VectorBase::Erase( reinterpret_cast< char* >( first ), reinterpret_cast< char *>( last ), elementSize ) );
349 * @brief Inserts the given elements into the vector.
352 * @param[in] at Address where to insert the elements into the vector
353 * @param[in] from Address to the first element to be inserted
354 * @param[in] to Address to the last element to be inserted
355 * @param[in] elementSize Size of one of the elements to be inserted
357 void Insert( uint8_t* at, uint8_t* from, uint8_t* to, SizeType elementSize )
359 const SizeType size = to - from;
360 const SizeType count = Count();
361 const SizeType newCount = count + size / elementSize;
363 if( newCount > Capacity() )
365 // Calculate the at offset as the pointer is invalid after the Reserve() call.
366 std::size_t offset = at - reinterpret_cast<uint8_t*>( mData );
369 Reserve( NextPowerOfTwo( static_cast<uint32_t>( newCount ) ), elementSize ); // reserve enough space to store at least the next power of two elements of the new required size.
371 // Set the new at pointer.
372 at = reinterpret_cast<uint8_t*>( mData ) + offset;
374 // set new count first as otherwise the debug assert will hit us
375 SetCount( newCount );
377 // Move current items to a new position inside the vector.
378 CopyMemory( reinterpret_cast< char* >( at + size ),
379 reinterpret_cast< const char* >( at ),
380 ( reinterpret_cast<uint8_t*>( mData ) + count * elementSize ) - at );
382 // Copy the given items.
383 CopyMemory( reinterpret_cast< char* >( at ), reinterpret_cast< const char* >( from ), size );
390 * @brief Vector algorithm variant for complex types.
392 * Not yet supported so will lead to compile error
393 * as constructor and destructor are private.
394 * TODO add support for this variant.
398 class VectorAlgorithms< false > : public VectorBase
409 * @brief Vector class with minimum space allocation when it's empty.
412 * @param type The type of the data that the vector holds
414 template< class T, bool IsTrivialType = TypeTraits<T>::IS_TRIVIAL_TYPE == true >
415 class Vector : public VectorAlgorithms< IsTrivialType >
420 * @brief Type definitions.
423 typedef VectorBase::SizeType SizeType; ///< Size type @SINCE_1_0.0
424 typedef T* Iterator; ///< Most simple Iterator is a pointer @SINCE_1_0.0
425 typedef const T* ConstIterator; ///< Const iterator @SINCE_1_0.0
426 typedef T ItemType; ///< Item type @SINCE_1_0.0
429 * @brief Enumeration for BaseType.
434 BaseType = IsTrivialType ///< @SINCE_1_0.0
438 * @brief Default constructor. Does not allocate any space.
445 * @brief Destructor. Releases the allocated space.
454 * @brief Copy constructor.
457 * @param[in] vector Vector to copy from
459 Vector( const Vector& vector )
461 // reuse copy assignment
466 * @brief Default move constructor.
469 * @param[in] vector Vector to move
471 Vector( Vector&& vector )
473 // reuse move assignment
474 operator=( std::move( vector ) );
478 * @brief Assignment operator.
481 * @param[in] vector Vector to assign from
482 * @return Reference to self for chaining
484 Vector& operator=( const Vector& vector )
486 if( this != &vector )
488 VectorAlgorithms<BaseType>::Copy( vector, sizeof( ItemType ) );
494 * @brief Default move assignment operator.
497 * @param[in] vector Vector to move
499 Vector& operator=( Vector&& vector )
501 if( this != &vector )
503 if( VectorBase::mData )
507 VectorBase::mData = vector.mData;
508 vector.mData = nullptr;
514 * @brief Iterator to the beginning of the data.
516 * @return Iterator to the beginning of the data
518 Iterator Begin() const
520 ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
525 * @brief Iterator to the end of the data (one past last element).
527 * @return Iterator to the end of the data (one past last element)
531 ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
532 address += VectorBase::Count();
537 * Support for C++11 Range-based for loop: for( item : container ).
539 * @return The start iterator
541 Iterator begin() const
547 * Support for C++11 Range-based for loop: for( item : container ).
549 * @return The end iterator
557 * @brief Subscript operator.
559 * @param[in] index Index of the element
560 * @return Reference to the element for given index
561 * @pre Index must be in the vector's range.
563 ItemType& operator[]( SizeType index )
565 // reuse the const version
566 return const_cast< ItemType& >( const_cast< const Vector< ItemType >& >( *this )[ index ] );
570 * @brief Subscript operator.
572 * @param[in] index Index of the element
573 * @return Reference to the element for given index
574 * @pre Index must be in the vector's range.
576 const ItemType& operator[]( SizeType index ) const
578 DALI_ASSERT_VECTOR( VectorBase::mData && "Vector is empty" );
579 DALI_ASSERT_VECTOR( index < VectorBase::Count() && "Index out of bounds" );
580 ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
586 * @brief Pushes back an element to the vector.
588 * The underlying storage may be reallocated to provide space.
589 * If this occurs, all pre-existing pointers into the vector will
593 * @param[in] element Element to be added
595 void PushBack( const ItemType& element )
597 const SizeType count = VectorBase::Count();
598 const SizeType newCount = count + 1u;
599 const SizeType capacity = VectorBase::Capacity();
600 if( newCount > capacity )
603 Reserve( newCount << 1u ); // reserve double the current count
605 // set new count first as otherwise the debug assert will hit us
606 VectorBase::SetCount( newCount );
607 operator[]( count ) = element;
611 * @brief Inserts an element to the vector.
613 * Elements after \e at are moved one position to the right.
615 * The underlying storage may be reallocated to provide space.
616 * If this occurs, all pre-existing pointers into the vector will
620 * @param[in] at Iterator where to insert the elements into the vector
621 * @param[in] element An element to be added
622 * @pre Iterator at must be in the vector's range ( Vector::Begin(), Vector::End() ).
624 void Insert( Iterator at, const ItemType& element )
626 DALI_ASSERT_VECTOR( ( at <= End() ) && ( at >= Begin() ) && "Iterator not inside vector" );
627 const SizeType size = sizeof( ItemType );
628 uint8_t* address = const_cast<uint8_t*>( reinterpret_cast<const uint8_t*>( &element ) );
629 VectorAlgorithms<BaseType>::Insert( reinterpret_cast< uint8_t* >( at ),
636 * @brief Inserts the given elements into the vector.
638 * Elements after \e at are moved the number of given elements positions to the right.
640 * The underlying storage may be reallocated to provide space.
641 * If this occurs, all pre-existing pointers into the vector will
645 * @param[in] at Iterator where to insert the elements into the vector
646 * @param[in] from Iterator to the first element to be inserted
647 * @param[in] to Iterator to the last element to be inserted
648 * @pre Iterator \e at must be in the vector's range ( Vector::Begin(), Vector::End() ).
649 * @pre Iterators \e from and \e to must be valid iterators.
650 * @pre Iterator \e from must not be grater than Iterator \e to.
653 void Insert( Iterator at, Iterator from, Iterator to )
655 DALI_ASSERT_VECTOR( ( at <= End() ) && ( at >= Begin() ) && "Iterator not inside vector" );
656 DALI_ASSERT_VECTOR( ( from <= to ) && "from address can't be greater than to" );
664 VectorAlgorithms<BaseType>::Insert( reinterpret_cast< uint8_t* >( at ),
665 reinterpret_cast< uint8_t* >( from ),
666 reinterpret_cast< uint8_t* >( to ),
667 sizeof( ItemType ) );
671 * @brief Reserves space in the vector.
673 * Reserving less than current Capacity is a no-op.
675 * @param[in] count Count of elements to reserve
677 void Reserve( SizeType count )
679 VectorAlgorithms<BaseType>::Reserve( count, sizeof( ItemType ) );
683 * @brief Resizes the vector. Does not change capacity.
686 * @param[in] count Count to resize to
688 void Resize( SizeType count )
690 ItemType item = ItemType();
695 * @brief Resizes the vector. Does not change capacity.
698 * @param[in] count Count to resize to
699 * @param[in] item An item to insert to the new indices
701 void Resize( SizeType count, const ItemType& item )
703 const SizeType oldCount = VectorBase::Count();
704 if( count <= oldCount )
706 // getting smaller so just set count
707 VectorBase::SetCount( count );
711 // remember how many new items get added
712 SizeType newItems = count - oldCount;
714 for( ; newItems > 0u; --newItems )
722 * @brief Erases an element.
724 * Does not change capacity. Other elements get moved.
727 * @param[in] iterator Iterator pointing to the item to remove
728 * @return Iterator pointing to next element
729 * @pre Iterator \e iterator must be within the vector's range ( Vector::Begin(), Vector::End() - 1 ).
732 Iterator Erase( Iterator iterator )
734 DALI_ASSERT_VECTOR( (iterator < End()) && (iterator >= Begin()) && "Iterator not inside vector" );
735 if( iterator < ( End() - 1u ) )
737 VectorAlgorithms<BaseType>::Erase( reinterpret_cast< uint8_t* >( iterator ), sizeof( ItemType ) );
741 // just remove the element
748 * @brief Erases a range of elements.
750 * Does not change capacity. Other elements get moved.
753 * @param[in] first Iterator to the first element to be erased
754 * @param[in] last Iterator to the last element to be erased
756 * @return Iterator pointing to the next element of the last one
757 * @pre Iterator \e first must be in the vector's range ( Vector::Begin(), Vector::End() ).
758 * @pre Iterator \e last must be in the vector's range ( Vector::Begin(), Vector::End() ).
759 * @pre Iterator \e first must not be grater than Iterator \e last.
762 Iterator Erase( Iterator first, Iterator last )
764 DALI_ASSERT_VECTOR( ( first <= End() ) && ( first >= Begin() ) && "Iterator not inside vector" );
765 DALI_ASSERT_VECTOR( ( last <= End() ) && ( last >= Begin() ) && "Iterator not inside vector" );
766 DALI_ASSERT_VECTOR( ( first <= last ) && "first iterator greater than last" );
768 Iterator nextElement;
772 // Erase up to the end.
773 VectorBase::SetCount( VectorBase::Count() - ( last - first ) );
778 nextElement = reinterpret_cast<Iterator>( VectorAlgorithms<BaseType>::Erase( reinterpret_cast< uint8_t* >( first ),
779 reinterpret_cast< uint8_t* >( last ),
780 sizeof( ItemType ) ) );
787 * @brief Removes an element.
789 * Does not maintain order. Swaps the element with end and
790 * decreases size by one. This is much faster than Erase so use
791 * this in case order does not matter. Does not change capacity.
794 * @param[in] iterator Iterator pointing to the item to remove
795 * @pre Iterator \e iterator must be in the vector's range ( Vector::Begin(), Vector::End() - 1 ).
798 void Remove( Iterator iterator )
800 DALI_ASSERT_VECTOR( (iterator < End()) && (iterator >= Begin()) && "Iterator not inside vector" );
802 Iterator last = End() - 1u;
803 if( last > iterator )
805 std::swap( *iterator, *last );
807 VectorBase::SetCount( VectorBase::Count() - 1u );
811 * @brief Swaps the contents of two vectors.
814 * @param[in] vector Vector to swap with
816 void Swap( Vector& vector )
818 VectorBase::Swap( vector );
822 * @brief Clears the contents of the vector. Keeps its capacity.
827 VectorAlgorithms<BaseType>::Clear();
831 * @brief Releases the memory that the vector holds.
836 VectorAlgorithms<BaseType>::Release();
845 #endif // DALI_VECTOR_H