base_set_operators.h revision f2477e01787aa58f445919b809d89e252beef54f 
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 <iterator>
9#include <map>
10
11#include "base/memory/linked_ptr.h"
12#include "base/template_util.h"
13
14namespace extensions {
15
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.
19template <typename T>
20struct BaseSetOperatorsTraits {};
21
22// Set operations shared by |APIPermissionSet| and |ManifestPermissionSet|.
23//
24// TODO(rpaquay): It would be nice to remove the need for the sub-classes and
25// instead directly use this class where needed.
26template <typename T>
27class BaseSetOperators {
28 public:
29  typedef typename BaseSetOperatorsTraits<T>::ElementType ElementType;
30  typedef typename BaseSetOperatorsTraits<T>::ElementIDType ElementIDType;
31  typedef std::map<ElementIDType, linked_ptr<ElementType> > Map;
32
33  class const_iterator :
34    public std::iterator<std::input_iterator_tag, const ElementType*> {
35   public:
36    const_iterator(const typename Map::const_iterator& it) : it_(it) {}
37    const_iterator(const const_iterator& ids_it) : it_(ids_it.it_) {}
38
39    const_iterator& operator++() {
40      ++it_;
41      return *this;
42    }
43
44    const_iterator operator++(int) {
45      const_iterator tmp(it_++);
46      return tmp;
47    }
48
49    bool operator==(const const_iterator& rhs) const {
50      return it_ == rhs.it_;
51    }
52
53    bool operator!=(const const_iterator& rhs) const {
54      return it_ != rhs.it_;
55    }
56
57    const ElementType* operator*() const {
58      return it_->second.get();
59    }
60
61    const ElementType* operator->() const {
62      return it_->second.get();
63    }
64
65   private:
66    typename Map::const_iterator it_;
67  };
68
69  BaseSetOperators() {
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);
74  }
75
76  BaseSetOperators(const T& set) {
77    this->operator=(set);
78  }
79
80  ~BaseSetOperators() {}
81
82  T& operator=(const T& rhs) {
83    return Assign(rhs);
84  }
85
86  bool operator==(const T& rhs) const {
87    return Equal(rhs);
88  }
89
90  bool operator!=(const T& rhs) const {
91    return !operator==(rhs);
92  }
93
94  T& Assign(const T& rhs) {
95    const_iterator it = rhs.begin();
96    const const_iterator end = rhs.end();
97    while (it != end) {
98      insert(it->Clone());
99      ++it;
100    }
101    return *static_cast<T*>(this);
102  }
103
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();
109
110    while (it != it_end && rhs_it != rhs_it_end) {
111      if (it->id() > rhs_it->id())
112        return false;
113      else if (it->id() < rhs_it->id())
114        return false;
115      else if (!it->Equal(*rhs_it))
116        return false;
117      ++it;
118      ++rhs_it;
119    }
120    return it == it_end && rhs_it == rhs_it_end;
121  }
122
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();
128
129    while (it1 != end1 && it2 != end2) {
130      if (it1->id() > it2->id()) {
131        return false;
132      } else if (it1->id() < it2->id()) {
133        ++it1;
134      } else {
135          if (!it1->Contains(*it2))
136            return false;
137        ++it1;
138        ++it2;
139      }
140    }
141
142    return it2 == end2;
143  }
144
145  static void Difference(const T& set1, const T& set2, T* set3) {
146    CHECK(set3);
147    set3->clear();
148
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();
153
154    while (it1 != end1 && it2 != end2) {
155      if (it1->id() < it2->id()) {
156        set3->insert(it1->Clone());
157        ++it1;
158      } else if (it1->id() > it2->id()) {
159        ++it2;
160      } else {
161        ElementType* p = it1->Diff(*it2);
162        if (p)
163          set3->insert(p);
164        ++it1;
165        ++it2;
166      }
167    }
168
169    while (it1 != end1) {
170      set3->insert(it1->Clone());
171      ++it1;
172    }
173  }
174
175  static void Intersection(const T& set1, const T& set2, T* set3) {
176    DCHECK(set3);
177    set3->clear();
178
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();
183
184    while (it1 != end1 && it2 != end2) {
185      if (it1->id() < it2->id()) {
186        ++it1;
187      } else if (it1->id() > it2->id()) {
188        ++it2;
189      } else {
190        ElementType* p = it1->Intersect(*it2);
191        if (p)
192          set3->insert(p);
193        ++it1;
194        ++it2;
195      }
196    }
197  }
198
199  static void Union(const T& set1, const T& set2, T* set3) {
200    DCHECK(set3);
201    set3->clear();
202
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();
207
208    while (true) {
209      if (it1 == end1) {
210        while (it2 != end2) {
211          set3->insert(it2->Clone());
212          ++it2;
213        }
214        break;
215      }
216      if (it2 == end2) {
217        while (it1 != end1) {
218          set3->insert(it1->Clone());
219          ++it1;
220        }
221        break;
222      }
223      if (it1->id() < it2->id()) {
224        set3->insert(it1->Clone());
225        ++it1;
226      } else if (it1->id() > it2->id()) {
227        set3->insert(it2->Clone());
228        ++it2;
229      } else {
230        set3->insert(it1->Union(*it2));
231        ++it1;
232        ++it2;
233      }
234    }
235  }
236
237  const_iterator begin() const {
238    return const_iterator(map().begin());
239  }
240
241  const_iterator end() const {
242    return map().end();
243  }
244
245  const_iterator find(ElementIDType id) const {
246    return map().find(id);
247  }
248
249  size_t count(ElementIDType id) const {
250    return map().count(id);
251  }
252
253  bool empty() const {
254    return map().empty();
255  }
256
257  size_t erase(ElementIDType id) {
258    return map().erase(id);
259  }
260
261  // Take ownership and insert |item| into the set.
262  void insert(ElementType* item) {
263    map_[item->id()].reset(item);
264  }
265
266  size_t size() const {
267    return map().size();
268  }
269
270  const Map& map() const {
271    return map_;
272  }
273
274  Map& map() {
275    return map_;
276  }
277
278  void clear() {
279    map_.clear();
280  }
281
282 private:
283  Map map_;
284};
285
286}  // namespace extensions
287
288#endif  // EXTENSIONS_COMMON_PERMISSIONS_BASE_SET_OPERATORS_H_
289