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.
30template<class Key, class Value>
31class 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  // Front and back accessors common to many stl containers.
83
84  // Returns the earliest-inserted element
85  const value_type& front() const {
86    return list_.front();
87  }
88
89  // Returns the earliest-inserted element.
90  value_type& front() {
91    return list_.front();
92  }
93
94  // Returns the most-recently-inserted element.
95  const value_type& back() const {
96    return list_.back();
97  }
98
99  // Returns the most-recently-inserted element.
100  value_type& back() {
101    return list_.back();
102  }
103
104  // Clears the map of all values.
105  void clear() {
106    map_.clear();
107    list_.clear();
108  }
109
110  // Returns true iff the map is empty.
111  bool empty() const {
112    return list_.empty();
113  }
114
115  // Erases values with the provided key.  Returns the number of elements
116  // erased.  In this implementation, this will be 0 or 1.
117  size_type erase(const Key& key) {
118    typename MapType::iterator found = map_.find(key);
119    if (found == map_.end()) return 0;
120
121    list_.erase(found->second);
122    map_.erase(found);
123
124    return 1;
125  }
126
127  // Erases values with the provided iterator. If the provided iterator is
128  // invalid or there is inconsistency between the map and list, a CHECK() error
129  // will occur.
130  void erase(iterator position) {
131    typename MapType::iterator found = map_.find(position->first);
132    CHECK(found->second == position)
133        << "Inconsisent iterator for map and list, or the iterator is invalid.";
134
135    list_.erase(position);
136    map_.erase(found);
137  }
138
139  // Erases values between first and last, not including last.
140  void erase(iterator first, iterator last) {
141    while (first != last && first != end()) {
142      erase(first++);
143    }
144  }
145
146  // Finds the element with the given key.  Returns an iterator to the
147  // value found, or to end() if the value was not found.  Like a map, this
148  // iterator points to a pair<Key, Value>.
149  iterator find(const Key& key) {
150    typename MapType::iterator found = map_.find(key);
151    if (found == map_.end()) {
152      return end();
153    }
154    return found->second;
155  }
156
157  const_iterator find(const Key& key) const {
158    typename MapType::const_iterator found = map_.find(key);
159    if (found == map_.end()) {
160      return end();
161    }
162    return found->second;
163  }
164
165  // Returns the bounds of a range that includes all the elements in the
166  // container with a key that compares equal to x.
167  std::pair<iterator, iterator> equal_range(const key_type& key) {
168    std::pair<typename MapType::iterator, typename MapType::iterator> eq_range =
169        map_.equal_range(key);
170
171    return std::make_pair(eq_range.first->second, eq_range.second->second);
172  }
173
174  std::pair<const_iterator, const_iterator> equal_range(
175      const key_type& key) const {
176    std::pair<typename MapType::const_iterator,
177        typename MapType::const_iterator> eq_range =
178        map_.equal_range(key);
179    const const_iterator& start_iter = eq_range.first != map_.end() ?
180        eq_range.first->second : end();
181    const const_iterator& end_iter = eq_range.second != map_.end() ?
182        eq_range.second->second : end();
183
184    return std::make_pair(start_iter, end_iter);
185  }
186
187  // Returns the value mapped to key, or an inserted iterator to that position
188  // in the map.
189  Value& operator[](const key_type& key) {
190    return (*((this->insert(std::make_pair(key, Value()))).first)).second;
191  }
192
193  // Inserts an element into the map
194  std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) {
195    // First make sure the map doesn't have a key with this value.  If it does,
196    // return a pair with an iterator to it, and false indicating that we
197    // didn't insert anything.
198    typename MapType::iterator found = map_.find(pair.first);
199    if (found != map_.end()) return std::make_pair(found->second, false);
200
201    // Otherwise, insert into the list first.
202    list_.push_back(pair);
203
204    // Obtain an iterator to the newly added element.  We do -- instead of -
205    // since list::iterator doesn't implement operator-().
206    typename ListType::iterator last = list_.end();
207    --last;
208
209    CHECK(map_.insert(std::make_pair(pair.first, last)).second)
210        << "Map and list are inconsistent";
211
212    return std::make_pair(last, true);
213  }
214
215  size_type size() const {
216    return list_.size();
217  }
218
219  void swap(linked_hash_map& other) {
220    map_.swap(other.map_);
221    list_.swap(other.list_);
222  }
223
224 private:
225  // The map component, used for speedy lookups
226  MapType map_;
227
228  // The list component, used for maintaining insertion order
229  ListType list_;
230};
231
232#endif  // UTIL_GTL_LINKED_HASH_MAP_H_
233