| 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 |