Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
CompressedStorage.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008-2014 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_COMPRESSED_STORAGE_H
12#define EIGEN_COMPRESSED_STORAGE_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
25template <typename Scalar_, typename StorageIndex_>
26class CompressedStorage {
27 public:
28 using Scalar = Scalar_;
29 using StorageIndex = StorageIndex_;
30
31 CompressedStorage() = default;
32
33 explicit CompressedStorage(Index size) : m_values(0), m_indices(0), m_size(0), m_allocatedSize(0) { resize(size); }
34
35 CompressedStorage(const CompressedStorage& other) : m_values(0), m_indices(0), m_size(0), m_allocatedSize(0) {
36 *this = other;
37 }
38
39 CompressedStorage& operator=(const CompressedStorage& other) {
40 if (this == &other) return *this;
41 resize(other.size());
42 if (other.size() > 0) {
43 internal::smart_copy(other.m_values, other.m_values + m_size, m_values);
44 internal::smart_copy(other.m_indices, other.m_indices + m_size, m_indices);
45 }
46 return *this;
47 }
48
49 void swap(CompressedStorage& other) {
50 std::swap(m_values, other.m_values);
51 std::swap(m_indices, other.m_indices);
52 std::swap(m_size, other.m_size);
53 std::swap(m_allocatedSize, other.m_allocatedSize);
54 }
55
56 ~CompressedStorage() {
57 conditional_aligned_delete_auto<Scalar, true>(m_values, m_allocatedSize);
58 conditional_aligned_delete_auto<StorageIndex, true>(m_indices, m_allocatedSize);
59 }
60
61 void reserve(Index size) {
62 Index newAllocatedSize = m_size + size;
63 if (newAllocatedSize > m_allocatedSize) reallocate(newAllocatedSize);
64 }
65
66 void squeeze() {
67 if (m_allocatedSize > m_size) reallocate(m_size);
68 }
69
70 void resize(Index size, double reserveSizeFactor = 0) {
71 if (m_allocatedSize < size) {
72 // Avoid underflow on the std::min<Index> call by choosing the smaller index type.
73 using SmallerIndexType = std::conditional_t<static_cast<size_t>((std::numeric_limits<Index>::max)()) <
74 static_cast<size_t>((std::numeric_limits<StorageIndex>::max)()),
75 Index, StorageIndex>;
76 Index realloc_size =
77 (std::min<Index>)(NumTraits<SmallerIndexType>::highest(), size + Index(reserveSizeFactor * double(size)));
78 if (realloc_size < size) internal::throw_std_bad_alloc();
79 reallocate(realloc_size);
80 }
81 m_size = size;
82 }
83
84 void append(const Scalar& v, Index i) {
85 Index id = m_size;
86 resize(m_size + 1, 1);
87 m_values[id] = v;
88 m_indices[id] = internal::convert_index<StorageIndex>(i);
89 }
90
91 inline Index size() const { return m_size; }
92 inline Index allocatedSize() const { return m_allocatedSize; }
93 inline void clear() { m_size = 0; }
94
95 const Scalar* valuePtr() const { return m_values; }
96 Scalar* valuePtr() { return m_values; }
97 const StorageIndex* indexPtr() const { return m_indices; }
98 StorageIndex* indexPtr() { return m_indices; }
99
100 inline Scalar& value(Index i) {
101 eigen_internal_assert(m_values != 0);
102 return m_values[i];
103 }
104 inline const Scalar& value(Index i) const {
105 eigen_internal_assert(m_values != 0);
106 return m_values[i];
107 }
108
109 inline StorageIndex& index(Index i) {
110 eigen_internal_assert(m_indices != 0);
111 return m_indices[i];
112 }
113 inline const StorageIndex& index(Index i) const {
114 eigen_internal_assert(m_indices != 0);
115 return m_indices[i];
116 }
117
119 inline Index searchLowerIndex(Index key) const { return searchLowerIndex(0, m_size, key); }
120
122 inline Index searchLowerIndex(Index start, Index end, Index key) const {
123 return static_cast<Index>(std::distance(m_indices, std::lower_bound(m_indices + start, m_indices + end, key)));
124 }
125
128 inline Scalar at(Index key, const Scalar& defaultValue = Scalar(0)) const {
129 if (m_size == 0)
130 return defaultValue;
131 else if (key == m_indices[m_size - 1])
132 return m_values[m_size - 1];
133 // ^^ optimization: let's first check if it is the last coefficient
134 // (very common in high level algorithms)
135 const Index id = searchLowerIndex(0, m_size - 1, key);
136 return ((id < m_size) && (m_indices[id] == key)) ? m_values[id] : defaultValue;
137 }
138
140 inline Scalar atInRange(Index start, Index end, Index key, const Scalar& defaultValue = Scalar(0)) const {
141 if (start >= end)
142 return defaultValue;
143 else if (end > start && key == m_indices[end - 1])
144 return m_values[end - 1];
145 // ^^ optimization: let's first check if it is the last coefficient
146 // (very common in high level algorithms)
147 const Index id = searchLowerIndex(start, end - 1, key);
148 return ((id < end) && (m_indices[id] == key)) ? m_values[id] : defaultValue;
149 }
150
154 inline Scalar& atWithInsertion(Index key, const Scalar& defaultValue = Scalar(0)) {
155 Index id = searchLowerIndex(0, m_size, key);
156 if (id >= m_size || m_indices[id] != key) {
157 if (m_allocatedSize < m_size + 1) {
158 Index newAllocatedSize = 2 * (m_size + 1);
159 reallocate(newAllocatedSize);
160 }
161 if (m_size > id) {
162 internal::move_or_copy_backward(m_values + id, m_values + m_size, m_values + m_size + 1);
163 std::move_backward(m_indices + id, m_indices + m_size, m_indices + m_size + 1);
164 }
165 m_size++;
166 m_indices[id] = internal::convert_index<StorageIndex>(key);
167 m_values[id] = defaultValue;
168 }
169 return m_values[id];
170 }
171
172 protected:
173 inline void reallocate(Index size) {
174#ifdef EIGEN_SPARSE_COMPRESSED_STORAGE_REALLOCATE_PLUGIN
175 EIGEN_SPARSE_COMPRESSED_STORAGE_REALLOCATE_PLUGIN
176#endif
177 eigen_internal_assert(size != m_allocatedSize);
178 EIGEN_IF_CONSTEXPR (!NumTraits<Scalar>::RequireInitialization && !NumTraits<StorageIndex>::RequireInitialization &&
179 std::is_trivially_copyable<Scalar>::value && std::is_trivially_copyable<StorageIndex>::value) {
180 const Index old_capacity = m_allocatedSize;
181 m_values = conditional_aligned_realloc_new_auto<Scalar, true>(m_values, size, old_capacity);
182 EIGEN_TRY { m_indices = conditional_aligned_realloc_new_auto<StorageIndex, true>(m_indices, size, old_capacity); }
183 EIGEN_CATCH(...) {
184 // The value buffer may have shrunk; never advertise more capacity than either buffer holds.
185 m_allocatedSize = (std::min)(old_capacity, size);
186 EIGEN_THROW;
187 }
188 m_allocatedSize = size;
189 return;
190 }
191 // Prepare indices first: once values have moved, no allocation may throw before committing the capacity.
192 StorageIndex* new_indices = conditional_aligned_new_auto<StorageIndex, true>(size);
193 EIGEN_TRY {
194 const Index copy_size = (std::min)(m_size, size);
195 if (copy_size > 0) internal::smart_copy(m_indices, m_indices + copy_size, new_indices);
196 EIGEN_IF_CONSTEXPR (NumTraits<Scalar>::RequireInitialization) {
197 // Every slot of the old buffer holds a constructed Scalar, and every slot of the new one must.
198 m_values = conditional_aligned_realloc_new_auto<Scalar, true>(m_values, size, m_allocatedSize);
199 } else {
200 // Slots past m_size hold no entry and may be uninitialized, so only the stored entries are relocated.
201 Scalar* new_values = conditional_aligned_new_auto<Scalar, true>(size);
202 EIGEN_TRY { move_construct_elements_of_array(new_values, m_values, static_cast<std::size_t>(copy_size)); }
203 EIGEN_CATCH(...) {
204 conditional_aligned_delete_auto<Scalar, true>(new_values, size);
205 EIGEN_THROW;
206 }
207 conditional_aligned_delete_auto<Scalar, true>(m_values, m_allocatedSize);
208 m_values = new_values;
209 }
210 }
211 EIGEN_CATCH(...) {
212 conditional_aligned_delete_auto<StorageIndex, true>(new_indices, size);
213 EIGEN_THROW;
214 }
215 conditional_aligned_delete_auto<StorageIndex, true>(m_indices, m_allocatedSize);
216 m_indices = new_indices;
217 m_allocatedSize = size;
218 }
219
220 protected:
221 Scalar* m_values = nullptr;
222 StorageIndex* m_indices = nullptr;
223 Index m_size = 0;
224 Index m_allocatedSize = 0;
225};
226
227} // end namespace internal
228
229} // end namespace Eigen
230
231#endif // EIGEN_COMPRESSED_STORAGE_H