1 #ifndef __DALI_VECTOR_H__
2 #define __DALI_VECTOR_H__
5 * Copyright (c) 2014 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>
29 * @brief For DALi internal use asserts are enabled in debug builds.
31 * For Application use asserts can be enabled manually.
33 #if defined( DEBUG_ENABLED )
34 #define ENABLE_VECTOR_ASSERTS
37 #if defined( ENABLE_VECTOR_ASSERTS )
38 #define DALI_ASSERT_VECTOR(cond) DALI_ASSERT_ALWAYS(cond)
40 #define DALI_ASSERT_VECTOR(cond)
43 namespace Dali DALI_IMPORT_API
47 * @brief Base class to handle the memory of simple vector.
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.
57 typedef std::size_t SizeType;
59 protected: // Construction
62 * @brief Default constructor. Does not allocate space.
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.
78 * @brief This method is inlined as its needed frequently for End() iterator.
80 * @return The count of elements in this vector.
82 SizeType Count() const
87 SizeType* metadata = reinterpret_cast< SizeType* >( mData );
88 items = *(metadata - 1);
95 * @return The count of elements in this vector.
103 * @return The capacity of this vector.
105 SizeType Capacity() const;
108 * @brief Release the data.
110 * Does not call destructors on objects held.
114 protected: // for Derived classes
117 * @brief Helper to set the count.
119 * @param count Number of elements in the vector.
121 void SetCount( SizeType count );
124 * @brief Reserve space in the vector.
126 * @param count of elements to reserve.
127 * @param elementSize of a single element.
129 void Reserve( SizeType count, SizeType elementSize );
132 * @brief Copy a vector.
134 * @param vector Vector to copy from.
135 * @param elementSize of a single element.
137 void Copy( const VectorBase& vector, SizeType elementSize );
140 * @brief Swap the contents of two vectors.
142 * @param vector Vector to swap with.
144 void Swap( VectorBase& vector );
147 * @brief Erase an element.
149 * Does not change capacity.
150 * @pre last element cannot be erased as there is nothing to move.
151 * @param address to erase from.
152 * @param elementSize to erase.
154 void Erase( char* address, SizeType elementSize );
158 // not copiable as it does not know the size of elements
159 VectorBase( const VectorBase& ); ///< Undefined
160 VectorBase& operator=( const VectorBase& ); ///< Undefined
164 void* mData; ///< Pointer to the data.
169 * @brief Vector algorithm variant for trivial types.
171 * Trivial types do not need destructor or copy constructor called.
173 template< bool IsTrivial >
174 class VectorAlgorithms : public VectorBase
176 protected: // API for deriving classes
178 typedef VectorBase::SizeType SizeType;
181 * @brief Empty constructor.
187 * @brief Empty destructor.
193 * @brief Copy vector contents.
195 * @param rhs to copy from.
196 * @param elementSize of the content.
198 void Copy( const VectorBase& rhs, SizeType elementSize )
200 if( rhs.Capacity() > 0u )
202 VectorBase::Copy( rhs, elementSize );
206 VectorBase::Release();
211 * @brief Reserve space in the vector.
213 * @param count of elements to reserve.
214 * @param elementSize of a single element.
216 void Reserve( SizeType count, SizeType elementSize )
218 VectorBase::Reserve( count, elementSize );
222 * @brief Resize the vector. Does not change capacity.
224 * @param count to resize to.
225 * @param elementSize of a single element.
227 void Resize( SizeType count, SizeType elementSize )
229 // reserve will copy old elements as well
230 Reserve( count, elementSize );
234 * @brief Clear the contents.
236 * For simple types nothing to do.
242 VectorBase::SetCount( 0u );
247 * @brief Release the vector.
251 VectorBase::Release();
255 * @brief Erase an element. Does not change capacity.
257 * @param address to erase from.
258 * @param elementSize to erase.
260 void Erase( char* address, SizeType elementSize )
262 VectorBase::Erase( address, elementSize );
268 * @brief Vector algorithm variant for complex types.
270 * Not yet supported so will lead to compile error
271 * as constructor and destructor are private.
272 * TODO add support for this variant.
275 class VectorAlgorithms< false > : public VectorBase
285 * @brief Vector class with minimum space allocation when its empty.
287 * @param type of the data that the vector holds.
289 template< class T, bool IsTrivialType = __has_trivial_destructor(T) && __has_trivial_copy(T) >
290 class Vector : public VectorAlgorithms< IsTrivialType >
295 * @brief Type definitions.
297 typedef VectorBase::SizeType SizeType;
298 typedef T* Iterator; ///< Most simple Iterator is a pointer
299 typedef const T* ConstIterator;
304 BaseType = IsTrivialType
308 * @brief Default constructor. Does not allocate any space.
314 * @brief Destructor. Releases the allocated space.
322 * @brief Copy constructor.
324 * @param vector Vector to copy from.
326 Vector( const Vector& vector )
333 * @brief Assignment operator.
335 * @param vector Vector to assign from.
336 * @return reference to self for chaining.
338 Vector& operator=( const Vector& vector )
340 if( this != &vector )
342 VectorAlgorithms<BaseType>::Copy( vector, sizeof( ItemType ) );
348 * @return Iterator to the beginning of the data.
350 Iterator Begin() const
352 ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
357 * @return Iterator to the end of the data (one past last element).
361 ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
362 address += VectorBase::Count();
367 * @param index of the element.
368 * @return reference to the element for given index.
370 ItemType& operator[]( SizeType index )
372 // reuse the const version
373 return const_cast< ItemType& >( const_cast< const Vector< ItemType >& >( *this )[ index ] );
377 * @param index of the element.
378 * @return reference to the element for given index.
380 const ItemType& operator[]( SizeType index ) const
382 DALI_ASSERT_VECTOR( VectorBase::mData && "Vector is empty" );
383 DALI_ASSERT_VECTOR( index < VectorBase::Count() && "Index out of bounds" );
384 ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
390 * @brief Push back an element to the vector.
392 * @param element to be added.
394 void PushBack( const ItemType& element )
396 const SizeType count = VectorBase::Count();
397 const SizeType newCount = count + 1u;
398 const SizeType capacity = VectorBase::Capacity();
399 if( newCount > capacity )
402 Reserve( newCount << 1 ); // reserve double the current count
404 // set new count first as otherwise the debug assert will hit us
405 VectorBase::SetCount( newCount );
406 operator[]( count ) = element;
410 * @brief Reserve space in the vector.
412 * Reserving less than current Capacity is a no-op.
413 * @param count of elements to reserve.
415 void Reserve( SizeType count )
417 VectorAlgorithms<BaseType>::Reserve( count, sizeof( ItemType ) );
421 * @brief Resize the vector. Does not change capacity.
423 * @param count to resize to.
424 * @param item to insert to the new indeces.
426 void Resize( SizeType count, ItemType item = ItemType() )
428 const SizeType oldCount = VectorBase::Count();
429 if( count <= oldCount )
431 // getting smaller so just set count
432 VectorBase::SetCount( count );
436 // remember how many new items get added
437 SizeType newItems = count - oldCount;
439 for( ; newItems > 0; --newItems )
447 * @brief Erase an element.
449 * Does not change capacity. Other elements get moved.
450 * @param iterator Iterator pointing to item to remove.
451 * @return Iterator pointing to next element.
453 Iterator Erase( Iterator iterator )
455 DALI_ASSERT_VECTOR( VectorBase::mData && "Vector is empty" );
456 DALI_ASSERT_VECTOR( (iterator < End()) && (iterator >= Begin() ) && "Iterator not inside vector" );
457 if( iterator < ( End() - 1 ) )
459 VectorAlgorithms<BaseType>::Erase( reinterpret_cast< char* >( iterator ), sizeof( ItemType ) );
463 // just remove the element
470 * @brief Removes an element.
472 * Does not maintain order. Swaps the element with end and
473 * decreases size by one. This is much faster than Erase so use
474 * this in case order does not matter. Does not change capacity.
476 * @param iterator Iterator pointing to item to remove.
478 void Remove( Iterator iterator )
480 DALI_ASSERT_VECTOR( VectorBase::mData && "Vector is empty" );
481 Iterator end = End();
482 DALI_ASSERT_VECTOR( (iterator < end) && (iterator >= Begin() ) && "Iterator not inside vector" );
483 Iterator last = end - 1;
484 if( last != iterator )
486 std::swap( *iterator, *last );
488 VectorBase::SetCount( VectorBase::Count() - 1 );
492 * @brief Swap the contents of two vectors.
494 * @param vector Vector to swap with.
496 void Swap( Vector& vector )
498 VectorBase::Swap( vector );
502 * @brief Clear the contents of the vector. Keeps its capacity.
506 VectorAlgorithms<BaseType>::Clear();
510 * @brief Release the memory that the vector holds.
514 VectorAlgorithms<BaseType>::Release();
521 #endif /* __DALI_VECTOR_H__ */