list_set.h revision 8bcbed890bc3ce4d7a057a8f32cab53fa534672e
1868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Copyright (c) 2013 The Chromium Authors. All rights reserved. 2868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// found in the LICENSE file. 4868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 5868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#ifndef CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_ 6868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#define CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_ 7868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 8868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include <algorithm> 9868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include <iterator> 10868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include <list> 11868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include <set> 12868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/logging.h" 13868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/memory/scoped_ptr.h" 14868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 15868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 16868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// A container class that provides fast containment test (like a set) 17868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// but maintains insertion order for iteration (like list). 18868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 19868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Member types of value (primitives and objects by value), raw pointers 20868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// and scoped_refptr<> are supported. 21868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 22868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)template <typename T> 23868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)class list_set { 24868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) public: 25868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list_set() {} 26868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list_set(const list_set<T>& other) : list_(other.list_), set_(other.set_) {} 27868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list_set& operator=(const list_set<T>& other) { 28868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list_ = other.list_; 29868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) set_ = other.set_; 30868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return *this; 31868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 32868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 33868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) void insert(const T& elem) { 34868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (set_.find(elem) != set_.end()) 35868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 36868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) set_.insert(elem); 37868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list_.push_back(elem); 38868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 39868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 40868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) void erase(const T& elem) { 41868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (set_.find(elem) == set_.end()) 42868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 43868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) set_.erase(elem); 44868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typename std::list<T>::iterator it = 45868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) std::find(list_.begin(), list_.end(), elem); 46868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DCHECK(it != list_.end()); 47868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list_.erase(it); 48868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 49868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 508bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) size_t count(const T& elem) const { 518bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) return set_.find(elem) == set_.end() ? 0 : 1; 528bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) } 53868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 54868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) size_t size() const { 55868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DCHECK_EQ(list_.size(), set_.size()); 56868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return set_.size(); 57868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 58868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 59868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) bool empty() const { 60868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DCHECK_EQ(list_.empty(), set_.empty()); 61868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return set_.empty(); 62868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 63868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 64868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) class const_iterator; 65868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 66868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) class iterator { 67868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) public: 68868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef iterator self_type; 69868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef T value_type; 70868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef T& reference; 71868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef T* pointer; 72868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef std::bidirectional_iterator_tag iterator_category; 73868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef std::ptrdiff_t difference_type; 74868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 75868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) explicit inline iterator(typename std::list<T>::iterator it) : it_(it) {} 76868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline self_type& operator++() { 77868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) ++it_; 78868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return *this; 79868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 80868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline self_type operator++(int /*ignored*/) { 81868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) self_type result(*this); 82868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) ++(*this); 83868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return result; 84868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 85868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline self_type& operator--() { 86868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) --it_; 87868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return *this; 88868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 89868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline self_type operator--(int /*ignored*/) { 90868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) self_type result(*this); 91868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) --(*this); 92868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return result; 93868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 94868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline value_type& operator*() { return *it_; } 95868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline value_type* operator->() { return &(*it_); } 96868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline bool operator==(const iterator& rhs) const { return it_ == rhs.it_; } 97868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline bool operator!=(const iterator& rhs) const { return it_ != rhs.it_; } 98868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 99868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline operator const_iterator() const { return const_iterator(it_); } 100868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 101868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) private: 102868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typename std::list<T>::iterator it_; 103868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) }; 104868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 105868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) class const_iterator { 106868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) public: 107868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef const_iterator self_type; 108868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef T value_type; 109868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef T& reference; 110868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef T* pointer; 111868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef std::bidirectional_iterator_tag iterator_category; 112868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef std::ptrdiff_t difference_type; 113868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 114868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) explicit inline const_iterator(typename std::list<T>::const_iterator it) 115868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) : it_(it) {} 116868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline self_type& operator++() { 117868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) ++it_; 118868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return *this; 119868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 120868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline self_type operator++(int ignored) { 121868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) self_type result(*this); 122868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) ++(*this); 123868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return result; 124868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 125868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline self_type& operator--() { 126868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) --it_; 127868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return *this; 128868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 129868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline self_type operator--(int ignored) { 130868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) self_type result(*this); 131868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) --(*this); 132868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return result; 133868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 134868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline const value_type& operator*() { return *it_; } 135868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline const value_type* operator->() { return &(*it_); } 136868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline bool operator==(const const_iterator& rhs) const { 137868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return it_ == rhs.it_; 138868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 139868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) inline bool operator!=(const const_iterator& rhs) const { 140868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return it_ != rhs.it_; 141868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 142868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 143868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) private: 144868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typename std::list<T>::const_iterator it_; 145868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) }; 146868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 147868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) iterator begin() { return iterator(list_.begin()); } 148868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) iterator end() { return iterator(list_.end()); } 149868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) const_iterator begin() const { return const_iterator(list_.begin()); } 150868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) const_iterator end() const { return const_iterator(list_.end()); } 151868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 152868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) private: 153868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) std::list<T> list_; 154868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) std::set<T> set_; 155868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)}; 156868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 157868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Prevent instantiation of list_set<scoped_ptr<T>> as the current 158868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// implementation would fail. 159868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// TODO(jsbell): Support scoped_ptr through specialization. 160868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)template <typename T> 161868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)class list_set<scoped_ptr<T> >; 162868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 163868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#endif // CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_ 164