1 // Copyright 2014 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.
5 #include "net/spdy/hpack_header_table.h"
9 #include "base/logging.h"
10 #include "net/spdy/hpack_constants.h"
11 #include "net/spdy/hpack_static_table.h"
12 #include "net/spdy/hpack_string_util.h"
16 using base::StringPiece;
18 bool HpackHeaderTable::EntryComparator::operator() (
19 const HpackEntry* lhs, const HpackEntry* rhs) const {
20 int result = lhs->name().compare(rhs->name());
23 result = lhs->value().compare(rhs->value());
26 const size_t lhs_index = lhs->IsLookup() ? 0 : 1 + lhs->InsertionIndex();
27 const size_t rhs_index = rhs->IsLookup() ? 0 : 1 + rhs->InsertionIndex();
28 DCHECK(lhs == rhs || lhs_index != rhs_index)
29 << "lhs: (" << lhs->name() << ", " << rhs->value() << ") rhs: ("
30 << rhs->name() << ", " << rhs->value() << ")"
31 << " lhs index: " << lhs_index << " rhs index: " << rhs_index;
32 return lhs_index < rhs_index;
35 HpackHeaderTable::HpackHeaderTable()
36 : static_entries_(ObtainHpackStaticTable().GetStaticEntries()),
37 static_index_(ObtainHpackStaticTable().GetStaticIndex()),
38 settings_size_bound_(kDefaultHeaderTableSizeSetting),
40 max_size_(kDefaultHeaderTableSizeSetting),
41 total_insertions_(static_entries_.size()) {}
43 HpackHeaderTable::~HpackHeaderTable() {}
45 const HpackEntry* HpackHeaderTable::GetByIndex(size_t index) {
50 if (index < static_entries_.size()) {
51 return &static_entries_[index];
53 index -= static_entries_.size();
54 if (index < dynamic_entries_.size()) {
55 return &dynamic_entries_[index];
60 const HpackEntry* HpackHeaderTable::GetByName(StringPiece name) {
61 HpackEntry query(name, "");
63 OrderedEntrySet::const_iterator it = static_index_.lower_bound(&query);
64 if (it != static_index_.end() && (*it)->name() == name) {
69 OrderedEntrySet::const_iterator it = dynamic_index_.lower_bound(&query);
70 if (it != dynamic_index_.end() && (*it)->name() == name) {
77 const HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name,
79 HpackEntry query(name, value);
81 OrderedEntrySet::const_iterator it = static_index_.lower_bound(&query);
82 if (it != static_index_.end() &&
83 (*it)->name() == name &&
84 (*it)->value() == value) {
89 OrderedEntrySet::const_iterator it = dynamic_index_.lower_bound(&query);
90 if (it != dynamic_index_.end() &&
91 (*it)->name() == name &&
92 (*it)->value() == value) {
99 size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const {
100 if (entry->IsLookup()) {
102 } else if (entry->IsStatic()) {
103 return 1 + entry->InsertionIndex();
105 return total_insertions_ - entry->InsertionIndex() + static_entries_.size();
109 void HpackHeaderTable::SetMaxSize(size_t max_size) {
110 CHECK_LE(max_size, settings_size_bound_);
112 max_size_ = max_size;
113 if (size_ > max_size_) {
114 Evict(EvictionCountToReclaim(size_ - max_size_));
115 CHECK_LE(size_, max_size_);
119 void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) {
120 settings_size_bound_ = settings_size;
121 if (settings_size_bound_ < max_size_) {
122 SetMaxSize(settings_size_bound_);
126 void HpackHeaderTable::EvictionSet(StringPiece name,
128 EntryTable::iterator* begin_out,
129 EntryTable::iterator* end_out) {
130 size_t eviction_count = EvictionCountForEntry(name, value);
131 *begin_out = dynamic_entries_.end() - eviction_count;
132 *end_out = dynamic_entries_.end();
135 size_t HpackHeaderTable::EvictionCountForEntry(StringPiece name,
136 StringPiece value) const {
137 size_t available_size = max_size_ - size_;
138 size_t entry_size = HpackEntry::Size(name, value);
140 if (entry_size <= available_size) {
141 // No evictions are required.
144 return EvictionCountToReclaim(entry_size - available_size);
147 size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const {
149 for (EntryTable::const_reverse_iterator it = dynamic_entries_.rbegin();
150 it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) {
151 reclaim_size -= std::min(reclaim_size, it->Size());
156 void HpackHeaderTable::Evict(size_t count) {
157 for (size_t i = 0; i != count; ++i) {
158 CHECK(!dynamic_entries_.empty());
159 HpackEntry* entry = &dynamic_entries_.back();
161 size_ -= entry->Size();
162 CHECK_EQ(1u, dynamic_index_.erase(entry));
163 dynamic_entries_.pop_back();
167 const HpackEntry* HpackHeaderTable::TryAddEntry(StringPiece name,
169 Evict(EvictionCountForEntry(name, value));
171 size_t entry_size = HpackEntry::Size(name, value);
172 if (entry_size > (max_size_ - size_)) {
173 // Entire table has been emptied, but there's still insufficient room.
174 DCHECK(dynamic_entries_.empty());
175 DCHECK_EQ(0u, size_);
178 dynamic_entries_.push_front(HpackEntry(name,
182 CHECK(dynamic_index_.insert(&dynamic_entries_.front()).second);
187 return &dynamic_entries_.front();
190 void HpackHeaderTable::DebugLogTableState() const {
191 DVLOG(2) << "Dynamic table:";
192 for (EntryTable::const_iterator it = dynamic_entries_.begin();
193 it != dynamic_entries_.end(); ++it) {
194 DVLOG(2) << " " << it->GetDebugString();
196 DVLOG(2) << "Full Static Index:";
197 for (OrderedEntrySet::const_iterator it = static_index_.begin();
198 it != static_index_.end(); ++it) {
199 DVLOG(2) << " " << (*it)->GetDebugString();
201 DVLOG(2) << "Full Dynamic Index:";
202 for (OrderedEntrySet::const_iterator it = dynamic_index_.begin();
203 it != dynamic_index_.end(); ++it) {
204 DVLOG(2) << " " << (*it)->GetDebugString();