chromium/net/third_party/quiche/src/quiche/common/quiche_linked_hash_map.h

// 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.

#ifndef QUICHE_COMMON_QUICHE_LINKED_HASH_MAP_H_
#define QUICHE_COMMON_QUICHE_LINKED_HASH_MAP_H_

#include <functional>
#include <list>
#include <tuple>
#include <type_traits>
#include <utility>

#include "absl/container/flat_hash_map.h"
#include "absl/hash/hash.h"
#include "quiche/common/platform/api/quiche_export.h"
#include "quiche/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.

// QUICHE_NO_EXPORT comments suppress erroneous presubmit failures.
template <class Key,                      // QUICHE_NO_EXPORT
          class Value,                    // QUICHE_NO_EXPORT
          class Hash = absl::Hash<Key>,   // QUICHE_NO_EXPORT
          class Eq = std::equal_to<Key>>  // QUICHE_NO_EXPORT
class QuicheLinkedHashMap {               // QUICHE_NO_EXPORT
 private:
  typedef std::list<std::pair<Key, Value>> ListType;
  typedef absl::flat_hash_map<Key, typename ListType::iterator, Hash, Eq>
      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;

  QuicheLinkedHashMap() = default;
  explicit QuicheLinkedHashMap(size_type 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() { … }
  const_iterator begin() const { … }

  // Returns an iterator beyond the last element.
  iterator end() { … }
  const_iterator end() const { … }

  // Returns an iterator to the last (insertion-ordered) element.  Like a map,
  // this can be dereferenced to a pair<Key, Value>.
  reverse_iterator rbegin() { … }
  const_reverse_iterator rbegin() const { … }

  // Returns an iterator beyond the first element.
  reverse_iterator rend() { … }
  const_reverse_iterator rend() const { … }

  // Front and back accessors common to many stl containers.

  // Returns the earliest-inserted element
  const value_type& front() const { … }

  // Returns the earliest-inserted element.
  value_type& front() { … }

  // Returns the most-recently-inserted element.
  const value_type& back() const { … }

  // Returns the most-recently-inserted element.
  value_type& back() { … }

  // Clears the map of all values.
  void clear() { … }

  // Returns true iff the map is empty.
  bool empty() const { … }

  // Removes the first element from the list.
  void pop_front() { … }

  // 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) { … }

  // 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) { … }

  // 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) { … }

  // 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) { … }

  const_iterator find(const Key& key) const { … }

  bool contains(const Key& key) const { … }

  // Returns the value mapped to key, or an inserted iterator to that position
  // in the map.
  Value& operator[](const key_type& key) { … }

  // Inserts an element into the map
  std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) { … }

  // Inserts an element into the map
  std::pair<iterator, bool> insert(std::pair<Key, Value>&& pair) { … }

  // Derive size_ from map_, as list::size might be O(N).
  size_type size() const { … }

  template <typename... Args>
  std::pair<iterator, bool> emplace(Args&&... args) { … }

  void swap(QuicheLinkedHashMap& other) { … }

 private:
  template <typename U>
  std::pair<iterator, bool> InsertInternal(U&& pair) { … }

  // The map component, used for speedy lookups
  MapType map_;

  // The list component, used for maintaining insertion order
  ListType list_;
};

}  // namespace quiche

#endif  // QUICHE_COMMON_QUICHE_LINKED_HASH_MAP_H_