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