Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
AmbiVector.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_AMBIVECTOR_H
12#define EIGEN_AMBIVECTOR_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
26template <typename Scalar_, typename StorageIndex_>
27class AmbiVector {
28 public:
29 using Scalar = Scalar_;
30 using StorageIndex = StorageIndex_;
31
32 explicit AmbiVector(Index size)
33 : m_buffer(0),
34 m_zero(0),
35 m_size(0),
36 m_end(0),
37 m_allocatedSize(0),
38 m_allocatedElements(0),
39 m_denseConstructed(0),
40 m_mode(-1) {
41 resize(size);
42 }
43
44 void init(double estimatedDensity);
45 void init(int mode);
46
47 Index nonZeros() const;
48
50 void setBounds(Index start, Index end) {
51 m_start = convert_index(start);
52 m_end = convert_index(end);
53 }
54
55 void setZero();
56
57 void restart();
58 Scalar& coeffRef(Index i);
59 Scalar& coeff(Index i);
60
61 class Iterator;
62
63 ~AmbiVector() {
64 destructElements();
65 internal::aligned_free(m_buffer);
66 }
67
68 void resize(Index size) {
69 if (m_allocatedSize < size) reallocate(size);
70 m_size = convert_index(size);
71 // The bounds describe a sub-vector of the old size, so they cannot survive a
72 // resize that reuses the allocation: a smaller one would leave the iterators
73 // running past the end, a larger one would stop them short of it.
74 m_start = 0;
75 m_end = m_size;
76 }
77
78 StorageIndex size() const { return m_size; }
79
80 protected:
81 // element type of the linked list
82 struct ListEl {
83 StorageIndex next;
84 StorageIndex index;
85 Scalar value;
86 };
87
88 StorageIndex convert_index(Index idx) { return internal::convert_index<StorageIndex>(idx); }
89
90 ListEl* listElements() { return static_cast<ListEl*>(static_cast<void*>(m_buffer)); }
91 const ListEl* listElements() const { return static_cast<const ListEl*>(static_cast<const void*>(m_buffer)); }
92
93 void reallocate(Index size) {
94 // if the size of the matrix is not too large, let's allocate a bit more than needed such
95 // that we can handle dense vector even in sparse mode.
96 destructElements();
97 internal::aligned_free(m_buffer);
98 Index allocSize;
99 if (size < 1000) {
100 allocSize = numext::div_ceil<Index>(size * sizeof(ListEl), sizeof(Scalar));
101 m_allocatedElements = convert_index((allocSize * sizeof(Scalar)) / sizeof(ListEl));
102 } else {
103 allocSize = size;
104 m_allocatedElements = convert_index((size * sizeof(Scalar)) / sizeof(ListEl));
105 }
106 // The buffer is raw storage: init() constructs the elements the mode needs.
107 m_buffer = static_cast<Scalar*>(internal::aligned_malloc(allocSize * sizeof(Scalar)));
108 m_allocatedSize = convert_index(allocSize);
109 m_mode = -1;
110 }
111
112 void reallocateSparse() {
113 Index copyElements = m_llSize;
114 StorageIndex newAllocatedElements = (std::min)(StorageIndex(m_allocatedElements * 1.5), m_size);
115 Index allocSize = newAllocatedElements * sizeof(ListEl);
116 allocSize = numext::div_ceil<Index>(allocSize, sizeof(Scalar));
117 Scalar* newBuffer = static_cast<Scalar*>(internal::aligned_malloc(allocSize * sizeof(Scalar)));
118 ListEl* newElements = static_cast<ListEl*>(static_cast<void*>(newBuffer));
119 // A throwing move leaves the nodes where they are, so the vector stays
120 // destructible; the new buffer, which nothing points to yet, must be
121 // released, and the capacity must not describe it either.
122 EIGEN_TRY { internal::move_construct_elements_of_array(newElements, listElements(), copyElements); }
123 EIGEN_CATCH(...) {
124 internal::aligned_free(newBuffer);
125 EIGEN_THROW;
126 }
127 internal::destruct_elements_of_array(listElements(), copyElements);
128 internal::aligned_free(m_buffer);
129 m_buffer = newBuffer;
130 m_allocatedElements = newAllocatedElements;
131 m_allocatedSize = convert_index(allocSize);
132 }
133
134 // Constructs a node holding a zero coefficient. Initializing the coefficient
135 // as part of the construction keeps it atomic: a throwing Scalar leaves no
136 // ListEl behind, so the caller can commit the node to the list - and to
137 // m_llSize, which is what destructElements() destroys - only once it exists.
138 static ListEl* constructListEl(ListEl* dst, StorageIndex index, StorageIndex next) {
139 return ::new (static_cast<void*>(dst)) ListEl{next, index, Scalar(0)};
140 }
141
142 // Destroy whatever elements are currently alive in the raw buffer.
143 void destructElements() {
144 if (m_mode == IsDense) {
145 internal::destruct_elements_of_array(m_buffer, m_denseConstructed);
146 m_denseConstructed = 0;
147 } else if (m_mode == IsSparse) {
148 internal::destruct_elements_of_array(listElements(), m_llSize);
149 m_llSize = 0;
150 }
151 }
152
153 // used to store data in both modes
154 Scalar* m_buffer;
155 Scalar m_zero;
156 StorageIndex m_size;
157 StorageIndex m_start;
158 StorageIndex m_end;
159 StorageIndex m_allocatedSize;
160 StorageIndex m_allocatedElements;
161 StorageIndex m_denseConstructed; // number of live Scalar objects in dense mode
162 StorageIndex m_mode;
163
164 // linked list mode
165 StorageIndex m_llStart;
166 StorageIndex m_llCurrent;
167 StorageIndex m_llSize;
168};
169
171template <typename Scalar_, typename StorageIndex_>
172Index AmbiVector<Scalar_, StorageIndex_>::nonZeros() const {
173 if (m_mode == IsSparse)
174 return m_llSize;
175 else
176 return m_end - m_start;
177}
178
179template <typename Scalar_, typename StorageIndex_>
180void AmbiVector<Scalar_, StorageIndex_>::init(double estimatedDensity) {
181 if (estimatedDensity > 0.1)
182 init(IsDense);
183 else
184 init(IsSparse);
185}
186
187template <typename Scalar_, typename StorageIndex_>
188void AmbiVector<Scalar_, StorageIndex_>::init(int mode) {
189 if (mode != m_mode) {
190 destructElements();
191 m_mode = convert_index(mode);
192 } else if (m_mode == IsSparse) {
193 // Re-initializing in sparse mode discards the previous list.
194 internal::destruct_elements_of_array(listElements(), m_llSize);
195 }
196 if (m_mode == IsDense && m_denseConstructed < m_size) {
197 // Construct the dense coefficients this mode reads and writes; they stay
198 // alive across subsequent dense inits, like the values they carry.
199 internal::default_construct_elements_of_array(m_buffer + m_denseConstructed, m_size - m_denseConstructed);
200 m_denseConstructed = m_size;
201 }
202 // This is only necessary in sparse mode, but we set these unconditionally to avoid some maybe-uninitialized warnings
203 // if (m_mode==IsSparse)
204 {
205 m_llSize = 0;
206 m_llStart = -1;
207 }
208}
209
215template <typename Scalar_, typename StorageIndex_>
216void AmbiVector<Scalar_, StorageIndex_>::restart() {
217 m_llCurrent = m_llStart;
218}
219
221template <typename Scalar_, typename StorageIndex_>
222void AmbiVector<Scalar_, StorageIndex_>::setZero() {
223 if (m_mode == IsDense) {
224 for (Index i = m_start; i < m_end; ++i) m_buffer[i] = Scalar(0);
225 } else {
226 eigen_assert(m_mode == IsSparse);
227 // The nodes being dropped own their coefficients, and a later coeffRef()
228 // constructs its node in place over this storage.
229 internal::destruct_elements_of_array(listElements(), m_llSize);
230 m_llSize = 0;
231 m_llStart = -1;
232 }
233}
234
235template <typename Scalar_, typename StorageIndex_>
236Scalar_& AmbiVector<Scalar_, StorageIndex_>::coeffRef(Index i) {
237 if (m_mode == IsDense)
238 return m_buffer[i];
239 else {
240 ListEl* EIGEN_RESTRICT llElements = listElements();
241 // TODO: factor out the following code to reduce code generation
242 eigen_assert(m_mode == IsSparse);
243 if (m_llSize == 0) {
244 // this is the first element
245 ListEl& el = *constructListEl(llElements, convert_index(i), -1);
246 m_llStart = 0;
247 m_llCurrent = 0;
248 m_llSize = 1;
249 return el.value;
250 } else if (i < llElements[m_llStart].index) {
251 // this is going to be the new first element of the list
252 if (m_llSize >= m_allocatedElements) {
253 reallocateSparse();
254 llElements = listElements();
255 }
256 ListEl& el = *constructListEl(llElements + m_llSize, convert_index(i), m_llStart);
257 m_llStart = m_llSize;
258 m_llCurrent = m_llStart;
259 ++m_llSize;
260 return el.value;
261 } else {
262 StorageIndex nextel = llElements[m_llCurrent].next;
263 eigen_assert(i >= llElements[m_llCurrent].index &&
264 "you must call restart() before inserting an element with lower or equal index");
265 while (nextel >= 0 && llElements[nextel].index <= i) {
266 m_llCurrent = nextel;
267 nextel = llElements[nextel].next;
268 }
269
270 if (llElements[m_llCurrent].index == i) {
271 // the coefficient already exists and we found it !
272 return llElements[m_llCurrent].value;
273 } else {
274 if (m_llSize >= m_allocatedElements) {
275 reallocateSparse();
276 llElements = listElements();
277 }
278 eigen_internal_assert(m_llSize < m_allocatedElements && "internal error: overflow in sparse mode");
279 // let's insert a new coefficient
280 ListEl& el = *constructListEl(llElements + m_llSize, convert_index(i), llElements[m_llCurrent].next);
281 llElements[m_llCurrent].next = m_llSize;
282 ++m_llSize;
283 return el.value;
284 }
285 }
286 }
287}
288
289template <typename Scalar_, typename StorageIndex_>
290Scalar_& AmbiVector<Scalar_, StorageIndex_>::coeff(Index i) {
291 if (m_mode == IsDense)
292 return m_buffer[i];
293 else {
294 ListEl* EIGEN_RESTRICT llElements = listElements();
295 eigen_assert(m_mode == IsSparse);
296 if ((m_llSize == 0) || (i < llElements[m_llStart].index)) {
297 return m_zero;
298 } else {
299 Index elid = m_llStart;
300 while (elid >= 0 && llElements[elid].index < i) elid = llElements[elid].next;
301
302 if (elid >= 0 && llElements[elid].index == i)
303 return llElements[elid].value;
304 else
305 return m_zero;
306 }
307 }
308}
309
311template <typename Scalar_, typename StorageIndex_>
312class AmbiVector<Scalar_, StorageIndex_>::Iterator {
313 public:
314 using Scalar = Scalar_;
315 using RealScalar = typename NumTraits<Scalar>::Real;
316
323 explicit Iterator(const AmbiVector& vec, const RealScalar& epsilon = 0) : m_vector(vec) {
324 m_epsilon = epsilon;
325 m_isDense = m_vector.m_mode == IsDense;
326 if (m_isDense) {
327 m_currentEl = 0; // this is to avoid a compilation warning
328 m_cachedValue = 0; // this is to avoid a compilation warning
329 m_cachedIndex = m_vector.m_start - 1;
330 ++(*this);
331 } else {
332 const ListEl* EIGEN_RESTRICT llElements = m_vector.listElements();
333 m_currentEl = m_vector.m_llStart;
334 while (m_currentEl >= 0 && numext::abs(llElements[m_currentEl].value) <= m_epsilon)
335 m_currentEl = llElements[m_currentEl].next;
336 if (m_currentEl < 0) {
337 m_cachedValue = 0; // this is to avoid a compilation warning
338 m_cachedIndex = -1;
339 } else {
340 m_cachedIndex = llElements[m_currentEl].index;
341 m_cachedValue = llElements[m_currentEl].value;
342 }
343 }
344 }
345
346 StorageIndex index() const { return m_cachedIndex; }
347 Scalar value() const { return m_cachedValue; }
348
349 operator bool() const { return m_cachedIndex >= 0; }
350
351 Iterator& operator++() {
352 if (m_isDense) {
353 do {
354 ++m_cachedIndex;
355 } while (m_cachedIndex < m_vector.m_end && numext::abs(m_vector.m_buffer[m_cachedIndex]) <= m_epsilon);
356 if (m_cachedIndex < m_vector.m_end)
357 m_cachedValue = m_vector.m_buffer[m_cachedIndex];
358 else
359 m_cachedIndex = -1;
360 } else {
361 const ListEl* EIGEN_RESTRICT llElements = m_vector.listElements();
362 do {
363 m_currentEl = llElements[m_currentEl].next;
364 } while (m_currentEl >= 0 && numext::abs(llElements[m_currentEl].value) <= m_epsilon);
365 if (m_currentEl < 0) {
366 m_cachedIndex = -1;
367 } else {
368 m_cachedIndex = llElements[m_currentEl].index;
369 m_cachedValue = llElements[m_currentEl].value;
370 }
371 }
372 return *this;
373 }
374
375 protected:
376 const AmbiVector& m_vector; // the target vector
377 StorageIndex m_currentEl; // the current element in sparse/linked-list mode
378 RealScalar m_epsilon; // epsilon used to prune zero coefficients
379 StorageIndex m_cachedIndex; // current coordinate
380 Scalar m_cachedValue; // current value
381 bool m_isDense; // mode of the vector
382};
383
384} // end namespace internal
385
386} // end namespace Eigen
387
388#endif // EIGEN_AMBIVECTOR_H
Definition AmbiVector.h:312
Iterator(const AmbiVector &vec, const RealScalar &epsilon=0)
Definition AmbiVector.h:323