diff options
Diffstat (limited to 'chromium/net/base/linked_hash_map.h')
-rw-r--r-- | chromium/net/base/linked_hash_map.h | 210 |
1 files changed, 210 insertions, 0 deletions
diff --git a/chromium/net/base/linked_hash_map.h b/chromium/net/base/linked_hash_map.h new file mode 100644 index 00000000000..d08b68d2592 --- /dev/null +++ b/chromium/net/base/linked_hash_map.h @@ -0,0 +1,210 @@ +// 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(); + } + + // 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_ |