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 3 // found in the LICENSE file. 4 5 #ifndef NET_SPDY_WRITE_BLOCKED_LIST_H_ 6 #define NET_SPDY_WRITE_BLOCKED_LIST_H_ 7 8 #include <algorithm> 9 #include <deque> 10 11 #include "base/logging.h" 12 #include "net/spdy/spdy_protocol.h" 13 14 namespace net { 15 16 const int kHighestPriority = 0; 17 const int kLowestPriority = 7; 18 19 template <typename IdType> 20 class WriteBlockedList { 21 public: 22 // 0(1) size lookup. 0(1) insert at front or back. 23 typedef std::deque<IdType> BlockedList; 24 typedef typename BlockedList::iterator iterator; 25 ClampPriority(SpdyPriority priority)26 static SpdyPriority ClampPriority(SpdyPriority priority) { 27 if (priority < kHighestPriority) { 28 LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority); 29 return kHighestPriority; 30 } 31 if (priority > kLowestPriority) { 32 LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority); 33 return kLowestPriority; 34 } 35 return priority; 36 } 37 38 // Returns the priority of the highest priority list with sessions on it. GetHighestPriorityWriteBlockedList()39 SpdyPriority GetHighestPriorityWriteBlockedList() const { 40 for (SpdyPriority i = 0; i <= kLowestPriority; ++i) { 41 if (write_blocked_lists_[i].size() > 0) 42 return i; 43 } 44 LOG(DFATAL) << "No blocked streams"; 45 return kHighestPriority; 46 } 47 PopFront(SpdyPriority priority)48 IdType PopFront(SpdyPriority priority) { 49 priority = ClampPriority(priority); 50 DCHECK(!write_blocked_lists_[priority].empty()); 51 IdType stream_id = write_blocked_lists_[priority].front(); 52 write_blocked_lists_[priority].pop_front(); 53 return stream_id; 54 } 55 HasWriteBlockedStreamsGreaterThanPriority(SpdyPriority priority)56 bool HasWriteBlockedStreamsGreaterThanPriority(SpdyPriority priority) const { 57 priority = ClampPriority(priority); 58 for (SpdyPriority i = kHighestPriority; i < priority; ++i) { 59 if (!write_blocked_lists_[i].empty()) { 60 return true; 61 } 62 } 63 return false; 64 } 65 HasWriteBlockedStreams()66 bool HasWriteBlockedStreams() const { 67 for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) { 68 if (!write_blocked_lists_[i].empty()) { 69 return true; 70 } 71 } 72 return false; 73 } 74 PushBack(IdType stream_id,SpdyPriority priority)75 void PushBack(IdType stream_id, SpdyPriority priority) { 76 write_blocked_lists_[ClampPriority(priority)].push_back(stream_id); 77 } 78 RemoveStreamFromWriteBlockedList(IdType stream_id,SpdyPriority priority)79 void RemoveStreamFromWriteBlockedList(IdType stream_id, 80 SpdyPriority priority) { 81 iterator it = std::find(write_blocked_lists_[priority].begin(), 82 write_blocked_lists_[priority].end(), 83 stream_id); 84 while (it != write_blocked_lists_[priority].end()) { 85 write_blocked_lists_[priority].erase(it); 86 it = std::find(write_blocked_lists_[priority].begin(), 87 write_blocked_lists_[priority].end(), 88 stream_id); 89 } 90 } 91 NumBlockedStreams()92 size_t NumBlockedStreams() const { 93 size_t num_blocked_streams = 0; 94 for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) { 95 num_blocked_streams += write_blocked_lists_[i].size(); 96 } 97 return num_blocked_streams; 98 } 99 100 private: 101 BlockedList write_blocked_lists_[kLowestPriority + 1]; 102 }; 103 104 } // namespace net 105 106 #endif // NET_SPDY_WRITE_BLOCKED_LIST_H_ 107