/src/re2/re2/sparse_array.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright 2006 The RE2 Authors. All Rights Reserved. |
2 | | // Use of this source code is governed by a BSD-style |
3 | | // license that can be found in the LICENSE file. |
4 | | |
5 | | #ifndef RE2_SPARSE_ARRAY_H_ |
6 | | #define RE2_SPARSE_ARRAY_H_ |
7 | | |
8 | | // DESCRIPTION |
9 | | // |
10 | | // SparseArray<T>(m) is a map from integers in [0, m) to T values. |
11 | | // It requires (sizeof(T)+sizeof(int))*m memory, but it provides |
12 | | // fast iteration through the elements in the array and fast clearing |
13 | | // of the array. The array has a concept of certain elements being |
14 | | // uninitialized (having no value). |
15 | | // |
16 | | // Insertion and deletion are constant time operations. |
17 | | // |
18 | | // Allocating the array is a constant time operation |
19 | | // when memory allocation is a constant time operation. |
20 | | // |
21 | | // Clearing the array is a constant time operation (unusual!). |
22 | | // |
23 | | // Iterating through the array is an O(n) operation, where n |
24 | | // is the number of items in the array (not O(m)). |
25 | | // |
26 | | // The array iterator visits entries in the order they were first |
27 | | // inserted into the array. It is safe to add items to the array while |
28 | | // using an iterator: the iterator will visit indices added to the array |
29 | | // during the iteration, but will not re-visit indices whose values |
30 | | // change after visiting. Thus SparseArray can be a convenient |
31 | | // implementation of a work queue. |
32 | | // |
33 | | // The SparseArray implementation is NOT thread-safe. It is up to the |
34 | | // caller to make sure only one thread is accessing the array. (Typically |
35 | | // these arrays are temporary values and used in situations where speed is |
36 | | // important.) |
37 | | // |
38 | | // The SparseArray interface does not present all the usual STL bells and |
39 | | // whistles. |
40 | | // |
41 | | // Implemented with reference to Briggs & Torczon, An Efficient |
42 | | // Representation for Sparse Sets, ACM Letters on Programming Languages |
43 | | // and Systems, Volume 2, Issue 1-4 (March-Dec. 1993), pp. 59-69. |
44 | | // |
45 | | // Briggs & Torczon popularized this technique, but it had been known |
46 | | // long before their paper. They point out that Aho, Hopcroft, and |
47 | | // Ullman's 1974 Design and Analysis of Computer Algorithms and Bentley's |
48 | | // 1986 Programming Pearls both hint at the technique in exercises to the |
49 | | // reader (in Aho & Hopcroft, exercise 2.12; in Bentley, column 1 |
50 | | // exercise 8). |
51 | | // |
52 | | // Briggs & Torczon describe a sparse set implementation. I have |
53 | | // trivially generalized it to create a sparse array (actually the original |
54 | | // target of the AHU and Bentley exercises). |
55 | | |
56 | | // IMPLEMENTATION |
57 | | // |
58 | | // SparseArray is an array dense_ and an array sparse_ of identical size. |
59 | | // At any point, the number of elements in the sparse array is size_. |
60 | | // |
61 | | // The array dense_ contains the size_ elements in the sparse array (with |
62 | | // their indices), |
63 | | // in the order that the elements were first inserted. This array is dense: |
64 | | // the size_ pairs are dense_[0] through dense_[size_-1]. |
65 | | // |
66 | | // The array sparse_ maps from indices in [0,m) to indices in [0,size_). |
67 | | // For indices present in the array, dense_[sparse_[i]].index_ == i. |
68 | | // For indices not present in the array, sparse_ can contain any value at all, |
69 | | // perhaps outside the range [0, size_) but perhaps not. |
70 | | // |
71 | | // The lax requirement on sparse_ values makes clearing the array very easy: |
72 | | // set size_ to 0. Lookups are slightly more complicated. |
73 | | // An index i has a value in the array if and only if: |
74 | | // sparse_[i] is in [0, size_) AND |
75 | | // dense_[sparse_[i]].index_ == i. |
76 | | // If both these properties hold, only then it is safe to refer to |
77 | | // dense_[sparse_[i]].value_ |
78 | | // as the value associated with index i. |
79 | | // |
80 | | // To insert a new entry, set sparse_[i] to size_, |
81 | | // initialize dense_[size_], and then increment size_. |
82 | | // |
83 | | // To make the sparse array as efficient as possible for non-primitive types, |
84 | | // elements may or may not be destroyed when they are deleted from the sparse |
85 | | // array through a call to resize(). They immediately become inaccessible, but |
86 | | // they are only guaranteed to be destroyed when the SparseArray destructor is |
87 | | // called. |
88 | | // |
89 | | // A moved-from SparseArray will be empty. |
90 | | |
91 | | // Doing this simplifies the logic below. |
92 | | #ifndef __has_feature |
93 | | #define __has_feature(x) 0 |
94 | | #endif |
95 | | |
96 | | #include <assert.h> |
97 | | #include <stdint.h> |
98 | | #if __has_feature(memory_sanitizer) |
99 | | #include <sanitizer/msan_interface.h> |
100 | | #endif |
101 | | #include <algorithm> |
102 | | #include <memory> |
103 | | #include <utility> |
104 | | |
105 | | #include "re2/pod_array.h" |
106 | | |
107 | | namespace re2 { |
108 | | |
109 | | template<typename Value> |
110 | | class SparseArray { |
111 | | public: |
112 | 2.67k | SparseArray(); |
113 | | explicit SparseArray(int max_size); |
114 | | ~SparseArray(); |
115 | | |
116 | | // IndexValue pairs: exposed in SparseArray::iterator. |
117 | | class IndexValue; |
118 | | |
119 | | typedef IndexValue* iterator; |
120 | | typedef const IndexValue* const_iterator; |
121 | | |
122 | | SparseArray(const SparseArray& src); |
123 | | SparseArray(SparseArray&& src); |
124 | | |
125 | | SparseArray& operator=(const SparseArray& src); |
126 | | SparseArray& operator=(SparseArray&& src); |
127 | | |
128 | | // Return the number of entries in the array. |
129 | 5.69M | int size() const { |
130 | 5.69M | return size_; |
131 | 5.69M | } re2::SparseArray<re2::NFA::Thread*>::size() const Line | Count | Source | 129 | 50.6k | int size() const { | 130 | 50.6k | return size_; | 131 | 50.6k | } |
re2::SparseArray<int>::size() const Line | Count | Source | 129 | 5.64M | int size() const { | 130 | 5.64M | return size_; | 131 | 5.64M | } |
|
132 | | |
133 | | // Indicate whether the array is empty. |
134 | | int empty() const { |
135 | | return size_ == 0; |
136 | | } |
137 | | |
138 | | // Iterate over the array. |
139 | 4.91M | iterator begin() { |
140 | 4.91M | return dense_.data(); |
141 | 4.91M | } re2::SparseArray<int>::begin() Line | Count | Source | 139 | 4.86M | iterator begin() { | 140 | 4.86M | return dense_.data(); | 141 | 4.86M | } |
re2::SparseArray<re2::NFA::Thread*>::begin() Line | Count | Source | 139 | 55.4k | iterator begin() { | 140 | 55.4k | return dense_.data(); | 141 | 55.4k | } |
|
142 | 68.1M | iterator end() { |
143 | 68.1M | return dense_.data() + size_; |
144 | 68.1M | } re2::SparseArray<int>::end() Line | Count | Source | 142 | 11.3M | iterator end() { | 143 | 11.3M | return dense_.data() + size_; | 144 | 11.3M | } |
re2::SparseArray<re2::NFA::Thread*>::end() Line | Count | Source | 142 | 56.7M | iterator end() { | 143 | 56.7M | return dense_.data() + size_; | 144 | 56.7M | } |
|
145 | | |
146 | | const_iterator begin() const { |
147 | | return dense_.data(); |
148 | | } |
149 | | const_iterator end() const { |
150 | | return dense_.data() + size_; |
151 | | } |
152 | | |
153 | | // Change the maximum size of the array. |
154 | | // Invalidates all iterators. |
155 | | void resize(int new_max_size); |
156 | | |
157 | | // Return the maximum size of the array. |
158 | | // Indices can be in the range [0, max_size). |
159 | 1.43G | int max_size() const { |
160 | 1.43G | if (dense_.data() != NULL) |
161 | 1.43G | return dense_.size(); |
162 | 5.34k | else |
163 | 5.34k | return 0; |
164 | 1.43G | } re2::SparseArray<re2::NFA::Thread*>::max_size() const Line | Count | Source | 159 | 114M | int max_size() const { | 160 | 114M | if (dense_.data() != NULL) | 161 | 114M | return dense_.size(); | 162 | 5.34k | else | 163 | 5.34k | return 0; | 164 | 114M | } |
re2::SparseArray<int>::max_size() const Line | Count | Source | 159 | 1.32G | int max_size() const { | 160 | 1.32G | if (dense_.data() != NULL) | 161 | 1.32G | return dense_.size(); | 162 | 0 | else | 163 | 0 | return 0; | 164 | 1.32G | } |
|
165 | | |
166 | | // Clear the array. |
167 | 176k | void clear() { |
168 | 176k | size_ = 0; |
169 | 176k | } re2::SparseArray<re2::NFA::Thread*>::clear() Line | Count | Source | 167 | 158k | void clear() { | 168 | 158k | size_ = 0; | 169 | 158k | } |
re2::SparseArray<int>::clear() Line | Count | Source | 167 | 17.7k | void clear() { | 168 | 17.7k | size_ = 0; | 169 | 17.7k | } |
|
170 | | |
171 | | // Check whether index i is in the array. |
172 | | bool has_index(int i) const; |
173 | | |
174 | | // Comparison function for sorting. |
175 | | // Can sort the sparse array so that future iterations |
176 | | // will visit indices in increasing order using |
177 | | // std::sort(arr.begin(), arr.end(), arr.less); |
178 | | static bool less(const IndexValue& a, const IndexValue& b); |
179 | | |
180 | | public: |
181 | | // Set the value at index i to v. |
182 | | iterator set(int i, const Value& v) { |
183 | | return SetInternal(true, i, v); |
184 | | } |
185 | | |
186 | | // Set the value at new index i to v. |
187 | | // Fast but unsafe: only use if has_index(i) is false. |
188 | 80.9M | iterator set_new(int i, const Value& v) { |
189 | 80.9M | return SetInternal(false, i, v); |
190 | 80.9M | } re2::SparseArray<re2::NFA::Thread*>::set_new(int, re2::NFA::Thread* const&) Line | Count | Source | 188 | 56.7M | iterator set_new(int i, const Value& v) { | 189 | 56.7M | return SetInternal(false, i, v); | 190 | 56.7M | } |
re2::SparseArray<int>::set_new(int, int const&) Line | Count | Source | 188 | 24.1M | iterator set_new(int i, const Value& v) { | 189 | 24.1M | return SetInternal(false, i, v); | 190 | 24.1M | } |
|
191 | | |
192 | | // Set the value at index i to v. |
193 | | // Fast but unsafe: only use if has_index(i) is true. |
194 | | iterator set_existing(int i, const Value& v) { |
195 | | return SetExistingInternal(i, v); |
196 | | } |
197 | | |
198 | | // Get the value at index i. |
199 | | // Fast but unsafe: only use if has_index(i) is true. |
200 | 686M | Value& get_existing(int i) { |
201 | 686M | assert(has_index(i)); |
202 | 686M | return dense_[sparse_[i]].value_; |
203 | 686M | } re2::SparseArray<re2::NFA::Thread*>::get_existing(int) Line | Count | Source | 200 | 56.7M | Value& get_existing(int i) { | 201 | 56.7M | assert(has_index(i)); | 202 | 56.7M | return dense_[sparse_[i]].value_; | 203 | 56.7M | } |
re2::SparseArray<int>::get_existing(int) Line | Count | Source | 200 | 629M | Value& get_existing(int i) { | 201 | 629M | assert(has_index(i)); | 202 | 629M | return dense_[sparse_[i]].value_; | 203 | 629M | } |
|
204 | | const Value& get_existing(int i) const { |
205 | | assert(has_index(i)); |
206 | | return dense_[sparse_[i]].value_; |
207 | | } |
208 | | |
209 | | private: |
210 | 80.9M | iterator SetInternal(bool allow_existing, int i, const Value& v) { |
211 | 80.9M | DebugCheckInvariants(); |
212 | 80.9M | if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(max_size())) { |
213 | 0 | assert(false && "illegal index"); |
214 | | // Semantically, end() would be better here, but we already know |
215 | | // the user did something stupid, so begin() insulates them from |
216 | | // dereferencing an invalid pointer. |
217 | 0 | return begin(); |
218 | 0 | } |
219 | 80.9M | if (!allow_existing) { |
220 | 80.9M | assert(!has_index(i)); |
221 | 80.9M | create_index(i); |
222 | 80.9M | } else { |
223 | 0 | if (!has_index(i)) |
224 | 0 | create_index(i); |
225 | 0 | } |
226 | 80.9M | return SetExistingInternal(i, v); |
227 | 80.9M | } re2::SparseArray<re2::NFA::Thread*>::SetInternal(bool, int, re2::NFA::Thread* const&) Line | Count | Source | 210 | 56.7M | iterator SetInternal(bool allow_existing, int i, const Value& v) { | 211 | 56.7M | DebugCheckInvariants(); | 212 | 56.7M | if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(max_size())) { | 213 | 0 | assert(false && "illegal index"); | 214 | | // Semantically, end() would be better here, but we already know | 215 | | // the user did something stupid, so begin() insulates them from | 216 | | // dereferencing an invalid pointer. | 217 | 0 | return begin(); | 218 | 0 | } | 219 | 56.7M | if (!allow_existing) { | 220 | 56.7M | assert(!has_index(i)); | 221 | 56.7M | create_index(i); | 222 | 56.7M | } else { | 223 | 0 | if (!has_index(i)) | 224 | 0 | create_index(i); | 225 | 0 | } | 226 | 56.7M | return SetExistingInternal(i, v); | 227 | 56.7M | } |
re2::SparseArray<int>::SetInternal(bool, int, int const&) Line | Count | Source | 210 | 24.1M | iterator SetInternal(bool allow_existing, int i, const Value& v) { | 211 | 24.1M | DebugCheckInvariants(); | 212 | 24.1M | if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(max_size())) { | 213 | 0 | assert(false && "illegal index"); | 214 | | // Semantically, end() would be better here, but we already know | 215 | | // the user did something stupid, so begin() insulates them from | 216 | | // dereferencing an invalid pointer. | 217 | 0 | return begin(); | 218 | 0 | } | 219 | 24.1M | if (!allow_existing) { | 220 | 24.1M | assert(!has_index(i)); | 221 | 24.1M | create_index(i); | 222 | 24.1M | } else { | 223 | 0 | if (!has_index(i)) | 224 | 0 | create_index(i); | 225 | 0 | } | 226 | 24.1M | return SetExistingInternal(i, v); | 227 | 24.1M | } |
|
228 | | |
229 | 80.9M | iterator SetExistingInternal(int i, const Value& v) { |
230 | 80.9M | DebugCheckInvariants(); |
231 | 80.9M | assert(has_index(i)); |
232 | 80.9M | dense_[sparse_[i]].value_ = v; |
233 | 80.9M | DebugCheckInvariants(); |
234 | 80.9M | return dense_.data() + sparse_[i]; |
235 | 80.9M | } re2::SparseArray<re2::NFA::Thread*>::SetExistingInternal(int, re2::NFA::Thread* const&) Line | Count | Source | 229 | 56.7M | iterator SetExistingInternal(int i, const Value& v) { | 230 | 56.7M | DebugCheckInvariants(); | 231 | 56.7M | assert(has_index(i)); | 232 | 56.7M | dense_[sparse_[i]].value_ = v; | 233 | 56.7M | DebugCheckInvariants(); | 234 | 56.7M | return dense_.data() + sparse_[i]; | 235 | 56.7M | } |
re2::SparseArray<int>::SetExistingInternal(int, int const&) Line | Count | Source | 229 | 24.1M | iterator SetExistingInternal(int i, const Value& v) { | 230 | 24.1M | DebugCheckInvariants(); | 231 | 24.1M | assert(has_index(i)); | 232 | 24.1M | dense_[sparse_[i]].value_ = v; | 233 | 24.1M | DebugCheckInvariants(); | 234 | 24.1M | return dense_.data() + sparse_[i]; | 235 | 24.1M | } |
|
236 | | |
237 | | // Add the index i to the array. |
238 | | // Only use if has_index(i) is known to be false. |
239 | | // Since it doesn't set the value associated with i, |
240 | | // this function is private, only intended as a helper |
241 | | // for other methods. |
242 | | void create_index(int i); |
243 | | |
244 | | // In debug mode, verify that some invariant properties of the class |
245 | | // are being maintained. This is called at the end of the constructor |
246 | | // and at the beginning and end of all public non-const member functions. |
247 | | void DebugCheckInvariants() const; |
248 | | |
249 | | // Initializes memory for elements [min, max). |
250 | 59.8k | void MaybeInitializeMemory(int min, int max) { |
251 | | #if __has_feature(memory_sanitizer) |
252 | | __msan_unpoison(sparse_.data() + min, (max - min) * sizeof sparse_[0]); |
253 | | #elif defined(RE2_ON_VALGRIND) |
254 | | for (int i = min; i < max; i++) { |
255 | | sparse_[i] = 0xababababU; |
256 | | } |
257 | | #endif |
258 | 59.8k | } re2::SparseArray<int>::MaybeInitializeMemory(int, int) Line | Count | Source | 250 | 57.1k | void MaybeInitializeMemory(int min, int max) { | 251 | | #if __has_feature(memory_sanitizer) | 252 | | __msan_unpoison(sparse_.data() + min, (max - min) * sizeof sparse_[0]); | 253 | | #elif defined(RE2_ON_VALGRIND) | 254 | | for (int i = min; i < max; i++) { | 255 | | sparse_[i] = 0xababababU; | 256 | | } | 257 | | #endif | 258 | 57.1k | } |
re2::SparseArray<re2::NFA::Thread*>::MaybeInitializeMemory(int, int) Line | Count | Source | 250 | 2.67k | void MaybeInitializeMemory(int min, int max) { | 251 | | #if __has_feature(memory_sanitizer) | 252 | | __msan_unpoison(sparse_.data() + min, (max - min) * sizeof sparse_[0]); | 253 | | #elif defined(RE2_ON_VALGRIND) | 254 | | for (int i = min; i < max; i++) { | 255 | | sparse_[i] = 0xababababU; | 256 | | } | 257 | | #endif | 258 | 2.67k | } |
|
259 | | |
260 | | int size_ = 0; |
261 | | PODArray<int> sparse_; |
262 | | PODArray<IndexValue> dense_; |
263 | | }; |
264 | | |
265 | | template<typename Value> |
266 | | SparseArray<Value>::SparseArray() = default; |
267 | | |
268 | | template<typename Value> |
269 | | SparseArray<Value>::SparseArray(const SparseArray& src) |
270 | | : size_(src.size_), |
271 | | sparse_(src.max_size()), |
272 | 19.7k | dense_(src.max_size()) { |
273 | 19.7k | std::copy_n(src.sparse_.data(), src.max_size(), sparse_.data()); |
274 | 19.7k | std::copy_n(src.dense_.data(), src.max_size(), dense_.data()); |
275 | 19.7k | } |
276 | | |
277 | | template<typename Value> |
278 | | SparseArray<Value>::SparseArray(SparseArray&& src) |
279 | | : size_(src.size_), |
280 | | sparse_(std::move(src.sparse_)), |
281 | | dense_(std::move(src.dense_)) { |
282 | | src.size_ = 0; |
283 | | } |
284 | | |
285 | | template<typename Value> |
286 | | SparseArray<Value>& SparseArray<Value>::operator=(const SparseArray& src) { |
287 | | // Construct these first for exception safety. |
288 | | PODArray<int> a(src.max_size()); |
289 | | PODArray<IndexValue> b(src.max_size()); |
290 | | |
291 | | size_ = src.size_; |
292 | | sparse_ = std::move(a); |
293 | | dense_ = std::move(b); |
294 | | std::copy_n(src.sparse_.data(), src.max_size(), sparse_.data()); |
295 | | std::copy_n(src.dense_.data(), src.max_size(), dense_.data()); |
296 | | return *this; |
297 | | } |
298 | | |
299 | | template<typename Value> |
300 | | SparseArray<Value>& SparseArray<Value>::operator=(SparseArray&& src) { |
301 | | size_ = src.size_; |
302 | | sparse_ = std::move(src.sparse_); |
303 | | dense_ = std::move(src.dense_); |
304 | | src.size_ = 0; |
305 | | return *this; |
306 | | } |
307 | | |
308 | | // IndexValue pairs: exposed in SparseArray::iterator. |
309 | | template<typename Value> |
310 | | class SparseArray<Value>::IndexValue { |
311 | | public: |
312 | 76.3M | int index() const { return index_; } re2::SparseArray<re2::NFA::Thread*>::IndexValue::index() const Line | Count | Source | 312 | 53.6M | int index() const { return index_; } |
re2::SparseArray<int>::IndexValue::index() const Line | Count | Source | 312 | 22.6M | int index() const { return index_; } |
|
313 | 65.1M | Value& value() { return value_; } re2::SparseArray<int>::IndexValue::value() Line | Count | Source | 313 | 8.44M | Value& value() { return value_; } |
re2::SparseArray<re2::NFA::Thread*>::IndexValue::value() Line | Count | Source | 313 | 56.7M | Value& value() { return value_; } |
|
314 | 11.2M | const Value& value() const { return value_; } |
315 | | |
316 | | private: |
317 | | friend class SparseArray; |
318 | | int index_; |
319 | | Value value_; |
320 | | }; |
321 | | |
322 | | // Change the maximum size of the array. |
323 | | // Invalidates all iterators. |
324 | | template<typename Value> |
325 | 2.67k | void SparseArray<Value>::resize(int new_max_size) { |
326 | 2.67k | DebugCheckInvariants(); |
327 | 2.67k | if (new_max_size > max_size()) { |
328 | 2.67k | const int old_max_size = max_size(); |
329 | | |
330 | | // Construct these first for exception safety. |
331 | 2.67k | PODArray<int> a(new_max_size); |
332 | 2.67k | PODArray<IndexValue> b(new_max_size); |
333 | | |
334 | 2.67k | std::copy_n(sparse_.data(), old_max_size, a.data()); |
335 | 2.67k | std::copy_n(dense_.data(), old_max_size, b.data()); |
336 | | |
337 | 2.67k | sparse_ = std::move(a); |
338 | 2.67k | dense_ = std::move(b); |
339 | | |
340 | 2.67k | MaybeInitializeMemory(old_max_size, new_max_size); |
341 | 2.67k | } |
342 | 2.67k | if (size_ > new_max_size) |
343 | 0 | size_ = new_max_size; |
344 | 2.67k | DebugCheckInvariants(); |
345 | 2.67k | } |
346 | | |
347 | | // Check whether index i is in the array. |
348 | | template<typename Value> |
349 | 1.35G | bool SparseArray<Value>::has_index(int i) const { |
350 | 1.35G | assert(i >= 0); |
351 | 1.35G | assert(i < max_size()); |
352 | 1.35G | if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(max_size())) { |
353 | 0 | return false; |
354 | 0 | } |
355 | | // Unsigned comparison avoids checking sparse_[i] < 0. |
356 | 1.35G | return (uint32_t)sparse_[i] < (uint32_t)size_ && |
357 | 1.35G | dense_[sparse_[i]].index_ == i; |
358 | 1.35G | } re2::SparseArray<re2::NFA::Thread*>::has_index(int) const Line | Count | Source | 349 | 57.4M | bool SparseArray<Value>::has_index(int i) const { | 350 | 57.4M | assert(i >= 0); | 351 | 57.4M | assert(i < max_size()); | 352 | 57.4M | if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(max_size())) { | 353 | 0 | return false; | 354 | 0 | } | 355 | | // Unsigned comparison avoids checking sparse_[i] < 0. | 356 | 57.4M | return (uint32_t)sparse_[i] < (uint32_t)size_ && | 357 | 57.4M | dense_[sparse_[i]].index_ == i; | 358 | 57.4M | } |
re2::SparseArray<int>::has_index(int) const Line | Count | Source | 349 | 1.29G | bool SparseArray<Value>::has_index(int i) const { | 350 | 1.29G | assert(i >= 0); | 351 | 1.29G | assert(i < max_size()); | 352 | 1.29G | if (static_cast<uint32_t>(i) >= static_cast<uint32_t>(max_size())) { | 353 | 0 | return false; | 354 | 0 | } | 355 | | // Unsigned comparison avoids checking sparse_[i] < 0. | 356 | 1.29G | return (uint32_t)sparse_[i] < (uint32_t)size_ && | 357 | 1.29G | dense_[sparse_[i]].index_ == i; | 358 | 1.29G | } |
|
359 | | |
360 | | template<typename Value> |
361 | 80.9M | void SparseArray<Value>::create_index(int i) { |
362 | 80.9M | assert(!has_index(i)); |
363 | 80.9M | assert(size_ < max_size()); |
364 | 80.9M | sparse_[i] = size_; |
365 | 80.9M | dense_[size_].index_ = i; |
366 | 80.9M | size_++; |
367 | 80.9M | } re2::SparseArray<re2::NFA::Thread*>::create_index(int) Line | Count | Source | 361 | 56.7M | void SparseArray<Value>::create_index(int i) { | 362 | 56.7M | assert(!has_index(i)); | 363 | 56.7M | assert(size_ < max_size()); | 364 | 56.7M | sparse_[i] = size_; | 365 | 56.7M | dense_[size_].index_ = i; | 366 | 56.7M | size_++; | 367 | 56.7M | } |
re2::SparseArray<int>::create_index(int) Line | Count | Source | 361 | 24.1M | void SparseArray<Value>::create_index(int i) { | 362 | 24.1M | assert(!has_index(i)); | 363 | 24.1M | assert(size_ < max_size()); | 364 | 24.1M | sparse_[i] = size_; | 365 | 24.1M | dense_[size_].index_ = i; | 366 | 24.1M | size_++; | 367 | 24.1M | } |
|
368 | | |
369 | | template<typename Value> SparseArray<Value>::SparseArray(int max_size) : |
370 | 57.1k | sparse_(max_size), dense_(max_size) { |
371 | 57.1k | MaybeInitializeMemory(size_, max_size); |
372 | 57.1k | DebugCheckInvariants(); |
373 | 57.1k | } |
374 | | |
375 | 79.5k | template<typename Value> SparseArray<Value>::~SparseArray() { |
376 | 79.5k | DebugCheckInvariants(); |
377 | 79.5k | } re2::SparseArray<int>::~SparseArray() Line | Count | Source | 375 | 76.9k | template<typename Value> SparseArray<Value>::~SparseArray() { | 376 | 76.9k | DebugCheckInvariants(); | 377 | 76.9k | } |
re2::SparseArray<re2::NFA::Thread*>::~SparseArray() Line | Count | Source | 375 | 2.67k | template<typename Value> SparseArray<Value>::~SparseArray() { | 376 | 2.67k | DebugCheckInvariants(); | 377 | 2.67k | } |
|
378 | | |
379 | 242M | template<typename Value> void SparseArray<Value>::DebugCheckInvariants() const { |
380 | 242M | assert(0 <= size_); |
381 | 242M | assert(size_ <= max_size()); |
382 | 242M | } re2::SparseArray<int>::DebugCheckInvariants() const Line | Count | Source | 379 | 72.6M | template<typename Value> void SparseArray<Value>::DebugCheckInvariants() const { | 380 | 72.6M | assert(0 <= size_); | 381 | 72.6M | assert(size_ <= max_size()); | 382 | 72.6M | } |
re2::SparseArray<re2::NFA::Thread*>::DebugCheckInvariants() const Line | Count | Source | 379 | 170M | template<typename Value> void SparseArray<Value>::DebugCheckInvariants() const { | 380 | 170M | assert(0 <= size_); | 381 | 170M | assert(size_ <= max_size()); | 382 | 170M | } |
|
383 | | |
384 | | // Comparison function for sorting. |
385 | | template<typename Value> bool SparseArray<Value>::less(const IndexValue& a, |
386 | 58.1M | const IndexValue& b) { |
387 | 58.1M | return a.index_ < b.index_; |
388 | 58.1M | } |
389 | | |
390 | | } // namespace re2 |
391 | | |
392 | | #endif // RE2_SPARSE_ARRAY_H_ |