Remove //net (except for Android test stuff) and sdch

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/containers/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();
-  }
-
-  // Front and back accessors common to many stl containers.
-
-  // Returns the earliest-inserted element
-  const value_type& front() const {
-    return list_.front();
-  }
-
-  // Returns the earliest-inserted element.
-  value_type& front() {
-    return list_.front();
-  }
-
-  // Returns the most-recently-inserted element.
-  const value_type& back() const {
-    return list_.back();
-  }
-
-  // Returns the most-recently-inserted element.
-  value_type& back() {
-    return list_.back();
-  }
-
-  // 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 std::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 std::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(std::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 std::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(std::make_pair(pair.first, last)).second)
-        << "Map and list are inconsistent";
-
-    return std::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_