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/containers/hash_tables.h"
  12 #include "base/logging.h"
  13 #include "net/spdy/spdy_protocol.h"
  14
  15 namespace net {
  16
  17 namespace test {
  18 class WriteBlockedListPeer;
  19 }  // namespace test
  20
  21 const int kHighestPriority = 0;
  22 const int kLowestPriority = 7;
  23
  24 template <typename IdType>
  25 class WriteBlockedList {
  26  public:
  27   // 0(1) size lookup.  0(1) insert at front or back.
  28   typedef std::deque<IdType> BlockedList;
  29   typedef typename BlockedList::iterator iterator;
  30
  31   WriteBlockedList() {}
  32
  33   static SpdyPriority ClampPriority(SpdyPriority priority) {
  34     if (priority < kHighestPriority) {
  35       LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority);
  36       return kHighestPriority;
  37     }
  38     if (priority > kLowestPriority) {
  39       LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority);
  40       return kLowestPriority;
  41     }
  42     return priority;
  43   }
  44
  45   // Returns the priority of the highest priority list with sessions on it.
  46   SpdyPriority GetHighestPriorityWriteBlockedList() const {
  47     for (SpdyPriority i = 0; i <= kLowestPriority; ++i) {
  48       if (write_blocked_lists_[i].size() > 0) {
  49         return i;
  50       }
  51     }
  52     LOG(DFATAL) << "No blocked streams";
  53     return kHighestPriority;
  54   }
  55
  56   IdType PopFront(SpdyPriority priority) {
  57     priority = ClampPriority(priority);
  58     DCHECK(!write_blocked_lists_[priority].empty());
  59     IdType stream_id = write_blocked_lists_[priority].front();
  60     write_blocked_lists_[priority].pop_front();
  61     stream_to_priority_.erase(stream_id);
  62     return stream_id;
  63   }
  64
  65   bool HasWriteBlockedStreamsGreaterThanPriority(SpdyPriority priority) const {
  66     priority = ClampPriority(priority);
  67     for (SpdyPriority i = kHighestPriority; i < priority; ++i) {
  68       if (!write_blocked_lists_[i].empty()) {
  69         return true;
  70       }
  71     }
  72     return false;
  73   }
  74
  75   bool HasWriteBlockedStreams() const {
  76     for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) {
  77       if (!write_blocked_lists_[i].empty()) {
  78         return true;
  79       }
  80     }
  81     return false;
  82   }
  83
  84   void PushBack(IdType stream_id, SpdyPriority priority) {
  85     priority = ClampPriority(priority);
  86     DVLOG(2) << "Adding stream " << stream_id << " at priority "
  87              << static_cast<int>(priority);
  88     bool should_insert_stream = true;
  89     typename StreamToPriorityMap::iterator iter =
  90         stream_to_priority_.find(stream_id);
  91     if (iter != stream_to_priority_.end()) {
  92       DVLOG(1) << "Stream " << stream_id << " already in write blocked list.";
  93       if (iter->second == priority) {
  94         // The stream is already in the write blocked list for the priority.
  95         should_insert_stream = false;
  96       } else {
  97         // The stream is in a write blocked list for a different priority.
  98         bool removed =
  99             RemoveStreamFromWriteBlockedList(stream_id, iter->second);
 100         DCHECK(removed);
 101       }
 102     }
 103     if (should_insert_stream) {
 104       stream_to_priority_[stream_id] = priority;
 105       write_blocked_lists_[priority].push_back(stream_id);
 106     }
 107   }
 108
 109   bool RemoveStreamFromWriteBlockedList(IdType stream_id,
 110                                         SpdyPriority priority) {
 111     typename StreamToPriorityMap::iterator iter =
 112         stream_to_priority_.find(stream_id);
 113     if (iter == stream_to_priority_.end()) {
 114       // The stream is not present in the write blocked list.
 115       return false;
 116     } else if (iter->second == priority) {
 117       stream_to_priority_.erase(iter);
 118     } else {
 119       // The stream is not present at the specified priority level.
 120       return false;
 121     }
 122     // We shouldn't really add a stream_id to a list multiple times,
 123     // but under some conditions it does happen. Doing a check in PushBack
 124     // would be too costly, so instead we check here to eliminate duplicates.
 125     bool found = false;
 126     iterator it = std::find(write_blocked_lists_[priority].begin(),
 127                             write_blocked_lists_[priority].end(), stream_id);
 128     while (it != write_blocked_lists_[priority].end()) {
 129       found = true;
 130       iterator next_it = write_blocked_lists_[priority].erase(it);
 131       it = std::find(next_it, write_blocked_lists_[priority].end(), stream_id);
 132     }
 133     return found;
 134   }
 135
 136   void UpdateStreamPriorityInWriteBlockedList(IdType stream_id,
 137                                               SpdyPriority old_priority,
 138                                               SpdyPriority new_priority) {
 139     if (old_priority == new_priority) {
 140       return;
 141     }
 142     bool found = RemoveStreamFromWriteBlockedList(stream_id, old_priority);
 143     if (found) {
 144       PushBack(stream_id, new_priority);
 145     }
 146   }
 147
 148   size_t NumBlockedStreams() const {
 149     size_t num_blocked_streams = 0;
 150     for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) {
 151       num_blocked_streams += write_blocked_lists_[i].size();
 152     }
 153     return num_blocked_streams;
 154   }
 155
 156  private:
 157   friend class net::test::WriteBlockedListPeer;
 158
 159   typedef base::hash_map<IdType, SpdyPriority> StreamToPriorityMap;
 160
 161   BlockedList write_blocked_lists_[kLowestPriority + 1];
 162   StreamToPriorityMap stream_to_priority_;
 163 };
 164
 165 }  // namespace net
 166
 167 #endif  // NET_SPDY_WRITE_BLOCKED_LIST_H_