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 #ifndef NET_SPDY_HPACK_HEADER_TABLE_H_
6 #define NET_SPDY_HPACK_HEADER_TABLE_H_
12 #include "base/basictypes.h"
13 #include "base/macros.h"
14 #include "net/base/net_export.h"
15 #include "net/spdy/hpack_entry.h"
17 // All section references below are to
18 // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-06
23 class HpackHeaderTablePeer;
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 {
30 friend class test::HpackHeaderTablePeer;
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;
43 // Last-aknowledged value of SETTINGS_HEADER_TABLE_SIZE.
44 size_t settings_size_bound() { return settings_size_bound_; }
46 // Current and maximum estimated byte size of the table, as described in
47 // 3.3.1. Notably, this is /not/ the number of entries in the table.
48 size_t size() const { return size_; }
49 size_t max_size() const { return max_size_; }
51 const HpackEntry::OrderedSet& reference_set() {
52 return reference_set_;
55 // Returns the entry matching the index, or NULL.
56 HpackEntry* GetByIndex(size_t index);
58 // Returns the lowest-value entry having |name|, or NULL.
59 HpackEntry* GetByName(base::StringPiece name);
61 // Returns the lowest-index matching entry, or NULL.
62 HpackEntry* GetByNameAndValue(base::StringPiece name,
63 base::StringPiece value);
65 // Sets the maximum size of the header table, evicting entries if
66 // necessary as described in 3.3.2.
67 void SetMaxSize(size_t max_size);
69 // Sets the SETTINGS_HEADER_TABLE_SIZE bound of the table. Will call
70 // SetMaxSize() as needed to preserve max_size() <= settings_size_bound().
71 void SetSettingsHeaderTableSize(size_t settings_size);
73 // Determine the set of entries which would be evicted by the insertion
74 // of |name| & |value| into the table, as per section 3.3.3. No eviction
75 // actually occurs. The set is returned via range [begin_out, end_out).
76 void EvictionSet(base::StringPiece name, base::StringPiece value,
77 EntryTable::iterator* begin_out,
78 EntryTable::iterator* end_out);
80 // Adds an entry for the representation, evicting entries as needed. |name|
81 // and |value| must not be owned by an entry which could be evicted. The
82 // added HpackEntry is returned, or NULL is returned if all entries were
83 // evicted and the empty table is of insufficent size for the representation.
84 HpackEntry* TryAddEntry(base::StringPiece name, base::StringPiece value);
86 // Toggles the presence of a dynamic entry in the reference set. Returns
87 // true if the entry was added, or false if removed. It is an error to
88 // Toggle(entry) if |entry->state()| != 0.
89 bool Toggle(HpackEntry* entry);
91 // Removes all entries from the reference set. Sets the state of each removed
93 void ClearReferenceSet();
95 void DebugLogTableState() const;
98 // Returns number of evictions required to enter |name| & |value|.
99 size_t EvictionCountForEntry(base::StringPiece name,
100 base::StringPiece value) const;
102 // Returns number of evictions required to reclaim |reclaim_size| table size.
103 size_t EvictionCountToReclaim(size_t reclaim_size) const;
105 // Evicts |count| oldest entries from the table.
106 void Evict(size_t count);
108 EntryTable dynamic_entries_;
109 EntryTable static_entries_;
111 // Full table index, over |dynamic_entries_| and |static_entries_|.
112 HpackEntry::OrderedSet index_;
113 // The reference set is strictly a subset of |dynamic_entries_|.
114 HpackEntry::OrderedSet reference_set_;
116 // Last acknowledged value for SETTINGS_HEADER_TABLE_SIZE.
117 size_t settings_size_bound_;
119 // Estimated current and maximum byte size of the table.
120 // |max_size_| <= |settings_header_table_size_|
124 // Total number of table insertions which have occurred. Referenced by
125 // dynamic HpackEntry instances for determination of table index.
126 size_t total_insertions_;
128 // Current number of dynamic entries. Referenced by static HpackEntry
129 // instances for determination of table index.
130 size_t dynamic_entries_count_;
132 DISALLOW_COPY_AND_ASSIGN(HpackHeaderTable);
137 #endif // NET_SPDY_HPACK_HEADER_TABLE_H_