Dali 3D User Interface Engine
dali-vector.h
Go to the documentation of this file.
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
29 
36 #if defined( DEBUG_ENABLED )
37 #define ENABLE_VECTOR_ASSERTS
38 #endif
39 
40 #if defined( ENABLE_VECTOR_ASSERTS )
41 #define DALI_ASSERT_VECTOR(cond) DALI_ASSERT_ALWAYS(cond)
42 #else
43 #define DALI_ASSERT_VECTOR(cond)
44 #endif
45 
46 namespace Dali
47 {
62 {
63 public: // Typedefs
64 
65  typedef std::size_t SizeType;
66 
67 protected: // Construction
68 
73  VectorBase();
74 
83  ~VectorBase();
84 
85 public: // API
86 
93  SizeType Count() const
94  {
95  SizeType items = 0u;
96  if( mData )
97  {
98  SizeType* metadata = reinterpret_cast< SizeType* >( mData );
99  items = *(metadata - 1u);
100  }
101  return items;
102  }
103 
109  SizeType Size() const
110  {
111  return Count();
112  }
113 
118  bool Empty() const
119  {
120  return Count() == 0u;
121  }
122 
128  SizeType Capacity() const;
129 
136  void Release();
137 
138 protected: // for Derived classes
139 
146  void SetCount( SizeType count );
147 
155  void Reserve( SizeType count, SizeType elementSize );
156 
164  void Copy( const VectorBase& vector, SizeType elementSize );
165 
172  void Swap( VectorBase& vector );
173 
183  void Erase( char* address, SizeType elementSize );
184 
195  char* Erase( char* first, char* last, SizeType elementSize );
196 
207  void CopyMemory( char* destination, const char* source, size_t numberOfBytes );
208 
209 private:
210 
211  // not copiable as it does not know the size of elements
212  VectorBase( const VectorBase& );
213  VectorBase& operator=( const VectorBase& );
214 
215 protected: // Data
216 
217  void* mData;
218 
219 };
220 
227 template< bool IsTrivial >
229 {
230 protected: // API for deriving classes
231 
233 
239  { }
240 
246  { }
247 
255  void Copy( const VectorBase& rhs, SizeType elementSize )
256  {
257  if( rhs.Capacity() > 0u )
258  {
259  VectorBase::Copy( rhs, elementSize );
260  }
261  else
262  {
264  }
265  }
266 
274  void Reserve( SizeType count, SizeType elementSize )
275  {
276  VectorBase::Reserve( count, elementSize );
277  }
278 
286  void Resize( SizeType count, SizeType elementSize )
287  {
288  // reserve will copy old elements as well
289  Reserve( count, elementSize );
290  }
291 
298  void Clear()
299  {
300  if( mData )
301  {
302  VectorBase::SetCount( 0u );
303  }
304  }
305 
310  void Release()
311  {
313  }
314 
322  void Erase( char* address, SizeType elementSize )
323  {
324  VectorBase::Erase( address, elementSize );
325  }
326 
336  char* Erase( char* first, char* last, SizeType elementSize )
337  {
338  return VectorBase::Erase( first, last, elementSize );
339  }
340 
350  void Insert( char* at, char* from, char* to, SizeType elementSize )
351  {
352  const SizeType size = to - from;
353  const SizeType count = Count();
354  const SizeType newCount = count + size / elementSize;
355 
356  if( newCount > Capacity() )
357  {
358  // Calculate the at offset as the pointer is invalid after the Reserve() call.
359  std::size_t offset = at - reinterpret_cast<char*>( mData );
360 
361  // need more space
362  Reserve( NextPowerOfTwo( newCount ), elementSize ); // reserve enough space to store at least the next power of two elements of the new required size.
363 
364  // Set the new at pointer.
365  at = reinterpret_cast<char*>( mData ) + offset;
366  }
367  // set new count first as otherwise the debug assert will hit us
368  SetCount( newCount );
369 
370  // Move current items to a new position inside the vector.
371  CopyMemory( at + size,
372  at,
373  ( reinterpret_cast<char*>( mData ) + count * elementSize ) - at );
374 
375  // Copy the given items.
376  CopyMemory( at, from, size );
377  }
378 };
379 
388 template<>
389 class VectorAlgorithms< false > : public VectorBase
390 {
391 private:
393  { }
395  { }
396 };
397 
404 template< class T, bool IsTrivialType = TypeTraits<T>::IS_TRIVIAL_TYPE == true >
405 class Vector : public VectorAlgorithms< IsTrivialType >
406 {
407 public: // API
408 
414  typedef T* Iterator;
415  typedef const T* ConstIterator;
416  typedef T ItemType;
417 
418  enum
419  {
420  BaseType = IsTrivialType
421  };
422 
428  { }
429 
435  {
436  Release();
437  }
438 
445  Vector( const Vector& vector )
446  {
447  // reuse assignment
448  operator=( vector );
449  }
450 
458  Vector& operator=( const Vector& vector )
459  {
460  if( this != &vector )
461  {
462  VectorAlgorithms<BaseType>::Copy( vector, sizeof( ItemType ) );
463  }
464  return *this;
465  }
466 
472  Iterator Begin() const
473  {
474  ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
475  return address;
476  }
477 
483  Iterator End() const
484  {
485  ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
486  address += VectorBase::Count();
487  return address;
488  }
489 
498  {
499  // reuse the const version
500  return const_cast< ItemType& >( const_cast< const Vector< ItemType >& >( *this )[ index ] );
501  }
502 
510  const ItemType& operator[]( SizeType index ) const
511  {
512  DALI_ASSERT_VECTOR( VectorBase::mData && "Vector is empty" );
513  DALI_ASSERT_VECTOR( index < VectorBase::Count() && "Index out of bounds" );
514  ItemType* address = reinterpret_cast<ItemType*>( VectorBase::mData );
515  address += index;
516  return *address;
517  }
518 
529  void PushBack( const ItemType& element )
530  {
531  const SizeType count = VectorBase::Count();
532  const SizeType newCount = count + 1u;
533  const SizeType capacity = VectorBase::Capacity();
534  if( newCount > capacity )
535  {
536  // need more space
537  Reserve( newCount << 1u ); // reserve double the current count
538  }
539  // set new count first as otherwise the debug assert will hit us
540  VectorBase::SetCount( newCount );
541  operator[]( count ) = element;
542  }
543 
559  void Insert( Iterator at, const ItemType& element )
560  {
561  DALI_ASSERT_VECTOR( ( at <= End() ) && ( at >= Begin() ) && "Iterator not inside vector" );
562  const SizeType size = sizeof( ItemType );
563  char* address = const_cast<char*>( reinterpret_cast<const char*>( &element ) );
564  VectorAlgorithms<BaseType>::Insert( reinterpret_cast< char* >( at ),
565  address,
566  address + size,
567  size );
568  }
569 
588  void Insert( Iterator at, Iterator from, Iterator to )
589  {
590  DALI_ASSERT_VECTOR( ( at <= End() ) && ( at >= Begin() ) && "Iterator not inside vector" );
591  DALI_ASSERT_VECTOR( ( from <= to ) && "from address can't be greater than to" );
592 
593  if( from == to )
594  {
595  // nothing to copy.
596  return;
597  }
598 
599  VectorAlgorithms<BaseType>::Insert( reinterpret_cast< char* >( at ),
600  reinterpret_cast< char* >( from ),
601  reinterpret_cast< char* >( to ),
602  sizeof( ItemType ) );
603  }
604 
612  void Reserve( SizeType count )
613  {
614  VectorAlgorithms<BaseType>::Reserve( count, sizeof( ItemType ) );
615  }
616 
623  void Resize( SizeType count )
624  {
625  ItemType item = ItemType();
626  Resize(count, item);
627  }
628 
636  void Resize( SizeType count, const ItemType& item )
637  {
638  const SizeType oldCount = VectorBase::Count();
639  if( count <= oldCount )
640  {
641  // getting smaller so just set count
642  VectorBase::SetCount( count );
643  }
644  else
645  {
646  // remember how many new items get added
647  SizeType newItems = count - oldCount;
648  Reserve( count );
649  for( ; newItems > 0u; --newItems )
650  {
651  PushBack( item );
652  }
653  }
654  }
655 
667  Iterator Erase( Iterator iterator )
668  {
669  DALI_ASSERT_VECTOR( (iterator < End()) && (iterator >= Begin()) && "Iterator not inside vector" );
670  if( iterator < ( End() - 1u ) )
671  {
672  VectorAlgorithms<BaseType>::Erase( reinterpret_cast< char* >( iterator ), sizeof( ItemType ) );
673  }
674  else
675  {
676  // just remove the element
677  Remove( iterator );
678  }
679  return iterator;
680  }
681 
698  {
699  DALI_ASSERT_VECTOR( ( first <= End() ) && ( first >= Begin() ) && "Iterator not inside vector" );
700  DALI_ASSERT_VECTOR( ( last <= End() ) && ( last >= Begin() ) && "Iterator not inside vector" );
701  DALI_ASSERT_VECTOR( ( first <= last ) && "first iterator greater than last" );
702 
703  Iterator nextElement;
704 
705  if( last == End() )
706  {
707  // Erase up to the end.
708  VectorBase::SetCount( VectorBase::Count() - ( last - first ) );
709  nextElement = End();
710  }
711  else
712  {
713  nextElement = reinterpret_cast<Iterator>( VectorAlgorithms<BaseType>::Erase( reinterpret_cast< char* >( first ),
714  reinterpret_cast< char* >( last ),
715  sizeof( ItemType ) ) );
716  }
717 
718  return nextElement;
719  }
720 
733  void Remove( Iterator iterator )
734  {
735  DALI_ASSERT_VECTOR( (iterator < End()) && (iterator >= Begin()) && "Iterator not inside vector" );
736 
737  Iterator last = End() - 1u;
738  if( last > iterator )
739  {
740  std::swap( *iterator, *last );
741  }
743  }
744 
751  void Swap( Vector& vector )
752  {
753  VectorBase::Swap( vector );
754  }
755 
760  void Clear()
761  {
763  }
764 
769  void Release()
770  {
772  }
773 };
774 
778 } // namespace Dali
779 
780 #endif /* __DALI_VECTOR_H__ */
Dali Docs Home
Read more about Dali