content/browser/indexed_db/list_set.h

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