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 <memory> | 10 #include <memory> |
11 #include <set> | 11 #include <set> |
12 #include <type_traits> | 12 #include <type_traits> |
13 #include <utility> | 13 #include <utility> |
14 | 14 |
15 #include "base/containers/hash_tables.h" | 15 #include "base/containers/hash_tables.h" |
16 #include "base/logging.h" | 16 #include "base/logging.h" |
17 #include "base/macros.h" | 17 #include "base/macros.h" |
18 #include "base/sequence_checker.h" | 18 #include "base/sequence_checker.h" |
19 | 19 |
20 // Ownership semantics: | |
21 // - OwnPointer means we store a unique_ptr that owns the object (so the | |
22 // object is deleted in Remove() and during destruction). | |
23 // - ExternalPointer means we store a raw pointer and don't own the object | |
24 | |
25 // TODO (http://crbug.com/647091): eliminate this enum, replace OwnPointer | |
26 // mode in callsites with IDMap<unique_ptr<T>> | |
27 enum IDMapOwnershipSemantics { | |
28 IDMapExternalPointer, | |
29 IDMapOwnPointer | |
30 }; | |
31 | |
32 // This object maintains a list of IDs that can be quickly converted to | 20 // This object maintains a list of IDs that can be quickly converted to |
33 // pointers to objects. It is implemented as a hash table, optimized for | 21 // pointers to objects. It is implemented as a hash table, optimized for |
34 // relatively small data sets (in the common case, there will be exactly one | 22 // relatively small data sets (in the common case, there will be exactly one |
35 // item in the list). | 23 // item in the list). |
36 // | 24 // |
37 // Items can be inserted into the container with arbitrary ID, but the caller | 25 // Items can be inserted into the container with arbitrary ID, but the caller |
38 // must ensure they are unique. Inserting IDs and relying on automatically | 26 // must ensure they are unique. Inserting IDs and relying on automatically |
39 // generated ones is not allowed because they can collide. | 27 // generated ones is not allowed because they can collide. |
40 // | 28 // |
41 // This class does not have a virtual destructor, do not inherit from it when | 29 // This class does not have a virtual destructor, do not inherit from it when |
danakj
2016/11/30 23:02:21
This comment doesn't quite make sense anymore. Doe
rlanday
2016/12/01 00:50:07
Yeah it looks like nothing inherits from this
| |
42 // ownership semantics are set to own because pointers will leak. | 30 // ownership semantics are set to own because pointers will leak. |
43 template <typename T, | 31 template <typename V, typename K = int32_t> |
danakj
2016/11/30 23:02:21
Maybe worth a comment now saying that the values (
rlanday
2016/12/01 00:50:07
Ok, that's a good point
| |
44 IDMapOwnershipSemantics OS = IDMapExternalPointer, | |
45 typename K = int32_t> | |
46 class IDMap { | 32 class IDMap { |
47 public: | 33 public: |
48 using KeyType = K; | 34 using KeyType = K; |
49 | 35 |
50 private: | 36 private: |
51 using V = typename std:: | 37 using T = typename std::remove_reference<decltype(*V())>::type; |
52 conditional<OS == IDMapExternalPointer, T*, std::unique_ptr<T>>::type; | |
53 using HashTable = base::hash_map<KeyType, V>; | 38 using HashTable = base::hash_map<KeyType, V>; |
54 | 39 |
55 public: | 40 public: |
56 IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) { | 41 IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) { |
57 // A number of consumers of IDMap create it on one thread but always | 42 // A number of consumers of IDMap create it on one thread but always |
58 // access it from a different, but consistent, thread (or sequence) | 43 // access it from a different, but consistent, thread (or sequence) |
59 // post-construction. The first call to CalledOnValidSequence() will re-bind | 44 // post-construction. The first call to CalledOnValidSequence() will re-bind |
60 // it. | 45 // it. |
61 sequence_checker_.DetachFromSequence(); | 46 sequence_checker_.DetachFromSequence(); |
62 } | 47 } |
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
142 int iteration_depth() const { | 127 int iteration_depth() const { |
143 return iteration_depth_; | 128 return iteration_depth_; |
144 } | 129 } |
145 #endif // defined(UNIT_TEST) | 130 #endif // defined(UNIT_TEST) |
146 | 131 |
147 // It is safe to remove elements from the map during iteration. All iterators | 132 // It is safe to remove elements from the map during iteration. All iterators |
148 // will remain valid. | 133 // will remain valid. |
149 template<class ReturnType> | 134 template<class ReturnType> |
150 class Iterator { | 135 class Iterator { |
151 public: | 136 public: |
152 Iterator(IDMap<T, OS, K>* map) | 137 Iterator(IDMap<V, K>* map) : map_(map), iter_(map_->data_.begin()) { |
153 : map_(map), | |
154 iter_(map_->data_.begin()) { | |
155 Init(); | 138 Init(); |
156 } | 139 } |
157 | 140 |
158 Iterator(const Iterator& iter) | 141 Iterator(const Iterator& iter) |
159 : map_(iter.map_), | 142 : map_(iter.map_), |
160 iter_(iter.iter_) { | 143 iter_(iter.iter_) { |
161 Init(); | 144 Init(); |
162 } | 145 } |
163 | 146 |
164 const Iterator& operator=(const Iterator& iter) { | 147 const Iterator& operator=(const Iterator& iter) { |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
208 } | 191 } |
209 | 192 |
210 void SkipRemovedEntries() { | 193 void SkipRemovedEntries() { |
211 while (iter_ != map_->data_.end() && | 194 while (iter_ != map_->data_.end() && |
212 map_->removed_ids_.find(iter_->first) != | 195 map_->removed_ids_.find(iter_->first) != |
213 map_->removed_ids_.end()) { | 196 map_->removed_ids_.end()) { |
214 ++iter_; | 197 ++iter_; |
215 } | 198 } |
216 } | 199 } |
217 | 200 |
218 IDMap<T, OS, K>* map_; | 201 IDMap<V, K>* map_; |
219 typename HashTable::const_iterator iter_; | 202 typename HashTable::const_iterator iter_; |
220 }; | 203 }; |
221 | 204 |
222 typedef Iterator<T> iterator; | 205 typedef Iterator<T> iterator; |
223 typedef Iterator<const T> const_iterator; | 206 typedef Iterator<const T> const_iterator; |
224 | 207 |
225 private: | 208 private: |
226 KeyType AddInternal(V data) { | 209 KeyType AddInternal(V data) { |
227 DCHECK(sequence_checker_.CalledOnValidSequence()); | 210 DCHECK(sequence_checker_.CalledOnValidSequence()); |
228 DCHECK(!check_on_null_data_ || data); | 211 DCHECK(!check_on_null_data_ || data); |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
263 | 246 |
264 // See description above setter. | 247 // See description above setter. |
265 bool check_on_null_data_; | 248 bool check_on_null_data_; |
266 | 249 |
267 base::SequenceChecker sequence_checker_; | 250 base::SequenceChecker sequence_checker_; |
268 | 251 |
269 DISALLOW_COPY_AND_ASSIGN(IDMap); | 252 DISALLOW_COPY_AND_ASSIGN(IDMap); |
270 }; | 253 }; |
271 | 254 |
272 #endif // BASE_ID_MAP_H_ | 255 #endif // BASE_ID_MAP_H_ |
OLD | NEW |