OLD | NEW |
| (Empty) |
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 // DESCRIPTION | |
6 // | |
7 // SparseArray<T>(m) is a map from integers in [0, m) to T values. | |
8 // It requires (sizeof(T)+sizeof(int))*m memory, but it provides | |
9 // fast iteration through the elements in the array and fast clearing | |
10 // of the array. The array has a concept of certain elements being | |
11 // uninitialized (having no value). | |
12 // | |
13 // Insertion and deletion are constant time operations. | |
14 // | |
15 // Allocating the array is a constant time operation | |
16 // when memory allocation is a constant time operation. | |
17 // | |
18 // Clearing the array is a constant time operation (unusual!). | |
19 // | |
20 // Iterating through the array is an O(n) operation, where n | |
21 // is the number of items in the array (not O(m)). | |
22 // | |
23 // The array iterator visits entries in the order they were first | |
24 // inserted into the array. It is safe to add items to the array while | |
25 // using an iterator: the iterator will visit indices added to the array | |
26 // during the iteration, but will not re-visit indices whose values | |
27 // change after visiting. Thus SparseArray can be a convenient | |
28 // implementation of a work queue. | |
29 // | |
30 // The SparseArray implementation is NOT thread-safe. It is up to the | |
31 // caller to make sure only one thread is accessing the array. (Typically | |
32 // these arrays are temporary values and used in situations where speed is | |
33 // important.) | |
34 // | |
35 // The SparseArray interface does not present all the usual STL bells and | |
36 // whistles. | |
37 // | |
38 // Implemented with reference to Briggs & Torczon, An Efficient | |
39 // Representation for Sparse Sets, ACM Letters on Programming Languages | |
40 // and Systems, Volume 2, Issue 1-4 (March-Dec. 1993), pp. 59-69. | |
41 // | |
42 // Briggs & Torczon popularized this technique, but it had been known | |
43 // long before their paper. They point out that Aho, Hopcroft, and | |
44 // Ullman's 1974 Design and Analysis of Computer Algorithms and Bentley's | |
45 // 1986 Programming Pearls both hint at the technique in exercises to the | |
46 // reader (in Aho & Hopcroft, exercise 2.12; in Bentley, column 1 | |
47 // exercise 8). | |
48 // | |
49 // Briggs & Torczon describe a sparse set implementation. I have | |
50 // trivially generalized it to create a sparse array (actually the original | |
51 // target of the AHU and Bentley exercises). | |
52 | |
53 // IMPLEMENTATION | |
54 // | |
55 // SparseArray uses a vector dense_ and an array sparse_to_dense_, both of | |
56 // size max_size_. At any point, the number of elements in the sparse array is | |
57 // size_. | |
58 // | |
59 // The vector dense_ contains the size_ elements in the sparse array (with | |
60 // their indices), | |
61 // in the order that the elements were first inserted. This array is dense: | |
62 // the size_ pairs are dense_[0] through dense_[size_-1]. | |
63 // | |
64 // The array sparse_to_dense_ maps from indices in [0,m) to indices in | |
65 // [0,size_). | |
66 // For indices present in the array, dense_[sparse_to_dense_[i]].index_ == i. | |
67 // For indices not present in the array, sparse_to_dense_ can contain | |
68 // any value at all, perhaps outside the range [0, size_) but perhaps not. | |
69 // | |
70 // The lax requirement on sparse_to_dense_ values makes clearing | |
71 // the array very easy: set size_ to 0. Lookups are slightly more | |
72 // complicated. An index i has a value in the array if and only if: | |
73 // sparse_to_dense_[i] is in [0, size_) AND | |
74 // dense_[sparse_to_dense_[i]].index_ == i. | |
75 // If both these properties hold, only then it is safe to refer to | |
76 // dense_[sparse_to_dense_[i]].value_ | |
77 // as the value associated with index i. | |
78 // | |
79 // To insert a new entry, set sparse_to_dense_[i] to size_, | |
80 // initialize dense_[size_], and then increment size_. | |
81 // | |
82 // Deletion of specific values from the array is implemented by | |
83 // swapping dense_[size_-1] and the dense_ being deleted and then | |
84 // updating the appropriate sparse_to_dense_ entries. | |
85 // | |
86 // To make the sparse array as efficient as possible for non-primitive types, | |
87 // elements may or may not be destroyed when they are deleted from the sparse | |
88 // array through a call to erase(), erase_existing() or resize(). They | |
89 // immediately become inaccessible, but they are only guaranteed to be | |
90 // destroyed when the SparseArray destructor is called. | |
91 | |
92 #ifndef RE2_UTIL_SPARSE_ARRAY_H__ | |
93 #define RE2_UTIL_SPARSE_ARRAY_H__ | |
94 | |
95 #include "util/util.h" | |
96 | |
97 namespace re2 { | |
98 | |
99 template<typename Value> | |
100 class SparseArray { | |
101 public: | |
102 SparseArray(); | |
103 SparseArray(int max_size); | |
104 ~SparseArray(); | |
105 | |
106 // IndexValue pairs: exposed in SparseArray::iterator. | |
107 class IndexValue; | |
108 | |
109 typedef IndexValue value_type; | |
110 typedef typename vector<IndexValue>::iterator iterator; | |
111 typedef typename vector<IndexValue>::const_iterator const_iterator; | |
112 | |
113 inline const IndexValue& iv(int i) const; | |
114 | |
115 // Return the number of entries in the array. | |
116 int size() const { | |
117 return size_; | |
118 } | |
119 | |
120 // Iterate over the array. | |
121 iterator begin() { | |
122 return dense_.begin(); | |
123 } | |
124 iterator end() { | |
125 return dense_.begin() + size_; | |
126 } | |
127 | |
128 const_iterator begin() const { | |
129 return dense_.begin(); | |
130 } | |
131 const_iterator end() const { | |
132 return dense_.begin() + size_; | |
133 } | |
134 | |
135 // Change the maximum size of the array. | |
136 // Invalidates all iterators. | |
137 void resize(int max_size); | |
138 | |
139 // Return the maximum size of the array. | |
140 // Indices can be in the range [0, max_size). | |
141 int max_size() const { | |
142 return max_size_; | |
143 } | |
144 | |
145 // Clear the array. | |
146 void clear() { | |
147 size_ = 0; | |
148 } | |
149 | |
150 // Check whether index i is in the array. | |
151 inline bool has_index(int i) const; | |
152 | |
153 // Comparison function for sorting. | |
154 // Can sort the sparse array so that future iterations | |
155 // will visit indices in increasing order using | |
156 // sort(arr.begin(), arr.end(), arr.less); | |
157 static bool less(const IndexValue& a, const IndexValue& b); | |
158 | |
159 public: | |
160 // Set the value at index i to v. | |
161 inline iterator set(int i, Value v); | |
162 | |
163 pair<iterator, bool> insert(const value_type& new_value); | |
164 | |
165 // Returns the value at index i | |
166 // or defaultv if index i is not initialized in the array. | |
167 inline Value get(int i, Value defaultv) const; | |
168 | |
169 iterator find(int i); | |
170 | |
171 const_iterator find(int i) const; | |
172 | |
173 // Change the value at index i to v. | |
174 // Fast but unsafe: only use if has_index(i) is true. | |
175 inline iterator set_existing(int i, Value v); | |
176 | |
177 // Set the value at the new index i to v. | |
178 // Fast but unsafe: only use if has_index(i) is false. | |
179 inline iterator set_new(int i, Value v); | |
180 | |
181 // Get the value at index i from the array.. | |
182 // Fast but unsafe: only use if has_index(i) is true. | |
183 inline Value get_existing(int i) const; | |
184 | |
185 // Erasing items from the array during iteration is in general | |
186 // NOT safe. There is one special case, which is that the current | |
187 // index-value pair can be erased as long as the iterator is then | |
188 // checked for being at the end before being incremented. | |
189 // For example: | |
190 // | |
191 // for (i = m.begin(); i != m.end(); ++i) { | |
192 // if (ShouldErase(i->index(), i->value())) { | |
193 // m.erase(i->index()); | |
194 // --i; | |
195 // } | |
196 // } | |
197 // | |
198 // Except in the specific case just described, elements must | |
199 // not be erased from the array (including clearing the array) | |
200 // while iterators are walking over the array. Otherwise, | |
201 // the iterators could walk past the end of the array. | |
202 | |
203 // Erases the element at index i from the array. | |
204 inline void erase(int i); | |
205 | |
206 // Erases the element at index i from the array. | |
207 // Fast but unsafe: only use if has_index(i) is true. | |
208 inline void erase_existing(int i); | |
209 | |
210 private: | |
211 // Add the index i to the array. | |
212 // Only use if has_index(i) is known to be false. | |
213 // Since it doesn't set the value associated with i, | |
214 // this function is private, only intended as a helper | |
215 // for other methods. | |
216 inline void create_index(int i); | |
217 | |
218 // In debug mode, verify that some invariant properties of the class | |
219 // are being maintained. This is called at the end of the constructor | |
220 // and at the beginning and end of all public non-const member functions. | |
221 inline void DebugCheckInvariants() const; | |
222 | |
223 static bool InitMemory() { | |
224 #ifdef MEMORY_SANITIZER | |
225 return true; | |
226 #else | |
227 return RunningOnValgrind(); | |
228 #endif | |
229 } | |
230 | |
231 int size_; | |
232 int max_size_; | |
233 int* sparse_to_dense_; | |
234 vector<IndexValue> dense_; | |
235 | |
236 DISALLOW_COPY_AND_ASSIGN(SparseArray); | |
237 }; | |
238 | |
239 template<typename Value> | |
240 SparseArray<Value>::SparseArray() | |
241 : size_(0), max_size_(0), sparse_to_dense_(NULL), dense_() {} | |
242 | |
243 // IndexValue pairs: exposed in SparseArray::iterator. | |
244 template<typename Value> | |
245 class SparseArray<Value>::IndexValue { | |
246 friend class SparseArray; | |
247 public: | |
248 typedef int first_type; | |
249 typedef Value second_type; | |
250 | |
251 IndexValue() {} | |
252 IndexValue(int index, const Value& value) : second(value), index_(index) {} | |
253 | |
254 int index() const { return index_; } | |
255 Value value() const { return second; } | |
256 | |
257 // Provide the data in the 'second' member so that the utilities | |
258 // in map-util work. | |
259 Value second; | |
260 | |
261 private: | |
262 int index_; | |
263 }; | |
264 | |
265 template<typename Value> | |
266 const typename SparseArray<Value>::IndexValue& | |
267 SparseArray<Value>::iv(int i) const { | |
268 DCHECK_GE(i, 0); | |
269 DCHECK_LT(i, size_); | |
270 return dense_[i]; | |
271 } | |
272 | |
273 // Change the maximum size of the array. | |
274 // Invalidates all iterators. | |
275 template<typename Value> | |
276 void SparseArray<Value>::resize(int new_max_size) { | |
277 DebugCheckInvariants(); | |
278 if (new_max_size > max_size_) { | |
279 int* a = new int[new_max_size]; | |
280 if (sparse_to_dense_) { | |
281 memmove(a, sparse_to_dense_, max_size_*sizeof a[0]); | |
282 delete[] sparse_to_dense_; | |
283 } | |
284 sparse_to_dense_ = a; | |
285 | |
286 dense_.resize(new_max_size); | |
287 | |
288 // These don't need to be initialized for correctness, | |
289 // but Valgrind will warn about use of uninitialized memory, | |
290 // so initialize the new memory when compiling debug binaries. | |
291 // Initialize it to garbage to detect bugs in the future. | |
292 if (InitMemory()) { | |
293 for (int i = max_size_; i < new_max_size; i++) { | |
294 sparse_to_dense_[i] = 0xababababU; | |
295 dense_[i].index_ = 0xababababU; | |
296 } | |
297 } | |
298 } | |
299 max_size_ = new_max_size; | |
300 if (size_ > max_size_) | |
301 size_ = max_size_; | |
302 DebugCheckInvariants(); | |
303 } | |
304 | |
305 // Check whether index i is in the array. | |
306 template<typename Value> | |
307 bool SparseArray<Value>::has_index(int i) const { | |
308 DCHECK_GE(i, 0); | |
309 DCHECK_LT(i, max_size_); | |
310 if (static_cast<uint>(i) >= static_cast<uint>(max_size_)) { | |
311 return false; | |
312 } | |
313 // Unsigned comparison avoids checking sparse_to_dense_[i] < 0. | |
314 return (uint)sparse_to_dense_[i] < (uint)size_ && | |
315 dense_[sparse_to_dense_[i]].index_ == i; | |
316 } | |
317 | |
318 // Set the value at index i to v. | |
319 template<typename Value> | |
320 typename SparseArray<Value>::iterator SparseArray<Value>::set(int i, Value v) { | |
321 DebugCheckInvariants(); | |
322 if (static_cast<uint>(i) >= static_cast<uint>(max_size_)) { | |
323 // Semantically, end() would be better here, but we already know | |
324 // the user did something stupid, so begin() insulates them from | |
325 // dereferencing an invalid pointer. | |
326 return begin(); | |
327 } | |
328 if (!has_index(i)) | |
329 create_index(i); | |
330 return set_existing(i, v); | |
331 } | |
332 | |
333 template<typename Value> | |
334 pair<typename SparseArray<Value>::iterator, bool> SparseArray<Value>::insert( | |
335 const value_type& new_value) { | |
336 DebugCheckInvariants(); | |
337 pair<typename SparseArray<Value>::iterator, bool> p; | |
338 if (has_index(new_value.index_)) { | |
339 p = make_pair(dense_.begin() + sparse_to_dense_[new_value.index_], false); | |
340 } else { | |
341 p = make_pair(set_new(new_value.index_, new_value.second), true); | |
342 } | |
343 DebugCheckInvariants(); | |
344 return p; | |
345 } | |
346 | |
347 template<typename Value> | |
348 Value SparseArray<Value>::get(int i, Value defaultv) const { | |
349 if (!has_index(i)) | |
350 return defaultv; | |
351 return get_existing(i); | |
352 } | |
353 | |
354 template<typename Value> | |
355 typename SparseArray<Value>::iterator SparseArray<Value>::find(int i) { | |
356 if (has_index(i)) | |
357 return dense_.begin() + sparse_to_dense_[i]; | |
358 return end(); | |
359 } | |
360 | |
361 template<typename Value> | |
362 typename SparseArray<Value>::const_iterator | |
363 SparseArray<Value>::find(int i) const { | |
364 if (has_index(i)) { | |
365 return dense_.begin() + sparse_to_dense_[i]; | |
366 } | |
367 return end(); | |
368 } | |
369 | |
370 template<typename Value> | |
371 typename SparseArray<Value>::iterator | |
372 SparseArray<Value>::set_existing(int i, Value v) { | |
373 DebugCheckInvariants(); | |
374 DCHECK(has_index(i)); | |
375 dense_[sparse_to_dense_[i]].second = v; | |
376 DebugCheckInvariants(); | |
377 return dense_.begin() + sparse_to_dense_[i]; | |
378 } | |
379 | |
380 template<typename Value> | |
381 typename SparseArray<Value>::iterator | |
382 SparseArray<Value>::set_new(int i, Value v) { | |
383 DebugCheckInvariants(); | |
384 if (static_cast<uint>(i) >= static_cast<uint>(max_size_)) { | |
385 // Semantically, end() would be better here, but we already know | |
386 // the user did something stupid, so begin() insulates them from | |
387 // dereferencing an invalid pointer. | |
388 return begin(); | |
389 } | |
390 DCHECK(!has_index(i)); | |
391 create_index(i); | |
392 return set_existing(i, v); | |
393 } | |
394 | |
395 template<typename Value> | |
396 Value SparseArray<Value>::get_existing(int i) const { | |
397 DCHECK(has_index(i)); | |
398 return dense_[sparse_to_dense_[i]].second; | |
399 } | |
400 | |
401 template<typename Value> | |
402 void SparseArray<Value>::erase(int i) { | |
403 DebugCheckInvariants(); | |
404 if (has_index(i)) | |
405 erase_existing(i); | |
406 DebugCheckInvariants(); | |
407 } | |
408 | |
409 template<typename Value> | |
410 void SparseArray<Value>::erase_existing(int i) { | |
411 DebugCheckInvariants(); | |
412 DCHECK(has_index(i)); | |
413 int di = sparse_to_dense_[i]; | |
414 if (di < size_ - 1) { | |
415 dense_[di] = dense_[size_ - 1]; | |
416 sparse_to_dense_[dense_[di].index_] = di; | |
417 } | |
418 size_--; | |
419 DebugCheckInvariants(); | |
420 } | |
421 | |
422 template<typename Value> | |
423 void SparseArray<Value>::create_index(int i) { | |
424 DCHECK(!has_index(i)); | |
425 DCHECK_LT(size_, max_size_); | |
426 sparse_to_dense_[i] = size_; | |
427 dense_[size_].index_ = i; | |
428 size_++; | |
429 } | |
430 | |
431 template<typename Value> SparseArray<Value>::SparseArray(int max_size) { | |
432 max_size_ = max_size; | |
433 sparse_to_dense_ = new int[max_size]; | |
434 dense_.resize(max_size); | |
435 // Don't need to zero the new memory, but appease Valgrind. | |
436 if (InitMemory()) { | |
437 for (int i = 0; i < max_size; i++) { | |
438 sparse_to_dense_[i] = 0xababababU; | |
439 dense_[i].index_ = 0xababababU; | |
440 } | |
441 } | |
442 size_ = 0; | |
443 DebugCheckInvariants(); | |
444 } | |
445 | |
446 template<typename Value> SparseArray<Value>::~SparseArray() { | |
447 DebugCheckInvariants(); | |
448 delete[] sparse_to_dense_; | |
449 } | |
450 | |
451 template<typename Value> void SparseArray<Value>::DebugCheckInvariants() const { | |
452 DCHECK_LE(0, size_); | |
453 DCHECK_LE(size_, max_size_); | |
454 DCHECK(size_ == 0 || sparse_to_dense_ != NULL); | |
455 } | |
456 | |
457 // Comparison function for sorting. | |
458 template<typename Value> bool SparseArray<Value>::less(const IndexValue& a, | |
459 const IndexValue& b) { | |
460 return a.index_ < b.index_; | |
461 } | |
462 | |
463 } // namespace re2 | |
464 | |
465 #endif // RE2_UTIL_SPARSE_ARRAY_H__ | |
OLD | NEW |