diff options
Diffstat (limited to 'src/network/access/http2/hpacktable_p.h')
| -rw-r--r-- | src/network/access/http2/hpacktable_p.h | 237 |
1 files changed, 237 insertions, 0 deletions
diff --git a/src/network/access/http2/hpacktable_p.h b/src/network/access/http2/hpacktable_p.h new file mode 100644 index 0000000000..aaea89b986 --- /dev/null +++ b/src/network/access/http2/hpacktable_p.h @@ -0,0 +1,237 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtNetwork module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef HPACKTABLE_P_H +#define HPACKTABLE_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtCore/qbytearray.h> +#include <QtCore/qglobal.h> +#include <QtCore/qpair.h> + +#include <vector> +#include <memory> +#include <deque> +#include <set> + +QT_BEGIN_NAMESPACE + +namespace HPack +{ + +struct Q_AUTOTEST_EXPORT HeaderField +{ + HeaderField() + { + } + + HeaderField(const QByteArray &n, const QByteArray &v) + : name(n), + value(v) + { + } + + bool operator == (const HeaderField &rhs) const + { + return name == rhs.name && value == rhs.value; + } + + QByteArray name; + QByteArray value; +}; + +using HeaderSize = QPair<bool, quint32>; + +HeaderSize entry_size(const QByteArray &name, const QByteArray &value); + +inline HeaderSize entry_size(const HeaderField &entry) +{ + return entry_size(entry.name, entry.value); +} + +/* + Lookup table consists of two parts (HPACK, 2.3): + the immutable static table (pre-defined by HPACK's specs) + and dynamic table which is updated while + compressing/decompressing headers. + + Table must provide/implement: + 1. Fast random access - we read fields' indices from + HPACK's bit stream. + 2. FIFO for dynamic part - to push new items to the front + and evict them from the back (HPACK, 2.3.2). + 3. Fast lookup - encoder receives pairs of strings + (name|value) and it has to find an index for a pair + as the whole or for a name at least (if it's already + in either static or dynamic table). + + Static table is an immutable vector. + + Dynamic part is implemented in a way similar to std::deque - + it's a vector of pointers to chunks. Each chunk is a vector of + (name|value) pairs. Once allocated with a fixed size, chunk + never re-allocates its data, so entries' addresses do not change. + We add new chunks prepending them to the front of a vector, + in each chunk we fill (name|value) pairs starting from the back + of the chunk (this simplifies item eviction/FIFO). + Given a 'linear' index we can find a chunk number and + offset in this chunk - random access. + + Lookup in a static part is straightforward: + it's an (immutable) vector, data is sorted, + contains no duplicates, we use binary search comparing string values. + + To provide a lookup in dynamic table faster than a linear search, + we have an std::set of 'SearchEntries', where each entry contains: + - a pointer to a (name|value) pair (to compare + name|value strings). + - a pointer to a chunk containing this pair and + - an offset within this chunk - to calculate a + 'linear' index. + + Entries in a table can be duplicated (HPACK, 2.3.2), + if we evict an entry, we must update our index removing + the exactly right key, thus keys in this set are sorted + by name|value pairs first, and then by chunk index/offset + (so that NewSearchEntryKey < OldSearchEntry even if strings + are equal). +*/ + +class Q_AUTOTEST_EXPORT FieldLookupTable +{ +public: + enum + { + ChunkSize = 16, + DefaultSize = 4096 // Recommended by HTTP2. + }; + + FieldLookupTable(quint32 maxTableSize, bool useIndex); + + bool prependField(const QByteArray &name, const QByteArray &value); + void evictEntry(); + + quint32 numberOfEntries() const; + quint32 numberOfStaticEntries() const; + quint32 numberOfDynamicEntries() const; + quint32 dynamicDataSize() const; + void clearDynamicTable(); + + bool indexIsValid(quint32 index) const; + quint32 indexOf(const QByteArray &name, const QByteArray &value) const; + quint32 indexOf(const QByteArray &name) const; + bool field(quint32 index, QByteArray *name, QByteArray *value) const; + bool fieldName(quint32 index, QByteArray *dst) const; + bool fieldValue(quint32 index, QByteArray *dst) const; + + bool updateDynamicTableSize(quint32 size); + void setMaxDynamicTableSize(quint32 size); + +private: + // Table's maximum size is controlled + // by SETTINGS_HEADER_TABLE_SIZE (HTTP/2, 6.5.2). + quint32 maxTableSize; + // The tableCapacity is how many bytes the table + // can currently hold. It cannot exceed maxTableSize. + // It can be modified by a special message in + // the HPACK bit stream (HPACK, 6.3). + quint32 tableCapacity; + + using Chunk = std::vector<HeaderField>; + using ChunkPtr = std::unique_ptr<Chunk>; + std::deque<ChunkPtr> chunks; + using size_type = std::deque<ChunkPtr>::size_type; + + struct SearchEntry; + friend struct SearchEntry; + + struct SearchEntry + { + SearchEntry(); + SearchEntry(const HeaderField *f, const Chunk *c, + quint32 o, const FieldLookupTable *t); + + const HeaderField *field; + const Chunk *chunk; + const quint32 offset; + const FieldLookupTable *table; + + bool operator < (const SearchEntry &rhs) const; + }; + + bool useIndex; + std::set<SearchEntry> searchIndex; + + SearchEntry frontKey() const; + SearchEntry backKey() const; + + bool fieldAt(quint32 index, HeaderField *field) const; + + const HeaderField &front() const; + HeaderField &front(); + const HeaderField &back() const; + + quint32 nDynamic; + quint32 begin; + quint32 end; + quint32 dataSize; + + quint32 indexOfChunk(const Chunk *chunk) const; + quint32 keyToIndex(const SearchEntry &key) const; + + mutable QByteArray dummyDst; + + Q_DISABLE_COPY(FieldLookupTable); +}; + +} + +QT_END_NAMESPACE + +#endif |