ECCE @ EIC Software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
dfe_smallvector.hpp
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file dfe_smallvector.hpp
1 // SPDX-License-Identifier: MIT
2 // Copyright 2019 Moritz Kiehn
3 //
4 // Permission is hereby granted, free of charge, to any person obtaining a copy
5 // of this software and associated documentation files (the "Software"), to deal
6 // in the Software without restriction, including without limitation the rights
7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 // copies of the Software, and to permit persons to whom the Software is
9 // furnished to do so, subject to the following conditions:
10 //
11 // The above copyright notice and this permission notice shall be included in
12 // all copies or substantial portions of the Software.
13 //
14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20 // SOFTWARE.
21 
26 
27 #pragma once
28 
29 #include <iterator>
30 #include <memory>
31 
32 namespace dfe {
33 
46 template<typename T, std::size_t N, typename Allocator = std::allocator<T>>
47 class SmallVector {
48 public:
49  using value_type = T;
50  using size_type = std::size_t;
51  using iterator = T*;
52  using const_iterator = const T*;
53 
54  SmallVector() = default;
56 
58  const value_type& operator[](size_type idx) const;
59 
60  iterator begin();
61  iterator end() { return begin() + m_size; }
62  const_iterator begin() const;
63  const_iterator end() const { return begin() + m_size; }
64 
66  bool empty() const { return (m_size == 0); }
68  size_type size() const { return m_size; }
70  size_type capacity() const { return (m_size <= N) ? N : m_onheap.capacity; }
71 
76  void clear();
78  template<typename... Args>
79  iterator emplace(const_iterator pos, Args&&... args);
81  template<typename... Args>
82  T& emplace_back(Args&&... args);
83 
84 private:
87  T* data;
88  };
89 
91  void destruct_inplace();
93 
95  union {
97  // use 'raw' memory to have full control over constructor/destructor calls
98  alignas(T) char m_inplace[N * sizeof(T)];
99  };
100  Allocator m_alloc;
101 };
102 
103 // implementation
104 
105 template<typename T, std::size_t N, typename Allocator>
106 inline typename SmallVector<T, N, Allocator>::AllocatedStorage
109  s.capacity = capacity;
110  s.data = std::allocator_traits<Allocator>::allocate(m_alloc, capacity);
111  return s;
112 }
113 
114 // Destruct elements in in-place storage assuming they are valid.
115 template<typename T, std::size_t N, typename Allocator>
116 inline void
118  T* ptr = reinterpret_cast<T*>(m_inplace);
119  for (T* end = ptr + m_size; ptr != end; ++ptr) {
120  ptr->~T();
121  }
122 }
123 
124 // Destruct and deallocate elements in heap-allocated storage.
125 template<typename T, std::size_t N, typename Allocator>
126 inline void
128  T* ptr = m_onheap.data;
129  for (T* end = ptr + m_size; ptr != end; ++ptr) {
130  std::allocator_traits<Allocator>::destroy(m_alloc, ptr);
131  }
132  std::allocator_traits<Allocator>::deallocate(
133  m_alloc, m_onheap.data, m_onheap.capacity);
134  m_onheap.capacity = 0;
135  m_onheap.data = nullptr;
136 }
137 
138 template<typename T, std::size_t N, typename Allocator>
140  if (m_size <= N) {
141  return *(reinterpret_cast<T*>(m_inplace) + idx);
142  } else {
143  return m_onheap.data[idx];
144  }
145 }
146 
147 template<typename T, std::size_t N, typename Allocator>
149  if (m_size <= N) {
150  return *(reinterpret_cast<const T*>(m_inplace) + idx);
151  } else {
152  return m_onheap.data[idx];
153  }
154 }
155 
156 template<typename T, std::size_t N, typename Allocator>
159  return (m_size <= N) ? reinterpret_cast<T*>(m_inplace) : m_onheap.data;
160 }
161 
162 template<typename T, std::size_t N, typename Allocator>
165  return (m_size <= N) ? reinterpret_cast<const T*>(m_inplace) : m_onheap.data;
166 }
167 
168 template<typename T, std::size_t N, typename Allocator>
169 inline void
171  if (m_size <= N) {
173  } else {
175  }
176  m_size = 0;
177 }
178 
179 template<typename T, std::size_t N, typename Allocator>
180 template<typename... Args>
183  using AllocatorTraits = std::allocator_traits<Allocator>;
184 
185  // TODO how, when to check iterator validity?
186 
187  // available storage is sufficient to hold one extra element.
188  // existing data after the insertion point needs to be shifted by 1 to the
189  // right so the new element can be constructed at the given position.
190  if (size() < capacity()) {
191  T* i = const_cast<T*>(pos);
192  T* e = end();
193 
194  // the underlying storage is raw memory. in order for the move assignment
195  // to be well-defined, the memory for the additiona element needs to be
196  // (default-)initialized using placement-new first.
197  (void)new (e) T();
198  std::move_backward(i, e, std::next(e));
199  // insertion points contains moved-from object. move-assignment should be
200  // valid. placement-new construction would double-initialize.
201  *i = T(std::forward<Args>(args)...);
202 
203  m_size += 1;
204  return i;
205  }
206 
207  // available storage is in-sufficient. move to larger heap-allocated storage.
208  auto storage = allocate_storage(1.3f * (m_size + 1));
209  T* source = begin();
210  T* target = storage.data;
211 
212  // move data before insertion point to the new storage
213  for (T* e = const_cast<T*>(pos); source != e; ++source, ++target) {
214  AllocatorTraits::construct(m_alloc, target, std::move(*source));
215  }
216  // construct element directly in the new storage
217  T* insert = target++;
218  AllocatorTraits::construct(m_alloc, insert, std::forward<Args>(args)...);
219  // move data after the insertion point to the new storage
220  for (T* e = end(); source != e; ++source, ++target) {
221  AllocatorTraits::construct(m_alloc, target, std::move(*source));
222  }
223 
224  // clear previous data before replacing it with the next storage
225  if (m_size == N) {
227  } else {
229  }
230  m_onheap = storage;
231 
232  m_size += 1;
233  return insert;
234 }
235 
236 template<typename T, std::size_t N, typename Allocator>
237 template<typename... Args>
240  return *emplace(end(), std::forward<Args>(args)...);
241 }
242 
243 } // namespace dfe