include/dfe/dfe_smallvector.hpp

0001 // SPDX-License-Identifier: MIT
0002 // Copyright 2019 Moritz Kiehn
0003 //
0004 // Permission is hereby granted, free of charge, to any person obtaining a copy
0005 // of this software and associated documentation files (the "Software"), to deal
0006 // in the Software without restriction, including without limitation the rights
0007 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
0008 // copies of the Software, and to permit persons to whom the Software is
0009 // furnished to do so, subject to the following conditions:
0010 //
0011 // The above copyright notice and this permission notice shall be included in
0012 // all copies or substantial portions of the Software.
0013 //
0014 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0015 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0016 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
0017 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
0018 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
0019 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
0020 // SOFTWARE.
0021
0022 /// \file
0023 /// \brief   Minimal small vector implementation
0024 /// \author  Moritz Kiehn <msmk@cern.ch>
0025 /// \date    2019-04-00, Initial version
0026
0027 #pragma once
0028
0029 #include <iterator>
0030 #include <memory>
0031
0032 namespace dfe {
0033
0034 /// An continous container that stores some elements in-place.
0035 ///
0036 /// \tparam T Stored element type
0037 /// \tparam N Maximum number of elements stored in-place.
0038 /// \tparam Allocator Allocator for elements of type T
0039 ///
0040 /// If the vector contains less or equal than N elements, they are stored in
0041 /// the vector itself without the need to allocate additional memory.
0042 ///
0043 /// Supports access by index, iteration over elements, deleting all existing
0044 /// elements from the vector, and adding elements at a specified location or at
0045 /// the back.
0046 template<typename T, std::size_t N, typename Allocator = std::allocator<T>>
0047 class SmallVector {
0048 public:
0049   using value_type = T;
0050   using size_type = std::size_t;
0051   using iterator = T*;
0052   using const_iterator = const T*;
0053
0054   SmallVector() = default;
0055   ~SmallVector() { clear(); }
0056
0057   value_type& operator[](size_type idx);
0058   const value_type& operator[](size_type idx) const;
0059
0060   iterator begin();
0061   iterator end() { return begin() + m_size; }
0062   const_iterator begin() const;
0063   const_iterator end() const { return begin() + m_size; }
0064
0065   /// Return true if there are no elements in the vector.
0066   bool empty() const { return (m_size == 0); }
0067   /// Return the number of elements in the vector.
0068   size_type size() const { return m_size; }
0069   /// Return the number of elements that can be stored in the available memory.
0070   size_type capacity() const { return (m_size <= N) ? N : m_onheap.capacity; }
0071
0072   /// Remove all elements.
0073   ///
0074   /// This will release allocated memory if the vector contains more elements
0075   /// than can be stored in-place.
0076   void clear();
0077   /// Construct an element directly before the given position in the vector.
0078   template<typename... Args>
0079   iterator emplace(const_iterator pos, Args&&... args);
0080   /// Construct an element at the back of the vector and return its reference.
0081   template<typename... Args>
0082   T& emplace_back(Args&&... args);
0083
0084 private:
0085   struct AllocatedStorage {
0086     size_type capacity;
0087     T* data;
0088   };
0089
0090   AllocatedStorage allocate_storage(size_type capacity);
0091   void destruct_inplace();
0092   void destruct_deallocate_onheap();
0093
0094   size_type m_size = 0;
0095   union {
0096     AllocatedStorage m_onheap;
0097     // use 'raw' memory to have full control over constructor/destructor calls
0098     alignas(T) char m_inplace[N * sizeof(T)];
0099   };
0100   Allocator m_alloc;
0101 };
0102
0103 // implementation
0104
0105 template<typename T, std::size_t N, typename Allocator>
0106 inline typename SmallVector<T, N, Allocator>::AllocatedStorage
0107 SmallVector<T, N, Allocator>::allocate_storage(size_type capacity) {
0108   AllocatedStorage s;
0109   s.capacity = capacity;
0110   s.data = std::allocator_traits<Allocator>::allocate(m_alloc, capacity);
0111   return s;
0112 }
0113
0114 // Destruct elements in in-place storage assuming they are valid.
0115 template<typename T, std::size_t N, typename Allocator>
0116 inline void
0117 SmallVector<T, N, Allocator>::destruct_inplace() {
0118   T* ptr = reinterpret_cast<T*>(m_inplace);
0119   for (T* end = ptr + m_size; ptr != end; ++ptr) {
0120     ptr->~T();
0121   }
0122 }
0123
0124 // Destruct and deallocate elements in heap-allocated storage.
0125 template<typename T, std::size_t N, typename Allocator>
0126 inline void
0127 SmallVector<T, N, Allocator>::destruct_deallocate_onheap() {
0128   T* ptr = m_onheap.data;
0129   for (T* end = ptr + m_size; ptr != end; ++ptr) {
0130     std::allocator_traits<Allocator>::destroy(m_alloc, ptr);
0131   }
0132   std::allocator_traits<Allocator>::deallocate(
0133     m_alloc, m_onheap.data, m_onheap.capacity);
0134   m_onheap.capacity = 0;
0135   m_onheap.data = nullptr;
0136 }
0137
0138 template<typename T, std::size_t N, typename Allocator>
0139 inline T& SmallVector<T, N, Allocator>::operator[](size_type idx) {
0140   if (m_size <= N) {
0141     return *(reinterpret_cast<T*>(m_inplace) + idx);
0142   } else {
0143     return m_onheap.data[idx];
0144   }
0145 }
0146
0147 template<typename T, std::size_t N, typename Allocator>
0148 inline const T& SmallVector<T, N, Allocator>::operator[](size_type idx) const {
0149   if (m_size <= N) {
0150     return *(reinterpret_cast<const T*>(m_inplace) + idx);
0151   } else {
0152     return m_onheap.data[idx];
0153   }
0154 }
0155
0156 template<typename T, std::size_t N, typename Allocator>
0157 inline typename SmallVector<T, N, Allocator>::iterator
0158 SmallVector<T, N, Allocator>::begin() {
0159   return (m_size <= N) ? reinterpret_cast<T*>(m_inplace) : m_onheap.data;
0160 }
0161
0162 template<typename T, std::size_t N, typename Allocator>
0163 inline typename SmallVector<T, N, Allocator>::const_iterator
0164 SmallVector<T, N, Allocator>::begin() const {
0165   return (m_size <= N) ? reinterpret_cast<const T*>(m_inplace) : m_onheap.data;
0166 }
0167
0168 template<typename T, std::size_t N, typename Allocator>
0169 inline void
0170 SmallVector<T, N, Allocator>::clear() {
0171   if (m_size <= N) {
0172     destruct_inplace();
0173   } else {
0174     destruct_deallocate_onheap();
0175   }
0176   m_size = 0;
0177 }
0178
0179 template<typename T, std::size_t N, typename Allocator>
0180 template<typename... Args>
0181 typename SmallVector<T, N, Allocator>::iterator
0182 SmallVector<T, N, Allocator>::emplace(const_iterator pos, Args&&... args) {
0183   using AllocatorTraits = std::allocator_traits<Allocator>;
0184
0185   // TODO how, when to check iterator validity?
0186
0187   // available storage is sufficient to hold one extra element.
0188   // existing data after the insertion point needs to be shifted by 1 to the
0189   // right so the new element can be constructed at the given position.
0190   if (size() < capacity()) {
0191     T* i = const_cast<T*>(pos);
0192     T* e = end();
0193
0194     // the underlying storage is raw memory. in order for the move assignment
0195     // to be well-defined, the memory for the additiona element needs to be
0196     // (default-)initialized using placement-new first.
0197     (void)new (e) T();
0198     std::move_backward(i, e, std::next(e));
0199     // insertion points contains moved-from object. move-assignment should be
0200     // valid. placement-new construction would double-initialize.
0201     *i = T(std::forward<Args>(args)...);
0202
0203     m_size += 1;
0204     return i;
0205   }
0206
0207   // available storage is in-sufficient. move to larger heap-allocated storage.
0208   auto storage = allocate_storage(1.3f * (m_size + 1));
0209   T* source = begin();
0210   T* target = storage.data;
0211
0212   // move data before insertion point to the new storage
0213   for (T* e = const_cast<T*>(pos); source != e; ++source, ++target) {
0214     AllocatorTraits::construct(m_alloc, target, std::move(*source));
0215   }
0216   // construct element directly in the new storage
0217   T* insert = target++;
0218   AllocatorTraits::construct(m_alloc, insert, std::forward<Args>(args)...);
0219   // move data after the insertion point to the new storage
0220   for (T* e = end(); source != e; ++source, ++target) {
0221     AllocatorTraits::construct(m_alloc, target, std::move(*source));
0222   }
0223
0224   // clear previous data before replacing it with the next storage
0225   if (m_size == N) {
0226     destruct_inplace();
0227   } else {
0228     destruct_deallocate_onheap();
0229   }
0230   m_onheap = storage;
0231
0232   m_size += 1;
0233   return insert;
0234 }
0235
0236 template<typename T, std::size_t N, typename Allocator>
0237 template<typename... Args>
0238 inline typename SmallVector<T, N, Allocator>::value_type&
0239 SmallVector<T, N, Allocator>::emplace_back(Args&&... args) {
0240   return *emplace(end(), std::forward<Args>(args)...);
0241 }
0242
0243 } // namespace dfe