← Back to branch summary

~alinuxninja/nginx-edge/trunk

« back to all changes in this revision

Viewing changes to debian/modules/ngx_pagespeed/psol/include/third_party/chromium/src/net/base/linked_hash_map.h

  • Committer: Vivian
  • Date: 2015-12-04 18:20:11 UTC
  • Revision ID: git-v1:a36f2bc32e884f7473b3a47040e5411306144d7d
* Do not extract psol.tar.gz

Show diffs side-by-side

added added

removed removed

Lines of Context:
debian/modules/ngx_pagespeed/psol/include/third_party/chromium/src/net/base/linked_hash_map.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
 
// This is a simplistic insertion-ordered map.  It behaves similarly to an STL
6
 
// map, but only implements a small subset of the map's methods.  Internally, we
7
 
// just keep a map and a list going in parallel.
8
 
//
9
 
// This class provides no thread safety guarantees, beyond what you would
10
 
// normally see with std::list.
11
 
//
12
 
// Iterators should be stable in the face of mutations, except for an
13
 
// iterator pointing to an element that was just deleted.
14
 
 
15
 
#ifndef UTIL_GTL_LINKED_HASH_MAP_H_
16
 
#define UTIL_GTL_LINKED_HASH_MAP_H_
17
 
 
18
 
#include <list>
19
 
#include <utility>
20
 
 
21
 
#include "base/containers/hash_tables.h"
22
 
#include "base/logging.h"
23
 
 
24
 
// This holds a list of pair<Key, Value> items.  This list is what gets
25
 
// traversed, and it's iterators from this list that we return from
26
 
// begin/end/find.
27
 
//
28
 
// We also keep a map<Key, list::iterator> for find.  Since std::list is a
29
 
// doubly-linked list, the iterators should remain stable.
30
 
template<class Key, class Value>
31
 
class linked_hash_map {
32
 
 private:
33
 
  typedef std::list<std::pair<Key, Value> > ListType;
34
 
  typedef base::hash_map<Key, typename ListType::iterator> MapType;
35
 
 
36
 
 public:
37
 
  typedef typename ListType::iterator iterator;
38
 
  typedef typename ListType::reverse_iterator reverse_iterator;
39
 
  typedef typename ListType::const_iterator const_iterator;
40
 
  typedef typename ListType::const_reverse_iterator const_reverse_iterator;
41
 
  typedef typename MapType::key_type key_type;
42
 
  typedef typename ListType::value_type value_type;
43
 
  typedef typename ListType::size_type size_type;
44
 
 
45
 
  linked_hash_map() : map_(), list_() {
46
 
  }
47
 
 
48
 
  // Returns an iterator to the first (insertion-ordered) element.  Like a map,
49
 
  // this can be dereferenced to a pair<Key, Value>.
50
 
  iterator begin() {
51
 
    return list_.begin();
52
 
  }
53
 
  const_iterator begin() const {
54
 
    return list_.begin();
55
 
  }
56
 
 
57
 
  // Returns an iterator beyond the last element.
58
 
  iterator end() {
59
 
    return list_.end();
60
 
  }
61
 
  const_iterator end() const {
62
 
    return list_.end();
63
 
  }
64
 
 
65
 
  // Returns an iterator to the last (insertion-ordered) element.  Like a map,
66
 
  // this can be dereferenced to a pair<Key, Value>.
67
 
  reverse_iterator rbegin() {
68
 
    return list_.rbegin();
69
 
  }
70
 
  const_reverse_iterator rbegin() const {
71
 
    return list_.rbegin();
72
 
  }
73
 
 
74
 
  // Returns an iterator beyond the first element.
75
 
  reverse_iterator rend() {
76
 
    return list_.rend();
77
 
  }
78
 
  const_reverse_iterator rend() const {
79
 
    return list_.rend();
80
 
  }
81
 
 
82
 
  // Clears the map of all values.
83
 
  void clear() {
84
 
    map_.clear();
85
 
    list_.clear();
86
 
  }
87
 
 
88
 
  // Returns true iff the map is empty.
89
 
  bool empty() const {
90
 
    return list_.empty();
91
 
  }
92
 
 
93
 
  // Erases values with the provided key.  Returns the number of elements
94
 
  // erased.  In this implementation, this will be 0 or 1.
95
 
  size_type erase(const Key& key) {
96
 
    typename MapType::iterator found = map_.find(key);
97
 
    if (found == map_.end()) return 0;
98
 
 
99
 
    list_.erase(found->second);
100
 
    map_.erase(found);
101
 
 
102
 
    return 1;
103
 
  }
104
 
 
105
 
