diff --git a/spdy/core/http2_priority_write_scheduler.h b/spdy/core/http2_priority_write_scheduler.h
new file mode 100644
index 0000000..1f72fdb
--- /dev/null
+++ b/spdy/core/http2_priority_write_scheduler.h
@@ -0,0 +1,774 @@
+// 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.
+
+#ifndef QUICHE_SPDY_CORE_HTTP2_PRIORITY_WRITE_SCHEDULER_H_
+#define QUICHE_SPDY_CORE_HTTP2_PRIORITY_WRITE_SCHEDULER_H_
+
+#include <cstdint>
+#include <deque>
+#include <map>
+#include <memory>
+#include <queue>
+#include <set>
+#include <tuple>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+#include "net/third_party/quiche/src/spdy/core/spdy_intrusive_list.h"
+#include "net/third_party/quiche/src/spdy/core/spdy_protocol.h"
+#include "net/third_party/quiche/src/spdy/core/write_scheduler.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_bug_tracker.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_containers.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_logging.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_map_util.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_ptr_util.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_utils.h"
+
+namespace spdy {
+
+namespace test {
+template <typename StreamIdType>
+class Http2PriorityWriteSchedulerPeer;
+}
+
+// This data structure implements the HTTP/2 stream priority tree defined in
+// section 5.3 of RFC 7540:
+// http://tools.ietf.org/html/rfc7540#section-5.3
+//
+// Streams can be added and removed, and dependencies between them defined.
+// Streams constitute a tree rooted at stream ID 0: each stream has a single
+// parent stream, and 0 or more child streams.  Individual streams can be
+// marked as ready to read/write, and then the whole structure can be queried
+// to pick the next stream to read/write out of those that are ready.
+template <typename StreamIdType>
+class Http2PriorityWriteScheduler : public WriteScheduler<StreamIdType> {
+ public:
+  using typename WriteScheduler<StreamIdType>::StreamPrecedenceType;
+
+  Http2PriorityWriteScheduler();
+  Http2PriorityWriteScheduler(const Http2PriorityWriteScheduler&) = delete;
+  Http2PriorityWriteScheduler& operator=(const Http2PriorityWriteScheduler&) =
+      delete;
+
+  // WriteScheduler methods
+  void RegisterStream(StreamIdType stream_id,
+                      const StreamPrecedenceType& precedence) override;
+  void UnregisterStream(StreamIdType stream_id) override;
+  bool StreamRegistered(StreamIdType stream_id) const override;
+  StreamPrecedenceType GetStreamPrecedence(
+      StreamIdType stream_id) const override;
+  void UpdateStreamPrecedence(StreamIdType stream_id,
+                              const StreamPrecedenceType& precedence) override;
+  std::vector<StreamIdType> GetStreamChildren(
+      StreamIdType stream_id) const override;
+  void RecordStreamEventTime(StreamIdType stream_id,
+                             int64_t now_in_usec) override;
+  int64_t GetLatestEventWithPrecedence(StreamIdType stream_id) const override;
+  bool ShouldYield(StreamIdType stream_id) const override;
+  void MarkStreamReady(StreamIdType stream_id, bool add_to_front) override;
+  void MarkStreamNotReady(StreamIdType stream_id) override;
+  bool HasReadyStreams() const override;
+  StreamIdType PopNextReadyStream() override;
+  std::tuple<StreamIdType, StreamPrecedenceType>
+  PopNextReadyStreamAndPrecedence() override;
+  size_t NumReadyStreams() const override;
+  bool IsStreamReady(StreamIdType stream_id) const override;
+  SpdyString DebugString() const override;
+
+  // Return the number of streams currently in the tree.
+  int num_streams() const;
+
+ private:
+  friend class test::Http2PriorityWriteSchedulerPeer<StreamIdType>;
+
+  struct StreamInfo;
+  typedef SpdyInlinedVector<StreamInfo*, 4> StreamInfoVector;
+
+  struct StreamInfo : public SpdyIntrusiveLink<StreamInfo> {
+    // ID for this stream.
+    StreamIdType id;
+    // StreamInfo for parent stream.
+    StreamInfo* parent = nullptr;
+    // Weights can range between 1 and 256 (inclusive).
+    int weight = kHttp2DefaultStreamWeight;
+    // The total weight of this stream's direct descendants.
+    int total_child_weights = 0;
+    // Pointers to StreamInfos for children, if any.
+    StreamInfoVector children;
+    // Whether the stream is ready for writing. The stream is present in
+    // scheduling_queue_ iff true.
+    bool ready = false;
+    // The scheduling priority of this stream. Streams with higher priority
+    // values are scheduled first.
+    // TODO(mpw): rename to avoid confusion with SPDY priorities,
+    //   which this is not.
+    float priority = 0;
+    // Ordinal value for this stream, used to ensure round-robin scheduling:
+    // among streams with the same scheduling priority, streams with lower
+    // ordinal are scheduled first.
+    int64_t ordinal = 0;
+    // Time of latest write event for stream of this priority, in microseconds.
+    int64_t last_event_time_usec = 0;
+
+    // Whether this stream should be scheduled ahead of another stream.
+    bool SchedulesBefore(const StreamInfo& other) const {
+      return (priority != other.priority) ? priority > other.priority
+                                          : ordinal < other.ordinal;
+    }
+
+    // Returns the StreamPrecedenceType for this StreamInfo.
+    StreamPrecedenceType ToStreamPrecedence() const {
+      StreamIdType parent_id =
+          parent == nullptr ? kHttp2RootStreamId : parent->id;
+      bool exclusive = parent != nullptr && parent->children.size() == 1;
+      return StreamPrecedenceType(parent_id, weight, exclusive);
+    }
+  };
+
+  static bool Remove(StreamInfoVector* stream_infos,
+                     const StreamInfo* stream_info);
+
+  // Returns true iff any direct or transitive parent of the given stream is
+  // currently ready.
+  static bool HasReadyAncestor(const StreamInfo& stream_info);
+
+  // Returns StreamInfo for the given stream, or nullptr if it isn't
+  // registered.
+  const StreamInfo* FindStream(StreamIdType stream_id) const;
+  StreamInfo* FindStream(StreamIdType stream_id);
+
+  // Helpers for UpdateStreamPrecedence().
+  void UpdateStreamParent(StreamInfo* stream_info,
+                          StreamIdType parent_id,
+                          bool exclusive);
+  void UpdateStreamWeight(StreamInfo* stream_info, int weight);
+
+  // Update all priority values in the subtree rooted at the given stream, not
+  // including the stream itself. If this results in priority value changes for
+  // scheduled streams, those streams are rescheduled to ensure proper ordering
+  // of scheduling_queue_.
+  // TODO(mpw): rename to avoid confusion with SPDY priorities.
+  void UpdatePrioritiesUnder(StreamInfo* stream_info);
+
+  // Inserts stream into scheduling_queue_ at the appropriate location given
+  // its priority and ordinal. Time complexity is O(scheduling_queue.size()).
+  void Schedule(StreamInfo* stream_info);
+
+  // Removes stream from scheduling_queue_.
+  void Unschedule(StreamInfo* stream_info);
+
+  // Return true if all internal invariants hold (useful for unit tests).
+  // Unless there are bugs, this should always return true.
+  bool ValidateInvariantsForTests() const;
+
+  // Returns true if the parent stream has the given stream in its children.
+  bool StreamHasChild(const StreamInfo& parent_info,
+                      const StreamInfo* child_info) const;
+
+  // Pointee owned by all_stream_infos_.
+  StreamInfo* root_stream_info_;
+  // Maps from stream IDs to StreamInfo objects.
+  SpdySmallMap<StreamIdType, std::unique_ptr<StreamInfo>, 10> all_stream_infos_;
+  // Queue containing all ready streams, ordered with streams of higher
+  // priority before streams of lower priority, and, among streams of equal
+  // priority, streams with lower ordinal before those with higher
+  // ordinal. Note that not all streams in scheduling_queue_ are eligible to be
+  // picked as the next stream: some may have ancestor stream(s) that are ready
+  // and unblocked. In these situations the occluded child streams are left in
+  // the queue, to reduce churn.
+  SpdyIntrusiveList<StreamInfo> scheduling_queue_;
+  // Ordinal value to assign to next node inserted into scheduling_queue_ when
+  // |add_to_front == true|. Decremented after each assignment.
+  int64_t head_ordinal_ = -1;
+  // Ordinal value to assign to next node inserted into scheduling_queue_ when
+  // |add_to_front == false|. Incremented after each assignment.
+  int64_t tail_ordinal_ = 0;
+};
+
+template <typename StreamIdType>
+Http2PriorityWriteScheduler<StreamIdType>::Http2PriorityWriteScheduler() {
+  auto root_stream_info = SpdyMakeUnique<StreamInfo>();
+  root_stream_info_ = root_stream_info.get();
+  root_stream_info->id = kHttp2RootStreamId;
+  root_stream_info->weight = kHttp2DefaultStreamWeight;
+  root_stream_info->parent = nullptr;
+  root_stream_info->priority = 1.0;
+  root_stream_info->ready = false;
+  all_stream_infos_[kHttp2RootStreamId] = std::move(root_stream_info);
+}
+
+template <typename StreamIdType>
+int Http2PriorityWriteScheduler<StreamIdType>::num_streams() const {
+  return all_stream_infos_.size();
+}
+
+template <typename StreamIdType>
+bool Http2PriorityWriteScheduler<StreamIdType>::StreamRegistered(
+    StreamIdType stream_id) const {
+  return SpdyContainsKey(all_stream_infos_, stream_id);
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::RegisterStream(
+    StreamIdType stream_id,
+    const StreamPrecedenceType& precedence) {
+  // TODO(mpw): uncomment the SPDY_BUG_IF below once all tests
+  //   (e.g. SpdyClientDispatcher) modified to pass StreamPrecedence instances
+  //   appropriate for protocol version under test.
+  //
+  // SPDY_BUG_IF(precedence.is_spdy3_priority())
+  //     << "Expected HTTP/2 stream dependency";
+
+  if (StreamRegistered(stream_id)) {
+    SPDY_BUG << "Stream " << stream_id << " already registered";
+    return;
+  }
+
+  StreamInfo* parent = FindStream(precedence.parent_id());
+  if (parent == nullptr) {
+    // parent_id may legitimately not be registered yet--see b/15676312.
+    SPDY_VLOG(1) << "Parent stream " << precedence.parent_id()
+                 << " not registered";
+    parent = root_stream_info_;
+  }
+
+  auto new_stream_info = SpdyMakeUnique<StreamInfo>();
+  StreamInfo* new_stream_info_ptr = new_stream_info.get();
+  new_stream_info_ptr->id = stream_id;
+  new_stream_info_ptr->weight = precedence.weight();
+  new_stream_info_ptr->parent = parent;
+  all_stream_infos_[stream_id] = std::move(new_stream_info);
+  if (precedence.is_exclusive()) {
+    // Move the parent's current children below the new stream.
+    using std::swap;
+    swap(new_stream_info_ptr->children, parent->children);
+    new_stream_info_ptr->total_child_weights = parent->total_child_weights;
+    // Update each child's parent.
+    for (StreamInfo* child : new_stream_info_ptr->children) {
+      child->parent = new_stream_info_ptr;
+    }
+    // Clear parent's old child data.
+    DCHECK(parent->children.empty());
+    parent->total_child_weights = 0;
+  }
+  // Add new stream to parent.
+  parent->children.push_back(new_stream_info_ptr);
+  parent->total_child_weights += precedence.weight();
+
+  // Update all priorities under parent, since addition of a stream affects
+  // sibling priorities as well.
+  UpdatePrioritiesUnder(parent);
+
+  // Stream starts with ready == false, so no need to schedule it yet.
+  DCHECK(!new_stream_info_ptr->ready);
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::UnregisterStream(
+    StreamIdType stream_id) {
+  if (stream_id == kHttp2RootStreamId) {
+    SPDY_BUG << "Cannot unregister root stream";
+    return;
+  }
+  // Remove the stream from table.
+  auto it = all_stream_infos_.find(stream_id);
+  if (it == all_stream_infos_.end()) {
+    SPDY_BUG << "Stream " << stream_id << " not registered";
+    return;
+  }
+  std::unique_ptr<StreamInfo> stream_info(std::move(it->second));
+  all_stream_infos_.erase(it);
+  // If ready (and hence scheduled), unschedule.
+  if (stream_info->ready) {
+    Unschedule(stream_info.get());
+  }
+
+  StreamInfo* parent = stream_info->parent;
+  // Remove the stream from parent's child list.
+  Remove(&parent->children, stream_info.get());
+  parent->total_child_weights -= stream_info->weight;
+
+  // Move the stream's children to the parent's child list.
+  // Update each child's parent and weight.
+  for (StreamInfo* child : stream_info->children) {
+    child->parent = parent;
+    parent->children.push_back(child);
+    // Divide the removed stream's weight among its children, rounding to the
+    // nearest valid weight.
+    float float_weight = stream_info->weight *
+                         static_cast<float>(child->weight) /
+                         static_cast<float>(stream_info->total_child_weights);
+    int new_weight = floor(float_weight + 0.5);
+    if (new_weight == 0) {
+      new_weight = 1;
+    }
+    child->weight = new_weight;
+    parent->total_child_weights += child->weight;
+  }
+  UpdatePrioritiesUnder(parent);
+}
+
+template <typename StreamIdType>
+typename Http2PriorityWriteScheduler<StreamIdType>::StreamPrecedenceType
+Http2PriorityWriteScheduler<StreamIdType>::GetStreamPrecedence(
+    StreamIdType stream_id) const {
+  const StreamInfo* stream_info = FindStream(stream_id);
+  if (stream_info == nullptr) {
+    // Unknown streams tolerated due to b/15676312. However, return lowest
+    // weight.
+    SPDY_VLOG(1) << "Stream " << stream_id << " not registered";
+    return StreamPrecedenceType(kHttp2RootStreamId, kHttp2MinStreamWeight,
+                                false);
+  }
+  return stream_info->ToStreamPrecedence();
+}
+
+template <typename StreamIdType>
+std::vector<StreamIdType>
+Http2PriorityWriteScheduler<StreamIdType>::GetStreamChildren(
+    StreamIdType stream_id) const {
+  std::vector<StreamIdType> child_vec;
+  const StreamInfo* stream_info = FindStream(stream_id);
+  if (stream_info == nullptr) {
+    SPDY_BUG << "Stream " << stream_id << " not registered";
+  } else {
+    child_vec.reserve(stream_info->children.size());
+    for (StreamInfo* child : stream_info->children) {
+      child_vec.push_back(child->id);
+    }
+  }
+  return child_vec;
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::UpdateStreamPrecedence(
+    StreamIdType stream_id,
+    const StreamPrecedenceType& precedence) {
+  // TODO(mpw): uncomment the SPDY_BUG_IF below once all tests
+  //   (e.g. SpdyClientDispatcher) modified to pass StreamPrecedence instances
+  //   appropriate for protocol version under test.
+  //
+  // SPDY_BUG_IF(precedence.is_spdy3_priority())
+  //     << "Expected HTTP/2 stream dependency";
+  if (stream_id == kHttp2RootStreamId) {
+    SPDY_BUG << "Cannot set precedence of root stream";
+    return;
+  }
+
+  StreamInfo* stream_info = FindStream(stream_id);
+  if (stream_info == nullptr) {
+    // TODO(mpw): add to all_stream_infos_ on demand--see b/15676312.
+    SPDY_VLOG(1) << "Stream " << stream_id << " not registered";
+    return;
+  }
+  UpdateStreamParent(stream_info, precedence.parent_id(),
+                     precedence.is_exclusive());
+  UpdateStreamWeight(stream_info, precedence.weight());
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::UpdateStreamWeight(
+    StreamInfo* stream_info,
+    int weight) {
+  if (weight == stream_info->weight) {
+    return;
+  }
+  if (stream_info->parent != nullptr) {
+    stream_info->parent->total_child_weights += (weight - stream_info->weight);
+  }
+  stream_info->weight = weight;
+
+  // Change in weight also affects sibling priorities.
+  UpdatePrioritiesUnder(stream_info->parent);
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::UpdateStreamParent(
+    StreamInfo* stream_info,
+    StreamIdType parent_id,
+    bool exclusive) {
+  if (stream_info->id == parent_id) {
+    SPDY_BUG << "Cannot set stream to be its own parent";
+    return;
+  }
+  StreamInfo* new_parent = FindStream(parent_id);
+  if (new_parent == nullptr) {
+    // parent_id may legitimately not be registered yet--see b/15676312.
+    SPDY_VLOG(1) << "Parent stream " << parent_id << " not registered";
+    return;
+  }
+
+  // If the new parent is already the stream's parent, we're done.
+  if (stream_info->parent == new_parent) {
+    return;
+  }
+
+  // Next, check to see if the new parent is currently a descendant
+  // of the stream.
+  StreamInfo* last = new_parent->parent;
+  bool cycle_exists = false;
+  while (last != nullptr) {
+    if (last == stream_info) {
+      cycle_exists = true;
+      break;
+    }
+    last = last->parent;
+  }
+
+  if (cycle_exists) {
+    // The new parent moves to the level of the current stream.
+    UpdateStreamParent(new_parent, stream_info->parent->id, false);
+  }
+
+  // Remove stream from old parent's child list.
+  StreamInfo* old_parent = stream_info->parent;
+  Remove(&old_parent->children, stream_info);
+  old_parent->total_child_weights -= stream_info->weight;
+  UpdatePrioritiesUnder(old_parent);
+
+  if (exclusive) {
+    // Move the new parent's current children below the current stream.
+    for (StreamInfo* child : new_parent->children) {
+      child->parent = stream_info;
+      stream_info->children.push_back(child);
+    }
+    stream_info->total_child_weights += new_parent->total_child_weights;
+    // Clear new parent's old child data.
+    new_parent->children.clear();
+    new_parent->total_child_weights = 0;
+  }
+
+  // Make the change.
+  stream_info->parent = new_parent;
+  new_parent->children.push_back(stream_info);
+  new_parent->total_child_weights += stream_info->weight;
+  UpdatePrioritiesUnder(new_parent);
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::RecordStreamEventTime(
+    StreamIdType stream_id,
+    int64_t now_in_usec) {
+  if (stream_id == kHttp2RootStreamId) {
+    SPDY_BUG << "Cannot record event time for root stream";
+    return;
+  }
+  StreamInfo* stream_info = FindStream(stream_id);
+  if (stream_info == nullptr) {
+    SPDY_BUG << "Stream " << stream_id << " not registered";
+    return;
+  }
+  stream_info->last_event_time_usec = now_in_usec;
+}
+
+// O(n) in the number of streams, which isn't great. However, this method will
+// soon be superseded by
+// Http2WeightedWriteScheduler::GetLatestEventWithPrecedence(), for which an
+// efficient implementation is straightforward. Also, this method is only
+// called when calculating idle timeouts, so performance isn't key.
+template <typename StreamIdType>
+int64_t Http2PriorityWriteScheduler<StreamIdType>::GetLatestEventWithPrecedence(
+    StreamIdType stream_id) const {
+  if (stream_id == kHttp2RootStreamId) {
+    SPDY_BUG << "Invalid argument: root stream";
+    return 0;
+  }
+  const StreamInfo* stream_info = FindStream(stream_id);
+  if (stream_info == nullptr) {
+    SPDY_BUG << "Stream " << stream_id << " not registered";
+    return 0;
+  }
+  int64_t last_event_time_usec = 0;
+  for (const auto& kv : all_stream_infos_) {
+    const StreamInfo& other = *kv.second;
+    if (other.priority > stream_info->priority) {
+      last_event_time_usec =
+          std::max(last_event_time_usec, other.last_event_time_usec);
+    }
+  }
+  return last_event_time_usec;
+}
+
+// Worst-case time complexity of O(n*d), where n is scheduling queue length and
+// d is tree depth. In practice, should be much shorter, since loop terminates
+// at first writable stream or |stream_id| (whichever is first).
+template <typename StreamIdType>
+bool Http2PriorityWriteScheduler<StreamIdType>::ShouldYield(
+    StreamIdType stream_id) const {
+  if (stream_id == kHttp2RootStreamId) {
+    SPDY_BUG << "Invalid argument: root stream";
+    return false;
+  }
+  const StreamInfo* stream_info = FindStream(stream_id);
+  if (stream_info == nullptr) {
+    SPDY_BUG << "Stream " << stream_id << " not registered";
+    return false;
+  }
+  for (const StreamInfo& scheduled : scheduling_queue_) {
+    if (stream_info == &scheduled) {
+      return false;
+    }
+    if (!HasReadyAncestor(scheduled)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::MarkStreamReady(
+    StreamIdType stream_id,
+    bool add_to_front) {
+  if (stream_id == kHttp2RootStreamId) {
+    SPDY_BUG << "Cannot mark root stream ready";
+    return;
+  }
+  StreamInfo* stream_info = FindStream(stream_id);
+  if (stream_info == nullptr) {
+    SPDY_BUG << "Stream " << stream_id << " not registered";
+    return;
+  }
+  if (stream_info->ready) {
+    return;
+  }
+  stream_info->ordinal = add_to_front ? head_ordinal_-- : tail_ordinal_++;
+  Schedule(stream_info);
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::MarkStreamNotReady(
+    StreamIdType stream_id) {
+  if (stream_id == kHttp2RootStreamId) {
+    SPDY_BUG << "Cannot mark root stream unready";
+    return;
+  }
+  StreamInfo* stream_info = FindStream(stream_id);
+  if (stream_info == nullptr) {
+    SPDY_BUG << "Stream " << stream_id << " not registered";
+    return;
+  }
+  if (!stream_info->ready) {
+    return;
+  }
+  Unschedule(stream_info);
+}
+
+template <typename StreamIdType>
+bool Http2PriorityWriteScheduler<StreamIdType>::Remove(
+    StreamInfoVector* stream_infos,
+    const StreamInfo* stream_info) {
+  for (typename StreamInfoVector::iterator it = stream_infos->begin();
+       it != stream_infos->end(); ++it) {
+    if (*it == stream_info) {
+      stream_infos->erase(it);
+      return true;
+    }
+  }
+  return false;
+}
+
+template <typename StreamIdType>
+bool Http2PriorityWriteScheduler<StreamIdType>::HasReadyAncestor(
+    const StreamInfo& stream_info) {
+  for (const StreamInfo* parent = stream_info.parent; parent != nullptr;
+       parent = parent->parent) {
+    if (parent->ready) {
+      return true;
+    }
+  }
+  return false;
+}
+
+template <typename StreamIdType>
+const typename Http2PriorityWriteScheduler<StreamIdType>::StreamInfo*
+Http2PriorityWriteScheduler<StreamIdType>::FindStream(
+    StreamIdType stream_id) const {
+  auto it = all_stream_infos_.find(stream_id);
+  return it == all_stream_infos_.end() ? nullptr : it->second.get();
+}
+
+template <typename StreamIdType>
+typename Http2PriorityWriteScheduler<StreamIdType>::StreamInfo*
+Http2PriorityWriteScheduler<StreamIdType>::FindStream(StreamIdType stream_id) {
+  auto it = all_stream_infos_.find(stream_id);
+  return it == all_stream_infos_.end() ? nullptr : it->second.get();
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::UpdatePrioritiesUnder(
+    StreamInfo* stream_info) {
+  for (StreamInfo* child : stream_info->children) {
+    child->priority = stream_info->priority *
+                      (static_cast<float>(child->weight) /
+                       static_cast<float>(stream_info->total_child_weights));
+    if (child->ready) {
+      // Reposition in scheduling_queue_. Use post-order for scheduling, to
+      // benefit from the fact that children have priority <= parent priority.
+      Unschedule(child);
+      UpdatePrioritiesUnder(child);
+      Schedule(child);
+    } else {
+      UpdatePrioritiesUnder(child);
+    }
+  }
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::Schedule(
+    StreamInfo* stream_info) {
+  DCHECK(!stream_info->ready);
+  for (StreamInfo& s : scheduling_queue_) {
+    if (stream_info->SchedulesBefore(s)) {
+      scheduling_queue_.insert(&s, stream_info);
+      stream_info->ready = true;
+      return;
+    }
+  }
+  scheduling_queue_.push_back(stream_info);
+  stream_info->ready = true;
+}
+
+template <typename StreamIdType>
+void Http2PriorityWriteScheduler<StreamIdType>::Unschedule(
+    StreamInfo* stream_info) {
+  DCHECK(stream_info->ready);
+  scheduling_queue_.erase(stream_info);
+  stream_info->ready = false;
+}
+
+template <typename StreamIdType>
+bool Http2PriorityWriteScheduler<StreamIdType>::StreamHasChild(
+    const StreamInfo& parent_info,
+    const StreamInfo* child_info) const {
+  auto found = std::find(parent_info.children.begin(),
+                         parent_info.children.end(), child_info);
+  return found != parent_info.children.end();
+}
+
+template <typename StreamIdType>
+bool Http2PriorityWriteScheduler<StreamIdType>::HasReadyStreams() const {
+  return !scheduling_queue_.empty();
+}
+
+template <typename StreamIdType>
+StreamIdType Http2PriorityWriteScheduler<StreamIdType>::PopNextReadyStream() {
+  return std::get<0>(PopNextReadyStreamAndPrecedence());
+}
+
+template <typename StreamIdType>
+std::tuple<
+    StreamIdType,
+    typename Http2PriorityWriteScheduler<StreamIdType>::StreamPrecedenceType>
+Http2PriorityWriteScheduler<StreamIdType>::PopNextReadyStreamAndPrecedence() {
+  for (StreamInfo& stream_info : scheduling_queue_) {
+    if (!HasReadyAncestor(stream_info)) {
+      Unschedule(&stream_info);
+      return std::make_tuple(stream_info.id, stream_info.ToStreamPrecedence());
+    }
+  }
+  SPDY_BUG << "No ready streams";
+  return std::make_tuple(
+      kHttp2RootStreamId,
+      StreamPrecedenceType(kHttp2RootStreamId, kHttp2MinStreamWeight, false));
+}
+
+template <typename StreamIdType>
+size_t Http2PriorityWriteScheduler<StreamIdType>::NumReadyStreams() const {
+  return scheduling_queue_.size();
+}
+
+template <typename StreamIdType>
+bool Http2PriorityWriteScheduler<StreamIdType>::IsStreamReady(
+    StreamIdType stream_id) const {
+  if (stream_id == kHttp2RootStreamId) {
+    SPDY_BUG << "Try to check whether root stream is ready";
+    return false;
+  }
+  const StreamInfo* stream_info = FindStream(stream_id);
+  if (stream_info == nullptr) {
+    SPDY_BUG << "Stream " << stream_id << " not registered";
+    return false;
+  }
+  return stream_info->ready;
+}
+
+template <typename StreamIdType>
+SpdyString Http2PriorityWriteScheduler<StreamIdType>::DebugString() const {
+  return SpdyStrCat("Http2PriorityWriteScheduler {num_streams=", num_streams(),
+                    " num_ready_streams=", NumReadyStreams(), "}");
+}
+
+template <typename StreamIdType>
+bool Http2PriorityWriteScheduler<StreamIdType>::ValidateInvariantsForTests()
+    const {
+  int total_streams = 0;
+  int streams_visited = 0;
+  // Iterate through all streams in the map.
+  for (const auto& kv : all_stream_infos_) {
+    ++total_streams;
+    ++streams_visited;
+    StreamIdType stream_id = kv.first;
+    const StreamInfo& stream_info = *kv.second;
+
+    // Verify each StreamInfo mapped under the proper stream ID.
+    if (stream_id != stream_info.id) {
+      SPDY_DLOG(INFO) << "Stream ID " << stream_id
+                      << " maps to StreamInfo with ID " << stream_info.id;
+      return false;
+    }
+
+    // All streams except the root should have a parent, and should appear in
+    // the children of that parent.
+    if (stream_info.id != kHttp2RootStreamId &&
+        !StreamHasChild(*stream_info.parent, &stream_info)) {
+      SPDY_DLOG(INFO) << "Parent stream " << stream_info.parent->id
+                      << " is not registered, or does not list stream "
+                      << stream_info.id << " as its child.";
+      return false;
+    }
+
+    if (!stream_info.children.empty()) {
+      int total_child_weights = 0;
+      // Iterate through the stream's children.
+      for (StreamInfo* child : stream_info.children) {
+        ++streams_visited;
+        // Each stream in the list should exist and should have this stream
+        // set as its parent.
+        if (!StreamRegistered(child->id) || child->parent != &stream_info) {
+          SPDY_DLOG(INFO) << "Child stream " << child->id
+                          << " is not registered, "
+                          << "or does not list " << stream_info.id
+                          << " as its parent.";
+          return false;
+        }
+        total_child_weights += child->weight;
+      }
+      // Verify that total_child_weights is correct.
+      if (total_child_weights != stream_info.total_child_weights) {
+        SPDY_DLOG(INFO) << "Child weight totals do not agree. For stream "
+                        << stream_info.id << " total_child_weights has value "
+                        << stream_info.total_child_weights << ", expected "
+                        << total_child_weights;
+        return false;
+      }
+    }
+  }
+
+  // Make sure num_streams reflects the total number of streams the map
+  // contains.
+  if (total_streams != num_streams()) {
+    SPDY_DLOG(INFO) << "Map contains incorrect number of streams.";
+    return false;
+  }
+  // Validate the validation function; we should have visited each stream twice
+  // (except for the root)
+  DCHECK(streams_visited == 2 * num_streams() - 1);
+  return true;
+}
+
+}  // namespace spdy
+
+#endif  // QUICHE_SPDY_CORE_HTTP2_PRIORITY_WRITE_SCHEDULER_H_
diff --git a/spdy/core/http2_priority_write_scheduler_test.cc b/spdy/core/http2_priority_write_scheduler_test.cc
new file mode 100644
index 0000000..17b7721
--- /dev/null
+++ b/spdy/core/http2_priority_write_scheduler_test.cc
@@ -0,0 +1,799 @@
+#include "net/third_party/quiche/src/spdy/core/http2_priority_write_scheduler.h"
+
+#include <initializer_list>
+
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_test.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_test_helpers.h"
+
+using ::testing::AssertionFailure;
+using ::testing::AssertionResult;
+using ::testing::AssertionSuccess;
+using ::testing::ElementsAre;
+using ::testing::IsEmpty;
+using ::testing::UnorderedElementsAre;
+
+namespace spdy {
+
+namespace test {
+
+template <typename StreamIdType>
+class Http2PriorityWriteSchedulerPeer {
+ public:
+  explicit Http2PriorityWriteSchedulerPeer(
+      Http2PriorityWriteScheduler<StreamIdType>* scheduler)
+      : scheduler_(scheduler) {}
+
+  int TotalChildWeights(StreamIdType stream_id) const {
+    return scheduler_->FindStream(stream_id)->total_child_weights;
+  }
+
+  bool ValidateInvariants() const {
+    return scheduler_->ValidateInvariantsForTests();
+  }
+
+ private:
+  Http2PriorityWriteScheduler<StreamIdType>* scheduler_;
+};
+
+class Http2PriorityWriteSchedulerTest : public ::testing::Test {
+ protected:
+  typedef uint32_t SpdyStreamId;
+
+  Http2PriorityWriteSchedulerTest() : peer_(&scheduler_) {}
+
+  Http2PriorityWriteScheduler<SpdyStreamId> scheduler_;
+  Http2PriorityWriteSchedulerPeer<SpdyStreamId> peer_;
+};
+
+TEST_F(Http2PriorityWriteSchedulerTest, RegisterAndUnregisterStreams) {
+  EXPECT_EQ(1, scheduler_.num_streams());
+  EXPECT_TRUE(scheduler_.StreamRegistered(0));
+  EXPECT_FALSE(scheduler_.StreamRegistered(1));
+
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  EXPECT_EQ(2, scheduler_.num_streams());
+  ASSERT_TRUE(scheduler_.StreamRegistered(1));
+  EXPECT_EQ(100, scheduler_.GetStreamPrecedence(1).weight());
+  EXPECT_FALSE(scheduler_.StreamRegistered(5));
+  EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1));
+
+  scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 50, false));
+  // Should not be able to add a stream with an id that already exists.
+  EXPECT_SPDY_BUG(
+      scheduler_.RegisterStream(5, SpdyStreamPrecedence(1, 50, false)),
+      "Stream 5 already registered");
+  EXPECT_EQ(3, scheduler_.num_streams());
+  EXPECT_TRUE(scheduler_.StreamRegistered(1));
+  ASSERT_TRUE(scheduler_.StreamRegistered(5));
+  EXPECT_EQ(50, scheduler_.GetStreamPrecedence(5).weight());
+  EXPECT_FALSE(scheduler_.StreamRegistered(13));
+
+  scheduler_.RegisterStream(13, SpdyStreamPrecedence(5, 130, true));
+  EXPECT_EQ(4, scheduler_.num_streams());
+  EXPECT_TRUE(scheduler_.StreamRegistered(1));
+  EXPECT_TRUE(scheduler_.StreamRegistered(5));
+  ASSERT_TRUE(scheduler_.StreamRegistered(13));
+  EXPECT_EQ(130, scheduler_.GetStreamPrecedence(13).weight());
+  EXPECT_EQ(5, scheduler_.GetStreamPrecedence(13).parent_id());
+
+  scheduler_.UnregisterStream(5);
+  // Cannot remove a stream that has already been removed.
+  EXPECT_SPDY_BUG(scheduler_.UnregisterStream(5), "Stream 5 not registered");
+  EXPECT_EQ(3, scheduler_.num_streams());
+  EXPECT_TRUE(scheduler_.StreamRegistered(1));
+  EXPECT_FALSE(scheduler_.StreamRegistered(5));
+  EXPECT_TRUE(scheduler_.StreamRegistered(13));
+  EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(13).parent_id());
+
+  // The parent stream 19 doesn't exist, so this should use 0 as parent stream:
+  scheduler_.RegisterStream(7, SpdyStreamPrecedence(19, 70, false));
+  EXPECT_TRUE(scheduler_.StreamRegistered(7));
+  EXPECT_EQ(0, scheduler_.GetStreamPrecedence(7).parent_id());
+  // Now stream 7 already exists, so this should fail:
+  EXPECT_SPDY_BUG(
+      scheduler_.RegisterStream(7, SpdyStreamPrecedence(1, 70, false)),
+      "Stream 7 already registered");
+  // Try adding a second child to stream 13:
+  scheduler_.RegisterStream(17, SpdyStreamPrecedence(13, 170, false));
+
+  scheduler_.UpdateStreamPrecedence(17, SpdyStreamPrecedence(13, 150, false));
+  EXPECT_EQ(150, scheduler_.GetStreamPrecedence(17).weight());
+
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, RegisterStreamWithSpdy3Priority) {
+  EXPECT_FALSE(scheduler_.StreamRegistered(1));
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(3));
+  EXPECT_EQ(0, scheduler_.NumReadyStreams());
+  EXPECT_TRUE(scheduler_.StreamRegistered(1));
+  EXPECT_EQ(3, scheduler_.GetStreamPrecedence(1).spdy3_priority());
+  EXPECT_EQ(147, scheduler_.GetStreamPrecedence(1).weight());
+  EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(1).parent_id());
+  EXPECT_THAT(scheduler_.GetStreamChildren(1), IsEmpty());
+
+  EXPECT_SPDY_BUG(scheduler_.RegisterStream(1, SpdyStreamPrecedence(4)),
+                  "Expected HTTP/2 stream dependency|"
+                  "Stream 1 already registered");
+  EXPECT_EQ(3, scheduler_.GetStreamPrecedence(1).spdy3_priority());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, GetStreamWeight) {
+  // Unknown streams tolerated due to b/15676312.
+  EXPECT_EQ(kHttp2MinStreamWeight, scheduler_.GetStreamPrecedence(3).weight());
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 130, true));
+  EXPECT_EQ(130, scheduler_.GetStreamPrecedence(3).weight());
+  scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 50, true));
+  EXPECT_EQ(50, scheduler_.GetStreamPrecedence(3).weight());
+  scheduler_.UnregisterStream(3);
+  EXPECT_EQ(kHttp2MinStreamWeight, scheduler_.GetStreamPrecedence(3).weight());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, GetStreamPriority) {
+  // Unknown streams tolerated due to b/15676312.
+  EXPECT_EQ(kV3LowestPriority,
+            scheduler_.GetStreamPrecedence(3).spdy3_priority());
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 130, true));
+  EXPECT_EQ(3, scheduler_.GetStreamPrecedence(3).spdy3_priority());
+  scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 50, true));
+  EXPECT_EQ(5, scheduler_.GetStreamPrecedence(3).spdy3_priority());
+  scheduler_.UnregisterStream(3);
+  EXPECT_EQ(kV3LowestPriority,
+            scheduler_.GetStreamPrecedence(3).spdy3_priority());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, GetStreamParent) {
+  // Unknown streams tolerated due to b/15676312.
+  EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(3).parent_id());
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 20, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(2, 30, false));
+  EXPECT_EQ(2, scheduler_.GetStreamPrecedence(3).parent_id());
+  scheduler_.UnregisterStream(3);
+  EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(3).parent_id());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, GetStreamChildren) {
+  EXPECT_SPDY_BUG(EXPECT_THAT(scheduler_.GetStreamChildren(7), IsEmpty()),
+                  "Stream 7 not registered");
+  scheduler_.RegisterStream(7, SpdyStreamPrecedence(0, 70, false));
+  EXPECT_THAT(scheduler_.GetStreamChildren(7), IsEmpty());
+  scheduler_.RegisterStream(9, SpdyStreamPrecedence(7, 90, false));
+  scheduler_.RegisterStream(15, SpdyStreamPrecedence(7, 150, false));
+  EXPECT_THAT(scheduler_.GetStreamChildren(7), UnorderedElementsAre(9, 15));
+  scheduler_.UnregisterStream(7);
+  EXPECT_SPDY_BUG(EXPECT_THAT(scheduler_.GetStreamChildren(7), IsEmpty()),
+                  "Stream 7 not registered");
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamWeight) {
+  EXPECT_SPDY_BUG(
+      scheduler_.UpdateStreamPrecedence(0, SpdyStreamPrecedence(0, 10, false)),
+      "Cannot set precedence of root stream");
+
+  // For the moment, updating stream precedence on a non-registered stream
+  // should have no effect. In the future, it will lazily cause the stream to
+  // be registered (b/15676312).
+  scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 10, false));
+  EXPECT_FALSE(scheduler_.StreamRegistered(3));
+
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 10, false));
+  scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 20, false));
+  EXPECT_EQ(20, scheduler_.GetStreamPrecedence(3).weight());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+
+  EXPECT_SPDY_BUG(
+      scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 500, false)),
+      "Invalid weight: 500");
+  EXPECT_EQ(kHttp2MaxStreamWeight, scheduler_.GetStreamPrecedence(3).weight());
+  EXPECT_SPDY_BUG(
+      scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 0, false)),
+      "Invalid weight: 0");
+  EXPECT_EQ(kHttp2MinStreamWeight, scheduler_.GetStreamPrecedence(3).weight());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+
+  scheduler_.UnregisterStream(3);
+}
+
+// Basic case of reparenting a subtree.
+TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentBasicNonExclusive) {
+  /* Tree:
+        0
+       / \
+      1   2
+     / \
+    3   4
+   */
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, false));
+  EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2));
+  EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(3, 4));
+  EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(1));
+  EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+// Basic case of reparenting a subtree.  Result here is the same as the
+// non-exclusive case.
+TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentBasicExclusive) {
+  /* Tree:
+        0
+       / \
+      1   2
+     / \
+    3   4
+   */
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, true));
+  EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2));
+  EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(3, 4));
+  EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(1));
+  EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+// We can't set the parent of a nonexistent stream, or set the parent to a
+// nonexistent stream.
+TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentNonexistent) {
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false));
+  for (bool exclusive : {true, false}) {
+    // For the moment, updating stream precedence on a non-registered stream or
+    // attempting to set parent to a nonexistent stream should have no
+    // effect. In the future, it will lazily cause the stream(s) to be
+    // registered (b/15676312).
+
+    // No-op: parent stream 3 not registered
+    scheduler_.UpdateStreamPrecedence(1,
+                                      SpdyStreamPrecedence(3, 100, exclusive));
+
+    // No-op: stream 4 not registered
+    scheduler_.UpdateStreamPrecedence(4,
+                                      SpdyStreamPrecedence(2, 100, exclusive));
+
+    // No-op: stream 3 not registered
+    scheduler_.UpdateStreamPrecedence(3,
+                                      SpdyStreamPrecedence(4, 100, exclusive));
+
+    EXPECT_THAT(scheduler_.GetStreamChildren(0), UnorderedElementsAre(1, 2));
+    EXPECT_THAT(scheduler_.GetStreamChildren(1), IsEmpty());
+    EXPECT_THAT(scheduler_.GetStreamChildren(2), IsEmpty());
+    EXPECT_FALSE(scheduler_.StreamRegistered(3));
+    EXPECT_FALSE(scheduler_.StreamRegistered(4));
+  }
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+// We should be able to add multiple children to streams.
+TEST_F(Http2PriorityWriteSchedulerTest,
+       UpdateStreamParentMultipleChildrenNonExclusive) {
+  /* Tree:
+        0
+       / \
+      1   2
+     / \   \
+    3   4   5
+   */
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false));
+  scheduler_.UpdateStreamPrecedence(2, SpdyStreamPrecedence(1, 100, false));
+  EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1));
+  EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3, 4));
+  EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(5));
+  EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest,
+       UpdateStreamParentMultipleChildrenExclusive) {
+  /* Tree:
+        0
+       / \
+      1   2
+     / \   \
+    3   4   5
+   */
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false));
+  scheduler_.UpdateStreamPrecedence(2, SpdyStreamPrecedence(1, 100, true));
+  EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1));
+  EXPECT_THAT(scheduler_.GetStreamChildren(1), ElementsAre(2));
+  EXPECT_THAT(scheduler_.GetStreamChildren(2), UnorderedElementsAre(3, 4, 5));
+  EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToChildNonExclusive) {
+  /* Tree:
+        0
+        |
+        1
+       / \
+      2   3
+      |
+      4
+   */
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false));
+  scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, false));
+  EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2));
+  EXPECT_THAT(scheduler_.GetStreamChildren(1), ElementsAre(3));
+  EXPECT_THAT(scheduler_.GetStreamChildren(2), UnorderedElementsAre(1, 4));
+  EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToChildExclusive) {
+  /* Tree:
+        0
+        |
+        1
+       / \
+      2   3
+      |
+      4
+   */
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false));
+  scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, true));
+  EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2));
+  EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(3, 4));
+  EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(1));
+  EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest,
+       UpdateStreamParentToGrandchildNonExclusive) {
+  /* Tree:
+        0
+        |
+        1
+       / \
+      2   3
+     / \
+    4   5
+    |
+    6
+   */
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false));
+  scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false));
+  scheduler_.RegisterStream(6, SpdyStreamPrecedence(4, 100, false));
+  scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(4, 100, false));
+  EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(4));
+  EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3));
+  EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(5));
+  EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(4), UnorderedElementsAre(1, 6));
+  EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(6), IsEmpty());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest,
+       UpdateStreamParentToGrandchildExclusive) {
+  /* Tree:
+        0
+        |
+        1
+       / \
+      2   3
+     / \
+    4   5
+    |
+    6
+   */
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false));
+  scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false));
+  scheduler_.RegisterStream(6, SpdyStreamPrecedence(4, 100, false));
+  scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(4, 100, true));
+  EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(4));
+  EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3, 6));
+  EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(5));
+  EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(4), ElementsAre(1));
+  EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty());
+  EXPECT_THAT(scheduler_.GetStreamChildren(6), IsEmpty());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToParent) {
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false));
+  for (bool exclusive : {true, false}) {
+    scheduler_.UpdateStreamPrecedence(2,
+                                      SpdyStreamPrecedence(1, 100, exclusive));
+    EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1));
+    EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3));
+    EXPECT_THAT(scheduler_.GetStreamChildren(2), IsEmpty());
+    EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty());
+  }
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToSelf) {
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  EXPECT_SPDY_BUG(
+      scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(1, 100, false)),
+      "Cannot set stream to be its own parent");
+  EXPECT_SPDY_BUG(
+      scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(1, 100, true)),
+      "Cannot set stream to be its own parent");
+  EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1));
+  EXPECT_THAT(scheduler_.GetStreamChildren(1), IsEmpty());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, BlockAndUnblock) {
+  /* Create the tree.
+
+             0
+           / | \
+          /  |  \
+         1   2   3
+        / \   \   \
+       4   5   6   7
+      /|  / \  |   |\
+     8 9 10 11 12 13 14
+    / \
+   15 16
+
+  */
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(5, SpdyStreamPrecedence(1, 100, false));
+  scheduler_.RegisterStream(8, SpdyStreamPrecedence(4, 100, false));
+  scheduler_.RegisterStream(9, SpdyStreamPrecedence(4, 100, false));
+  scheduler_.RegisterStream(10, SpdyStreamPrecedence(5, 100, false));
+  scheduler_.RegisterStream(11, SpdyStreamPrecedence(5, 100, false));
+  scheduler_.RegisterStream(15, SpdyStreamPrecedence(8, 100, false));
+  scheduler_.RegisterStream(16, SpdyStreamPrecedence(8, 100, false));
+  scheduler_.RegisterStream(12, SpdyStreamPrecedence(2, 100, false));
+  scheduler_.RegisterStream(6, SpdyStreamPrecedence(2, 100, true));
+  scheduler_.RegisterStream(7, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(13, SpdyStreamPrecedence(7, 100, true));
+  scheduler_.RegisterStream(14, SpdyStreamPrecedence(7, 100, false));
+  scheduler_.UpdateStreamPrecedence(7, SpdyStreamPrecedence(3, 100, false));
+  EXPECT_EQ(0, scheduler_.GetStreamPrecedence(1).parent_id());
+  EXPECT_EQ(0, scheduler_.GetStreamPrecedence(2).parent_id());
+  EXPECT_EQ(0, scheduler_.GetStreamPrecedence(3).parent_id());
+  EXPECT_EQ(1, scheduler_.GetStreamPrecedence(4).parent_id());
+  EXPECT_EQ(1, scheduler_.GetStreamPrecedence(5).parent_id());
+  EXPECT_EQ(2, scheduler_.GetStreamPrecedence(6).parent_id());
+  EXPECT_EQ(3, scheduler_.GetStreamPrecedence(7).parent_id());
+  EXPECT_EQ(4, scheduler_.GetStreamPrecedence(8).parent_id());
+  EXPECT_EQ(4, scheduler_.GetStreamPrecedence(9).parent_id());
+  EXPECT_EQ(5, scheduler_.GetStreamPrecedence(10).parent_id());
+  EXPECT_EQ(5, scheduler_.GetStreamPrecedence(11).parent_id());
+  EXPECT_EQ(6, scheduler_.GetStreamPrecedence(12).parent_id());
+  EXPECT_EQ(7, scheduler_.GetStreamPrecedence(13).parent_id());
+  EXPECT_EQ(7, scheduler_.GetStreamPrecedence(14).parent_id());
+  EXPECT_EQ(8, scheduler_.GetStreamPrecedence(15).parent_id());
+  EXPECT_EQ(8, scheduler_.GetStreamPrecedence(16).parent_id());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+
+  EXPECT_EQ(peer_.TotalChildWeights(0),
+            scheduler_.GetStreamPrecedence(1).weight() +
+                scheduler_.GetStreamPrecedence(2).weight() +
+                scheduler_.GetStreamPrecedence(3).weight());
+  EXPECT_EQ(peer_.TotalChildWeights(3),
+            scheduler_.GetStreamPrecedence(7).weight());
+  EXPECT_EQ(peer_.TotalChildWeights(7),
+            scheduler_.GetStreamPrecedence(13).weight() +
+                scheduler_.GetStreamPrecedence(14).weight());
+  EXPECT_EQ(peer_.TotalChildWeights(13), 0);
+  EXPECT_EQ(peer_.TotalChildWeights(14), 0);
+
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, HasReadyStreams) {
+  EXPECT_FALSE(scheduler_.HasReadyStreams());
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, false));
+  EXPECT_FALSE(scheduler_.HasReadyStreams());
+  scheduler_.MarkStreamReady(1, false);
+  EXPECT_TRUE(scheduler_.HasReadyStreams());
+  EXPECT_TRUE(scheduler_.IsStreamReady(1));
+  scheduler_.MarkStreamNotReady(1);
+  EXPECT_FALSE(scheduler_.HasReadyStreams());
+  EXPECT_FALSE(scheduler_.IsStreamReady(1));
+  scheduler_.MarkStreamReady(1, true);
+  EXPECT_TRUE(scheduler_.HasReadyStreams());
+  EXPECT_TRUE(scheduler_.IsStreamReady(1));
+  scheduler_.UnregisterStream(1);
+  EXPECT_FALSE(scheduler_.HasReadyStreams());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+  EXPECT_SPDY_BUG(scheduler_.IsStreamReady(1), "Stream 1 not registered");
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, CalculateRoundedWeights) {
+  /* Create the tree.
+
+           0
+          / \
+         1   2
+       /| |\  |\
+      8 3 4 5 6 7
+  */
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, true));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 5, false));
+  scheduler_.RegisterStream(6, SpdyStreamPrecedence(2, 1, false));
+  scheduler_.RegisterStream(7, SpdyStreamPrecedence(2, 1, false));
+  scheduler_.RegisterStream(8, SpdyStreamPrecedence(1, 1, false));
+
+  // Remove higher-level streams.
+  scheduler_.UnregisterStream(1);
+  scheduler_.UnregisterStream(2);
+
+  // 3.3 rounded down = 3.
+  EXPECT_EQ(3, scheduler_.GetStreamPrecedence(3).weight());
+  EXPECT_EQ(3, scheduler_.GetStreamPrecedence(4).weight());
+  EXPECT_EQ(3, scheduler_.GetStreamPrecedence(5).weight());
+  // 2.5 rounded up = 3.
+  EXPECT_EQ(3, scheduler_.GetStreamPrecedence(6).weight());
+  EXPECT_EQ(3, scheduler_.GetStreamPrecedence(7).weight());
+  // 0 is not a valid weight, so round up to 1.
+  EXPECT_EQ(1, scheduler_.GetStreamPrecedence(8).weight());
+  ASSERT_TRUE(peer_.ValidateInvariants());
+}
+
+TEST_F(Http2PriorityWriteSchedulerTest, GetLatestEventWithPrecedence) {
+  EXPECT_SPDY_BUG(scheduler_.RecordStreamEventTime(3, 5),
+                  "Stream 3 not registered");
+  EXPECT_SPDY_BUG(EXPECT_EQ(0, scheduler_.GetLatestEventWithPrecedence(4)),
+                  "Stream 4 not registered");
+
+  for (int i = 1; i < 5; ++i) {
+    int weight = SpdyStreamPrecedence(i).weight();
+    scheduler_.RegisterStream(i, SpdyStreamPrecedence(0, weight, false));
+  }
+  for (int i = 1; i < 5; ++i) {
+    EXPECT_EQ(0, scheduler_.GetLatestEventWithPrecedence(i));
+  }
+  for (int i = 1; i < 5; ++i) {
+    scheduler_.RecordStreamEventTime(i, i * 100);
+  }
+  for (int i = 1; i < 5; ++i) {
+    EXPECT_EQ((i - 1) * 100, scheduler_.GetLatestEventWithPrecedence(i));
+  }
+}
+
+// Add ready streams at front and back.
+TEST_F(Http2PriorityWriteSchedulerTest, MarkReadyFrontAndBack) {
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 20, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 20, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(0, 20, false));
+  scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 30, false));
+
+  for (int i = 1; i < 6; ++i) {
+    scheduler_.MarkStreamReady(i, false);
+  }
+  EXPECT_EQ(5, scheduler_.PopNextReadyStream());
+  EXPECT_EQ(2, scheduler_.PopNextReadyStream());
+  scheduler_.MarkStreamReady(2, false);
+  EXPECT_EQ(3, scheduler_.PopNextReadyStream());
+  scheduler_.MarkStreamReady(3, false);
+  EXPECT_EQ(4, scheduler_.PopNextReadyStream());
+  scheduler_.MarkStreamReady(4, false);
+  EXPECT_EQ(2, scheduler_.PopNextReadyStream());
+  scheduler_.MarkStreamReady(2, true);
+  EXPECT_EQ(2, scheduler_.PopNextReadyStream());
+  scheduler_.MarkStreamReady(5, false);
+  scheduler_.MarkStreamReady(2, true);
+  EXPECT_EQ(5, scheduler_.PopNextReadyStream());
+}
+
+// Add ready streams at front and back and pop them with
+// PopNextReadyStreamAndPrecedence.
+TEST_F(Http2PriorityWriteSchedulerTest, PopNextReadyStreamAndPrecedence) {
+  scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, false));
+  scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 20, false));
+  scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 20, false));
+  scheduler_.RegisterStream(4, SpdyStreamPrecedence(0, 20, false));
+  scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 30, false));
+
+  for (int i = 1; i < 6; ++i) {
+    scheduler_.MarkStreamReady(i, false);
+  }
+  EXPECT_EQ(std::make_tuple(5, SpdyStreamPrecedence(0, 30, false)),
+            scheduler_.PopNextReadyStreamAndPrecedence());
+  EXPECT_EQ(std::make_tuple(2, SpdyStreamPrecedence(0, 20, false)),
+            scheduler_.PopNextReadyStreamAndPrecedence());
+  scheduler_.MarkStreamReady(2, false);
+  EXPECT_EQ(std::make_tuple(3, SpdyStreamPrecedence(0, 20, false)),
+            scheduler_.PopNextReadyStreamAndPrecedence());
+  scheduler_.MarkStreamReady(3, false);
+  EXPECT_EQ(std::make_tuple(4, SpdyStreamPrecedence(0, 20, false)),
+            scheduler_.PopNextReadyStreamAndPrecedence());
+  scheduler_.MarkStreamReady(4, false);
+  EXPECT_EQ(std::make_tuple(2, SpdyStreamPrecedence(0, 20, false)),
+            scheduler_.PopNextReadyStreamAndPrecedence());
+  scheduler_.MarkStreamReady(2, true);
+  EXPECT_EQ(std::make_tuple(2, SpdyStreamPrecedence(0, 20, false)),
+            scheduler_.PopNextReadyStreamAndPrecedence());
+  scheduler_.MarkStreamReady(5, false);
+  scheduler_.MarkStreamReady(2, true);
+  EXPECT_EQ(std::make_tuple(5, SpdyStreamPrecedence(0, 30, false)),
+            scheduler_.PopNextReadyStreamAndPrecedence());
+}
+
+class PopNextReadyStreamTest : public Http2PriorityWriteSchedulerTest {
+ protected:
+  void SetUp() override {
+    /* Create the tree.
+
+             0
+            /|\
+           1 2 3
+          /| |\
+         4 5 6 7
+        /
+       8
+
+    */
+    scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false));
+    scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false));
+    scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, false));
+    scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false));
+    scheduler_.RegisterStream(5, SpdyStreamPrecedence(1, 100, false));
+    scheduler_.RegisterStream(6, SpdyStreamPrecedence(2, 100, false));
+    scheduler_.RegisterStream(7, SpdyStreamPrecedence(2, 100, false));
+    scheduler_.RegisterStream(8, SpdyStreamPrecedence(4, 100, false));
+
+    // Set all nodes ready to write.
+    for (SpdyStreamId id = 1; id <= 8; ++id) {
+      scheduler_.MarkStreamReady(id, false);
+    }
+  }
+
+  AssertionResult PopNextReturnsCycle(
+      std::initializer_list<SpdyStreamId> stream_ids) {
+    int count = 0;
+    const int kNumCyclesToCheck = 2;
+    for (int i = 0; i < kNumCyclesToCheck; i++) {
+      for (SpdyStreamId expected_id : stream_ids) {
+        SpdyStreamId next_id = scheduler_.PopNextReadyStream();
+        scheduler_.MarkStreamReady(next_id, false);
+        if (next_id != expected_id) {
+          return AssertionFailure() << "Pick " << count << ": expected stream "
+                                    << expected_id << " instead of " << next_id;
+        }
+        if (!peer_.ValidateInvariants()) {
+          return AssertionFailure() << "ValidateInvariants failed";
+        }
+        ++count;
+      }
+    }
+    return AssertionSuccess();
+  }
+};
+
+// When all streams are schedulable, only top-level streams should be returned.
+TEST_F(PopNextReadyStreamTest, NoneBlocked) {
+  EXPECT_TRUE(PopNextReturnsCycle({1, 2, 3}));
+}
+
+// When a parent stream is blocked, its children should be scheduled, if
+// priorities allow.
+TEST_F(PopNextReadyStreamTest, SingleStreamBlocked) {
+  scheduler_.MarkStreamNotReady(1);
+
+  // Round-robin only across 2 and 3, since children of 1 have lower priority.
+  EXPECT_TRUE(PopNextReturnsCycle({2, 3}));
+
+  // Make children of 1 have equal priority as 2 and 3, after which they should
+  // be returned as well.
+  scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(0, 200, false));
+  EXPECT_TRUE(PopNextReturnsCycle({4, 5, 2, 3}));
+}
+
+// Block multiple levels of streams.
+TEST_F(PopNextReadyStreamTest, MultiLevelBlocked) {
+  for (SpdyStreamId stream_id : {1, 4, 5}) {
+    scheduler_.MarkStreamNotReady(stream_id);
+  }
+  // Round-robin only across 2 and 3, since children of 1 have lower priority.
+  EXPECT_TRUE(PopNextReturnsCycle({2, 3}));
+
+  // Make 8 have equal priority as 2 and 3.
+  scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(0, 200, false));
+  EXPECT_TRUE(PopNextReturnsCycle({8, 2, 3}));
+}
+
+// A removed stream shouldn't be scheduled.
+TEST_F(PopNextReadyStreamTest, RemoveStream) {
+  scheduler_.UnregisterStream(1);
+
+  // Round-robin only across 2 and 3, since previous children of 1 have lower
+  // priority (the weight of 4 and 5 is scaled down when they are elevated to
+  // siblings of 2 and 3).
+  EXPECT_TRUE(PopNextReturnsCycle({2, 3}));
+
+  // Make previous children of 1 have equal priority as 2 and 3.
+  scheduler_.UpdateStreamPrecedence(4, SpdyStreamPrecedence(0, 100, false));
+  scheduler_.UpdateStreamPrecedence(5, SpdyStreamPrecedence(0, 100, false));
+  EXPECT_TRUE(PopNextReturnsCycle({4, 5, 2, 3}));
+}
+
+// Block an entire subtree.
+TEST_F(PopNextReadyStreamTest, SubtreeBlocked) {
+  for (SpdyStreamId stream_id : {1, 4, 5, 8}) {
+    scheduler_.MarkStreamNotReady(stream_id);
+  }
+  EXPECT_TRUE(PopNextReturnsCycle({2, 3}));
+}
+
+// If all parent streams are blocked, children should be returned.
+TEST_F(PopNextReadyStreamTest, ParentsBlocked) {
+  for (SpdyStreamId stream_id : {1, 2, 3}) {
+    scheduler_.MarkStreamNotReady(stream_id);
+  }
+  EXPECT_TRUE(PopNextReturnsCycle({4, 5, 6, 7}));
+}
+
+// Unblocking streams should make them schedulable.
+TEST_F(PopNextReadyStreamTest, BlockAndUnblock) {
+  EXPECT_TRUE(PopNextReturnsCycle({1, 2, 3}));
+  scheduler_.MarkStreamNotReady(2);
+  EXPECT_TRUE(PopNextReturnsCycle({1, 3}));
+  scheduler_.MarkStreamReady(2, false);
+  // Cycle order permuted since 2 effectively appended at tail.
+  EXPECT_TRUE(PopNextReturnsCycle({1, 3, 2}));
+}
+
+// Block nodes in multiple subtrees.
+TEST_F(PopNextReadyStreamTest, ScatteredBlocked) {
+  for (SpdyStreamId stream_id : {1, 2, 6, 7}) {
+    scheduler_.MarkStreamNotReady(stream_id);
+  }
+  // Only 3 returned, since of remaining streams it has highest priority.
+  EXPECT_TRUE(PopNextReturnsCycle({3}));
+
+  // Make children of 1 have priority equal to 3.
+  scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(0, 200, false));
+  EXPECT_TRUE(PopNextReturnsCycle({4, 5, 3}));
+
+  // When 4 is blocked, its child 8 should take its place, since it has same
+  // priority.
+  scheduler_.MarkStreamNotReady(4);
+  EXPECT_TRUE(PopNextReturnsCycle({8, 5, 3}));
+}
+
+}  // namespace test
+}  // namespace spdy
diff --git a/spdy/core/spdy_intrusive_list.h b/spdy/core/spdy_intrusive_list.h
new file mode 100644
index 0000000..16917f9
--- /dev/null
+++ b/spdy/core/spdy_intrusive_list.h
@@ -0,0 +1,326 @@
+// 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.
+
+#ifndef QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_
+#define QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_
+
+// A SpdyIntrusiveList<> is a doubly-linked list where the link pointers are
+// embedded in the elements. They are circularly linked making insertion and
+// removal into a known position constant time and branch-free operations.
+//
+// Usage is similar to an STL list<> where feasible, but there are important
+// differences. First and foremost, the elements must derive from the
+// SpdyIntrusiveLink<> base class:
+//
+//   struct Foo : public SpdyIntrusiveLink<Foo> {
+//     // ...
+//   }
+//
+//   SpdyIntrusiveList<Foo> l;
+//   l.push_back(new Foo);
+//   l.push_front(new Foo);
+//   l.erase(&l.front());
+//   l.erase(&l.back());
+//
+// Intrusive lists are primarily useful when you would have considered embedding
+// link pointers in your class directly for space or performance reasons. An
+// SpdyIntrusiveLink<> is the size of 2 pointers, usually 16 bytes on 64-bit
+// systems. Intrusive lists do not perform memory allocation (unlike the STL
+// list<> class) and thus may use less memory than list<>. In particular, if the
+// list elements are pointers to objects, using a list<> would perform an extra
+// memory allocation for each list node structure, while an SpdyIntrusiveList<>
+// would not.
+//
+// Note that SpdyIntrusiveLink is exempt from the C++ style guide's limitations
+// on multiple inheritance, so it's fine to inherit from both SpdyIntrusiveLink
+// and a base class, even if the base class is not a pure interface.
+//
+// Because the list pointers are embedded in the objects stored in an
+// SpdyIntrusiveList<>, erasing an item from a list is constant time. Consider
+// the following:
+//
+//   map<string,Foo> foo_map;
+//   list<Foo*> foo_list;
+//
+//   foo_list.push_back(&foo_map["bar"]);
+//   foo_list.erase(&foo_map["bar"]); // Compile error!
+//
+// The problem here is that a Foo* doesn't know where on foo_list it resides,
+// so removal requires iteration over the list. Various tricks can be performed
+// to overcome this. For example, a foo_list::iterator can be stored inside of
+// the Foo object. But at that point you'd be better off using an
+// SpdyIntrusiveList<>:
+//
+//   map<string,Foo> foo_map;
+//   SpdyIntrusiveList<Foo> foo_list;
+//
+//   foo_list.push_back(&foo_map["bar"]);
+//   foo_list.erase(&foo_map["bar"]); // Yeah!
+//
+// Note that SpdyIntrusiveLists come with a few limitations. The primary
+// limitation is that the SpdyIntrusiveLink<> base class is not copyable or
+// assignable. The result is that STL algorithms which mutate the order of
+// iterators, such as reverse() and unique(), will not work by default with
+// SpdyIntrusiveLists. In order to allow these algorithms to work you'll need to
+// define swap() and/or operator= for your class.
+//
+// Another limitation is that the SpdyIntrusiveList<> structure itself is not
+// copyable or assignable since an item/link combination can only exist on one
+// SpdyIntrusiveList<> at a time. This limitation is a result of the link
+// pointers for an item being intrusive in the item itself. For example, the
+// following will not compile:
+//
+//   FooList a;
+//   FooList b(a); // no copy constructor
+//   b = a;        // no assignment operator
+//
+// The similar STL code does work since the link pointers are external to the
+// item:
+//
+//   list<int*> a;
+//   a.push_back(new int);
+//   list<int*> b(a);
+//   CHECK(a.front() == b.front());
+//
+// Note that SpdyIntrusiveList::size() runs in O(N) time.
+
+#include <stddef.h>
+#include <iterator>
+
+
+namespace spdy {
+
+template <typename T, typename ListID> class SpdyIntrusiveList;
+
+template <typename T, typename ListID = void> class SpdyIntrusiveLink {
+ protected:
+  // We declare the constructor protected so that only derived types and the
+  // befriended list can construct this.
+  SpdyIntrusiveLink() : next_(nullptr), prev_(nullptr) {}
+
+#ifndef SWIG
+  SpdyIntrusiveLink(const SpdyIntrusiveLink&) = delete;
+  SpdyIntrusiveLink& operator=(const SpdyIntrusiveLink&) = delete;
+#endif  // SWIG
+
+ private:
+  // We befriend the matching list type so that it can manipulate the links
+  // while they are kept private from others.
+  friend class SpdyIntrusiveList<T, ListID>;
+
+  // Encapsulates the logic to convert from a link to its derived type.
+  T* cast_to_derived() { return static_cast<T*>(this); }
+  const T* cast_to_derived() const { return static_cast<const T*>(this); }
+
+  SpdyIntrusiveLink* next_;
+  SpdyIntrusiveLink* prev_;
+};
+
+template <typename T, typename ListID = void> class SpdyIntrusiveList {
+  template <typename QualifiedT, typename QualifiedLinkT> class iterator_impl;
+
+ public:
+  typedef T value_type;
+  typedef value_type *pointer;
+  typedef const value_type *const_pointer;
+  typedef value_type &reference;
+  typedef const value_type &const_reference;
+  typedef size_t size_type;
+  typedef ptrdiff_t difference_type;
+
+  typedef SpdyIntrusiveLink<T, ListID> link_type;
+  typedef iterator_impl<T, link_type> iterator;
+  typedef iterator_impl<const T, const link_type> const_iterator;
+  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+  typedef std::reverse_iterator<iterator> reverse_iterator;
+
+  SpdyIntrusiveList() { clear(); }
+  // After the move constructor the moved-from list will be empty.
+  //
+  // NOTE: There is no move assign operator (for now).
+  // The reason is that at the moment 'clear()' does not unlink the nodes.
+  // It makes is_linked() return true when it should return false.
+  // If such node is removed from the list (e.g. from its destructor), or is
+  // added to another list - a memory corruption will occur.
+  // Admitedly the destructor does not unlink the nodes either, but move-assign
+  // will likely make the problem more prominent.
+#ifndef SWIG
+  SpdyIntrusiveList(SpdyIntrusiveList&& src) noexcept {
+    clear();
+    if (src.empty()) return;
+    sentinel_link_.next_ = src.sentinel_link_.next_;
+    sentinel_link_.prev_ = src.sentinel_link_.prev_;
+    // Fix head and tail nodes of the list.
+    sentinel_link_.prev_->next_ = &sentinel_link_;
+    sentinel_link_.next_->prev_ = &sentinel_link_;
+    src.clear();
+  }
+#endif  // SWIG
+
+  iterator begin() { return iterator(sentinel_link_.next_); }
+  const_iterator begin() const { return const_iterator(sentinel_link_.next_); }
+  iterator end() { return iterator(&sentinel_link_); }
+  const_iterator end() const { return const_iterator(&sentinel_link_); }
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+  const_reverse_iterator rbegin() const {
+    return const_reverse_iterator(end());
+  }
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+  const_reverse_iterator rend() const {
+    return const_reverse_iterator(begin());
+  }
+
+  bool empty() const { return (sentinel_link_.next_ == &sentinel_link_); }
+  // This runs in O(N) time.
+  size_type size() const { return std::distance(begin(), end()); }
+  size_type max_size() const { return size_type(-1); }
+
+  reference front() { return *begin(); }
+  const_reference front() const { return *begin(); }
+  reference back() { return *(--end()); }
+  const_reference back() const { return *(--end()); }
+
+  static iterator insert(iterator position, T *obj) {
+    return insert_link(position.link(), obj);
+  }
+  void push_front(T* obj) { insert(begin(), obj); }
+  void push_back(T* obj) { insert(end(), obj); }
+
+  static iterator erase(T* obj) {
+    link_type* obj_link = obj;
+    // Fix up the next and previous links for the previous and next objects.
+    obj_link->next_->prev_ = obj_link->prev_;
+    obj_link->prev_->next_ = obj_link->next_;
+    // Zero out the next and previous links for the removed item. This will
+    // cause any future attempt to remove the item from the list to cause a
+    // crash instead of possibly corrupting the list structure.
+    link_type* next_link = obj_link->next_;
+    obj_link->next_ = nullptr;
+    obj_link->prev_ = nullptr;
+    return iterator(next_link);
+  }
+
+  static iterator erase(iterator position) {
+    return erase(position.operator->());
+  }
+  void pop_front() { erase(begin()); }
+  void pop_back() { erase(--end()); }
+
+  // Check whether the given element is linked into some list. Note that this
+  // does *not* check whether it is linked into a particular list.
+  // Also, if clear() is used to clear the containing list, is_linked() will
+  // still return true even though obj is no longer in any list.
+  static bool is_linked(const T* obj) {
+    return obj->link_type::next_ != nullptr;
+  }
+
+  void clear() {
+    sentinel_link_.next_ = sentinel_link_.prev_ = &sentinel_link_;
+  }
+  void swap(SpdyIntrusiveList& x) {
+    SpdyIntrusiveList tmp;
+    tmp.splice(tmp.begin(), *this);
+    this->splice(this->begin(), x);
+    x.splice(x.begin(), tmp);
+  }
+
+  void splice(iterator pos, SpdyIntrusiveList& src) {
+    splice(pos, src.begin(), src.end());
+  }
+
+  void splice(iterator pos, iterator i) { splice(pos, i, std::next(i)); }
+
+  void splice(iterator pos, iterator first, iterator last) {
+    if (first == last) return;
+
+    link_type* const last_prev = last.link()->prev_;
+
+    // Remove from the source.
+    first.link()->prev_->next_ = last.operator->();
+    last.link()->prev_ = first.link()->prev_;
+
+    // Attach to the destination.
+    first.link()->prev_ = pos.link()->prev_;
+    pos.link()->prev_->next_ = first.operator->();
+    last_prev->next_ = pos.operator->();
+    pos.link()->prev_ = last_prev;
+  }
+
+ private:
+  static iterator insert_link(link_type* next_link, T* obj) {
+    link_type* obj_link = obj;
+    obj_link->next_ = next_link;
+    link_type* const initial_next_prev = next_link->prev_;
+    obj_link->prev_ = initial_next_prev;
+    initial_next_prev->next_ = obj_link;
+    next_link->prev_ = obj_link;
+    return iterator(obj_link);
+  }
+
+  // The iterator implementation is parameterized on a potentially qualified
+  // variant of T and the matching qualified link type. Essentially, QualifiedT
+  // will either be 'T' or 'const T', the latter for a const_iterator.
+  template <typename QualifiedT, typename QualifiedLinkT>
+  class iterator_impl : public std::iterator<std::bidirectional_iterator_tag,
+                                             QualifiedT> {
+   public:
+    typedef std::iterator<std::bidirectional_iterator_tag, QualifiedT> base;
+
+    iterator_impl() : link_(nullptr) {}
+    iterator_impl(QualifiedLinkT* link) : link_(link) {}
+    iterator_impl(const iterator_impl& x) : link_(x.link_) {}
+
+    // Allow converting and comparing across iterators where the pointer
+    // assignment and comparisons (respectively) are allowed.
+    template <typename U, typename V>
+    iterator_impl(const iterator_impl<U, V>& x) : link_(x.link_) {}
+    template <typename U, typename V>
+    bool operator==(const iterator_impl<U, V>& x) const {
+      return link_ == x.link_;
+    }
+    template <typename U, typename V>
+    bool operator!=(const iterator_impl<U, V>& x) const {
+      return link_ != x.link_;
+    }
+
+    typename base::reference operator*() const { return *operator->(); }
+    typename base::pointer operator->() const {
+      return link_->cast_to_derived();
+    }
+
+    QualifiedLinkT *link() const { return link_; }
+
+#ifndef SWIG  // SWIG can't wrap these operator overloads.
+    iterator_impl& operator++() { link_ = link_->next_; return *this; }
+    iterator_impl operator++(int /*unused*/) {
+      iterator_impl tmp = *this;
+      ++*this;
+      return tmp;
+    }
+    iterator_impl& operator--() { link_ = link_->prev_; return *this; }
+    iterator_impl operator--(int /*unused*/) {
+      iterator_impl tmp = *this;
+      --*this;
+      return tmp;
+    }
+#endif  // SWIG
+
+   private:
+    // Ensure iterators can access other iterators node directly.
+    template <typename U, typename V> friend class iterator_impl;
+
+    QualifiedLinkT* link_;
+  };
+
+  // This bare link acts as the sentinel node.
+  link_type sentinel_link_;
+
+  // These are private and undefined to prevent copying and assigning.
+  SpdyIntrusiveList(const SpdyIntrusiveList&);
+  void operator=(const SpdyIntrusiveList&);
+};
+
+}  // namespace spdy
+
+#endif  // QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_
diff --git a/spdy/core/spdy_intrusive_list_test.cc b/spdy/core/spdy_intrusive_list_test.cc
new file mode 100644
index 0000000..eee65e3
--- /dev/null
+++ b/spdy/core/spdy_intrusive_list_test.cc
@@ -0,0 +1,427 @@
+// 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.
+
+#include "net/third_party/quiche/src/spdy/core/spdy_intrusive_list.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <list>
+#include <utility>
+
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_test.h"
+
+namespace spdy {
+namespace test {
+
+struct ListId2 {};
+
+struct TestItem : public SpdyIntrusiveLink<TestItem>,
+                  public SpdyIntrusiveLink<TestItem, ListId2> {
+  int n;
+};
+typedef SpdyIntrusiveList<TestItem> TestList;
+typedef std::list<TestItem*> CanonicalList;
+
+void swap(TestItem &a, TestItem &b) {
+  using std::swap;
+  swap(a.n, b.n);
+}
+
+class IntrusiveListTest : public ::testing::Test {
+ protected:
+  void CheckLists() {
+    CheckLists(l1, ll1);
+    if (::testing::Test::HasFailure()) return;
+    CheckLists(l2, ll2);
+  }
+
+  void CheckLists(const TestList &list_a, const CanonicalList &list_b) {
+    ASSERT_EQ(list_a.size(), list_b.size());
+    TestList::const_iterator it_a = list_a.begin();
+    CanonicalList::const_iterator it_b = list_b.begin();
+    while (it_a != list_a.end()) {
+      EXPECT_EQ(&*it_a++, *it_b++);
+    }
+    EXPECT_EQ(list_a.end(), it_a);
+    EXPECT_EQ(list_b.end(), it_b);
+  }
+
+  void PrepareLists(int num_elems_1, int num_elems_2 = 0) {
+    FillLists(&l1, &ll1, e, num_elems_1);
+    FillLists(&l2, &ll2, e + num_elems_1, num_elems_2);
+  }
+
+  void FillLists(TestList *list_a, CanonicalList *list_b, TestItem *elems,
+                 int num_elems) {
+    list_a->clear();
+    list_b->clear();
+    for (int i = 0; i < num_elems; ++i) {
+      list_a->push_back(elems + i);
+      list_b->push_back(elems + i);
+    }
+    CheckLists(*list_a, *list_b);
+  }
+
+  TestItem e[10];
+  TestList l1, l2;
+  CanonicalList ll1, ll2;
+};
+
+TEST(NewIntrusiveListTest, Basic) {
+  TestList list1;
+
+  CHECK_EQ(sizeof(SpdyIntrusiveLink<TestItem>), sizeof(void *) * 2);
+
+  for (int i = 0; i < 10; ++i) {
+    TestItem *e = new TestItem;
+    e->n = i;
+    list1.push_front(e);
+  }
+  CHECK_EQ(list1.size(), 10);
+
+  // Verify we can reverse a list because we defined swap for TestItem.
+  std::reverse(list1.begin(), list1.end());
+  CHECK_EQ(list1.size(), 10);
+
+  // Check both const and non-const forward iteration.
+  const TestList& clist1 = list1;
+  int i = 0;
+  TestList::iterator iter = list1.begin();
+  for (;
+       iter != list1.end();
+       ++iter, ++i) {
+    CHECK_EQ(iter->n, i);
+  }
+  CHECK(iter == clist1.end());
+  CHECK(iter != clist1.begin());
+  i = 0;
+  iter = list1.begin();
+  for (;
+       iter != list1.end();
+       ++iter, ++i) {
+    CHECK_EQ(iter->n, i);
+  }
+  CHECK(iter == clist1.end());
+  CHECK(iter != clist1.begin());
+
+  CHECK_EQ(list1.front().n, 0);
+  CHECK_EQ(list1.back().n, 9);
+
+  // Verify we can swap 2 lists.
+  TestList list2;
+  list2.swap(list1);
+  CHECK_EQ(list1.size(), 0);
+  CHECK_EQ(list2.size(), 10);
+
+  // Check both const and non-const reverse iteration.
+  const TestList& clist2 = list2;
+  TestList::reverse_iterator riter = list2.rbegin();
+  i = 9;
+  for (;
+       riter != list2.rend();
+       ++riter, --i) {
+    CHECK_EQ(riter->n, i);
+  }
+  CHECK(riter == clist2.rend());
+  CHECK(riter != clist2.rbegin());
+
+  riter = list2.rbegin();
+  i = 9;
+  for (;
+       riter != list2.rend();
+       ++riter, --i) {
+    CHECK_EQ(riter->n, i);
+  }
+  CHECK(riter == clist2.rend());
+  CHECK(riter != clist2.rbegin());
+
+  while (!list2.empty()) {
+    TestItem *e = &list2.front();
+    list2.pop_front();
+    delete e;
+  }
+}
+
+TEST(NewIntrusiveListTest, Erase) {
+  TestList l;
+  TestItem *e[10];
+
+  // Create a list with 10 items.
+  for (int i = 0; i < 10; ++i) {
+    e[i] = new TestItem;
+    l.push_front(e[i]);
+  }
+
+  // Test that erase works.
+  for (int i = 0; i < 10; ++i) {
+    CHECK_EQ(l.size(), (10 - i));
+
+    TestList::iterator iter = l.erase(e[i]);
+    CHECK(iter != TestList::iterator(e[i]));
+
+    CHECK_EQ(l.size(), (10 - i - 1));
+    delete e[i];
+  }
+}
+
+TEST(NewIntrusiveListTest, Insert) {
+  TestList l;
+  TestList::iterator iter = l.end();
+  TestItem *e[10];
+
+  // Create a list with 10 items.
+  for (int i = 9; i >= 0; --i) {
+    e[i] = new TestItem;
+    iter = l.insert(iter, e[i]);
+    CHECK_EQ(&(*iter), e[i]);
+  }
+
+  CHECK_EQ(l.size(), 10);
+
+  // Verify insertion order.
+  iter = l.begin();
+  for (TestItem *item : e) {
+    CHECK_EQ(&(*iter), item);
+    iter = l.erase(item);
+    delete item;
+  }
+}
+
+TEST(NewIntrusiveListTest, Move) {
+  // Move contructible.
+
+  {  // Move-construct from an empty list.
+    TestList src;
+    TestList dest(std::move(src));
+    EXPECT_TRUE(dest.empty());
+  }
+
+  {  // Move-construct from a single item list.
+    TestItem e;
+    TestList src;
+    src.push_front(&e);
+
+    TestList dest(std::move(src));
+    EXPECT_TRUE(src.empty());  // NOLINT bugprone-use-after-move
+    ASSERT_THAT(dest.size(), 1);
+    EXPECT_THAT(&dest.front(), &e);
+    EXPECT_THAT(&dest.back(), &e);
+  }
+
+  {  // Move-construct from a list with multiple items.
+    TestItem items[10];
+    TestList src;
+    for (TestItem &e : items) src.push_back(&e);
+
+    TestList dest(std::move(src));
+    EXPECT_TRUE(src.empty());  // NOLINT bugprone-use-after-move
+    // Verify the items on the destination list.
+    ASSERT_THAT(dest.size(), 10);
+    int i = 0;
+    for (TestItem &e : dest) {
+      EXPECT_THAT(&e, &items[i++]) << " for index " << i;
+    }
+  }
+}
+
+TEST(NewIntrusiveListTest, StaticInsertErase) {
+  TestList l;
+  TestItem e[2];
+  TestList::iterator i = l.begin();
+  TestList::insert(i, &e[0]);
+  TestList::insert(&e[0], &e[1]);
+  TestList::erase(&e[0]);
+  TestList::erase(TestList::iterator(&e[1]));
+  EXPECT_TRUE(l.empty());
+}
+
+TEST_F(IntrusiveListTest, Splice) {
+  // We verify that the contents of this secondary list aren't affected by any
+  // of the splices.
+  SpdyIntrusiveList<TestItem, ListId2> secondary_list;
+  for (int i  = 0; i < 3; ++i) {
+    secondary_list.push_back(&e[i]);
+  }
+
+  // Test the basic cases:
+  // - The lists range from 0 to 2 elements.
+  // - The insertion point ranges from begin() to end()
+  // - The transfered range has multiple sizes and locations in the source.
+  for (int l1_count = 0; l1_count < 3; ++l1_count) {
+    for (int l2_count = 0; l2_count < 3; ++l2_count) {
+      for (int pos = 0; pos <= l1_count; ++pos) {
+        for (int first = 0; first <= l2_count; ++first) {
+          for (int last = first; last <= l2_count; ++last) {
+            PrepareLists(l1_count, l2_count);
+
+            l1.splice(std::next(l1.begin(), pos), std::next(l2.begin(), first),
+                      std::next(l2.begin(), last));
+            ll1.splice(std::next(ll1.begin(), pos), ll2,
+                       std::next(ll2.begin(), first),
+                       std::next(ll2.begin(), last));
+
+            CheckLists();
+
+            ASSERT_EQ(3, secondary_list.size());
+            for (int i = 0; i < 3; ++i) {
+              EXPECT_EQ(&e[i], &*std::next(secondary_list.begin(), i));
+            }
+          }
+        }
+      }
+    }
+  }
+}
+
+// Build up a set of classes which form "challenging" type hierarchies to use
+// with an SpdyIntrusiveList.
+struct BaseLinkId {};
+struct DerivedLinkId {};
+
+struct AbstractBase : public SpdyIntrusiveLink<AbstractBase, BaseLinkId> {
+  virtual ~AbstractBase() = 0;
+  virtual SpdyString name() { return "AbstractBase"; }
+};
+AbstractBase::~AbstractBase() {}
+struct DerivedClass : public SpdyIntrusiveLink<DerivedClass, DerivedLinkId>,
+                      public AbstractBase {
+  virtual ~DerivedClass() {}
+  virtual SpdyString name() { return "DerivedClass"; }
+};
+struct VirtuallyDerivedBaseClass : public virtual AbstractBase {
+  virtual ~VirtuallyDerivedBaseClass() = 0;
+  virtual SpdyString name() { return "VirtuallyDerivedBaseClass"; }
+};
+VirtuallyDerivedBaseClass::~VirtuallyDerivedBaseClass() {}
+struct VirtuallyDerivedClassA
+    : public SpdyIntrusiveLink<VirtuallyDerivedClassA, DerivedLinkId>,
+      public virtual VirtuallyDerivedBaseClass {
+  virtual ~VirtuallyDerivedClassA() {}
+  virtual SpdyString name() { return "VirtuallyDerivedClassA"; }
+};
+struct NonceClass {
+  virtual ~NonceClass() {}
+  int data_;
+};
+struct VirtuallyDerivedClassB
+    : public SpdyIntrusiveLink<VirtuallyDerivedClassB, DerivedLinkId>,
+      public virtual NonceClass,
+      public virtual VirtuallyDerivedBaseClass {
+  virtual ~VirtuallyDerivedClassB() {}
+  virtual SpdyString name() { return "VirtuallyDerivedClassB"; }
+};
+struct VirtuallyDerivedClassC
+    : public SpdyIntrusiveLink<VirtuallyDerivedClassC, DerivedLinkId>,
+      public virtual AbstractBase,
+      public virtual NonceClass,
+      public virtual VirtuallyDerivedBaseClass {
+  virtual ~VirtuallyDerivedClassC() {}
+  virtual SpdyString name() { return "VirtuallyDerivedClassC"; }
+};
+
+// Test for multiple layers between the element type and the link.
+namespace templated_base_link {
+template <typename T> struct AbstractBase : public SpdyIntrusiveLink<T> {
+  virtual ~AbstractBase() = 0;
+};
+template <typename T> AbstractBase<T>::~AbstractBase() {}
+struct DerivedClass : public AbstractBase<DerivedClass> {
+  int n;
+};
+}
+
+TEST(NewIntrusiveListTest, HandleInheritanceHierarchies) {
+  {
+    SpdyIntrusiveList<DerivedClass, DerivedLinkId> list;
+    DerivedClass elements[2];
+    EXPECT_TRUE(list.empty());
+    list.push_back(&elements[0]);
+    EXPECT_EQ(1, list.size());
+    list.push_back(&elements[1]);
+    EXPECT_EQ(2, list.size());
+    list.pop_back();
+    EXPECT_EQ(1, list.size());
+    list.pop_back();
+    EXPECT_TRUE(list.empty());
+  }
+  {
+    SpdyIntrusiveList<VirtuallyDerivedClassA, DerivedLinkId> list;
+    VirtuallyDerivedClassA elements[2];
+    EXPECT_TRUE(list.empty());
+    list.push_back(&elements[0]);
+    EXPECT_EQ(1, list.size());
+    list.push_back(&elements[1]);
+    EXPECT_EQ(2, list.size());
+    list.pop_back();
+    EXPECT_EQ(1, list.size());
+    list.pop_back();
+    EXPECT_TRUE(list.empty());
+  }
+  {
+    SpdyIntrusiveList<VirtuallyDerivedClassC, DerivedLinkId> list;
+    VirtuallyDerivedClassC elements[2];
+    EXPECT_TRUE(list.empty());
+    list.push_back(&elements[0]);
+    EXPECT_EQ(1, list.size());
+    list.push_back(&elements[1]);
+    EXPECT_EQ(2, list.size());
+    list.pop_back();
+    EXPECT_EQ(1, list.size());
+    list.pop_back();
+    EXPECT_TRUE(list.empty());
+  }
+  {
+    SpdyIntrusiveList<AbstractBase, BaseLinkId> list;
+    DerivedClass d1;
+    VirtuallyDerivedClassA d2;
+    VirtuallyDerivedClassB d3;
+    VirtuallyDerivedClassC d4;
+    EXPECT_TRUE(list.empty());
+    list.push_back(&d1);
+    EXPECT_EQ(1, list.size());
+    list.push_back(&d2);
+    EXPECT_EQ(2, list.size());
+    list.push_back(&d3);
+    EXPECT_EQ(3, list.size());
+    list.push_back(&d4);
+    EXPECT_EQ(4, list.size());
+    SpdyIntrusiveList<AbstractBase, BaseLinkId>::iterator it = list.begin();
+    EXPECT_EQ("DerivedClass",           (it++)->name());
+    EXPECT_EQ("VirtuallyDerivedClassA", (it++)->name());
+    EXPECT_EQ("VirtuallyDerivedClassB", (it++)->name());
+    EXPECT_EQ("VirtuallyDerivedClassC", (it++)->name());
+  }
+  {
+    SpdyIntrusiveList<templated_base_link::DerivedClass> list;
+    templated_base_link::DerivedClass elements[2];
+    EXPECT_TRUE(list.empty());
+    list.push_back(&elements[0]);
+    EXPECT_EQ(1, list.size());
+    list.push_back(&elements[1]);
+    EXPECT_EQ(2, list.size());
+    list.pop_back();
+    EXPECT_EQ(1, list.size());
+    list.pop_back();
+    EXPECT_TRUE(list.empty());
+  }
+}
+
+
+class IntrusiveListTagTypeTest : public testing::Test {
+ protected:
+  struct Tag {};
+  class Element : public SpdyIntrusiveLink<Element, Tag> {};
+};
+
+TEST_F(IntrusiveListTagTypeTest, TagTypeListID) {
+  SpdyIntrusiveList<Element, Tag> list;
+  {
+    Element e;
+    list.push_back(&e);
+  }
+}
+
+}  // namespace test
+}  // namespace spdy
diff --git a/spdy/platform/api/spdy_containers.h b/spdy/platform/api/spdy_containers.h
index e4f4c49..9a90556 100644
--- a/spdy/platform/api/spdy_containers.h
+++ b/spdy/platform/api/spdy_containers.h
@@ -37,6 +37,12 @@
   return SpdyHashStringPairImpl(a, b);
 }
 
