Land recent QUIC changes.

net/base/linked_hash_map.h

+// Copyright (c) 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// This is a simplistic insertion-ordered map.  It behaves similarly to an STL
+// map, but only implements a small subset of the map's methods.  Internally, we
+// just keep a map and a list going in parallel.
+//
+// This class provides no thread safety guarantees, beyond what you would
+// normally see with std::list.
+//
+// Iterators should be stable in the face of mutations, except for an
+// iterator pointing to an element that was just deleted.
+
+#ifndef UTIL_GTL_LINKED_HASH_MAP_H_
+#define UTIL_GTL_LINKED_HASH_MAP_H_
+
+#include <list>
+#include <utility>
+
+#include "base/hash_tables.h"
+#include "base/logging.h"
+
+// This holds a list of pair<Key, Value> items.  This list is what gets
+// traversed, and it's iterators from this list that we return from
+// begin/end/find.
+//
+// We also keep a map<Key, list::iterator> for find.  Since std::list is a
+// doubly-linked list, the iterators should remain stable.
+template<class Key, class Value>
+class linked_hash_map {
+ private:
+  typedef std::list<std::pair<Key, Value> > ListType;
+  typedef base::hash_map<Key, typename ListType::iterator> MapType;
+
+ public:
+  typedef typename ListType::iterator iterator;
+  typedef typename ListType::reverse_iterator reverse_iterator;
+  typedef typename ListType::const_iterator const_iterator;
+  typedef typename ListType::const_reverse_iterator const_reverse_iterator;
+  typedef typename MapType::key_type key_type;
+  typedef typename ListType::value_type value_type;
+  typedef typename ListType::size_type size_type;
+
+  linked_hash_map() : map_(), list_() {
+  }
+
+  // Returns an iterator to the first (insertion-ordered) element.  Like a map,
+  // this can be dereferenced to a pair<Key, Value>.
+  iterator begin() {
+    return list_.begin();
+  }
+  const_iterator begin() const {
+    return list_.begin();
+  }
+
+  // Returns an iterator beyond the last element.
+  iterator end() {
+    return list_.end();
+  }
+  const_iterator end() const {
+    return list_.end();
+  }
+
+  // Returns an iterator to the last (insertion-ordered) element.  Like a map,
+  // this can be dereferenced to a pair<Key, Value>.
+  reverse_iterator rbegin() {
+    return list_.rbegin();
+  }
+  const_reverse_iterator rbegin() const {
+    return list_.rbegin();
+  }
+
+  // Returns an iterator beyond the first element.
+  reverse_iterator rend() {
+    return list_.rend();
+  }
+  const_reverse_iterator rend() const {
+    return list_.rend();
+  }
+
+  // Clears the map of all values.
+  void clear() {
+    map_.clear();
+    list_.clear();
+  }
+
+  // Returns true iff the map is empty.
+  bool empty() const {
+    return list_.empty();
+  }
+
+  // Erases values with the provided key.  Returns the number of elements
+  // erased.  In this implementation, this will be 0 or 1.
+  size_type erase(const Key& key) {
+    typename MapType::iterator found = map_.find(key);
+    if (found == map_.end()) return 0;
+
+    list_.erase(found->second);
+    map_.erase(found);
+
+    return 1;
+  }
+
+  // Erases values with the provided iterator. If the provided iterator is
+  // invalid or there is inconsistency between the map and list, a CHECK() error
+  // will occur.
+  void erase(iterator position) {
+    typename MapType::iterator found = map_.find(position->first);
+    CHECK(found->second == position)
+        << "Inconsisent iterator for map and list, or the iterator is invalid.";
+
+    list_.erase(position);
+    map_.erase(found);
+  }
+
+  // Erases values between first and last, not including last.
+  void erase(iterator first, iterator last) {
+    while (first != last && first != end()) {
+      erase(first++);
+    }
+  }
+
+  // Finds the element with the given key.  Returns an iterator to the
+  // value found, or to end() if the value was not found.  Like a map, this
+  // iterator points to a pair<Key, Value>.
+  iterator find(const Key& key) {
+    typename MapType::iterator found = map_.find(key);
+    if (found == map_.end()) {
+      return end();
+    }
+    return found->second;
+  }
+
+  const_iterator find(const Key& key) const {
+    typename MapType::const_iterator found = map_.find(key);
+    if (found == map_.end()) {
+      return end();
+    }
+    return found->second;
+  }
+
+  // Returns the bounds of a range that includes all the elements in the
+  // container with a key that compares equal to x.
+  std::pair<iterator, iterator> equal_range(const key_type& key) {
+    std::pair<typename MapType::iterator, typename MapType::iterator> eq_range =
+        map_.equal_range(key);
+
+    return make_pair(eq_range.first->second, eq_range.second->second);
+  }
+
+  std::pair<const_iterator, const_iterator> equal_range(
+      const key_type& key) const {
+    std::pair<typename MapType::const_iterator,
+        typename MapType::const_iterator> eq_range =
+        map_.equal_range(key);
+    const const_iterator& start_iter = eq_range.first != map_.end() ?
+        eq_range.first->second : end();
+    const const_iterator& end_iter = eq_range.second != map_.end() ?
+        eq_range.second->second : end();
+
+    return make_pair(start_iter, end_iter);
+  }
+
+  // Returns the value mapped to key, or an inserted iterator to that position
+  // in the map.
+  Value& operator[](const key_type& key) {
+    return (*((this->insert(make_pair(key, Value()))).first)).second;
+  }
+
+  // Inserts an element into the map
+  std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) {
+    // First make sure the map doesn't have a key with this value.  If it does,
+    // return a pair with an iterator to it, and false indicating that we
+    // didn't insert anything.
+    typename MapType::iterator found = map_.find(pair.first);
+    if (found != map_.end()) return make_pair(found->second, false);
+
+    // Otherwise, insert into the list first.
+    list_.push_back(pair);
+
+    // Obtain an iterator to the newly added element.  We do -- instead of -
+    // since list::iterator doesn't implement operator-().
+    typename ListType::iterator last = list_.end();
+    --last;
+
+    CHECK(map_.insert(make_pair(pair.first, last)).second)
+        << "Map and list are inconsistent";
+
+    return make_pair(last, true);
+  }
+
+  size_type size() const {
+    return list_.size();
+  }
+
+  void swap(linked_hash_map& other) {
+    map_.swap(other.map_);
+    list_.swap(other.list_);
+  }
+
+ private:
+  // The map component, used for speedy lookups
+  MapType map_;
+
+  // The list component, used for maintaining insertion order
+  ListType list_;
+};
+
+#endif  // UTIL_GTL_LINKED_HASH_MAP_H_