  // Erases values with the provided iterator. If the provided iterator is
106
 
  // invalid or there is inconsistency between the map and list, a CHECK() error
107
 
  // will occur.
108
 
  void erase(iterator position) {
109
 
    typename MapType::iterator found = map_.find(position->first);
110
 
    CHECK(found->second == position)
111
 
        << "Inconsisent iterator for map and list, or the iterator is invalid.";
112
 
 
113
 
    list_.erase(position);
114
 
    map_.erase(found);
115
 
  }
116
 
 
117
 
  // Erases values between first and last, not including last.
118
 
  void erase(iterator first, iterator last) {
119
 
    while (first != last && first != end()) {
120
 
      erase(first++);
121
 
    }
122
 
  }
123
 
 
124
 
  // Finds the element with the given key.  Returns an iterator to the
125
 
  // value found, or to end() if the value was not found.  Like a map, this
126
 
  // iterator points to a pair<Key, Value>.
127
 
  iterator find(const Key& key) {
128
 
    typename MapType::iterator found = map_.find(key);
129
 
    if (found == map_.end()) {
130
 
      return end();
131
 
    }
132
 
    return found->second;
133
 
  }
134
 
 
135
 
  const_iterator find(const Key& key) const {
136
 
    typename MapType::const_iterator found = map_.find(key);
137
 
    if (found == map_.end()) {
138
 
      return end();
139
 
    }
140
 
    return found->second;
141
 
  }
142
 
 
143
 
  // Returns the bounds of a range that includes all the elements in the
144
 
  // container with a key that compares equal to x.
145
 
  std::pair<iterator, iterator> equal_range(const key_type& key) {
146
 
    std::pair<typename MapType::iterator, typename MapType::iterator> eq_range =
147
 
        map_.equal_range(key);
148
 
 
149
 
    return std::make_pair(eq_range.first->second, eq_range.second->second);
150
 
  }
151
 
 
152
 
  std::pair<const_iterator, const_iterator> equal_range(
153
 
      const key_type& key) const {
154
 
    std::pair<typename MapType::const_iterator,
155
 
        typename MapType::const_iterator> eq_range =
156
 
        map_.equal_range(key);
157
 
    const const_iterator& start_iter = eq_range.first != map_.end() ?
158
 
        eq_range.first->second : end();
159
 
    const const_iterator& end_iter = eq_range.second != map_.end() ?
160
 
        eq_range.second->second : end();
161
 
 
162
 
    return std::make_pair(start_iter, end_iter);
163
 
  }
164
 
 
165
 
  // Returns the value mapped to key, or an inserted iterator to that position
166
 
  // in the map.
167
 
  Value& operator[](const key_type& key) {
168
 
    return (*((this->insert(std::make_pair(key, Value()))).first)).second;
169
 
  }
170
 
 
171
 
  // Inserts an element into the map
172
 
  std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) {
173
 
    // First make sure the map doesn't have a key with this value.  If it does,
174
 
    // return a pair with an iterator to it, and false indicating that we
175
 
    // didn't insert anything.
176
 
    typename MapType::iterator found = map_.find(pair.first);
177
 
    if (found != map_.end()) return std::make_pair(found->second, false);
178
 
 
179
 
    // Otherwise, insert into the list first.
180
 
    list_.push_back(pair);
181
 
 
182
 
    // Obtain an iterator to the newly added element.  We do -- instead of -
183
 
    // since list::iterator doesn't implement operator-().
184
 
    typename ListType::iterator last = list_.end();
185
 
    --last;
186
 
 
187
 
    CHECK(map_.insert(std::make_pair(pair.first, last)).second)
188
 
        << "Map and list are inconsistent";
189
 
 
190
 
    return std::make_pair(last, true);
191
 
  }
192
 
 
193
 
  size_type size() const {
194
 
    return list_.size();
195
 
  }
196
 
 
197
 
  void swap(linked_hash_map& other) {
198
 
    map_.swap(other.map_);
199
 
    list_.swap(other.list_);
200
 
  }
201
 
 
202
 
 private:
203
 
  // The map component, used for speedy lookups
204
 
  MapType map_;
205
 
 
206
 
  // The list component, used for maintaining insertion order
207
 
  ListType list_;
208
 
};
209
 
 
210
 
#endif  // UTIL_GTL_LINKED_HASH_MAP_H_