+// Used for maps that are typically small, then it is faster than (for example)
+// hash_map which is optimized for large data sets. SpdySmallMap upgrades itself
+// automatically to a SpdySmallMapImpl-specified map when it runs out of space.
+template <typename Key, typename Value, int Size>
+using SpdySmallMap = SpdySmallMapImpl<Key, Value, Size>;
+
 }  // namespace spdy
 
 #endif  // QUICHE_SPDY_PLATFORM_API_SPDY_CONTAINERS_H_
diff --git a/spdy/platform/api/spdy_map_util.h b/spdy/platform/api/spdy_map_util.h
new file mode 100644
index 0000000..e9b5f85
--- /dev/null
+++ b/spdy/platform/api/spdy_map_util.h
@@ -0,0 +1,19 @@
+// 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.
+
+#ifndef QUICHE_SPDY_PLATFORM_API_SPDY_MAP_UTIL_H_
+#define QUICHE_SPDY_PLATFORM_API_SPDY_MAP_UTIL_H_
+
+#include "net/spdy/platform/impl/spdy_map_util_impl.h"
+
+namespace spdy {
+
+template <class Collection, class Key>
+bool SpdyContainsKey(const Collection& collection, const Key& key) {
+  return SpdyContainsKeyImpl(collection, key);
+}
+
+}  // namespace spdy
+
+#endif  // QUICHE_SPDY_PLATFORM_API_SPDY_MAP_UTIL_H_