1
    2
    3
    4
    5
    6
    7
    8
    9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55
   56
   57
   58
   59
   60
   61
   62
   63
   64
   65
   66
   67
   68
   69
   70
   71
   72
   73
   74
   75
   76
   77
   78
   79
   80
   81
   82
   83
   84
   85
   86
   87
   88
   89
   90
   91
   92
   93
   94
   95
   96
   97
   98
   99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  155
  156
  157
  158
  159
  160
  161
  162
  163
  164
  165
  166
  167
  168
  169
  170
  171
  172
  173
  174


content / browser / indexed_db / list_set.h [blame]

// Copyright 2013 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
#define CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_

#include <stddef.h>

#include <iterator>
#include <list>
#include <memory>
#include <set>

#include "base/check_op.h"
#include "base/not_fatal_until.h"
#include "base/ranges/algorithm.h"

//
// A container class that provides fast containment test (like a set)
// but maintains insertion order for iteration (like list).
//
// Member types of value (primitives and objects by value), raw pointers
// and scoped_refptr<> are supported.
//
template <typename T>
class list_set {
 public:
  list_set() {}
  list_set(const list_set<T>& other) : list_(other.list_), set_(other.set_) {}
  list_set& operator=(const list_set<T>& other) {
    list_ = other.list_;
    set_ = other.set_;
    return *this;
  }

  void insert_front(const T& elem) {
    if (set_.find(elem) != set_.end())
      return;
    set_.insert(elem);
    list_.push_front(elem);
  }

  void insert(const T& elem) {
    if (set_.find(elem) != set_.end())
      return;
    set_.insert(elem);
    list_.push_back(elem);
  }

  void erase(const T& elem) {
    if (set_.find(elem) == set_.end())
      return;
    set_.erase(elem);
    typename std::list<T>::iterator it = base::ranges::find(list_, elem);
    CHECK(it != list_.end(), base::NotFatalUntil::M130);
    list_.erase(it);
  }

  void clear() {
    set_.clear();
    list_.clear();
  }

  size_t count(const T& elem) const {
    return set_.find(elem) == set_.end() ? 0 : 1;
  }

  size_t size() const {
    DCHECK_EQ(list_.size(), set_.size());
    return set_.size();
  }

  bool empty() const {
    DCHECK_EQ(list_.empty(), set_.empty());
    return set_.empty();
  }

  class const_iterator;

  class iterator {
   public:
    typedef iterator self_type;
    typedef T value_type;
    typedef value_type& reference;
    typedef value_type* pointer;
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef std::ptrdiff_t difference_type;

    explicit iterator(typename std::list<T>::iterator it) : it_(it) {}
    self_type& operator++() {
      ++it_;
      return *this;
    }
    self_type operator++(int /*ignored*/) {
      self_type result(*this);
      ++(*this);
      return result;
    }
    self_type& operator--() {
      --it_;
      return *this;
    }
    self_type operator--(int /*ignored*/) {
      self_type result(*this);
      --(*this);
      return result;
    }
    reference operator*() const { return *it_; }
    pointer operator->() const { return &(*it_); }
    bool operator==(const iterator& rhs) const { return it_ == rhs.it_; }
    bool operator!=(const iterator& rhs) const { return it_ != rhs.it_; }

    inline operator const_iterator() const { return const_iterator(it_); }

   private:
    typename std::list<T>::iterator it_;
  };

  class const_iterator {
   public:
    typedef const_iterator self_type;
    typedef T value_type;
    typedef const value_type& reference;
    typedef const value_type* pointer;
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef std::ptrdiff_t difference_type;

    explicit inline const_iterator(typename std::list<T>::const_iterator it)
        : it_(it) {}
    self_type& operator++() {
      ++it_;
      return *this;
    }
    self_type operator++(int ignored) {
      self_type result(*this);
      ++(*this);
      return result;
    }
    self_type& operator--() {
      --it_;
      return *this;
    }
    self_type operator--(int ignored) {
      self_type result(*this);
      --(*this);
      return result;
    }
    reference operator*() const { return *it_; }
    pointer operator->() const { return &(*it_); }
    bool operator==(const const_iterator& rhs) const { return it_ == rhs.it_; }
    bool operator!=(const const_iterator& rhs) const { return it_ != rhs.it_; }

   private:
    typename std::list<T>::const_iterator it_;
  };

  iterator begin() { return iterator(list_.begin()); }
  iterator end() { return iterator(list_.end()); }
  const_iterator begin() const { return const_iterator(list_.begin()); }
  const_iterator end() const { return const_iterator(list_.end()); }

 private:
  std::list<T> list_;
  std::set<T> set_;
};

// Prevent instantiation of list_set<std::unique_ptr<T>> as the current
// implementation would fail.
// TODO(jsbell): Support scoped_ptr through specialization.
template <typename T>
class list_set<std::unique_ptr<T>>;

#endif  // CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_