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