gfe-relnote: Move Http2PriorityWriteScheduler from gfe/gfe2/spdy/ to third_party/spdy/core/ to allow QUIC to use it. No functional change expected, not flag protected.
Also copy gtl::intrusive_list as SpdyIntrusiveList.
PiperOrigin-RevId: 259535206
Change-Id: Ie600cc4a403ac90a6302824f98bc5e7fd86fca25
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_
