13551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// Copyright 2013 The Chromium Authors. All rights reserved. 23551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 33551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// found in the LICENSE file. 43551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 53551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)#ifndef NET_SPDY_WRITE_BLOCKED_LIST_H_ 63551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)#define NET_SPDY_WRITE_BLOCKED_LIST_H_ 73551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 83551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)#include <algorithm> 93551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)#include <deque> 103551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 113551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)#include "base/logging.h" 12f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)#include "net/spdy/spdy_protocol.h" 133551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 143551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)namespace net { 153551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 163551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)const int kHighestPriority = 0; 173551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)const int kLowestPriority = 7; 183551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 193551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)template <typename IdType> 203551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)class WriteBlockedList { 213551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) public: 223551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // 0(1) size lookup. 0(1) insert at front or back. 233551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) typedef std::deque<IdType> BlockedList; 243551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) typedef typename BlockedList::iterator iterator; 253551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 26f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) static SpdyPriority ClampPriority(SpdyPriority priority) { 27f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (priority < kHighestPriority) { 28f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority); 29f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return kHighestPriority; 30f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 31f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (priority > kLowestPriority) { 32f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority); 33f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return kLowestPriority; 34f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 35f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return priority; 36f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 37f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 38f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // Returns the priority of the highest priority list with sessions on it. 39f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) SpdyPriority GetHighestPriorityWriteBlockedList() const { 40f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (SpdyPriority i = 0; i <= kLowestPriority; ++i) { 413551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (write_blocked_lists_[i].size() > 0) 423551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return i; 433551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 44f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) LOG(DFATAL) << "No blocked streams"; 45f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return kHighestPriority; 463551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 473551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 48f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) IdType PopFront(SpdyPriority priority) { 49f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) priority = ClampPriority(priority); 503551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) DCHECK(!write_blocked_lists_[priority].empty()); 513551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) IdType stream_id = write_blocked_lists_[priority].front(); 523551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) write_blocked_lists_[priority].pop_front(); 533551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return stream_id; 543551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 553551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 56f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) bool HasWriteBlockedStreamsGreaterThanPriority(SpdyPriority priority) const { 57f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) priority = ClampPriority(priority); 58f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (SpdyPriority i = kHighestPriority; i < priority; ++i) { 593551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (!write_blocked_lists_[i].empty()) { 603551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return true; 613551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 623551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 633551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return false; 643551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 653551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 663551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bool HasWriteBlockedStreams() const { 67f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) { 68f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (!write_blocked_lists_[i].empty()) { 69f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return true; 70f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 71f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 72f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return false; 733551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 743551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 75f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) void PushBack(IdType stream_id, SpdyPriority priority) { 76f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) write_blocked_lists_[ClampPriority(priority)].push_back(stream_id); 773551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 783551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 79f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) void RemoveStreamFromWriteBlockedList(IdType stream_id, 80f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) SpdyPriority priority) { 813551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) iterator it = std::find(write_blocked_lists_[priority].begin(), 823551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) write_blocked_lists_[priority].end(), 833551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) stream_id); 843551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) while (it != write_blocked_lists_[priority].end()) { 853551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) write_blocked_lists_[priority].erase(it); 863551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) it = std::find(write_blocked_lists_[priority].begin(), 873551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) write_blocked_lists_[priority].end(), 883551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) stream_id); 893551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 903551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 913551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 92f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) size_t NumBlockedStreams() const { 93f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) size_t num_blocked_streams = 0; 94f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) { 953551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) num_blocked_streams += write_blocked_lists_[i].size(); 963551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 973551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return num_blocked_streams; 983551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 993551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1003551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) private: 101f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) BlockedList write_blocked_lists_[kLowestPriority + 1]; 1023551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)}; 1033551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1043551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} // namespace net 1053551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1063551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)#endif // NET_SPDY_WRITE_BLOCKED_LIST_H_ 107