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 int size_; 224 int max_size_; 225 int* sparse_to_dense_; 226 vector<IndexValue> dense_; 227 bool valgrind_; 228 229 DISALLOW_EVIL_CONSTRUCTORS(SparseArray); 230 }; 231 232 template<typename Value> 233 SparseArray<Value>::SparseArray() 234 : size_(0), max_size_(0), sparse_to_dense_(NULL), dense_(), 235 valgrind_(RunningOnValgrindOrMemorySanitizer()) {} 236 237 // IndexValue pairs: exposed in SparseArray::iterator. 238 template<typename Value> 239 class SparseArray<Value>::IndexValue { 240 friend class SparseArray; 241 public: 242 typedef int first_type; 243 typedef Value second_type; 244 245 IndexValue() {} 246 IndexValue(int index, const Value& value) : second(value), index_(index) {} 247 248 int index() const { return index_; } 249 Value value() const { return second; } 250 251 // Provide the data in the 'second' member so that the utilities 252 // in map-util work. 253 Value second; 254 255 private: 256 int index_; 257 }; 258 259 template<typename Value> 260 const typename SparseArray<Value>::IndexValue& 261 SparseArray<Value>::iv(int i) const { 262 DCHECK_GE(i, 0); 263 DCHECK_LT(i, size_); 264 return dense_[i]; 265 } 266 267 // Change the maximum size of the array. 268 // Invalidates all iterators. 269 template<typename Value> 270 void SparseArray<Value>::resize(int new_max_size) { 271 DebugCheckInvariants(); 272 if (new_max_size > max_size_) { 273 int* a = new int[new_max_size]; 274 if (sparse_to_dense_) { 275 memmove(a, sparse_to_dense_, max_size_*sizeof a[0]); 276 // Don't need to zero the memory but appease Valgrind. 277 if (valgrind_) { 278 for (int i = max_size_; i < new_max_size; i++) 279 a[i] = 0xababababU; 280 } 281 delete[] sparse_to_dense_; 282 } 283 sparse_to_dense_ = a; 284 285 dense_.resize(new_max_size); 286 } 287 max_size_ = new_max_size; 288 if (size_ > max_size_) 289 size_ = max_size_; 290 DebugCheckInvariants(); 291 } 292 293 // Check whether index i is in the array. 294 template<typename Value> 295 bool SparseArray<Value>::has_index(int i) const { 296 DCHECK_GE(i, 0); 297 DCHECK_LT(i, max_size_); 298 if (static_cast<uint>(i) >= max_size_) { 299 return false; 300 } 301 // Unsigned comparison avoids checking sparse_to_dense_[i] < 0. 302 return (uint)sparse_to_dense_[i] < (uint)size_ && 303 dense_[sparse_to_dense_[i]].index_ == i; 304 } 305 306 // Set the value at index i to v. 307 template<typename Value> 308 typename SparseArray<Value>::iterator SparseArray<Value>::set(int i, Value v) { 309 DebugCheckInvariants(); 310 if (static_cast<uint>(i) >= max_size_) { 311 // Semantically, end() would be better here, but we already know 312 // the user did something stupid, so begin() insulates them from 313 // dereferencing an invalid pointer. 314 return begin(); 315 } 316 if (!has_index(i)) 317 create_index(i); 318 return set_existing(i, v); 319 } 320 321 template<typename Value> 322 pair<typename SparseArray<Value>::iterator, bool> SparseArray<Value>::insert( 323 const value_type& new_value) { 324 DebugCheckInvariants(); 325 pair<typename SparseArray<Value>::iterator, bool> p; 326 if (has_index(new_value.index_)) { 327 p = make_pair(dense_.begin() + sparse_to_dense_[new_value.index_], false); 328 } else { 329 p = make_pair(set_new(new_value.index_, new_value.second), true); 330 } 331 DebugCheckInvariants(); 332 return p; 333 } 334 335 template<typename Value> 336 Value SparseArray<Value>::get(int i, Value defaultv) const { 337 if (!has_index(i)) 338 return defaultv; 339 return get_existing(i); 340 } 341 342 template<typename Value> 343 typename SparseArray<Value>::iterator SparseArray<Value>::find(int i) { 344 if (has_index(i)) 345 return dense_.begin() + sparse_to_dense_[i]; 346 return end(); 347 } 348 349 template<typename Value> 350 typename SparseArray<Value>::const_iterator 351 SparseArray<Value>::find(int i) const { 352 if (has_index(i)) { 353 return dense_.begin() + sparse_to_dense_[i]; 354 } 355 return end(); 356 } 357 358 template<typename Value> 359 typename SparseArray<Value>::iterator 360 SparseArray<Value>::set_existing(int i, Value v) { 361 DebugCheckInvariants(); 362 DCHECK(has_index(i)); 363 dense_[sparse_to_dense_[i]].second = v; 364 DebugCheckInvariants(); 365 return dense_.begin() + sparse_to_dense_[i]; 366 } 367 368 template<typename Value> 369 typename SparseArray<Value>::iterator 370 SparseArray<Value>::set_new(int i, Value v) { 371 DebugCheckInvariants(); 372 if (static_cast<uint>(i) >= max_size_) { 373 // Semantically, end() would be better here, but we already know 374 // the user did something stupid, so begin() insulates them from 375 // dereferencing an invalid pointer. 376 return begin(); 377 } 378 DCHECK(!has_index(i)); 379 create_index(i); 380 return set_existing(i, v); 381 } 382 383 template<typename Value> 384 Value SparseArray<Value>::get_existing(int i) const { 385 DCHECK(has_index(i)); 386 return dense_[sparse_to_dense_[i]].second; 387 } 388 389 template<typename Value> 390 void SparseArray<Value>::erase(int i) { 391 DebugCheckInvariants(); 392 if (has_index(i)) 393 erase_existing(i); 394 DebugCheckInvariants(); 395 } 396 397 template<typename Value> 398 void SparseArray<Value>::erase_existing(int i) { 399 DebugCheckInvariants(); 400 DCHECK(has_index(i)); 401 int di = sparse_to_dense_[i]; 402 if (di < size_ - 1) { 403 dense_[di] = dense_[size_ - 1]; 404 sparse_to_dense_[dense_[di].index_] = di; 405 } 406 size_--; 407 DebugCheckInvariants(); 408 } 409 410 template<typename Value> 411 void SparseArray<Value>::create_index(int i) { 412 DCHECK(!has_index(i)); 413 DCHECK_LT(size_, max_size_); 414 sparse_to_dense_[i] = size_; 415 dense_[size_].index_ = i; 416 size_++; 417 } 418 419 template<typename Value> SparseArray<Value>::SparseArray(int max_size) { 420 max_size_ = max_size; 421 sparse_to_dense_ = new int[max_size]; 422 valgrind_ = RunningOnValgrindOrMemorySanitizer(); 423 dense_.resize(max_size); 424 // Don't need to zero the new memory, but appease Valgrind. 425 if (valgrind_) { 426 for (int i = 0; i < max_size; i++) { 427 sparse_to_dense_[i] = 0xababababU; 428 dense_[i].index_ = 0xababababU; 429 } 430 } 431 size_ = 0; 432 DebugCheckInvariants(); 433 } 434 435 template<typename Value> SparseArray<Value>::~SparseArray() { 436 DebugCheckInvariants(); 437 delete[] sparse_to_dense_; 438 } 439 440 template<typename Value> void SparseArray<Value>::DebugCheckInvariants() const { 441 DCHECK_LE(0, size_); 442 DCHECK_LE(size_, max_size_); 443 DCHECK(size_ == 0 || sparse_to_dense_ != NULL); 444 } 445 446 // Comparison function for sorting. 447 template<typename Value> bool SparseArray<Value>::less(const IndexValue& a, 448 const IndexValue& b) { 449 return a.index_ < b.index_; 450 } 451 452 } // namespace re2 453 454 #endif // RE2_UTIL_SPARSE_ARRAY_H__ 455