extensions/common/permissions/base_set_operators.h

   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
  14 namespace 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.
  19 template <typename T>
  20 struct 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.
  26 template <typename T>
  27 class 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     static_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_