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 // SparseSet<T>(m) is a set of integers in [0, m). | |
8 // It requires sizeof(int)*m memory, but it provides | |
9 // fast iteration through the elements in the set and fast clearing | |
10 // of the set. | |
11 // | |
12 // Insertion and deletion are constant time operations. | |
13 // | |
14 // Allocating the set is a constant time operation | |
15 // when memory allocation is a constant time operation. | |
16 // | |
17 // Clearing the set is a constant time operation (unusual!). | |
18 // | |
19 // Iterating through the set is an O(n) operation, where n | |
20 // is the number of items in the set (not O(m)). | |
21 // | |
22 // The set iterator visits entries in the order they were first | |
23 // inserted into the array. It is safe to add items to the set while | |
24 // using an iterator: the iterator will visit indices added to the set | |
25 // during the iteration, but will not re-visit indices whose values | |
26 // change after visiting. Thus SparseSet can be a convenient | |
27 // implementation of a work queue. | |
28 // | |
29 // The SparseSet implementation is NOT thread-safe. It is up to the | |
30 // caller to make sure only one thread is accessing the set. (Typically | |
31 // these sets are temporary values and used in situations where speed is | |
32 // important.) | |
33 // | |
34 // The SparseSet interface does not present all the usual STL bells and | |
35 // whistles. | |
36 // | |
37 // Implemented with reference to Briggs & Torczon, An Efficient | |
38 // Representation for Sparse Sets, ACM Letters on Programming Languages | |
39 // and Systems, Volume 2, Issue 1-4 (March-Dec. 1993), pp. 59-69. | |
40 // | |
41 // For a generalization to sparse array, see sparse_array.h. | |
42 | |
43 // IMPLEMENTATION | |
44 // | |
45 // See sparse_array.h for implementation details | |
46 | |
47 #ifndef RE2_UTIL_SPARSE_SET_H__ | |
48 #define RE2_UTIL_SPARSE_SET_H__ | |
49 | |
50 #include "util/util.h" | |
51 | |
52 namespace re2 { | |
53 | |
54 class SparseSet { | |
55 public: | |
56 SparseSet() | |
57 : size_(0), max_size_(0), sparse_to_dense_(NULL), dense_(NULL) {} | |
58 | |
59 SparseSet(int max_size) { | |
60 max_size_ = max_size; | |
61 sparse_to_dense_ = new int[max_size]; | |
62 dense_ = new int[max_size]; | |
63 // Don't need to zero the memory, but do so anyway | |
64 // to appease Valgrind. | |
65 if (InitMemory()) { | |
66 for (int i = 0; i < max_size; i++) { | |
67 dense_[i] = 0xababababU; | |
68 sparse_to_dense_[i] = 0xababababU; | |
69 } | |
70 } | |
71 size_ = 0; | |
72 } | |
73 | |
74 ~SparseSet() { | |
75 delete[] sparse_to_dense_; | |
76 delete[] dense_; | |
77 } | |
78 | |
79 typedef int* iterator; | |
80 typedef const int* const_iterator; | |
81 | |
82 int size() const { return size_; } | |
83 iterator begin() { return dense_; } | |
84 iterator end() { return dense_ + size_; } | |
85 const_iterator begin() const { return dense_; } | |
86 const_iterator end() const { return dense_ + size_; } | |
87 | |
88 // Change the maximum size of the array. | |
89 // Invalidates all iterators. | |
90 void resize(int new_max_size) { | |
91 if (size_ > new_max_size) | |
92 size_ = new_max_size; | |
93 if (new_max_size > max_size_) { | |
94 int* a = new int[new_max_size]; | |
95 if (sparse_to_dense_) { | |
96 memmove(a, sparse_to_dense_, max_size_*sizeof a[0]); | |
97 if (InitMemory()) { | |
98 for (int i = max_size_; i < new_max_size; i++) | |
99 a[i] = 0xababababU; | |
100 } | |
101 delete[] sparse_to_dense_; | |
102 } | |
103 sparse_to_dense_ = a; | |
104 | |
105 a = new int[new_max_size]; | |
106 if (dense_) { | |
107 memmove(a, dense_, size_*sizeof a[0]); | |
108 if (InitMemory()) { | |
109 for (int i = size_; i < new_max_size; i++) | |
110 a[i] = 0xababababU; | |
111 } | |
112 delete[] dense_; | |
113 } | |
114 dense_ = a; | |
115 } | |
116 max_size_ = new_max_size; | |
117 } | |
118 | |
119 // Return the maximum size of the array. | |
120 // Indices can be in the range [0, max_size). | |
121 int max_size() const { return max_size_; } | |
122 | |
123 // Clear the array. | |
124 void clear() { size_ = 0; } | |
125 | |
126 // Check whether i is in the array. | |
127 bool contains(int i) const { | |
128 DCHECK_GE(i, 0); | |
129 DCHECK_LT(i, max_size_); | |
130 if (static_cast<uint>(i) >= static_cast<uint>(max_size_)) { | |
131 return false; | |
132 } | |
133 // Unsigned comparison avoids checking sparse_to_dense_[i] < 0. | |
134 return (uint)sparse_to_dense_[i] < (uint)size_ && | |
135 dense_[sparse_to_dense_[i]] == i; | |
136 } | |
137 | |
138 // Adds i to the set. | |
139 void insert(int i) { | |
140 if (!contains(i)) | |
141 insert_new(i); | |
142 } | |
143 | |
144 // Set the value at the new index i to v. | |
145 // Fast but unsafe: only use if contains(i) is false. | |
146 void insert_new(int i) { | |
147 if (static_cast<uint>(i) >= static_cast<uint>(max_size_)) { | |
148 // Semantically, end() would be better here, but we already know | |
149 // the user did something stupid, so begin() insulates them from | |
150 // dereferencing an invalid pointer. | |
151 return; | |
152 } | |
153 DCHECK(!contains(i)); | |
154 DCHECK_LT(size_, max_size_); | |
155 sparse_to_dense_[i] = size_; | |
156 dense_[size_] = i; | |
157 size_++; | |
158 } | |
159 | |
160 // Comparison function for sorting. | |
161 // Can sort the sparse array so that future iterations | |
162 // will visit indices in increasing order using | |
163 // sort(arr.begin(), arr.end(), arr.less); | |
164 static bool less(int a, int b) { return a < b; } | |
165 | |
166 private: | |
167 static bool InitMemory() { | |
168 #ifdef MEMORY_SANITIZER | |
169 return true; | |
170 #else | |
171 return RunningOnValgrind(); | |
172 #endif | |
173 } | |
174 | |
175 int size_; | |
176 int max_size_; | |
177 int* sparse_to_dense_; | |
178 int* dense_; | |
179 | |
180 DISALLOW_COPY_AND_ASSIGN(SparseSet); | |
181 }; | |
182 | |
183 } // namespace re2 | |
184 | |
185 #endif // RE2_UTIL_SPARSE_SET_H__ | |
OLD | NEW |