Land recent SPDY changes (through 67282679)

net/spdy/hpack_header_table.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/spdy/hpack_header_table.h"
 
 #include <algorithm>
 
 #include "base/logging.h"
 #include "net/spdy/hpack_constants.h"
@@ skipping 81 matching lines @@
   STATIC_ENTRY("user-agent"                  , ""),             // 58
   STATIC_ENTRY("vary"                        , ""),             // 59
   STATIC_ENTRY("via"                         , ""),             // 60
   STATIC_ENTRY("www-authenticate"            , ""),             // 61
 };
 
 #undef STATIC_ENTRY
 
 }  // namespace
 
+bool HpackHeaderTable::EntryComparator::operator() (
+    const HpackEntry* lhs, const HpackEntry* rhs) const {
+  int result = lhs->name().compare(rhs->name());
+  if (result != 0)
+    return result < 0;
+  result = lhs->value().compare(rhs->value());
+  if (result != 0)
+    return result < 0;
+  const size_t lhs_index = table_->IndexOf(lhs);
+  const size_t rhs_index = table_->IndexOf(rhs);
+  DCHECK(lhs == rhs || lhs_index != rhs_index)
+      << "lhs: (" << lhs->name() << ", " << rhs->value() << ") rhs: ("
+      << rhs->name() << ", " << rhs->value() << ")"
+      << " lhs index: " << lhs_index << " rhs index: " << rhs_index;
+  return lhs_index < rhs_index;
+}
+
 HpackHeaderTable::HpackHeaderTable()
-    : settings_size_bound_(kDefaultHeaderTableSizeSetting),
+    : index_(EntryComparator(this)),
+      reference_set_(EntryComparator(this)),
+      settings_size_bound_(kDefaultHeaderTableSizeSetting),
       size_(0),
       max_size_(kDefaultHeaderTableSizeSetting),
-      total_insertions_(0),
-      dynamic_entries_count_(0) {
+      total_insertions_(0) {
   for (const StaticEntry* it = kStaticTable;
        it != kStaticTable + arraysize(kStaticTable); ++it) {
     static_entries_.push_back(
         HpackEntry(StringPiece(it->name, it->name_len),
                    StringPiece(it->value, it->value_len),
                    true,  // is_static
-                   total_insertions_,
-                   &dynamic_entries_count_));
+                   total_insertions_));
     CHECK(index_.insert(&static_entries_.back()).second);
 
     ++total_insertions_;
   }
 }
 
 HpackHeaderTable::~HpackHeaderTable() {}
 
 HpackEntry* HpackHeaderTable::GetByIndex(size_t index) {
   if (index == 0) {
     return NULL;
   }
   index -= 1;
   if (index < dynamic_entries_.size()) {
     return &dynamic_entries_[index];
   }
   index -= dynamic_entries_.size();
   if (index < static_entries_.size()) {
     return &static_entries_[index];
   }
   return NULL;
 }
 
 HpackEntry* HpackHeaderTable::GetByName(StringPiece name) {
   HpackEntry query(name, "");
-  HpackEntry::OrderedSet::const_iterator it = index_.lower_bound(&query);
+  OrderedEntrySet::const_iterator it = index_.lower_bound(&query);
   if (it != index_.end() && (*it)->name() == name) {
     return *it;
   }
   return NULL;
 }
 
 HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name,
                                                 StringPiece value) {
   HpackEntry query(name, value);
-  HpackEntry::OrderedSet::const_iterator it = index_.lower_bound(&query);
+  OrderedEntrySet::const_iterator it = index_.lower_bound(&query);
   if (it != index_.end() && (*it)->name() == name && (*it)->value() == value) {
     return *it;
   }
   return NULL;
 }
 
+size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const {
+  if (entry->IsLookup()) {
+    return 0;
+  } else if (entry->IsStatic()) {
+    return 1 + entry->InsertionIndex() + dynamic_entries_.size();
+  } else {
+    return total_insertions_ - entry->InsertionIndex();
+  }
+}
+
 void HpackHeaderTable::SetMaxSize(size_t max_size) {
   CHECK_LE(max_size, settings_size_bound_);
 
   max_size_ = max_size;
   if (size_ > max_size_) {
     Evict(EvictionCountToReclaim(size_ - max_size_));
     CHECK_LE(size_, max_size_);
   }
 }
 
@@ skipping 36 matching lines @@
 
 void HpackHeaderTable::Evict(size_t count) {
   for (size_t i = 0; i != count; ++i) {
     CHECK(!dynamic_entries_.empty());
     HpackEntry* entry = &dynamic_entries_.back();
 
     size_ -= entry->Size();
     CHECK_EQ(1u, index_.erase(entry));
     reference_set_.erase(entry);
     dynamic_entries_.pop_back();
-
-    --dynamic_entries_count_;
-    DCHECK_EQ(dynamic_entries_count_, dynamic_entries_.size());
   }
 }
 
 HpackEntry* HpackHeaderTable::TryAddEntry(StringPiece name, StringPiece value) {
   Evict(EvictionCountForEntry(name, value));
 
   size_t entry_size = HpackEntry::Size(name, value);
   if (entry_size > (max_size_ - size_)) {
     // Entire table has been emptied, but there's still insufficient room.
     DCHECK(dynamic_entries_.empty());
     DCHECK_EQ(0u, size_);
     return NULL;
   }
   dynamic_entries_.push_front(HpackEntry(name,
                                          value,
                                          false,  // is_static
-                                         total_insertions_,
-                                         &total_insertions_));
+                                         total_insertions_));
   CHECK(index_.insert(&dynamic_entries_.front()).second);
 
   size_ += entry_size;
-  ++dynamic_entries_count_;
   ++total_insertions_;
 
-  DCHECK_EQ(dynamic_entries_count_, dynamic_entries_.size());
   return &dynamic_entries_.front();
 }
 
 void HpackHeaderTable::ClearReferenceSet() {
-  for (HpackEntry::OrderedSet::iterator it = reference_set_.begin();
+  for (OrderedEntrySet::iterator it = reference_set_.begin();
        it != reference_set_.end(); ++it) {
     (*it)->set_state(0);
   }
   reference_set_.clear();
 }
 
 bool HpackHeaderTable::Toggle(HpackEntry* entry) {
   CHECK(!entry->IsStatic());
   CHECK_EQ(0u, entry->state());
 
-  std::pair<HpackEntry::OrderedSet::iterator, bool> insert_result =
+  std::pair<OrderedEntrySet::iterator, bool> insert_result =
       reference_set_.insert(entry);
   if (insert_result.second) {
     return true;
   } else {
     reference_set_.erase(insert_result.first);
     return false;
   }
 }
 
 void HpackHeaderTable::DebugLogTableState() const {
   DVLOG(2) << "Reference Set:";
-  for (HpackEntry::OrderedSet::const_iterator it = reference_set_.begin();
+  for (OrderedEntrySet::const_iterator it = reference_set_.begin();
       it != reference_set_.end(); ++it) {
     DVLOG(2) << "  " << (*it)->GetDebugString();
   }
   DVLOG(2) << "Dynamic table:";
   for (EntryTable::const_iterator it = dynamic_entries_.begin();
       it != dynamic_entries_.end(); ++it) {
     DVLOG(2) << "  " << it->GetDebugString();
   }
   DVLOG(2) << "Full Index:";
-  for (HpackEntry::OrderedSet::const_iterator it = index_.begin();
+  for (OrderedEntrySet::const_iterator it = index_.begin();
       it != index_.end(); ++it) {
     DVLOG(2) << "  " << (*it)->GetDebugString();
   }
 }
 
 }  // namespace net