1 // Copyright (c) 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 CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_ 6 #define CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_ 7 8 #include <stddef.h> 9 10 #include <algorithm> 11 #include <iterator> 12 #include <list> 13 #include <memory> 14 #include <set> 15 16 #include "base/logging.h" 17 18 // 19 // A container class that provides fast containment test (like a set) 20 // but maintains insertion order for iteration (like list). 21 // 22 // Member types of value (primitives and objects by value), raw pointers 23 // and scoped_refptr<> are supported. 24 // 25 template <typename T> 26 class list_set { 27 public: list_set()28 list_set() {} list_set(const list_set<T> & other)29 list_set(const list_set<T>& other) : list_(other.list_), set_(other.set_) {} 30 list_set& operator=(const list_set<T>& other) { 31 list_ = other.list_; 32 set_ = other.set_; 33 return *this; 34 } 35 insert_front(const T & elem)36 void insert_front(const T& elem) { 37 if (set_.find(elem) != set_.end()) 38 return; 39 set_.insert(elem); 40 list_.push_front(elem); 41 } 42 insert(const T & elem)43 void insert(const T& elem) { 44 if (set_.find(elem) != set_.end()) 45 return; 46 set_.insert(elem); 47 list_.push_back(elem); 48 } 49 erase(const T & elem)50 void erase(const T& elem) { 51 if (set_.find(elem) == set_.end()) 52 return; 53 set_.erase(elem); 54 typename std::list<T>::iterator it = 55 std::find(list_.begin(), list_.end(), elem); 56 DCHECK(it != list_.end()); 57 list_.erase(it); 58 } 59 clear()60 void clear() { 61 set_.clear(); 62 list_.clear(); 63 } 64 count(const T & elem)65 size_t count(const T& elem) const { 66 return set_.find(elem) == set_.end() ? 0 : 1; 67 } 68 size()69 size_t size() const { 70 DCHECK_EQ(list_.size(), set_.size()); 71 return set_.size(); 72 } 73 empty()74 bool empty() const { 75 DCHECK_EQ(list_.empty(), set_.empty()); 76 return set_.empty(); 77 } 78 79 class const_iterator; 80 81 class iterator { 82 public: 83 typedef iterator self_type; 84 typedef T value_type; 85 typedef value_type& reference; 86 typedef value_type* pointer; 87 typedef std::bidirectional_iterator_tag iterator_category; 88 typedef std::ptrdiff_t difference_type; 89 iterator(typename std::list<T>::iterator it)90 explicit iterator(typename std::list<T>::iterator it) : it_(it) {} 91 self_type& operator++() { 92 ++it_; 93 return *this; 94 } 95 self_type operator++(int /*ignored*/) { 96 self_type result(*this); 97 ++(*this); 98 return result; 99 } 100 self_type& operator--() { 101 --it_; 102 return *this; 103 } 104 self_type operator--(int /*ignored*/) { 105 self_type result(*this); 106 --(*this); 107 return result; 108 } 109 reference operator*() const { return *it_; } 110 pointer operator->() const { return &(*it_); } 111 bool operator==(const iterator& rhs) const { return it_ == rhs.it_; } 112 bool operator!=(const iterator& rhs) const { return it_ != rhs.it_; } 113 const_iterator()114 inline operator const_iterator() const { return const_iterator(it_); } 115 116 private: 117 typename std::list<T>::iterator it_; 118 }; 119 120 class const_iterator { 121 public: 122 typedef const_iterator self_type; 123 typedef T value_type; 124 typedef const value_type& reference; 125 typedef const value_type* pointer; 126 typedef std::bidirectional_iterator_tag iterator_category; 127 typedef std::ptrdiff_t difference_type; 128 const_iterator(typename std::list<T>::const_iterator it)129 explicit inline const_iterator(typename std::list<T>::const_iterator it) 130 : it_(it) {} 131 self_type& operator++() { 132 ++it_; 133 return *this; 134 } 135 self_type operator++(int ignored) { 136 self_type result(*this); 137 ++(*this); 138 return result; 139 } 140 self_type& operator--() { 141 --it_; 142 return *this; 143 } 144 self_type operator--(int ignored) { 145 self_type result(*this); 146 --(*this); 147 return result; 148 } 149 reference operator*() const { return *it_; } 150 pointer operator->() const { return &(*it_); } 151 bool operator==(const const_iterator& rhs) const { return it_ == rhs.it_; } 152 bool operator!=(const const_iterator& rhs) const { return it_ != rhs.it_; } 153 154 private: 155 typename std::list<T>::const_iterator it_; 156 }; 157 begin()158 iterator begin() { return iterator(list_.begin()); } end()159 iterator end() { return iterator(list_.end()); } begin()160 const_iterator begin() const { return const_iterator(list_.begin()); } end()161 const_iterator end() const { return const_iterator(list_.end()); } 162 163 private: 164 std::list<T> list_; 165 std::set<T> set_; 166 }; 167 168 // Prevent instantiation of list_set<std::unique_ptr<T>> as the current 169 // implementation would fail. 170 // TODO(jsbell): Support scoped_ptr through specialization. 171 template <typename T> 172 class list_set<std::unique_ptr<T>>; 173 174 #endif // CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_ 175