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