net/spdy/write_blocked_list.h

   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 {
  15 class WriteBlockedListPeer;
  16 }
  17
  18 namespace net {
  19
  20 const int kHighestPriority = 0;
  21 const int kLowestPriority = 7;
  22
  23 template <typename IdType>
  24 class WriteBlockedList {
  25  public:
  26   // 0(1) size lookup.  0(1) insert at front or back.
  27   typedef std::deque<IdType> BlockedList;
  28   typedef typename BlockedList::iterator iterator;
  29
  30   static SpdyPriority ClampPriority(SpdyPriority priority) {
  31     if (priority < kHighestPriority) {
  32       LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority);
  33       return kHighestPriority;
  34     }
  35     if (priority > kLowestPriority) {
  36       LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority);
  37       return kLowestPriority;
  38     }
  39     return priority;
  40   }
  41
  42   // Returns the priority of the highest priority list with sessions on it.
  43   SpdyPriority GetHighestPriorityWriteBlockedList() const {
  44     for (SpdyPriority i = 0; i <= kLowestPriority; ++i) {
  45       if (write_blocked_lists_[i].size() > 0)
  46         return i;
  47     }
  48     LOG(DFATAL) << "No blocked streams";
  49     return kHighestPriority;
  50   }
  51
  52   IdType PopFront(SpdyPriority priority) {
  53     priority = ClampPriority(priority);
  54     DCHECK(!write_blocked_lists_[priority].empty());
  55     IdType stream_id = write_blocked_lists_[priority].front();
  56     write_blocked_lists_[priority].pop_front();
  57     return stream_id;
  58   }
  59
  60   bool HasWriteBlockedStreamsGreaterThanPriority(SpdyPriority priority) const {
  61     priority = ClampPriority(priority);
  62     for (SpdyPriority i = kHighestPriority; i < priority; ++i) {
  63       if (!write_blocked_lists_[i].empty()) {
  64         return true;
  65       }
  66     }
  67     return false;
  68   }
  69
  70   bool HasWriteBlockedStreams() const {
  71     for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) {
  72       if (!write_blocked_lists_[i].empty()) {
  73         return true;
  74       }
  75     }
  76     return false;
  77   }
  78
  79   void PushBack(IdType stream_id, SpdyPriority priority) {
  80     write_blocked_lists_[ClampPriority(priority)].push_back(stream_id);
  81   }
  82
  83   bool RemoveStreamFromWriteBlockedList(IdType stream_id,
  84                                         SpdyPriority priority) {
  85     // We shouldn't really add a stream_id to a list multiple times,
  86     // but under some conditions it does happen. Doing a check in PushBack
  87     // would be too costly, so instead we check here to eliminate duplicates.
  88     bool found = false;
  89     iterator it = std::find(write_blocked_lists_[priority].begin(),
  90                             write_blocked_lists_[priority].end(),
  91                             stream_id);
  92     while (it != write_blocked_lists_[priority].end()) {
  93       found = true;
  94       iterator next_it = write_blocked_lists_[priority].erase(it);
  95       it = std::find(next_it, write_blocked_lists_[priority].end(), stream_id);
  96     }
  97     return found;
  98   }
  99
 100   void UpdateStreamPriorityInWriteBlockedList(IdType stream_id,
 101                                               SpdyPriority old_priority,
 102                                               SpdyPriority new_priority) {
 103     if (old_priority == new_priority) {
 104       return;
 105     }
 106     bool found = RemoveStreamFromWriteBlockedList(stream_id, old_priority);
 107     if (found) {
 108       PushBack(stream_id, new_priority);
 109     }
 110   }
 111
 112   size_t NumBlockedStreams() const {
 113     size_t num_blocked_streams = 0;
 114     for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) {
 115       num_blocked_streams += write_blocked_lists_[i].size();
 116     }
 117     return num_blocked_streams;
 118   }
 119
 120  private:
 121   friend WriteBlockedListPeer;
 122   BlockedList write_blocked_lists_[kLowestPriority + 1];
 123 };
 124
 125 }  // namespace net
 126
 127 #endif  // NET_SPDY_WRITE_BLOCKED_LIST_H_