1// Copyright (C) 2019 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef HPACKTABLE_P_H
5#define HPACKTABLE_P_H
6
7//
8// W A R N I N G
9// -------------
10//
11// This file is not part of the Qt API. It exists for the convenience
12// of other Qt classes. This header file may change from version to
13// version without notice, or even be removed.
14//
15// We mean it.
16//
17
18#include <QtCore/qbytearray.h>
19#include <QtCore/private/qglobal_p.h>
20#include <QtCore/qpair.h>
21
22#include <vector>
23#include <memory>
24#include <deque>
25#include <set>
26
27QT_BEGIN_NAMESPACE
28
29namespace HPack
30{
31
32struct Q_AUTOTEST_EXPORT HeaderField
33{
34 HeaderField()
35 {
36 }
37
38 HeaderField(const QByteArray &n, const QByteArray &v)
39 : name(n),
40 value(v)
41 {
42 }
43
44 bool operator == (const HeaderField &rhs) const
45 {
46 return name == rhs.name && value == rhs.value;
47 }
48
49 QByteArray name;
50 QByteArray value;
51};
52
53using HeaderSize = QPair<bool, quint32>;
54
55HeaderSize entry_size(QByteArrayView name, QByteArrayView value);
56
57inline HeaderSize entry_size(const HeaderField &entry)
58{
59 return entry_size(name: entry.name, value: entry.value);
60}
61
62/*
63 Lookup table consists of two parts (HPACK, 2.3):
64 the immutable static table (pre-defined by HPACK's specs)
65 and dynamic table which is updated while
66 compressing/decompressing headers.
67
68 Table must provide/implement:
69 1. Fast random access - we read fields' indices from
70 HPACK's bit stream.
71 2. FIFO for dynamic part - to push new items to the front
72 and evict them from the back (HPACK, 2.3.2).
73 3. Fast lookup - encoder receives pairs of strings
74 (name|value) and it has to find an index for a pair
75 as the whole or for a name at least (if it's already
76 in either static or dynamic table).
77
78 Static table is an immutable vector.
79
80 Dynamic part is implemented in a way similar to std::deque -
81 it's a vector of pointers to chunks. Each chunk is a vector of
82 (name|value) pairs. Once allocated with a fixed size, chunk
83 never re-allocates its data, so entries' addresses do not change.
84 We add new chunks prepending them to the front of a vector,
85 in each chunk we fill (name|value) pairs starting from the back
86 of the chunk (this simplifies item eviction/FIFO).
87 Given a 'linear' index we can find a chunk number and
88 offset in this chunk - random access.
89
90 Lookup in a static part is straightforward:
91 it's an (immutable) vector, data is sorted,
92 contains no duplicates, we use binary search comparing string values.
93
94 To provide a lookup in dynamic table faster than a linear search,
95 we have an std::set of 'SearchEntries', where each entry contains:
96 - a pointer to a (name|value) pair (to compare
97 name|value strings).
98 - a pointer to a chunk containing this pair and
99 - an offset within this chunk - to calculate a
100 'linear' index.
101
102 Entries in a table can be duplicated (HPACK, 2.3.2),
103 if we evict an entry, we must update our index removing
104 the exactly right key, thus keys in this set are sorted
105 by name|value pairs first, and then by chunk index/offset
106 (so that NewSearchEntryKey < OldSearchEntry even if strings
107 are equal).
108*/
109
110class Q_AUTOTEST_EXPORT FieldLookupTable
111{
112public:
113 enum
114 {
115 ChunkSize = 16,
116 DefaultSize = 4096 // Recommended by HTTP2.
117 };
118
119 FieldLookupTable(quint32 maxTableSize, bool useIndex);
120
121 bool prependField(const QByteArray &name, const QByteArray &value);
122 void evictEntry();
123
124 quint32 numberOfEntries() const;
125 quint32 numberOfStaticEntries() const;
126 quint32 numberOfDynamicEntries() const;
127 quint32 dynamicDataSize() const;
128 void clearDynamicTable();
129
130 bool indexIsValid(quint32 index) const;
131 quint32 indexOf(const QByteArray &name, const QByteArray &value) const;
132 quint32 indexOf(const QByteArray &name) const;
133 bool field(quint32 index, QByteArray *name, QByteArray *value) const;
134 bool fieldName(quint32 index, QByteArray *dst) const;
135 bool fieldValue(quint32 index, QByteArray *dst) const;
136
137 bool updateDynamicTableSize(quint32 size);
138 void setMaxDynamicTableSize(quint32 size);
139
140 static const std::vector<HeaderField> &staticPart();
141
142private:
143 // Table's maximum size is controlled
144 // by SETTINGS_HEADER_TABLE_SIZE (HTTP/2, 6.5.2).
145 quint32 maxTableSize;
146 // The tableCapacity is how many bytes the table
147 // can currently hold. It cannot exceed maxTableSize.
148 // It can be modified by a special message in
149 // the HPACK bit stream (HPACK, 6.3).
150 quint32 tableCapacity;
151
152 using Chunk = std::vector<HeaderField>;
153 using ChunkPtr = std::unique_ptr<Chunk>;
154 std::deque<ChunkPtr> chunks;
155 using size_type = std::deque<ChunkPtr>::size_type;
156
157 struct SearchEntry;
158 friend struct SearchEntry;
159
160 struct SearchEntry
161 {
162 SearchEntry();
163 SearchEntry(const HeaderField *f, const Chunk *c,
164 quint32 o, const FieldLookupTable *t);
165
166 const HeaderField *field;
167 const Chunk *chunk;
168 const quint32 offset;
169 const FieldLookupTable *table;
170
171 bool operator < (const SearchEntry &rhs) const;
172 };
173
174 bool useIndex;
175 std::set<SearchEntry> searchIndex;
176
177 SearchEntry frontKey() const;
178 SearchEntry backKey() const;
179
180 bool fieldAt(quint32 index, HeaderField *field) const;
181
182 const HeaderField &front() const;
183 HeaderField &front();
184 const HeaderField &back() const;
185
186 quint32 nDynamic;
187 quint32 begin;
188 quint32 end;
189 quint32 dataSize;
190
191 quint32 indexOfChunk(const Chunk *chunk) const;
192 quint32 keyToIndex(const SearchEntry &key) const;
193
194 enum class CompareMode {
195 nameOnly,
196 nameAndValue
197 };
198
199 static std::vector<HeaderField>::const_iterator findInStaticPart(const HeaderField &field, CompareMode mode);
200
201 mutable QByteArray dummyDst;
202
203 Q_DISABLE_COPY_MOVE(FieldLookupTable)
204};
205
206}
207
208QT_END_NAMESPACE
209
210#endif
211

source code of qtbase/src/network/access/http2/hpacktable_p.h