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.
4
5#ifndef EXTENSIONS_COMMON_PERMISSIONS_BASE_SET_OPERATORS_H_
6#define EXTENSIONS_COMMON_PERMISSIONS_BASE_SET_OPERATORS_H_
7
8#include <stddef.h>
9
10#include <iterator>
11#include <map>
12#include <memory>
13
14#include "base/logging.h"
15
16namespace extensions {
17
18// Traits for template paramater of |BaseSetOperators<T>|. Specializations
19// should define |ElementType| for the type of elements to store in the set,
20// and |EmementIDType| for the type of element identifiers.
21template <typename T>
22struct BaseSetOperatorsTraits {};
23
24// Set operations shared by |APIPermissionSet| and |ManifestPermissionSet|.
25//
26// TODO(rpaquay): It would be nice to remove the need for the sub-classes and
27// instead directly use this class where needed.
28template <typename T>
29class BaseSetOperators {
30 public:
31 typedef typename BaseSetOperatorsTraits<T>::ElementType ElementType;
32 typedef typename BaseSetOperatorsTraits<T>::ElementIDType ElementIDType;
33
34 using Map = std::map<ElementIDType, std::unique_ptr<ElementType>>;
35
36 class const_iterator :
37 public std::iterator<std::input_iterator_tag, const ElementType*> {
38 public:
39 const_iterator(const typename Map::const_iterator& it) : it_(it) {}
40 const_iterator(const const_iterator& ids_it) : it_(ids_it.it_) {}
41
42 const_iterator& operator++() {
43 ++it_;
44 return *this;
45 }
46
47 const_iterator operator++(int) {
48 const_iterator tmp(it_++);
49 return tmp;
50 }
51
52 bool operator==(const const_iterator& rhs) const {
53 return it_ == rhs.it_;
54 }
55
56 bool operator!=(const const_iterator& rhs) const {
57 return it_ != rhs.it_;
58 }
59
60 const ElementType* operator*() const {
61 return it_->second.get();
62 }
63
64 const ElementType* operator->() const {
65 return it_->second.get();
66 }
67
68 private:
69 typename Map::const_iterator it_;
70 };
71
72 BaseSetOperators() {
73 // Ensure |T| is convertible to us, so we can safely downcast when calling
74 // methods that must exist in |T|.
75 static_assert(std::is_convertible<T*, BaseSetOperators<T>*>::value,
76 "U ptr must implicitly convert to T ptr");
77 }
78
79 BaseSetOperators(BaseSetOperators<T>&& other) = default;
80 BaseSetOperators<T>& operator=(BaseSetOperators<T>&& rhs) = default;
81
82 ~BaseSetOperators() {}
83
84 bool operator==(const T& rhs) const {
85 return Equal(rhs);
86 }
87
88 bool operator!=(const T& rhs) const {
89 return !operator==(rhs);
90 }
91
92 T Clone() const {
93 T result;
94 for (const auto* item : *this)
95 result.insert(item->Clone());
96 return result;
97 }
98
99 bool Equal(const T& rhs) const {
100 const_iterator it = begin();
101 const_iterator rhs_it = rhs.begin();
102 const_iterator it_end = end();
103 const_iterator rhs_it_end = rhs.end();
104
105 while (it != it_end && rhs_it != rhs_it_end) {
106 if (it->id() > rhs_it->id())
107 return false;
108 else if (it->id() < rhs_it->id())
109 return false;
110 else if (!it->Equal(*rhs_it))
111 return false;
112 ++it;
113 ++rhs_it;
114 }
115 return it == it_end && rhs_it == rhs_it_end;
116 }
117
118 bool Contains(const T& rhs) const {
119 const_iterator it1 = begin();
120 const_iterator it2 = rhs.begin();
121 const_iterator end1 = end();
122 const_iterator end2 = rhs.end();
123
124 while (it1 != end1 && it2 != end2) {
125 if (it1->id() > it2->id()) {
126 return false;
127 } else if (it1->id() < it2->id()) {
128 ++it1;
129 } else {
130 if (!it1->Contains(*it2))
131 return false;
132 ++it1;
133 ++it2;
134 }
135 }
136
137 return it2 == end2;
138 }
139
140 static void Difference(const T& set1, const T& set2, T* set3) {
141 CHECK(set3);
142 set3->clear();
143
144 const_iterator it1 = set1.begin();
145 const_iterator it2 = set2.begin();
146 const const_iterator end1 = set1.end();
147 const const_iterator end2 = set2.end();
148
149 while (it1 != end1 && it2 != end2) {
150 if (it1->id() < it2->id()) {
151 set3->insert(it1->Clone());
152 ++it1;
153 } else if (it1->id() > it2->id()) {
154 ++it2;
155 } else {
156 std::unique_ptr<ElementType> p = it1->Diff(*it2);
157 if (p)
158 set3->insert(std::move(p));
159 ++it1;
160 ++it2;
161 }
162 }
163
164 while (it1 != end1) {
165 set3->insert(it1->Clone());
166 ++it1;
167 }
168 }
169
170 static void Intersection(const T& set1, const T& set2, T* set3) {
171 DCHECK(set3);
172 set3->clear();
173
174 const_iterator it1 = set1.begin();
175 const_iterator it2 = set2.begin();
176 const const_iterator end1 = set1.end();
177 const const_iterator end2 = set2.end();
178
179 while (it1 != end1 && it2 != end2) {
180 if (it1->id() < it2->id()) {
181 ++it1;
182 } else if (it1->id() > it2->id()) {
183 ++it2;
184 } else {
185 std::unique_ptr<ElementType> p = it1->Intersect(*it2);
186 if (p)
187 set3->insert(std::move(p));
188 ++it1;
189 ++it2;
190 }
191 }
192 }
193
194 static void Union(const T& set1, const T& set2, T* set3) {
195 DCHECK(set3);
196 set3->clear();
197
198 const_iterator it1 = set1.begin();
199 const_iterator it2 = set2.begin();
200 const const_iterator end1 = set1.end();
201 const const_iterator end2 = set2.end();
202
203 while (true) {
204 if (it1 == end1) {
205 while (it2 != end2) {
206 set3->insert(it2->Clone());
207 ++it2;
208 }
209 break;
210 }
211 if (it2 == end2) {
212 while (it1 != end1) {
213 set3->insert(it1->Clone());
214 ++it1;
215 }
216 break;
217 }
218 if (it1->id() < it2->id()) {
219 set3->insert(it1->Clone());
220 ++it1;
221 } else if (it1->id() > it2->id()) {
222 set3->insert(it2->Clone());
223 ++it2;
224 } else {
225 set3->insert(it1->Union(*it2));
226 ++it1;
227 ++it2;
228 }
229 }
230 }
231
232 const_iterator begin() const { return const_iterator(map_.begin()); }
233
234 const_iterator end() const { return map_.end(); }
235
236 const_iterator find(ElementIDType id) const { return map_.find(id); }
237
238 size_t count(ElementIDType id) const { return map_.count(id); }
239
240 bool empty() const { return map_.empty(); }
241
242 size_t erase(ElementIDType id) { return map_.erase(id); }
243
244 void insert(std::unique_ptr<ElementType> item) {
245 ElementIDType id = item->id();
246 map_[id] = std::move(item);
247 }
248
249 size_t size() const { return map_.size(); }
250
251 const Map& map() const {
252 return map_;
253 }
254
255 void clear() {
256 map_.clear();
257 }
258
259 private:
260 Map map_;
261};
262
263} // namespace extensions
264
265#endif // EXTENSIONS_COMMON_PERMISSIONS_BASE_SET_OPERATORS_H_
266