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 quint32 dynamicDataCapacity() const;
129 quint32 maxDynamicDataCapacity() const;
130 void clearDynamicTable();
131
132 bool indexIsValid(quint32 index) const;
133 quint32 indexOf(const QByteArray &name, const QByteArray &value) const;
134 quint32 indexOf(const QByteArray &name) const;
135 bool field(quint32 index, QByteArray *name, QByteArray *value) const;
136 bool fieldName(quint32 index, QByteArray *dst) const;
137 bool fieldValue(quint32 index, QByteArray *dst) const;
138
139 bool updateDynamicTableSize(quint32 size);
140 void setMaxDynamicTableSize(quint32 size);
141
142 static const std::vector<HeaderField> &staticPart();
143
144private:
145 // Table's maximum size is controlled
146 // by SETTINGS_HEADER_TABLE_SIZE (HTTP/2, 6.5.2).
147 quint32 maxTableSize;
148 // The tableCapacity is how many bytes the table
149 // can currently hold. It cannot exceed maxTableSize.
150 // It can be modified by a special message in
151 // the HPACK bit stream (HPACK, 6.3).
152 quint32 tableCapacity;
153
154 using Chunk = std::vector<HeaderField>;
155 using ChunkPtr = std::unique_ptr<Chunk>;
156 std::deque<ChunkPtr> chunks;
157 using size_type = std::deque<ChunkPtr>::size_type;
158
159 struct SearchEntry;
160 friend struct SearchEntry;
161
162 struct SearchEntry
163 {
164 SearchEntry();
165 SearchEntry(const HeaderField *f, const Chunk *c,
166 quint32 o, const FieldLookupTable *t);
167
168 const HeaderField *field;
169 const Chunk *chunk;
170 const quint32 offset;
171 const FieldLookupTable *table;
172
173 bool operator < (const SearchEntry &rhs) const;
174 };
175
176 bool useIndex;
177 std::set<SearchEntry> searchIndex;
178
179 SearchEntry frontKey() const;
180 SearchEntry backKey() const;
181
182 bool fieldAt(quint32 index, HeaderField *field) const;
183
184 const HeaderField &front() const;
185 HeaderField &front();
186 const HeaderField &back() const;
187
188 quint32 nDynamic;
189 quint32 begin;
190 quint32 end;
191 quint32 dataSize;
192
193 quint32 indexOfChunk(const Chunk *chunk) const;
194 quint32 keyToIndex(const SearchEntry &key) const;
195
196 enum class CompareMode {
197 nameOnly,
198 nameAndValue
199 };
200
201 static std::vector<HeaderField>::const_iterator findInStaticPart(const HeaderField &field, CompareMode mode);
202
203 mutable QByteArray dummyDst;
204
205 Q_DISABLE_COPY_MOVE(FieldLookupTable)
206};
207
208}
209
210QT_END_NAMESPACE
211
212#endif
213

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