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 97namespace re2 { 98 99template<typename Value> 100class 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 232template<typename Value> 233SparseArray<Value>::SparseArray() 234 : size_(0), max_size_(0), sparse_to_dense_(NULL), dense_(), valgrind_(RunningOnValgrind()) {} 235 236// IndexValue pairs: exposed in SparseArray::iterator. 237template<typename Value> 238class 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 258template<typename Value> 259const typename SparseArray<Value>::IndexValue& 260SparseArray<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. 268template<typename Value> 269void 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. 293template<typename Value> 294bool 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. 306template<typename Value> 307typename 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 320template<typename Value> 321pair<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 334template<typename Value> 335Value SparseArray<Value>::get(int i, Value defaultv) const { 336 if (!has_index(i)) 337 return defaultv; 338 return get_existing(i); 339} 340 341template<typename Value> 342typename 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 348template<typename Value> 349typename SparseArray<Value>::const_iterator 350SparseArray<Value>::find(int i) const { 351 if (has_index(i)) { 352 return dense_.begin() + sparse_to_dense_[i]; 353 } 354 return end(); 355} 356 357template<typename Value> 358typename SparseArray<Value>::iterator 359SparseArray<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 367template<typename Value> 368typename SparseArray<Value>::iterator 369SparseArray<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 382template<typename Value> 383Value SparseArray<Value>::get_existing(int i) const { 384 DCHECK(has_index(i)); 385 return dense_[sparse_to_dense_[i]].second; 386} 387 388template<typename Value> 389void SparseArray<Value>::erase(int i) { 390 DebugCheckInvariants(); 391 if (has_index(i)) 392 erase_existing(i); 393 DebugCheckInvariants(); 394} 395 396template<typename Value> 397void 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 409template<typename Value> 410void 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 418template<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 434template<typename Value> SparseArray<Value>::~SparseArray() { 435 DebugCheckInvariants(); 436 delete[] sparse_to_dense_; 437} 438 439template<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. 446template<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