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   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_
    164