Home | History | Annotate | Download | only in indexed_db 
      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   bool has(const T& elem) { return set_.find(elem) != set_.end(); }
     51 
     52   size_t size() const {
     53     DCHECK_EQ(list_.size(), set_.size());
     54     return set_.size();
     55   }
     56 
     57   bool empty() const {
     58     DCHECK_EQ(list_.empty(), set_.empty());
     59     return set_.empty();
     60   }
     61 
     62   class const_iterator;
     63 
     64   class iterator {
     65    public:
     66     typedef iterator self_type;
     67     typedef T value_type;
     68     typedef T& reference;
     69     typedef T* pointer;
     70     typedef std::bidirectional_iterator_tag iterator_category;
     71     typedef std::ptrdiff_t difference_type;
     72 
     73     explicit inline iterator(typename std::list<T>::iterator it) : it_(it) {}
     74     inline self_type& operator++() {
     75       ++it_;
     76       return *this;
     77     }
     78     inline self_type operator++(int /*ignored*/) {
     79       self_type result(*this);
     80       ++(*this);
     81       return result;
     82     }
     83     inline self_type& operator--() {
     84       --it_;
     85       return *this;
     86     }
     87     inline self_type operator--(int /*ignored*/) {
     88       self_type result(*this);
     89       --(*this);
     90       return result;
     91     }
     92     inline value_type& operator*() { return *it_; }
     93     inline value_type* operator->() { return &(*it_); }
     94     inline bool operator==(const iterator& rhs) const { return it_ == rhs.it_; }
     95     inline bool operator!=(const iterator& rhs) const { return it_ != rhs.it_; }
     96 
     97     inline operator const_iterator() const { return const_iterator(it_); }
     98 
     99    private:
    100     typename std::list<T>::iterator it_;
    101   };
    102 
    103   class const_iterator {
    104    public:
    105     typedef const_iterator self_type;
    106     typedef T value_type;
    107     typedef T& reference;
    108     typedef T* pointer;
    109     typedef std::bidirectional_iterator_tag iterator_category;
    110     typedef std::ptrdiff_t difference_type;
    111 
    112     explicit inline const_iterator(typename std::list<T>::const_iterator it)
    113         : it_(it) {}
    114     inline self_type& operator++() {
    115       ++it_;
    116       return *this;
    117     }
    118     inline self_type operator++(int ignored) {
    119       self_type result(*this);
    120       ++(*this);
    121       return result;
    122     }
    123     inline self_type& operator--() {
    124       --it_;
    125       return *this;
    126     }
    127     inline self_type operator--(int ignored) {
    128       self_type result(*this);
    129       --(*this);
    130       return result;
    131     }
    132     inline const value_type& operator*() { return *it_; }
    133     inline const value_type* operator->() { return &(*it_); }
    134     inline bool operator==(const const_iterator& rhs) const {
    135       return it_ == rhs.it_;
    136     }
    137     inline bool operator!=(const const_iterator& rhs) const {
    138       return it_ != rhs.it_;
    139     }
    140 
    141    private:
    142     typename std::list<T>::const_iterator it_;
    143   };
    144 
    145   iterator begin() { return iterator(list_.begin()); }
    146   iterator end() { return iterator(list_.end()); }
    147   const_iterator begin() const { return const_iterator(list_.begin()); }
    148   const_iterator end() const { return const_iterator(list_.end()); }
    149 
    150  private:
    151   std::list<T> list_;
    152   std::set<T> set_;
    153 };
    154 
    155 // Prevent instantiation of list_set<scoped_ptr<T>> as the current
    156 // implementation would fail.
    157 // TODO(jsbell): Support scoped_ptr through specialization.
    158 template <typename T>
    159 class list_set<scoped_ptr<T> >;
    160 
    161 #endif  // CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
    162