12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright 2012 The Chromium Authors. All rights reserved. 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file. 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef CC_BASE_SCOPED_PTR_VECTOR_H_ 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define CC_BASE_SCOPED_PTR_VECTOR_H_ 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 8c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include <algorithm> 9c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include <vector> 10c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/basictypes.h" 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/logging.h" 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/memory/scoped_ptr.h" 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/stl_util.h" 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace cc { 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This type acts like a vector<scoped_ptr> based on top of std::vector. The 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// ScopedPtrVector has ownership of all elements in the vector. 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <typename T> 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class ScopedPtrVector { 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 231320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci typedef typename std::vector<T*>::const_iterator const_iterator; 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename std::vector<T*>::reverse_iterator reverse_iterator; 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename std::vector<T*>::const_reverse_iterator 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_reverse_iterator; 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#if defined(OS_ANDROID) 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // On Android the iterator is not a class, so we can't block assignment. 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename std::vector<T*>::iterator iterator; 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#else 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Ban setting values on the iterator directly. New pointers must be passed 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // to methods on the ScopedPtrVector class to appear in the vector. 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) class iterator : public std::vector<T*>::iterator { 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 3690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) iterator(const typename std::vector<T*>::iterator& other) // NOLINT 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : std::vector<T*>::iterator(other) {} 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* const& operator*() { return std::vector<T*>::iterator::operator*(); } 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) }; 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ScopedPtrVector() {} 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ~ScopedPtrVector() { clear(); } 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t size() const { 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return data_.size(); 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* at(size_t index) const { 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(index < size()); 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return data_[index]; 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* operator[](size_t index) const { 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return at(index); 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* front() const { 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!empty()); 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return at(0); 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* back() const { 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!empty()); 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return at(size() - 1); 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool empty() const { 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return data_.empty(); 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_ptr<T> take(iterator position) { 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (position == end()) 757d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) return scoped_ptr<T>(); 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(position < end()); 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<T*>::iterator writable_position = position; 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_ptr<T> ret(*writable_position); 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) *writable_position = NULL; 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return ret.Pass(); 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_ptr<T> take_back() { 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!empty()); 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (empty()) 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return scoped_ptr<T>(NULL); 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return take(end() - 1); 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void erase(iterator position) { 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (position == end()) 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<T*>::iterator writable_position = position; 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) delete *writable_position; 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) data_.erase(position); 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void erase(iterator first, iterator last) { 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(first <= last); 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (iterator it = first; it != last; ++it) { 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(it < end()); 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<T*>::iterator writable_it = it; 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) delete *writable_it; 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) data_.erase(first, last); 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void reserve(size_t size) { 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) data_.reserve(size); 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void clear() { 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) STLDeleteElements(&data_); 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void push_back(scoped_ptr<T> item) { 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) data_.push_back(item.release()); 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void pop_back() { 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) delete data_.back(); 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) data_.pop_back(); 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void insert(iterator position, scoped_ptr<T> item) { 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(position <= end()); 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) data_.insert(position, item.release()); 1302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci void insert_and_take(iterator position, ScopedPtrVector<T>* other) { 13390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) std::vector<T*> tmp_data; 1341320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (ScopedPtrVector<T>::iterator it = other->begin(); it != other->end(); 13590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) ++it) { 1361320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci tmp_data.push_back(other->take(it).release()); 13790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 13890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) data_.insert(position, tmp_data.begin(), tmp_data.end()); 13990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 14090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 1414e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) template <typename Predicate> 1424e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) iterator partition(Predicate predicate) { 1434e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) typename std::vector<T*>::iterator first = begin(); 1444e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) typename std::vector<T*>::iterator last = end(); 1454e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) return static_cast<iterator>(std::partition(first, last, predicate)); 1464e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) } 1474e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void swap(ScopedPtrVector<T>& other) { 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) data_.swap(other.data_); 1502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void swap(iterator a, iterator b) { 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(a < end()); 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(b < end()); 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (a == end() || b == end() || a == b) 1562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<T*>::iterator writable_a = a; 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<T*>::iterator writable_b = b; 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::swap(*writable_a, *writable_b); 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) template<class Compare> 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) inline void sort(Compare comp) { 164c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) std::sort(data_.begin(), data_.end(), comp); 1652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1675f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) template <class Compare> 1685f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) inline void make_heap(Compare comp) { 1695f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::make_heap(data_.begin(), data_.end(), comp); 1705f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 1715f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1725f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) template <class Compare> 1735f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) inline void push_heap(Compare comp) { 1745f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::push_heap(data_.begin(), data_.end(), comp); 1755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 1765f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1775f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) template <class Compare> 1785f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) inline void pop_heap(Compare comp) { 1795f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::pop_heap(data_.begin(), data_.end(), comp); 1805f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 1815f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterator begin() { return static_cast<iterator>(data_.begin()); } 1832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_iterator begin() const { return data_.begin(); } 1842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterator end() { return static_cast<iterator>(data_.end()); } 1852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_iterator end() const { return data_.end(); } 1862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) reverse_iterator rbegin() { return data_.rbegin(); } 1882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_reverse_iterator rbegin() const { return data_.rbegin(); } 1892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) reverse_iterator rend() { return data_.rend(); } 1902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_reverse_iterator rend() const { return data_.rend(); } 1912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 1932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<T*> data_; 1942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(ScopedPtrVector); 1962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 1972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // namespace cc 1992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // CC_BASE_SCOPED_PTR_VECTOR_H_ 201