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