1 // Copyright 2013 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.
5 #ifndef EXTENSIONS_COMMON_PERMISSIONS_BASE_SET_OPERATORS_H_
6 #define EXTENSIONS_COMMON_PERMISSIONS_BASE_SET_OPERATORS_H_
11 #include "base/memory/linked_ptr.h"
12 #include "base/template_util.h"
14 namespace extensions
{
16 // Traits for template paramater of |BaseSetOperators<T>|. Specializations
17 // should define |ElementType| for the type of elements to store in the set,
18 // and |EmementIDType| for the type of element identifiers.
20 struct BaseSetOperatorsTraits
{};
22 // Set operations shared by |APIPermissionSet| and |ManifestPermissionSet|.
24 // TODO(rpaquay): It would be nice to remove the need for the sub-classes and
25 // instead directly use this class where needed.
27 class BaseSetOperators
{
29 typedef typename BaseSetOperatorsTraits
<T
>::ElementType ElementType
;
30 typedef typename BaseSetOperatorsTraits
<T
>::ElementIDType ElementIDType
;
31 typedef std::map
<ElementIDType
, linked_ptr
<ElementType
> > Map
;
33 class const_iterator
:
34 public std::iterator
<std::input_iterator_tag
, const ElementType
*> {
36 const_iterator(const typename
Map::const_iterator
& it
) : it_(it
) {}
37 const_iterator(const const_iterator
& ids_it
) : it_(ids_it
.it_
) {}
39 const_iterator
& operator++() {
44 const_iterator
operator++(int) {
45 const_iterator
tmp(it_
++);
49 bool operator==(const const_iterator
& rhs
) const {
50 return it_
== rhs
.it_
;
53 bool operator!=(const const_iterator
& rhs
) const {
54 return it_
!= rhs
.it_
;
57 const ElementType
* operator*() const {
58 return it_
->second
.get();
61 const ElementType
* operator->() const {
62 return it_
->second
.get();
66 typename
Map::const_iterator it_
;
70 // Ensure |T| is convertible to us, so we can safely downcast when calling
71 // methods that must exist in |T|.
72 COMPILE_ASSERT((base::is_convertible
<T
*, BaseSetOperators
<T
>*>::value
),
73 U_ptr_must_implicitly_convert_to_T_ptr
);
76 BaseSetOperators(const T
& set
) {
80 ~BaseSetOperators() {}
82 T
& operator=(const T
& rhs
) {
86 bool operator==(const T
& rhs
) const {
90 bool operator!=(const T
& rhs
) const {
91 return !operator==(rhs
);
94 T
& Assign(const T
& rhs
) {
95 const_iterator it
= rhs
.begin();
96 const const_iterator end
= rhs
.end();
101 return *static_cast<T
*>(this);
104 bool Equal(const T
& rhs
) const {
105 const_iterator it
= begin();
106 const_iterator rhs_it
= rhs
.begin();
107 const_iterator it_end
= end();
108 const_iterator rhs_it_end
= rhs
.end();
110 while (it
!= it_end
&& rhs_it
!= rhs_it_end
) {
111 if (it
->id() > rhs_it
->id())
113 else if (it
->id() < rhs_it
->id())
115 else if (!it
->Equal(*rhs_it
))
120 return it
== it_end
&& rhs_it
== rhs_it_end
;
123 bool Contains(const T
& rhs
) const {
124 const_iterator it1
= begin();
125 const_iterator it2
= rhs
.begin();
126 const_iterator end1
= end();
127 const_iterator end2
= rhs
.end();
129 while (it1
!= end1
&& it2
!= end2
) {
130 if (it1
->id() > it2
->id()) {
132 } else if (it1
->id() < it2
->id()) {
135 if (!it1
->Contains(*it2
))
145 static void Difference(const T
& set1
, const T
& set2
, T
* set3
) {
149 const_iterator it1
= set1
.begin();
150 const_iterator it2
= set2
.begin();
151 const const_iterator end1
= set1
.end();
152 const const_iterator end2
= set2
.end();
154 while (it1
!= end1
&& it2
!= end2
) {
155 if (it1
->id() < it2
->id()) {
156 set3
->insert(it1
->Clone());
158 } else if (it1
->id() > it2
->id()) {
161 ElementType
* p
= it1
->Diff(*it2
);
169 while (it1
!= end1
) {
170 set3
->insert(it1
->Clone());
175 static void Intersection(const T
& set1
, const T
& set2
, T
* set3
) {
179 const_iterator it1
= set1
.begin();
180 const_iterator it2
= set2
.begin();
181 const const_iterator end1
= set1
.end();
182 const const_iterator end2
= set2
.end();
184 while (it1
!= end1
&& it2
!= end2
) {
185 if (it1
->id() < it2
->id()) {
187 } else if (it1
->id() > it2
->id()) {
190 ElementType
* p
= it1
->Intersect(*it2
);
199 static void Union(const T
& set1
, const T
& set2
, T
* set3
) {
203 const_iterator it1
= set1
.begin();
204 const_iterator it2
= set2
.begin();
205 const const_iterator end1
= set1
.end();
206 const const_iterator end2
= set2
.end();
210 while (it2
!= end2
) {
211 set3
->insert(it2
->Clone());
217 while (it1
!= end1
) {
218 set3
->insert(it1
->Clone());
223 if (it1
->id() < it2
->id()) {
224 set3
->insert(it1
->Clone());
226 } else if (it1
->id() > it2
->id()) {
227 set3
->insert(it2
->Clone());
230 set3
->insert(it1
->Union(*it2
));
237 const_iterator
begin() const {
238 return const_iterator(map().begin());
241 const_iterator
end() const {
245 const_iterator
find(ElementIDType id
) const {
246 return map().find(id
);
249 size_t count(ElementIDType id
) const {
250 return map().count(id
);
254 return map().empty();
257 size_t erase(ElementIDType id
) {
258 return map().erase(id
);
261 // Take ownership and insert |item| into the set.
262 void insert(ElementType
* item
) {
263 map_
[item
->id()].reset(item
);
266 size_t size() const {
270 const Map
& map() const {
286 } // namespace extensions
288 #endif // EXTENSIONS_COMMON_PERMISSIONS_BASE_SET_OPERATORS_H_