Implement basic classes for HPACK (HTTP/2 compression)

net/spdy/hpack_header_table_test.cc

+#include "net/spdy/hpack_header_table.h"
+
+#include <algorithm>
+#include <set>
+#include <string>
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/macros.h"
+#include "net/spdy/hpack_entry.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace net {
+
+namespace {
+
+using std::string;
+
+typedef std::vector<HpackEntry> HpackEntryVector;
+
+// Returns an entry whose Size() is equal to the given one.
+HpackEntry MakeEntryOfSize(uint32 size) {
+  EXPECT_GE(size, HpackEntry::kSizeOverhead);
+  string name((size - HpackEntry::kSizeOverhead) / 2, 'n');
+  string value(size - HpackEntry::kSizeOverhead - name.size(), 'v');
+  HpackEntry entry(name, value);
+  EXPECT_EQ(size, entry.Size());
+  return entry;
+}
+
+// Returns a vector of entries whose total size is equal to the given
+// one.
+HpackEntryVector MakeEntriesOfTotalSize(uint32 total_size) {
+  EXPECT_GE(total_size, HpackEntry::kSizeOverhead);
+  uint32 entry_size = HpackEntry::kSizeOverhead;
+  uint32 remaining_size = total_size;
+  HpackEntryVector entries;
+  while (remaining_size > 0) {
+    EXPECT_LE(entry_size, remaining_size);
+    entries.push_back(MakeEntryOfSize(entry_size));
+    remaining_size -= entry_size;
+    entry_size = std::min(remaining_size, entry_size + 32);
+  }
+  return entries;
+}
+
+// Adds the given vector of entries to the given header table,
+// expecting no eviction to happen.
+void AddEntriesExpectNoEviction(const HpackEntryVector& entries,
+                                HpackHeaderTable* header_table) {
+  int start_entry_count = header_table->GetEntryCount();
+  for (HpackEntryVector::const_iterator it = entries.begin();
+       it != entries.end(); ++it) {
+    int32 index = -1;
+    std::vector<uint32> removed_referenced_indices;
+    header_table->TryAddEntry(*it, &index, &removed_referenced_indices);
+    EXPECT_EQ(0, index);
+    EXPECT_TRUE(removed_referenced_indices.empty());
+    EXPECT_EQ(start_entry_count + (it - entries.begin()) + 1,
+              header_table->GetEntryCount());
+  }
+
+  for (HpackEntryVector::const_iterator it = entries.begin();
+       it != entries.end(); ++it) {
+    uint32 index = header_table->GetEntryCount() - (it - entries.begin()) - 1;
+    HpackEntry entry = header_table->GetEntry(index);
+    EXPECT_TRUE(it->Equals(entry))
+        << "it = " << it->GetDebugString() << " != entry = "
+        << entry.GetDebugString();
+  }
+}
+
+// Returns the set of all indices in header_table that are in that
+// table's reference set.
+std::set<uint32> GetReferenceSet(const HpackHeaderTable& header_table) {
+  std::set<uint32> reference_set;
+  for (uint32 i = 0; i < header_table.GetEntryCount(); ++i) {
+    if (header_table.GetEntry(i).IsReferenced()) {
+      reference_set.insert(i);
+    }
+  }
+  return reference_set;
+}
+
+// Fill a header table with entries. Make sure the entries are in
+// reverse order in the header table.
+TEST(HpackHeaderTableTest, TryAddEntryBasic) {
+  HpackHeaderTable header_table;
+  EXPECT_EQ(0u, header_table.size());
+
+  HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size());
+
+  // Most of the checks are in AddEntriesExpectNoEviction().
+  AddEntriesExpectNoEviction(entries, &header_table);
+  EXPECT_EQ(header_table.max_size(), header_table.size());
+}
+
+// Fill a header table with entries, and then ramp the table's max
+// size down to evict an entry one at a time. Make sure the eviction
+// happens as expected.
+TEST(HpackHeaderTableTest, SetMaxSize) {
+  HpackHeaderTable header_table;
+
+  HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size());
+  AddEntriesExpectNoEviction(entries, &header_table);
+
+  for (HpackEntryVector::const_iterator it = entries.begin();
+       it != entries.end(); ++it) {
+    uint32 expected_count = entries.end() - it;
+    EXPECT_EQ(expected_count, header_table.GetEntryCount());
+
+    header_table.SetMaxSize(header_table.size() + 1);
+    EXPECT_EQ(expected_count, header_table.GetEntryCount());
+
+    header_table.SetMaxSize(header_table.size());
+    EXPECT_EQ(expected_count, header_table.GetEntryCount());
+
+    --expected_count;
+    header_table.SetMaxSize(header_table.size() - 1);
+    EXPECT_EQ(expected_count, header_table.GetEntryCount());
+  }
+
+  EXPECT_EQ(0u, header_table.size());
+}
+
+// Setting the max size of a header table to zero should clear its
+// reference set.
+TEST(HpackHeaderTableTest, SetMaxSizeZeroClearsReferenceSet) {
+  HpackHeaderTable header_table;
+
+  HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size());
+  AddEntriesExpectNoEviction(entries, &header_table);
+
+  std::set<uint32> expected_reference_set;
+  for (uint32 i = 0; i < header_table.GetEntryCount(); ++i) {
+    header_table.GetMutableEntry(i)->SetReferenced(true);
+    expected_reference_set.insert(i);
+  }
+  EXPECT_EQ(expected_reference_set, GetReferenceSet(header_table));
+
+  header_table.SetMaxSize(0);
+  EXPECT_TRUE(GetReferenceSet(header_table).empty());
+}
+
+// Fill a header table with entries, and then add an entry just big
+// enough to cause eviction of all but one entry. Make sure the
+// eviction happens as expected and the long entry is inserted into
+// the table.
+TEST(HpackHeaderTableTest, TryAddEntryEviction) {
+  HpackHeaderTable header_table;
+
+  HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size());
+  AddEntriesExpectNoEviction(entries, &header_table);
+
+  EXPECT_EQ(entries.size(), header_table.GetEntryCount());
+  HpackEntry first_entry = header_table.GetEntry(0);
+  HpackEntry long_entry =
+      MakeEntryOfSize(header_table.size() - first_entry.Size());
+
+  header_table.SetMaxSize(header_table.size());
+  EXPECT_EQ(entries.size(), header_table.GetEntryCount());
+
+  std::set<uint32> expected_reference_set;
+  for (uint32 i = 1; i < header_table.GetEntryCount(); ++i) {
+    header_table.GetMutableEntry(i)->SetReferenced(true);
+    expected_reference_set.insert(i);
+  }
+  EXPECT_EQ(expected_reference_set, GetReferenceSet(header_table));
+
+  int32 index = -1;
+  std::vector<uint32> removed_referenced_indices;
+  header_table.TryAddEntry(long_entry, &index, &removed_referenced_indices);
+
+  EXPECT_EQ(0, index);
+  EXPECT_EQ(expected_reference_set,
+            std::set<uint32>(removed_referenced_indices.begin(),
+                             removed_referenced_indices.end()));
+  EXPECT_TRUE(GetReferenceSet(header_table).empty());
+  EXPECT_EQ(2u, header_table.GetEntryCount());
+  EXPECT_TRUE(header_table.GetEntry(0).Equals(long_entry));
+  EXPECT_TRUE(header_table.GetEntry(1).Equals(first_entry));
+}
+
+// Fill a header table with entries, and then add an entry bigger than
+// the entire table. Make sure no entry remains in the table.
+TEST(HpackHeaderTableTest, TryAddTooLargeEntry) {
+  HpackHeaderTable header_table;
+
+  HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size());
+  AddEntriesExpectNoEviction(entries, &header_table);
+
+  header_table.SetMaxSize(header_table.size());
+  EXPECT_EQ(entries.size(), header_table.GetEntryCount());
+
+  std::set<uint32> expected_removed_referenced_indices;
+  for (uint32 i = 0; i < header_table.GetEntryCount(); ++i) {
+    header_table.GetMutableEntry(i)->SetReferenced(true);
+    expected_removed_referenced_indices.insert(i);
+  }
+
+  HpackEntry long_entry = MakeEntryOfSize(header_table.size() + 1);
+  int32 index = -1;
+  std::vector<uint32> removed_referenced_indices;
+  header_table.TryAddEntry(long_entry, &index, &removed_referenced_indices);
+
+  EXPECT_EQ(-1, index);
+  EXPECT_EQ(expected_removed_referenced_indices,
+            std::set<uint32>(removed_referenced_indices.begin(),
+                             removed_referenced_indices.end()));
+  EXPECT_EQ(0u, header_table.GetEntryCount());
+}
+
+}  // namespace
+
+}  // namespace net