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. 4 5 #ifndef NET_SPDY_HPACK_HEADER_TABLE_H_ 6 #define NET_SPDY_HPACK_HEADER_TABLE_H_ 7 8 #include <cstddef> 9 #include <deque> 10 #include <set> 11 12 #include "base/basictypes.h" 13 #include "base/macros.h" 14 #include "net/base/net_export.h" 15 #include "net/spdy/hpack_entry.h" 16 17 // All section references below are to 18 // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07 19 20 namespace net { 21 22 namespace test { 23 class HpackHeaderTablePeer; 24 } // namespace test 25 26 // A data structure for both the header table (described in 3.1.2) and 27 // the reference set (3.1.3). 28 class NET_EXPORT_PRIVATE HpackHeaderTable { 29 public: 30 friend class test::HpackHeaderTablePeer; 31 32 // HpackHeaderTable takes advantage of the deque property that references 33 // remain valid, so long as insertions & deletions are at the head & tail. 34 // If this changes (eg we start to drop entries from the middle of the table), 35 // this needs to be a std::list, in which case |index_| can be trivially 36 // extended to map to list iterators. 37 typedef std::deque<HpackEntry> EntryTable; 38 39 // Implements a total ordering of HpackEntry on name(), value(), then index 40 // ascending. Note that index may change over the lifetime of an HpackEntry, 41 // but the relative index order of two entries will not. This comparator is 42 // composed with the 'lookup' HpackEntry constructor to allow for efficient 43 // lower-bounding of matching entries. 44 struct NET_EXPORT_PRIVATE EntryComparator { EntryComparatorEntryComparator45 explicit EntryComparator(HpackHeaderTable* table) : table_(table) {} 46 47 bool operator() (const HpackEntry* lhs, const HpackEntry* rhs) const; 48 49 private: 50 HpackHeaderTable* table_; 51 }; 52 typedef std::set<HpackEntry*, EntryComparator> OrderedEntrySet; 53 54 HpackHeaderTable(); 55 56 ~HpackHeaderTable(); 57 58 // Last-aknowledged value of SETTINGS_HEADER_TABLE_SIZE. settings_size_bound()59 size_t settings_size_bound() { return settings_size_bound_; } 60 61 // Current and maximum estimated byte size of the table, as described in 62 // 3.3.1. Notably, this is /not/ the number of entries in the table. size()63 size_t size() const { return size_; } max_size()64 size_t max_size() const { return max_size_; } 65 reference_set()66 const OrderedEntrySet& reference_set() { 67 return reference_set_; 68 } 69 70 // Returns the entry matching the index, or NULL. 71 HpackEntry* GetByIndex(size_t index); 72 73 // Returns the lowest-value entry having |name|, or NULL. 74 HpackEntry* GetByName(base::StringPiece name); 75 76 // Returns the lowest-index matching entry, or NULL. 77 HpackEntry* GetByNameAndValue(base::StringPiece name, 78 base::StringPiece value); 79 80 // Returns the index of an entry within this header table. 81 size_t IndexOf(const HpackEntry* entry) const; 82 83 // Sets the maximum size of the header table, evicting entries if 84 // necessary as described in 3.3.2. 85 void SetMaxSize(size_t max_size); 86 87 // Sets the SETTINGS_HEADER_TABLE_SIZE bound of the table. Will call 88 // SetMaxSize() as needed to preserve max_size() <= settings_size_bound(). 89 void SetSettingsHeaderTableSize(size_t settings_size); 90 91 // Determine the set of entries which would be evicted by the insertion 92 // of |name| & |value| into the table, as per section 3.3.3. No eviction 93 // actually occurs. The set is returned via range [begin_out, end_out). 94 void EvictionSet(base::StringPiece name, base::StringPiece value, 95 EntryTable::iterator* begin_out, 96 EntryTable::iterator* end_out); 97 98 // Adds an entry for the representation, evicting entries as needed. |name| 99 // and |value| must not be owned by an entry which could be evicted. The 100 // added HpackEntry is returned, or NULL is returned if all entries were 101 // evicted and the empty table is of insufficent size for the representation. 102 HpackEntry* TryAddEntry(base::StringPiece name, base::StringPiece value); 103 104 // Toggles the presence of a dynamic entry in the reference set. Returns 105 // true if the entry was added, or false if removed. It is an error to 106 // Toggle(entry) if |entry->state()| != 0. 107 bool Toggle(HpackEntry* entry); 108 109 // Removes all entries from the reference set. Sets the state of each removed 110 // entry to zero. 111 void ClearReferenceSet(); 112 113 void DebugLogTableState() const; 114 115 private: 116 // Returns number of evictions required to enter |name| & |value|. 117 size_t EvictionCountForEntry(base::StringPiece name, 118 base::StringPiece value) const; 119 120 // Returns number of evictions required to reclaim |reclaim_size| table size. 121 size_t EvictionCountToReclaim(size_t reclaim_size) const; 122 123 // Evicts |count| oldest entries from the table. 124 void Evict(size_t count); 125 126 EntryTable dynamic_entries_; 127 EntryTable static_entries_; 128 129 // Full table index, over |dynamic_entries_| and |static_entries_|. 130 OrderedEntrySet index_; 131 // The reference set is strictly a subset of |dynamic_entries_|. 132 OrderedEntrySet reference_set_; 133 134 // Last acknowledged value for SETTINGS_HEADER_TABLE_SIZE. 135 size_t settings_size_bound_; 136 137 // Estimated current and maximum byte size of the table. 138 // |max_size_| <= |settings_header_table_size_| 139 size_t size_; 140 size_t max_size_; 141 142 // Total number of table insertions which have occurred. Referenced by 143 // IndexOf() for determination of an HpackEntry's table index. 144 size_t total_insertions_; 145 146 DISALLOW_COPY_AND_ASSIGN(HpackHeaderTable); 147 }; 148 149 } // namespace net 150 151 #endif // NET_SPDY_HPACK_HEADER_TABLE_H_ 152