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
14namespace net {
15
16const int kHighestPriority = 0;
17const int kLowestPriority = 7;
18
19template <typename IdType>
20class 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
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.
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
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
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
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
75  void PushBack(IdType stream_id, SpdyPriority priority) {
76    write_blocked_lists_[ClampPriority(priority)].push_back(stream_id);
77  }
78
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
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