http2_priority_dependencies.h 4.0 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
  1. // Copyright 2016 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef NET_SPDY_HTTP2_PRIORITY_DEPENDENCIES_H_
  5. #define NET_SPDY_HTTP2_PRIORITY_DEPENDENCIES_H_
  6. #include <list>
  7. #include <map>
  8. #include <utility>
  9. #include <vector>
  10. #include "net/base/net_export.h"
  11. #include "net/third_party/quiche/src/quiche/spdy/core/spdy_protocol.h"
  12. namespace net {
  13. // A helper class encapsulating the state and logic to set the priority fields
  14. // for HTTP/2 streams based on their spdy::SpdyPriority and the ordering of
  15. // creation and deletion of the streams. This implentation includes a gross hack
  16. // in which the HTTP/2 weight is set to a transformation of the
  17. // spdy::SpdyPriority value in order to support servers which do not honor
  18. // HTTP/2 stream dependencies and instead treat the weight value like a SPDY/3
  19. // priority.
  20. // TODO(rch): Eliminate this gross hack when servers no longer act like this.
  21. class NET_EXPORT_PRIVATE Http2PriorityDependencies {
  22. public:
  23. Http2PriorityDependencies();
  24. ~Http2PriorityDependencies();
  25. // Called when a stream is created. This is used for both client-initiated
  26. // and server-initiated (pushed) streams.
  27. // On return, |*parent_stream_id| is set to the stream id that should become
  28. // the parent of this stream, |*exclusive| is set to whether that dependency
  29. // should be exclusive, and |*weight| is set to the relative weight for the
  30. // created stream given this priority.
  31. void OnStreamCreation(spdy::SpdyStreamId id,
  32. spdy::SpdyPriority priority,
  33. spdy::SpdyStreamId* parent_stream_id,
  34. int* weight,
  35. bool* exclusive);
  36. // Called when a stream is destroyed.
  37. void OnStreamDestruction(spdy::SpdyStreamId id);
  38. struct DependencyUpdate {
  39. spdy::SpdyStreamId id;
  40. spdy::SpdyStreamId parent_stream_id;
  41. int weight;
  42. bool exclusive;
  43. };
  44. // Called when a stream's priority has changed. Returns a list of
  45. // dependency updates that should be sent to the server to describe
  46. // the requested priority change. The updates should be sent in the
  47. // given order.
  48. std::vector<DependencyUpdate> OnStreamUpdate(spdy::SpdyStreamId id,
  49. spdy::SpdyPriority new_priority);
  50. private:
  51. // The requirements for the internal data structure for this class are:
  52. // a) Constant time insertion of entries at the end of the list,
  53. // b) Fast removal of any entry based on its id.
  54. // c) Constant time lookup of the entry at the end of the list.
  55. // std::list would satisfy (a) & (c), but some form of map is
  56. // needed for (b). The priority must be included in the map
  57. // entries so that deletion can determine which list in id_priority_lists_
  58. // to erase from.
  59. using IdList = std::list<std::pair<spdy::SpdyStreamId, spdy::SpdyPriority>>;
  60. using EntryMap = std::map<spdy::SpdyStreamId, IdList::iterator>;
  61. IdList id_priority_lists_[spdy::kV3LowestPriority + 1];
  62. // Tracks the location of an id anywhere in the above vector of lists.
  63. // Iterators to list elements remain valid until those particular elements
  64. // are erased.
  65. EntryMap entry_by_stream_id_;
  66. // Finds the lowest-priority stream that has a priority >= |priority|.
  67. // Returns false if there are no such streams.
  68. // Otherwise, returns true and sets |*bound|.
  69. bool PriorityLowerBound(spdy::SpdyPriority priority, IdList::iterator* bound);
  70. // Finds the stream just above |id| in the total order.
  71. // Returns false if there are no streams with a higher priority.
  72. // Otherwise, returns true and sets |*parent|.
  73. bool ParentOfStream(spdy::SpdyStreamId id, IdList::iterator* parent);
  74. // Finds the stream just below |id| in the total order.
  75. // Returns false if there are no streams with a lower priority.
  76. // Otherwise, returns true and sets |*child|.
  77. bool ChildOfStream(spdy::SpdyStreamId id, IdList::iterator* child);
  78. };
  79. } // namespace net
  80. #endif // NET_SPDY_HTTP2_PRIORITY_DEPENDENCIES_H_