cc/base/scoped_ptr_vector.h

   1 // Copyright 2012 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 CC_BASE_SCOPED_PTR_VECTOR_H_
   6 #define CC_BASE_SCOPED_PTR_VECTOR_H_
   7
   8 #include <algorithm>
   9 #include <vector>
  10
  11 #include "base/basictypes.h"
  12 #include "base/logging.h"
  13 #include "base/memory/scoped_ptr.h"
  14 #include "base/stl_util.h"
  15
  16 namespace cc {
  17
  18 // This type acts like a vector<scoped_ptr> based on top of std::vector. The
  19 // ScopedPtrVector has ownership of all elements in the vector.
  20 template <typename T>
  21 class ScopedPtrVector {
  22  public:
  23   typedef typename std::vector<T*>::const_iterator const_iterator;
  24   typedef typename std::vector<T*>::reverse_iterator reverse_iterator;
  25   typedef typename std::vector<T*>::const_reverse_iterator
  26       const_reverse_iterator;
  27
  28 #if defined(OS_ANDROID)
  29   // On Android the iterator is not a class, so we can't block assignment.
  30   typedef typename std::vector<T*>::iterator iterator;
  31 #else
  32   // Ban setting values on the iterator directly. New pointers must be passed
  33   // to methods on the ScopedPtrVector class to appear in the vector.
  34   class iterator : public std::vector<T*>::iterator {
  35    public:
  36     iterator(const typename std::vector<T*>::iterator& other) // NOLINT
  37         : std::vector<T*>::iterator(other) {}
  38     T* const& operator*() { return std::vector<T*>::iterator::operator*(); }
  39   };
  40 #endif
  41
  42   ScopedPtrVector() {}
  43
  44   ~ScopedPtrVector() { clear(); }
  45
  46   size_t size() const {
  47     return data_.size();
  48   }
  49
  50   T* at(size_t index) const {
  51     DCHECK(index < size());
  52     return data_[index];
  53   }
  54
  55   T* operator[](size_t index) const {
  56     return at(index);
  57   }
  58
  59   T* front() const {
  60     DCHECK(!empty());
  61     return at(0);
  62   }
  63
  64   T* back() const {
  65     DCHECK(!empty());
  66     return at(size() - 1);
  67   }
  68
  69   bool empty() const {
  70     return data_.empty();
  71   }
  72
  73   scoped_ptr<T> take(iterator position) {
  74     if (position == end())
  75       return nullptr;
  76     DCHECK(position < end());
  77
  78     typename std::vector<T*>::iterator writable_position = position;
  79     scoped_ptr<T> ret(*writable_position);
  80     *writable_position = nullptr;
  81     return ret.Pass();
  82   }
  83
  84   scoped_ptr<T> take_back() {
  85     DCHECK(!empty());
  86     if (empty())
  87       return nullptr;
  88     return take(end() - 1);
  89   }
  90
  91   void erase(iterator position) {
  92     if (position == end())
  93       return;
  94     typename std::vector<T*>::iterator writable_position = position;
  95     delete *writable_position;
  96     data_.erase(position);
  97   }
  98
  99   void erase(iterator first, iterator last) {
 100     DCHECK(first <= last);
 101     for (iterator it = first; it != last; ++it) {
 102       DCHECK(it < end());
 103
 104       typename std::vector<T*>::iterator writable_it = it;
 105       delete *writable_it;
 106     }
 107     data_.erase(first, last);
 108   }
 109
 110   void reserve(size_t size) {
 111     data_.reserve(size);
 112   }
 113
 114   void clear() {
 115     STLDeleteElements(&data_);
 116   }
 117
 118   void push_back(scoped_ptr<T> item) {
 119     data_.push_back(item.release());
 120   }
 121
 122   void pop_back() {
 123     delete data_.back();
 124     data_.pop_back();
 125   }
 126
 127   void insert(iterator position, scoped_ptr<T> item) {
 128     DCHECK(position <= end());
 129     data_.insert(position, item.release());
 130   }
 131
 132   void insert_and_take(iterator position, ScopedPtrVector<T>* other) {
 133     std::vector<T*> tmp_data;
 134     for (ScopedPtrVector<T>::iterator it = other->begin(); it != other->end();
 135          ++it) {
 136       tmp_data.push_back(other->take(it).release());
 137     }
 138     data_.insert(position, tmp_data.begin(), tmp_data.end());
 139   }
 140
 141   template <typename Predicate>
 142   iterator partition(Predicate predicate) {
 143     typename std::vector<T*>::iterator first = begin();
 144     typename std::vector<T*>::iterator last = end();
 145     return static_cast<iterator>(std::partition(first, last, predicate));
 146   }
 147
 148   void swap(ScopedPtrVector<T>& other) {
 149     data_.swap(other.data_);
 150   }
 151
 152   void swap(iterator a, iterator b) {
 153     DCHECK(a < end());
 154     DCHECK(b < end());
 155     if (a == end() || b == end() || a == b)
 156       return;
 157     typename std::vector<T*>::iterator writable_a = a;
 158     typename std::vector<T*>::iterator writable_b = b;
 159     std::swap(*writable_a, *writable_b);
 160   }
 161
 162   // This acts like std::remove_if but with one key difference. The values to be
 163   // removed to will each appear exactly once at or after the returned iterator,
 164   // so that erase(foo.remove_if(P), foo.end()) will not leak or double-free the
 165   // pointers in the vector.
 166   template <typename Predicate>
 167   iterator remove_if(Predicate predicate) {
 168     typename std::vector<T*>::iterator it =
 169         std::find_if(data_.begin(), data_.end(), predicate);
 170     typename std::vector<T*>::iterator end = data_.end();
 171     if (it == end)
 172       return it;
 173     typename std::vector<T*>::iterator result = it;
 174     ++it;
 175     for (; it != end; ++it) {
 176       if (!static_cast<bool>(predicate(*it))) {
 177         // Swap here instead of just assign to |result| so that all the
 178         // pointers are preserved to be deleted afterward.
 179         std::swap(*result, *it);
 180         ++result;
 181       }
 182     }
 183     return result;
 184   }
 185
 186   template<class Compare>
 187   inline void sort(Compare comp) {
 188     std::sort(data_.begin(), data_.end(), comp);
 189   }
 190
 191   template <class Compare>
 192   inline void make_heap(Compare comp) {
 193     std::make_heap(data_.begin(), data_.end(), comp);
 194   }
 195
 196   template <class Compare>
 197   inline void push_heap(Compare comp) {
 198     std::push_heap(data_.begin(), data_.end(), comp);
 199   }
 200
 201   template <class Compare>
 202   inline void pop_heap(Compare comp) {
 203     std::pop_heap(data_.begin(), data_.end(), comp);
 204   }
 205
 206   iterator begin() { return static_cast<iterator>(data_.begin()); }
 207   const_iterator begin() const { return data_.begin(); }
 208   iterator end() { return static_cast<iterator>(data_.end()); }
 209   const_iterator end() const { return data_.end(); }
 210
 211   reverse_iterator rbegin() { return data_.rbegin(); }
 212   const_reverse_iterator rbegin() const { return data_.rbegin(); }
 213   reverse_iterator rend() { return data_.rend(); }
 214   const_reverse_iterator rend() const { return data_.rend(); }
 215
 216  private:
 217   std::vector<T*> data_;
 218
 219   DISALLOW_COPY_AND_ASSIGN(ScopedPtrVector);
 220 };
 221
 222 }  // namespace cc
 223
 224 #endif  // CC_BASE_SCOPED_PTR_VECTOR_H_