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