Coverage Report

Created: 2022-08-24 06:41

/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_