OLD | NEW |
1 // Copyright 2013 The Chromium Authors. All rights reserved. | 1 // Copyright 2013 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef NET_SPDY_WRITE_BLOCKED_LIST_H_ | 5 #ifndef NET_SPDY_WRITE_BLOCKED_LIST_H_ |
6 #define NET_SPDY_WRITE_BLOCKED_LIST_H_ | 6 #define NET_SPDY_WRITE_BLOCKED_LIST_H_ |
7 | 7 |
8 #include <algorithm> | 8 #include <algorithm> |
9 #include <deque> | 9 #include <deque> |
10 | 10 |
(...skipping 10 matching lines...) Expand all Loading... |
21 const int kHighestPriority = 0; | 21 const int kHighestPriority = 0; |
22 const int kLowestPriority = 7; | 22 const int kLowestPriority = 7; |
23 | 23 |
24 template <typename IdType> | 24 template <typename IdType> |
25 class WriteBlockedList { | 25 class WriteBlockedList { |
26 public: | 26 public: |
27 // 0(1) size lookup. 0(1) insert at front or back. | 27 // 0(1) size lookup. 0(1) insert at front or back. |
28 typedef std::deque<IdType> BlockedList; | 28 typedef std::deque<IdType> BlockedList; |
29 typedef typename BlockedList::iterator iterator; | 29 typedef typename BlockedList::iterator iterator; |
30 | 30 |
31 explicit WriteBlockedList(bool use_stream_to_priority_map) | 31 WriteBlockedList() {} |
32 : use_stream_to_priority_(use_stream_to_priority_map) {} | |
33 | 32 |
34 static SpdyPriority ClampPriority(SpdyPriority priority) { | 33 static SpdyPriority ClampPriority(SpdyPriority priority) { |
35 if (priority < kHighestPriority) { | 34 if (priority < kHighestPriority) { |
36 LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority); | 35 LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority); |
37 return kHighestPriority; | 36 return kHighestPriority; |
38 } | 37 } |
39 if (priority > kLowestPriority) { | 38 if (priority > kLowestPriority) { |
40 LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority); | 39 LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority); |
41 return kLowestPriority; | 40 return kLowestPriority; |
42 } | 41 } |
43 return priority; | 42 return priority; |
44 } | 43 } |
45 | 44 |
46 // Returns the priority of the highest priority list with sessions on it. | 45 // Returns the priority of the highest priority list with sessions on it. |
47 SpdyPriority GetHighestPriorityWriteBlockedList() const { | 46 SpdyPriority GetHighestPriorityWriteBlockedList() const { |
48 for (SpdyPriority i = 0; i <= kLowestPriority; ++i) { | 47 for (SpdyPriority i = 0; i <= kLowestPriority; ++i) { |
49 if (write_blocked_lists_[i].size() > 0) | 48 if (write_blocked_lists_[i].size() > 0) |
50 return i; | 49 return i; |
51 } | 50 } |
52 LOG(DFATAL) << "No blocked streams"; | 51 LOG(DFATAL) << "No blocked streams"; |
53 return kHighestPriority; | 52 return kHighestPriority; |
54 } | 53 } |
55 | 54 |
56 IdType PopFront(SpdyPriority priority) { | 55 IdType PopFront(SpdyPriority priority) { |
57 priority = ClampPriority(priority); | 56 priority = ClampPriority(priority); |
58 DCHECK(!write_blocked_lists_[priority].empty()); | 57 DCHECK(!write_blocked_lists_[priority].empty()); |
59 IdType stream_id = write_blocked_lists_[priority].front(); | 58 IdType stream_id = write_blocked_lists_[priority].front(); |
60 write_blocked_lists_[priority].pop_front(); | 59 write_blocked_lists_[priority].pop_front(); |
61 if (use_stream_to_priority_) { | 60 stream_to_priority_.erase(stream_id); |
62 stream_to_priority_.erase(stream_id); | |
63 } | |
64 return stream_id; | 61 return stream_id; |
65 } | 62 } |
66 | 63 |
67 bool HasWriteBlockedStreamsGreaterThanPriority(SpdyPriority priority) const { | 64 bool HasWriteBlockedStreamsGreaterThanPriority(SpdyPriority priority) const { |
68 priority = ClampPriority(priority); | 65 priority = ClampPriority(priority); |
69 for (SpdyPriority i = kHighestPriority; i < priority; ++i) { | 66 for (SpdyPriority i = kHighestPriority; i < priority; ++i) { |
70 if (!write_blocked_lists_[i].empty()) { | 67 if (!write_blocked_lists_[i].empty()) { |
71 return true; | 68 return true; |
72 } | 69 } |
73 } | 70 } |
74 return false; | 71 return false; |
75 } | 72 } |
76 | 73 |
77 bool HasWriteBlockedStreams() const { | 74 bool HasWriteBlockedStreams() const { |
78 for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) { | 75 for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) { |
79 if (!write_blocked_lists_[i].empty()) { | 76 if (!write_blocked_lists_[i].empty()) { |
80 return true; | 77 return true; |
81 } | 78 } |
82 } | 79 } |
83 return false; | 80 return false; |
84 } | 81 } |
85 | 82 |
86 void PushBack(IdType stream_id, SpdyPriority priority) { | 83 void PushBack(IdType stream_id, SpdyPriority priority) { |
87 priority = ClampPriority(priority); | 84 priority = ClampPriority(priority); |
88 DVLOG(2) << "Adding stream " << stream_id << " at priority " | 85 DVLOG(2) << "Adding stream " << stream_id << " at priority " |
89 << static_cast<int>(priority); | 86 << static_cast<int>(priority); |
90 bool should_insert_stream = true; | 87 bool should_insert_stream = true; |
91 if (use_stream_to_priority_) { | 88 typename StreamToPriorityMap::iterator iter = |
92 typename StreamToPriorityMap::iterator iter = | 89 stream_to_priority_.find(stream_id); |
93 stream_to_priority_.find(stream_id); | 90 if (iter != stream_to_priority_.end()) { |
94 if (iter != stream_to_priority_.end()) { | 91 DVLOG(1) << "Stream " << stream_id << " already in write blocked list."; |
95 DVLOG(1) << "Stream " << stream_id << " already in write blocked list."; | 92 if (iter->second == priority) { |
96 if (iter->second == priority) { | 93 // The stream is already in the write blocked list for the priority. |
97 // The stream is already in the write blocked list for the priority. | 94 should_insert_stream = false; |
98 should_insert_stream = false; | 95 } else { |
99 } else { | 96 // The stream is in a write blocked list for a different priority. |
100 // The stream is in a write blocked list for a different priority. | 97 bool removed = |
101 bool removed = | 98 RemoveStreamFromWriteBlockedList(stream_id, iter->second); |
102 RemoveStreamFromWriteBlockedList(stream_id, iter->second); | 99 DCHECK(removed); |
103 DCHECK(removed); | |
104 } | |
105 } | 100 } |
106 if (should_insert_stream) { | 101 } |
107 stream_to_priority_[stream_id] = priority; | 102 if (should_insert_stream) { |
108 write_blocked_lists_[priority].push_back(stream_id); | 103 stream_to_priority_[stream_id] = priority; |
109 } | |
110 } else { | |
111 write_blocked_lists_[priority].push_back(stream_id); | 104 write_blocked_lists_[priority].push_back(stream_id); |
112 } | 105 } |
113 } | 106 } |
114 | 107 |
115 bool RemoveStreamFromWriteBlockedList(IdType stream_id, | 108 bool RemoveStreamFromWriteBlockedList(IdType stream_id, |
116 SpdyPriority priority) { | 109 SpdyPriority priority) { |
117 if (use_stream_to_priority_) { | 110 typename StreamToPriorityMap::iterator iter = |
118 typename StreamToPriorityMap::iterator iter = | 111 stream_to_priority_.find(stream_id); |
119 stream_to_priority_.find(stream_id); | 112 if (iter == stream_to_priority_.end()) { |
120 if (iter == stream_to_priority_.end()) { | 113 // The stream is not present in the write blocked list. |
121 // The stream is not present in the write blocked list. | 114 return false; |
122 return false; | 115 } else if (iter->second == priority) { |
123 } else if (iter->second == priority) { | 116 stream_to_priority_.erase(iter); |
124 stream_to_priority_.erase(iter); | 117 } else { |
125 } else { | 118 // The stream is not present at the specified priority level. |
126 // The stream is not present at the specified priority level. | 119 return false; |
127 return false; | |
128 } | |
129 } | 120 } |
130 // We shouldn't really add a stream_id to a list multiple times, | 121 // We shouldn't really add a stream_id to a list multiple times, |
131 // but under some conditions it does happen. Doing a check in PushBack | 122 // but under some conditions it does happen. Doing a check in PushBack |
132 // would be too costly, so instead we check here to eliminate duplicates. | 123 // would be too costly, so instead we check here to eliminate duplicates. |
133 bool found = false; | 124 bool found = false; |
134 iterator it = std::find(write_blocked_lists_[priority].begin(), | 125 iterator it = std::find(write_blocked_lists_[priority].begin(), |
135 write_blocked_lists_[priority].end(), stream_id); | 126 write_blocked_lists_[priority].end(), stream_id); |
136 while (it != write_blocked_lists_[priority].end()) { | 127 while (it != write_blocked_lists_[priority].end()) { |
137 found = true; | 128 found = true; |
138 iterator next_it = write_blocked_lists_[priority].erase(it); | 129 iterator next_it = write_blocked_lists_[priority].erase(it); |
(...skipping 15 matching lines...) Expand all Loading... |
154 } | 145 } |
155 | 146 |
156 size_t NumBlockedStreams() const { | 147 size_t NumBlockedStreams() const { |
157 size_t num_blocked_streams = 0; | 148 size_t num_blocked_streams = 0; |
158 for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) { | 149 for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) { |
159 num_blocked_streams += write_blocked_lists_[i].size(); | 150 num_blocked_streams += write_blocked_lists_[i].size(); |
160 } | 151 } |
161 return num_blocked_streams; | 152 return num_blocked_streams; |
162 } | 153 } |
163 | 154 |
164 bool avoids_inserting_duplicates() const { return use_stream_to_priority_; } | |
165 | |
166 private: | 155 private: |
167 friend class net::test::WriteBlockedListPeer; | 156 friend class net::test::WriteBlockedListPeer; |
168 | 157 |
169 typedef base::hash_map<IdType, SpdyPriority> StreamToPriorityMap; | 158 typedef base::hash_map<IdType, SpdyPriority> StreamToPriorityMap; |
170 | 159 |
171 BlockedList write_blocked_lists_[kLowestPriority + 1]; | 160 BlockedList write_blocked_lists_[kLowestPriority + 1]; |
172 StreamToPriorityMap stream_to_priority_; | 161 StreamToPriorityMap stream_to_priority_; |
173 bool use_stream_to_priority_; | |
174 }; | 162 }; |
175 | 163 |
176 } // namespace net | 164 } // namespace net |
177 | 165 |
178 #endif // NET_SPDY_WRITE_BLOCKED_LIST_H_ | 166 #endif // NET_SPDY_WRITE_BLOCKED_LIST_H_ |
OLD | NEW |