/****************************************************************************
**
** 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