5 * Copyright (c) 2021 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>
31 #define DALI_ASSERT_VECTOR(cond) DALI_ASSERT_ALWAYS(cond)
36 * @addtogroup dali_core_common
41 * @brief Base class to handle the memory of simple vector.
43 * Memory layout is such that it has two std::size_t to hold the count
44 * and capacity of the vector. VectorBase::mData is adjusted so that it points to the
45 * beginning of the first real item so that iterating the items is quick.
48 class DALI_CORE_API VectorBase
51 using SizeType = std::size_t;
53 protected: // Construction
55 * @brief Default constructor. Does not allocate space.
63 * Does not release the space. Derived class needs to call Release.
64 * Not virtual as this should not be called directly and we do not want
65 * a vtable for this class as it would unnecessarily increase size.
72 * @brief This method is inlined as it's needed frequently for Vector::End() iterator.
75 * @return The count of elements in this vector
77 SizeType Count() const
82 SizeType* metadata = reinterpret_cast<SizeType*>(mData);
83 items = *(metadata - 1u);
89 * @brief Gets the count of elements in this vector.
91 * @return The count of elements in this vector
99 * @brief @ return if the vector is empty.
101 * @return True if the count of elements is empty
105 return Count() == 0u;
109 * @brief Gets the capacity of this vector.
111 * @return The capacity of this vector
113 SizeType Capacity() const;
116 * @brief Releases the data.
118 * Does not call destructors on objects held.
123 protected: // for Derived classes
125 * @brief Helper to set the count.
128 * @param[in] count Number of elements in the vector
130 void SetCount(SizeType count);
133 * @brief Reserves space in the vector.
136 * @param[in] count Count of elements to reserve
137 * @param[in] elementSize Size of a single element
139 void Reserve(SizeType count, SizeType elementSize);
142 * @brief Copy a vector.
145 * @param[in] vector Vector to copy from
146 * @param[in] elementSize Size of a single element
148 void Copy(const VectorBase& vector, SizeType elementSize);
151 * @brief Swaps the contents of two vectors.
154 * @param[in] vector Vector to swap with
156 void Swap(VectorBase& vector);
159 * @brief Erases an element.
161 * Does not change capacity.
163 * @param[in] address Address to erase from
164 * @param[in] elementSize Size to erase
165 * @pre Last element cannot be erased as there is nothing to move.
167 void Erase(char* address, SizeType elementSize);
170 * @brief Erases a range of elements.
172 * Does not change capacity.
174 * @param[in] first Address to the first element to be erased
175 * @param[in] last Address to the last element to be erased
176 * @param[in] elementSize Size of one of the elements to be erased
177 * @return Address pointing to the next element of the last one
179 char* Erase(char* first, char* last, SizeType elementSize);
182 * @brief Copies a number of bytes from \e source to \e destination.
184 * \e source and \e destination must not overlap.
187 * @param[in] destination Pointer to the destination address
188 * @param[in] source Pointer to the source address
189 * @param[in] numberOfBytes The number of bytes to be copied
191 void CopyMemory(char* destination, const char* source, size_t numberOfBytes);
194 * @brief Replace the data as new data address.
195 * After replace, release the old data.
197 * It will be used when we want to keep the mData integrity.
199 * Does not call destructors on objects held.
200 * @param[in] newData new data address to be replaced
202 void Replace(void* newData);
205 // not copyable as it does not know the size of elements
206 VectorBase(const VectorBase&) = delete; ///< Deleted copy constructor. @SINCE_1_0.0
207 VectorBase& operator=(const VectorBase&) = delete; ///< Deleted copy assignment operator. @SINCE_1_0.0
209 // not movable as this is handled by deriving classes
210 VectorBase(VectorBase&&) = delete; ///< Deleted move constructor. @SINCE_1_9.25
211 VectorBase& operator=(VectorBase&&) = delete; ///< Deleted copy assignment operator. @SINCE_1_9.25
214 void* mData; ///< Pointer to the data.
219 * @brief Vector algorithm variant for trivial types.
221 * Trivial types do not need destructor or copy constructor called.
224 template<bool IsTrivial>
225 class VectorAlgorithms : public VectorBase
227 protected: // API for deriving classes
228 using SizeType = VectorBase::SizeType;
231 * @brief Empty constructor.
234 VectorAlgorithms() = default;
237 * @brief Empty destructor.
240 ~VectorAlgorithms() = default;
243 * @brief Copy vector contents.
246 * @param[in] rhs VectorBase object to copy from
247 * @param[in] elementSize Size of the content
249 void Copy(const VectorBase& rhs, SizeType elementSize)
251 if(rhs.Capacity() > 0u)
253 VectorBase::Copy(rhs, elementSize);
257 VectorBase::Release();
262 * @brief Reserves space in the vector.
265 * @param[in] count Count of elements to reserve
266 * @param[in] elementSize Size of a single element
268 void Reserve(SizeType count, SizeType elementSize)
270 VectorBase::Reserve(count, elementSize);
274 * @brief Resizes the vector. Does not change capacity.
277 * @param[in] count Count to resize to
278 * @param[in] elementSize Size of a single element
280 void Resize(SizeType count, SizeType elementSize)
282 // reserve will copy old elements as well
283 Reserve(count, elementSize);
287 * @brief Clears the contents.
289 * For simple types, nothing to do.
296 VectorBase::SetCount(0u);
301 * @brief Releases the vector.
306 VectorBase::Release();
310 * @brief Erases an element. Does not change capacity.
313 * @param[in] address Address to erase from
314 * @param[in] elementSize Size to erase
316 void Erase(uint8_t* address, SizeType elementSize)
318 VectorBase::Erase(reinterpret_cast<char*>(address), elementSize);
322 * @brief Erases a range of elements. Does not change capacity.
325 * @param[in] first Address to the first element to be erased
326 * @param[in] last Address to the last element to be erased
327 * @param[in] elementSize Size of one of the elements to be erased
328 * @return Address pointing to the next element of the last one
330 uint8_t* Erase(uint8_t* first, uint8_t* last, SizeType elementSize)
332 return reinterpret_cast<uint8_t*>(VectorBase::Erase(reinterpret_cast<char*>(first), reinterpret_cast<char*>(last), elementSize));
336 * @brief Inserts the given elements into the vector.
339 * @param[in] at Address where to insert the elements into the vector
340 * @param[in] from Address to the first element to be inserted
341 * @param[in] to Address to the last element to be inserted
342 * @param[in] elementSize Size of one of the elements to be inserted
344 void Insert(uint8_t* at, uint8_t* from, uint8_t* to, SizeType elementSize)
346 const SizeType size = to - from;
347 const SizeType count = Count();
348 const SizeType newCount = count + size / elementSize;
350 if(newCount > Capacity())
352 // Calculate the at offset as the pointer is invalid after the Reserve() call.
353 std::size_t offset = at - reinterpret_cast<uint8_t*>(mData);
356 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.
358 // Set the new at pointer.
359 at = reinterpret_cast<uint8_t*>(mData) + offset;
361 // set new count first as otherwise the debug assert will hit us
364 // Move current items to a new position inside the vector.
365 CopyMemory(reinterpret_cast<char*>(at + size),
366 reinterpret_cast<const char*>(at),
367 (reinterpret_cast<uint8_t*>(mData) + count * elementSize) - at);
369 // Copy the given items.
370 CopyMemory(reinterpret_cast<char*>(at), reinterpret_cast<const char*>(from), size);
377 * @brief Vector algorithm variant for complex types.
379 * Not yet supported so will lead to compile error
380 * as constructor and destructor are private.
381 * TODO add support for this variant.
385 class VectorAlgorithms<false> : public VectorBase
388 VectorAlgorithms() = default;
389 ~VectorAlgorithms() = default;
394 * @brief Vector class with minimum space allocation when it's empty.
397 * @param type The type of the data that the vector holds
399 template<class T, bool IsTrivialType = TypeTraits<T>::IS_TRIVIAL_TYPE == true>
400 class Vector : public VectorAlgorithms<IsTrivialType>
404 * @brief Type definitions.
407 using SizeType = VectorBase::SizeType; ///< Size type @SINCE_1_0.0
408 using Iterator = T*; ///< Most simple Iterator is a pointer @SINCE_1_0.0
409 using ConstIterator = const T*; ///< Const iterator @SINCE_1_0.0
410 using ItemType = T; ///< Item type @SINCE_1_0.0
413 * @brief Enumeration for BaseType.
418 BaseType = IsTrivialType ///< @SINCE_1_0.0
422 * @brief Default constructor. Does not allocate any space.
428 * @brief Destructor. Releases the allocated space.
437 * @brief Copy constructor.
440 * @param[in] vector Vector to copy from
442 Vector(const Vector& vector)
444 // reuse copy assignment
449 * @brief Default move constructor.
452 * @param[in] vector Vector to move
454 Vector(Vector&& vector)
456 // reuse move assignment
457 operator=(std::move(vector));
461 * @brief Assignment operator.
464 * @param[in] vector Vector to assign from
465 * @return Reference to self for chaining
467 Vector& operator=(const Vector& vector)
471 VectorAlgorithms<BaseType>::Copy(vector, sizeof(ItemType));
477 * @brief Default move assignment operator.
480 * @param[in] vector Vector to move
482 Vector& operator=(Vector&& vector)
486 VectorAlgorithms<BaseType>::Replace(vector.mData);
487 vector.mData = nullptr;
493 * @brief Iterator to the beginning of the data.
495 * @return Iterator to the beginning of the data
497 Iterator Begin() const
499 ItemType* address = reinterpret_cast<ItemType*>(VectorBase::mData);
504 * @brief Iterator to the end of the data (one past last element).
506 * @return Iterator to the end of the data (one past last element)
510 ItemType* address = reinterpret_cast<ItemType*>(VectorBase::mData);
511 address += VectorBase::Count();
516 * Support for C++11 Range-based for loop: for( item : container ).
518 * @return The start iterator
520 Iterator begin() const
526 * Support for C++11 Range-based for loop: for( item : container ).
528 * @return The end iterator
536 * @brief Subscript operator.
538 * @param[in] index Index of the element
539 * @return Reference to the element for given index
540 * @pre Index must be in the vector's range.
542 ItemType& operator[](SizeType index)
544 // reuse the const version
545 return const_cast<ItemType&>(const_cast<const Vector<ItemType>&>(*this)[index]);
549 * @brief Subscript operator.
551 * @param[in] index Index of the element
552 * @return Reference to the element for given index
553 * @pre Index must be in the vector's range.
555 const ItemType& operator[](SizeType index) const
557 DALI_ASSERT_VECTOR(VectorBase::mData && "Vector is empty");
558 if(index >= VectorBase::Count())
560 // Prevent accessing invalid index
563 ItemType* address = reinterpret_cast<ItemType*>(VectorBase::mData);
569 * @brief Pushes back an element to the vector.
571 * The underlying storage may be reallocated to provide space.
572 * If this occurs, all pre-existing pointers into the vector will
576 * @param[in] element Element to be added
578 void PushBack(const ItemType& element)
580 const SizeType count = VectorBase::Count();
581 const SizeType newCount = count + 1u;
582 const SizeType capacity = VectorBase::Capacity();
583 if(newCount > capacity)
586 Reserve(newCount << 1u); // reserve double the current count
588 // set new count first as otherwise the debug assert will hit us
589 VectorBase::SetCount(newCount);
590 operator[](count) = element;
594 * @brief Inserts an element to the vector.
596 * Elements after \e at are moved one position to the right.
598 * The underlying storage may be reallocated to provide space.
599 * If this occurs, all pre-existing pointers into the vector will
603 * @param[in] at Iterator where to insert the elements into the vector
604 * @param[in] element An element to be added
605 * @pre Iterator at must be in the vector's range ( Vector::Begin(), Vector::End() ).
607 void Insert(Iterator at, const ItemType& element)
609 DALI_ASSERT_VECTOR((at <= End()) && (at >= Begin()) && "Iterator not inside vector");
610 const SizeType size = sizeof(ItemType);
611 uint8_t* address = const_cast<uint8_t*>(reinterpret_cast<const uint8_t*>(&element));
612 VectorAlgorithms<BaseType>::Insert(reinterpret_cast<uint8_t*>(at),
619 * @brief Inserts the given elements into the vector.
621 * Elements after \e at are moved the number of given elements positions to the right.
623 * The underlying storage may be reallocated to provide space.
624 * If this occurs, all pre-existing pointers into the vector will
628 * @param[in] at Iterator where to insert the elements into the vector
629 * @param[in] from Iterator to the first element to be inserted
630 * @param[in] to Iterator to the last element to be inserted
631 * @pre Iterator \e at must be in the vector's range ( Vector::Begin(), Vector::End() ).
632 * @pre Iterators \e from and \e to must be valid iterators.
633 * @pre Iterator \e from must not be grater than Iterator \e to.
636 void Insert(Iterator at, Iterator from, Iterator to)
638 DALI_ASSERT_VECTOR((at <= End()) && (at >= Begin()) && "Iterator not inside vector");
639 DALI_ASSERT_VECTOR((from <= to) && "from address can't be greater than to");
647 VectorAlgorithms<BaseType>::Insert(reinterpret_cast<uint8_t*>(at),
648 reinterpret_cast<uint8_t*>(from),
649 reinterpret_cast<uint8_t*>(to),
654 * @brief Reserves space in the vector.
656 * Reserving less than current Capacity is a no-op.
658 * @param[in] count Count of elements to reserve
660 void Reserve(SizeType count)
662 VectorAlgorithms<BaseType>::Reserve(count, sizeof(ItemType));
666 * @brief Resizes the vector. Does not change capacity.
669 * @param[in] count Count to resize to
671 void Resize(SizeType count)
673 ItemType item = ItemType();
678 * @brief Resizes the vector without initializing the data.
680 * Can be used as a data container for reading whole file content.
682 * @param[in] count Count to resize to
684 void ResizeUninitialized(SizeType count)
687 VectorBase::SetCount(count);
691 * @brief Resizes the vector. Does not change capacity.
694 * @param[in] count Count to resize to
695 * @param[in] item An item to insert to the new indices
697 void Resize(SizeType count, const ItemType& item)
699 const SizeType oldCount = VectorBase::Count();
700 if(count <= oldCount)
702 // getting smaller so just set count
703 VectorBase::SetCount(count);
707 // remember how many new items get added
708 SizeType newItems = count - oldCount;
710 for(; newItems > 0u; --newItems)
718 * @brief Erases an element.
720 * Does not change capacity. Other elements get moved.
723 * @param[in] iterator Iterator pointing to the item to remove
724 * @return Iterator pointing to next element
725 * @pre Iterator \e iterator must be within the vector's range ( Vector::Begin(), Vector::End() - 1 ).
728 Iterator Erase(Iterator iterator)
730 DALI_ASSERT_VECTOR((iterator < End()) && (iterator >= Begin()) && "Iterator not inside vector");
731 if(iterator < (End() - 1u))
733 VectorAlgorithms<BaseType>::Erase(reinterpret_cast<uint8_t*>(iterator), sizeof(ItemType));
737 // just remove the element
744 * @brief Erases a range of elements.
746 * Does not change capacity. Other elements get moved.
749 * @param[in] first Iterator to the first element to be erased
750 * @param[in] last Iterator to the last element to be erased
752 * @return Iterator pointing to the next element of the last one
753 * @pre Iterator \e first must be in the vector's range ( Vector::Begin(), Vector::End() ).
754 * @pre Iterator \e last must be in the vector's range ( Vector::Begin(), Vector::End() ).
755 * @pre Iterator \e first must not be grater than Iterator \e last.
758 Iterator Erase(Iterator first, Iterator last)
760 DALI_ASSERT_VECTOR((first <= End()) && (first >= Begin()) && "Iterator not inside vector");
761 DALI_ASSERT_VECTOR((last <= End()) && (last >= Begin()) && "Iterator not inside vector");
762 DALI_ASSERT_VECTOR((first <= last) && "first iterator greater than last");
764 Iterator nextElement;
768 // Erase up to the end.
769 VectorBase::SetCount(VectorBase::Count() - (last - first));
774 nextElement = reinterpret_cast<Iterator>(VectorAlgorithms<BaseType>::Erase(reinterpret_cast<uint8_t*>(first),
775 reinterpret_cast<uint8_t*>(last),
783 * @brief Removes an element.
785 * Does not maintain order. Swaps the element with end and
786 * decreases size by one. This is much faster than Erase so use
787 * this in case order does not matter. Does not change capacity.
790 * @param[in] iterator Iterator pointing to the item to remove
791 * @pre Iterator \e iterator must be in the vector's range ( Vector::Begin(), Vector::End() - 1 ).
794 void Remove(Iterator iterator)
796 DALI_ASSERT_VECTOR((iterator < End()) && (iterator >= Begin()) && "Iterator not inside vector");
798 Iterator last = End() - 1u;
801 std::swap(*iterator, *last);
803 VectorBase::SetCount(VectorBase::Count() - 1u);
807 * @brief Swaps the contents of two vectors.
810 * @param[in] vector Vector to swap with
812 void Swap(Vector& vector)
814 VectorBase::Swap(vector);
818 * @brief Clears the contents of the vector. Keeps its capacity.
823 VectorAlgorithms<BaseType>::Clear();
827 * @brief Releases the memory that the vector holds.
832 VectorAlgorithms<BaseType>::Release();
837 * @brief Erases all elements that compare equal to value from the vector.
840 * @param[in] vector The vector
841 * @param[in] value The value to be removed.
843 template<class T, class U>
844 inline void Erase(Dali::Vector<T>& vector, const U& value)
846 auto begin = vector.Begin();
847 auto end = vector.End();
849 vector.Erase(std::remove(begin, end, value), end);
853 * @brief Erases all elements that satisfy the predicate from the vector.
856 * @param[in] vector The vector
857 * @param[in] predicate The predicate
859 template<class T, class Predicate>
860 inline void EraseIf(Dali::Vector<T>& vector, Predicate predicate)
862 auto begin = vector.Begin();
863 auto end = vector.End();
865 vector.Erase(std::remove_if(begin, end, predicate), end);
873 #endif // DALI_VECTOR_H