blob: a52863e40f5c93668cb7e03e38ac3916ab639ba6 [file] [log] [blame]
// Copyright (c) 2019 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 point into the list and should be stable in the face of
// mutations, except for an iterator pointing to an element that was just
// deleted.
#include <functional>
#include <list>
#include <tuple>
#include <type_traits>
#include <utility>
#include "absl/container/node_hash_map.h"
#include "common/platform/api/quiche_logging.h"
namespace quiche {
// 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 set<list::iterator> for find. Since std::list is a
// doubly-linked list, the iterators should remain stable.
template <class Key,
class Value,
class Hash = std::hash<Key>,
class Eq = std::equal_to<Key>>
class QuicheLinkedHashMap {
typedef std::list<std::pair<Key, Value>> ListType;
typedef absl::node_hash_map<Key, typename ListType::iterator, Hash, Eq>
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;
QuicheLinkedHashMap() = default;
explicit QuicheLinkedHashMap(size_type bucket_count) : map_(bucket_count) {}
QuicheLinkedHashMap(const QuicheLinkedHashMap& other) = delete;
QuicheLinkedHashMap& operator=(const QuicheLinkedHashMap& other) = delete;
QuicheLinkedHashMap(QuicheLinkedHashMap&& other) = default;
QuicheLinkedHashMap& operator=(QuicheLinkedHashMap&& other) = default;
// 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() {
// Returns true iff the map is empty.
bool empty() const { return list_.empty(); }
// Removes the first element from the list.
void pop_front() { erase(begin()); }
// 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;
return 1;
// Erases the item that 'position' points to. Returns an iterator that points
// to the item that comes immediately after the deleted item in the list, or
// end().
// If the provided iterator is invalid or there is inconsistency between the
// map and list, a QUICHE_CHECK() error will occur.
iterator erase(iterator position) {
typename MapType::iterator found = map_.find(position->first);
QUICHE_CHECK(found->second == position)
<< "Inconsistent iterator for map and list, or the iterator is "
return list_.erase(position);
// Erases all the items in the range [first, last). Returns an iterator that
// points to the item that comes immediately after the last deleted item in
// the list, or end().
iterator erase(iterator first, iterator last) {
while (first != last && first != end()) {
first = erase(first);
return 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;
bool contains(const Key& key) const { return find(key) != end(); }
// 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) {
return InsertInternal(pair);
// Inserts an element into the map
std::pair<iterator, bool> insert(std::pair<Key, Value>&& pair) {
return InsertInternal(std::move(pair));
// Derive size_ from map_, as list::size might be O(N).
size_type size() const { return map_.size(); }
template <typename... Args>
std::pair<iterator, bool> emplace(Args&&... args) {
ListType node_donor;
auto node_pos =
node_donor.emplace(node_donor.end(), std::forward<Args>(args)...);
const auto& k = node_pos->first;
auto ins = map_.insert({k, node_pos});
if (!ins.second) {
return {ins.first->second, false};
list_.splice(list_.end(), node_donor, node_pos);
return {ins.first->second, true};
void swap(QuicheLinkedHashMap& other) {
template <typename U>
std::pair<iterator, bool> InsertInternal(U&& pair) {
auto insert_result = map_.try_emplace(pair.first);
auto map_iter = insert_result.first;
// If the map already contains this key, return a pair with an iterator to
// it, and false indicating that we didn't insert anything.
if (!insert_result.second) {
return {map_iter->second, false};
// Otherwise, insert into the list, and set value in map.
auto list_iter = list_.insert(list_.end(), std::forward<U>(pair));
map_iter->second = list_iter;
return {list_iter, true};
// The map component, used for speedy lookups
MapType map_;
// The list component, used for maintaining insertion order
ListType list_;
} // namespace quiche