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
3 // found in the LICENSE file.
11 #include "base/basictypes.h"
12 #include "base/hash_tables.h"
13 #include "base/logging.h"
14 #include "base/threading/non_thread_safe.h"
16 // Ownership semantics - own pointer means the pointer is deleted in Remove()
17 // & during destruction
18 enum IDMapOwnershipSemantics
{
23 // This object maintains a list of IDs that can be quickly converted to
24 // pointers to objects. It is implemented as a hash table, optimized for
25 // relatively small data sets (in the common case, there will be exactly one
28 // Items can be inserted into the container with arbitrary ID, but the caller
29 // must ensure they are unique. Inserting IDs and relying on automatically
30 // generated ones is not allowed because they can collide.
32 // This class does not have a virtual destructor, do not inherit from it when
33 // ownership semantics are set to own because pointers will leak.
34 template<typename T
, IDMapOwnershipSemantics OS
= IDMapExternalPointer
>
35 class IDMap
: public base::NonThreadSafe
{
37 typedef int32 KeyType
;
38 typedef base::hash_map
<KeyType
, T
*> HashTable
;
41 IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) {
42 // A number of consumers of IDMap create it on one thread but always access
43 // it from a different, but consitent, thread post-construction.
48 // Many IDMap's are static, and hence will be destroyed on the main thread.
49 // However, all the accesses may take place on another thread, such as the
50 // IO thread. Detaching again to clean this up.
52 Releaser
<OS
, 0>::release_all(&data_
);
55 // Sets whether Add should CHECK if passed in NULL data. Default is false.
56 void set_check_on_null_data(bool value
) { check_on_null_data_
= value
; }
58 // Adds a view with an automatically generated unique ID. See AddWithID.
59 KeyType
Add(T
* data
) {
60 DCHECK(CalledOnValidThread());
61 CHECK(!check_on_null_data_
|| data
);
62 KeyType this_id
= next_id_
;
63 DCHECK(data_
.find(this_id
) == data_
.end()) << "Inserting duplicate item";
64 data_
[this_id
] = data
;
69 // Adds a new data member with the specified ID. The ID must not be in
70 // the list. The caller either must generate all unique IDs itself and use
71 // this function, or allow this object to generate IDs and call Add. These
72 // two methods may not be mixed, or duplicate IDs may be generated
73 void AddWithID(T
* data
, KeyType id
) {
74 DCHECK(CalledOnValidThread());
75 CHECK(!check_on_null_data_
|| data
);
76 DCHECK(data_
.find(id
) == data_
.end()) << "Inserting duplicate item";
80 void Remove(KeyType id
) {
81 DCHECK(CalledOnValidThread());
82 typename
HashTable::iterator i
= data_
.find(id
);
83 if (i
== data_
.end()) {
84 NOTREACHED() << "Attempting to remove an item not in the list";
88 if (iteration_depth_
== 0) {
89 Releaser
<OS
, 0>::release(i
->second
);
92 removed_ids_
.insert(id
);
96 bool IsEmpty() const {
97 DCHECK(CalledOnValidThread());
101 T
* Lookup(KeyType id
) const {
102 DCHECK(CalledOnValidThread());
103 typename
HashTable::const_iterator i
= data_
.find(id
);
104 if (i
== data_
.end())
109 size_t size() const {
110 DCHECK(CalledOnValidThread());
111 return data_
.size() - removed_ids_
.size();
114 // It is safe to remove elements from the map during iteration. All iterators
115 // will remain valid.
116 template<class ReturnType
>
119 Iterator(IDMap
<T
, OS
>* map
)
121 iter_(map_
->data_
.begin()) {
122 DCHECK(map
->CalledOnValidThread());
123 ++map_
->iteration_depth_
;
124 SkipRemovedEntries();
128 DCHECK(map_
->CalledOnValidThread());
129 if (--map_
->iteration_depth_
== 0)
133 bool IsAtEnd() const {
134 DCHECK(map_
->CalledOnValidThread());
135 return iter_
== map_
->data_
.end();
138 KeyType
GetCurrentKey() const {
139 DCHECK(map_
->CalledOnValidThread());
143 ReturnType
* GetCurrentValue() const {
144 DCHECK(map_
->CalledOnValidThread());
145 return iter_
->second
;
149 DCHECK(map_
->CalledOnValidThread());
151 SkipRemovedEntries();
155 void SkipRemovedEntries() {
156 while (iter_
!= map_
->data_
.end() &&
157 map_
->removed_ids_
.find(iter_
->first
) !=
158 map_
->removed_ids_
.end()) {
164 typename
HashTable::const_iterator iter_
;
167 typedef Iterator
<T
> iterator
;
168 typedef Iterator
<const T
> const_iterator
;
172 // The dummy parameter is there because C++ standard does not allow
173 // explicitly specialized templates inside classes
174 template<IDMapOwnershipSemantics OI
, int dummy
> struct Releaser
{
175 static inline void release(T
* ptr
) {}
176 static inline void release_all(HashTable
* table
) {}
179 template<int dummy
> struct Releaser
<IDMapOwnPointer
, dummy
> {
180 static inline void release(T
* ptr
) { delete ptr
;}
181 static inline void release_all(HashTable
* table
) {
182 for (typename
HashTable::iterator i
= table
->begin();
183 i
!= table
->end(); ++i
) {
191 DCHECK_EQ(0, iteration_depth_
);
192 for (std::set
<KeyType
>::const_iterator i
= removed_ids_
.begin();
193 i
!= removed_ids_
.end(); ++i
) {
196 removed_ids_
.clear();
199 // Keep track of how many iterators are currently iterating on us to safely
200 // handle removing items during iteration.
201 int iteration_depth_
;
203 // Keep set of IDs that should be removed after the outermost iteration has
204 // finished. This way we manage to not invalidate the iterator when an element
206 std::set
<KeyType
> removed_ids_
;
208 // The next ID that we will return from Add()
213 // See description above setter.
214 bool check_on_null_data_
;
216 DISALLOW_COPY_AND_ASSIGN(IDMap
);
219 #endif // BASE_ID_MAP_H_