OLD | NEW |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef BASE_ID_MAP_H_ | 5 #ifndef BASE_ID_MAP_H_ |
6 #define BASE_ID_MAP_H_ | 6 #define BASE_ID_MAP_H_ |
7 | 7 |
8 #include <stddef.h> | 8 #include <stddef.h> |
9 #include <stdint.h> | 9 #include <stdint.h> |
10 #include <set> | 10 #include <set> |
(...skipping 28 matching lines...) Expand all Loading... |
39 public: | 39 public: |
40 using KeyType = K; | 40 using KeyType = K; |
41 | 41 |
42 private: | 42 private: |
43 typedef base::hash_map<KeyType, T*> HashTable; | 43 typedef base::hash_map<KeyType, T*> HashTable; |
44 | 44 |
45 public: | 45 public: |
46 IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) { | 46 IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) { |
47 // A number of consumers of IDMap create it on one thread but always | 47 // A number of consumers of IDMap create it on one thread but always |
48 // access it from a different, but consistent, thread (or sequence) | 48 // access it from a different, but consistent, thread (or sequence) |
49 // post-construction. The first call to CalledOnValidSequencedThread() | 49 // post-construction. The first call to CalledOnValidSequence() will re-bind |
50 // will re-bind it. | 50 // it. |
51 sequence_checker_.DetachFromSequence(); | 51 sequence_checker_.DetachFromSequence(); |
52 } | 52 } |
53 | 53 |
54 ~IDMap() { | 54 ~IDMap() { |
55 // Many IDMap's are static, and hence will be destroyed on the main | 55 // Many IDMap's are static, and hence will be destroyed on the main |
56 // thread. However, all the accesses may take place on another thread (or | 56 // thread. However, all the accesses may take place on another thread (or |
57 // sequence), such as the IO thread. Detaching again to clean this up. | 57 // sequence), such as the IO thread. Detaching again to clean this up. |
58 sequence_checker_.DetachFromSequence(); | 58 sequence_checker_.DetachFromSequence(); |
59 Releaser<OS, 0>::release_all(&data_); | 59 Releaser<OS, 0>::release_all(&data_); |
60 } | 60 } |
61 | 61 |
62 // Sets whether Add and Replace should DCHECK if passed in NULL data. | 62 // Sets whether Add and Replace should DCHECK if passed in NULL data. |
63 // Default is false. | 63 // Default is false. |
64 void set_check_on_null_data(bool value) { check_on_null_data_ = value; } | 64 void set_check_on_null_data(bool value) { check_on_null_data_ = value; } |
65 | 65 |
66 // Adds a view with an automatically generated unique ID. See AddWithID. | 66 // Adds a view with an automatically generated unique ID. See AddWithID. |
67 KeyType Add(T* data) { | 67 KeyType Add(T* data) { |
68 DCHECK(sequence_checker_.CalledOnValidSequencedThread()); | 68 DCHECK(sequence_checker_.CalledOnValidSequence()); |
69 DCHECK(!check_on_null_data_ || data); | 69 DCHECK(!check_on_null_data_ || data); |
70 KeyType this_id = next_id_; | 70 KeyType this_id = next_id_; |
71 DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item"; | 71 DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item"; |
72 data_[this_id] = data; | 72 data_[this_id] = data; |
73 next_id_++; | 73 next_id_++; |
74 return this_id; | 74 return this_id; |
75 } | 75 } |
76 | 76 |
77 // Adds a new data member with the specified ID. The ID must not be in | 77 // Adds a new data member with the specified ID. The ID must not be in |
78 // the list. The caller either must generate all unique IDs itself and use | 78 // the list. The caller either must generate all unique IDs itself and use |
79 // this function, or allow this object to generate IDs and call Add. These | 79 // this function, or allow this object to generate IDs and call Add. These |
80 // two methods may not be mixed, or duplicate IDs may be generated | 80 // two methods may not be mixed, or duplicate IDs may be generated |
81 void AddWithID(T* data, KeyType id) { | 81 void AddWithID(T* data, KeyType id) { |
82 DCHECK(sequence_checker_.CalledOnValidSequencedThread()); | 82 DCHECK(sequence_checker_.CalledOnValidSequence()); |
83 DCHECK(!check_on_null_data_ || data); | 83 DCHECK(!check_on_null_data_ || data); |
84 DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item"; | 84 DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item"; |
85 data_[id] = data; | 85 data_[id] = data; |
86 } | 86 } |
87 | 87 |
88 void Remove(KeyType id) { | 88 void Remove(KeyType id) { |
89 DCHECK(sequence_checker_.CalledOnValidSequencedThread()); | 89 DCHECK(sequence_checker_.CalledOnValidSequence()); |
90 typename HashTable::iterator i = data_.find(id); | 90 typename HashTable::iterator i = data_.find(id); |
91 if (i == data_.end()) { | 91 if (i == data_.end()) { |
92 NOTREACHED() << "Attempting to remove an item not in the list"; | 92 NOTREACHED() << "Attempting to remove an item not in the list"; |
93 return; | 93 return; |
94 } | 94 } |
95 | 95 |
96 if (iteration_depth_ == 0) { | 96 if (iteration_depth_ == 0) { |
97 Releaser<OS, 0>::release(i->second); | 97 Releaser<OS, 0>::release(i->second); |
98 data_.erase(i); | 98 data_.erase(i); |
99 } else { | 99 } else { |
100 removed_ids_.insert(id); | 100 removed_ids_.insert(id); |
101 } | 101 } |
102 } | 102 } |
103 | 103 |
104 // Replaces the value for |id| with |new_data| and returns a pointer to the | 104 // Replaces the value for |id| with |new_data| and returns a pointer to the |
105 // existing value. If there is no entry for |id|, the map is not altered and | 105 // existing value. If there is no entry for |id|, the map is not altered and |
106 // nullptr is returned. The OwnershipSemantics of the map have no effect on | 106 // nullptr is returned. The OwnershipSemantics of the map have no effect on |
107 // how the existing value is treated, the IDMap does not delete the existing | 107 // how the existing value is treated, the IDMap does not delete the existing |
108 // value being replaced. | 108 // value being replaced. |
109 T* Replace(KeyType id, T* new_data) { | 109 T* Replace(KeyType id, T* new_data) { |
110 DCHECK(sequence_checker_.CalledOnValidSequencedThread()); | 110 DCHECK(sequence_checker_.CalledOnValidSequence()); |
111 DCHECK(!check_on_null_data_ || new_data); | 111 DCHECK(!check_on_null_data_ || new_data); |
112 typename HashTable::iterator i = data_.find(id); | 112 typename HashTable::iterator i = data_.find(id); |
113 if (i == data_.end()) { | 113 if (i == data_.end()) { |
114 NOTREACHED() << "Attempting to replace an item not in the list"; | 114 NOTREACHED() << "Attempting to replace an item not in the list"; |
115 return nullptr; | 115 return nullptr; |
116 } | 116 } |
117 | 117 |
118 T* temp = i->second; | 118 T* temp = i->second; |
119 i->second = new_data; | 119 i->second = new_data; |
120 return temp; | 120 return temp; |
121 } | 121 } |
122 | 122 |
123 void Clear() { | 123 void Clear() { |
124 DCHECK(sequence_checker_.CalledOnValidSequencedThread()); | 124 DCHECK(sequence_checker_.CalledOnValidSequence()); |
125 if (iteration_depth_ == 0) { | 125 if (iteration_depth_ == 0) { |
126 Releaser<OS, 0>::release_all(&data_); | 126 Releaser<OS, 0>::release_all(&data_); |
127 } else { | 127 } else { |
128 for (typename HashTable::iterator i = data_.begin(); | 128 for (typename HashTable::iterator i = data_.begin(); |
129 i != data_.end(); ++i) | 129 i != data_.end(); ++i) |
130 removed_ids_.insert(i->first); | 130 removed_ids_.insert(i->first); |
131 } | 131 } |
132 } | 132 } |
133 | 133 |
134 bool IsEmpty() const { | 134 bool IsEmpty() const { |
135 DCHECK(sequence_checker_.CalledOnValidSequencedThread()); | 135 DCHECK(sequence_checker_.CalledOnValidSequence()); |
136 return size() == 0u; | 136 return size() == 0u; |
137 } | 137 } |
138 | 138 |
139 T* Lookup(KeyType id) const { | 139 T* Lookup(KeyType id) const { |
140 DCHECK(sequence_checker_.CalledOnValidSequencedThread()); | 140 DCHECK(sequence_checker_.CalledOnValidSequence()); |
141 typename HashTable::const_iterator i = data_.find(id); | 141 typename HashTable::const_iterator i = data_.find(id); |
142 if (i == data_.end()) | 142 if (i == data_.end()) |
143 return NULL; | 143 return NULL; |
144 return i->second; | 144 return i->second; |
145 } | 145 } |
146 | 146 |
147 size_t size() const { | 147 size_t size() const { |
148 DCHECK(sequence_checker_.CalledOnValidSequencedThread()); | 148 DCHECK(sequence_checker_.CalledOnValidSequence()); |
149 return data_.size() - removed_ids_.size(); | 149 return data_.size() - removed_ids_.size(); |
150 } | 150 } |
151 | 151 |
152 #if defined(UNIT_TEST) | 152 #if defined(UNIT_TEST) |
153 int iteration_depth() const { | 153 int iteration_depth() const { |
154 return iteration_depth_; | 154 return iteration_depth_; |
155 } | 155 } |
156 #endif // defined(UNIT_TEST) | 156 #endif // defined(UNIT_TEST) |
157 | 157 |
158 // It is safe to remove elements from the map during iteration. All iterators | 158 // It is safe to remove elements from the map during iteration. All iterators |
(...skipping 14 matching lines...) Expand all Loading... |
173 } | 173 } |
174 | 174 |
175 const Iterator& operator=(const Iterator& iter) { | 175 const Iterator& operator=(const Iterator& iter) { |
176 map_ = iter.map; | 176 map_ = iter.map; |
177 iter_ = iter.iter; | 177 iter_ = iter.iter; |
178 Init(); | 178 Init(); |
179 return *this; | 179 return *this; |
180 } | 180 } |
181 | 181 |
182 ~Iterator() { | 182 ~Iterator() { |
183 DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread()); | 183 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); |
184 | 184 |
185 // We're going to decrement iteration depth. Make sure it's greater than | 185 // We're going to decrement iteration depth. Make sure it's greater than |
186 // zero so that it doesn't become negative. | 186 // zero so that it doesn't become negative. |
187 DCHECK_LT(0, map_->iteration_depth_); | 187 DCHECK_LT(0, map_->iteration_depth_); |
188 | 188 |
189 if (--map_->iteration_depth_ == 0) | 189 if (--map_->iteration_depth_ == 0) |
190 map_->Compact(); | 190 map_->Compact(); |
191 } | 191 } |
192 | 192 |
193 bool IsAtEnd() const { | 193 bool IsAtEnd() const { |
194 DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread()); | 194 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); |
195 return iter_ == map_->data_.end(); | 195 return iter_ == map_->data_.end(); |
196 } | 196 } |
197 | 197 |
198 KeyType GetCurrentKey() const { | 198 KeyType GetCurrentKey() const { |
199 DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread()); | 199 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); |
200 return iter_->first; | 200 return iter_->first; |
201 } | 201 } |
202 | 202 |
203 ReturnType* GetCurrentValue() const { | 203 ReturnType* GetCurrentValue() const { |
204 DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread()); | 204 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); |
205 return iter_->second; | 205 return iter_->second; |
206 } | 206 } |
207 | 207 |
208 void Advance() { | 208 void Advance() { |
209 DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread()); | 209 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); |
210 ++iter_; | 210 ++iter_; |
211 SkipRemovedEntries(); | 211 SkipRemovedEntries(); |
212 } | 212 } |
213 | 213 |
214 private: | 214 private: |
215 void Init() { | 215 void Init() { |
216 DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread()); | 216 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); |
217 ++map_->iteration_depth_; | 217 ++map_->iteration_depth_; |
218 SkipRemovedEntries(); | 218 SkipRemovedEntries(); |
219 } | 219 } |
220 | 220 |
221 void SkipRemovedEntries() { | 221 void SkipRemovedEntries() { |
222 while (iter_ != map_->data_.end() && | 222 while (iter_ != map_->data_.end() && |
223 map_->removed_ids_.find(iter_->first) != | 223 map_->removed_ids_.find(iter_->first) != |
224 map_->removed_ids_.end()) { | 224 map_->removed_ids_.end()) { |
225 ++iter_; | 225 ++iter_; |
226 } | 226 } |
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
276 | 276 |
277 // See description above setter. | 277 // See description above setter. |
278 bool check_on_null_data_; | 278 bool check_on_null_data_; |
279 | 279 |
280 base::SequenceChecker sequence_checker_; | 280 base::SequenceChecker sequence_checker_; |
281 | 281 |
282 DISALLOW_COPY_AND_ASSIGN(IDMap); | 282 DISALLOW_COPY_AND_ASSIGN(IDMap); |
283 }; | 283 }; |
284 | 284 |
285 #endif // BASE_ID_MAP_H_ | 285 #endif // BASE_ID_MAP_H_ |
OLD | NEW |