qstringhash_p.h

Go to the documentation of this file.

// Copyright (C) 2020 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
// Qt-Security score:significant
 
#ifndef QSTRINGHASH_P_H
#define QSTRINGHASH_P_H
 
//
//  W A R N I N G
//  -------------
//
// This file is not part of the Qt API.  It exists purely as an
// implementation detail.  This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.
//
 
#include <private/qhashedstring_p.h>
#include <private/qprimefornumbits_p.h>
 
#include <QtCore/qbytearray.h>
#include <QtCore/qstring.h>
#include <QtCore/qtaggedpointer.h>
 
QT_BEGIN_NAMESPACE
 
static inline QString::DataPointer &mutableStringData(const QHashedString &key)
{
    return const_cast<QHashedString &>(key).data_ptr();
}
 
class QStringHashData;
class QStringHashNode
{
public:
    QStringHashNode()
    {
    }
 
    QStringHashNode(const QHashedString &key)
    : length(int(key.size())), hash(key.hash()), symbolId(0)
    , arrayData(mutableStringData(key).d_ptr())
    , strData(mutableStringData(key).data())
    {
        Q_ASSERT(key.size() <= std::numeric_limits<int>::max());
        if (arrayData)
            arrayData->ref();
        setQString(true);
    }
 
    QStringHashNode(const QHashedCStringRef &key)
    : length(key.length()), hash(key.hash()), symbolId(0), ckey(key.constData())
    {
    }
 
    QStringHashNode(const QStringHashNode &o)
    : length(o.length), hash(o.hash), symbolId(o.symbolId), arrayData(o.arrayData)
    {
        setQString(o.isQString());
        if (isQString()) {
            strData = o.strData;
            if (arrayData)
                arrayData->ref();
        } else {
            ckey = o.ckey;
        }
    }
 
    ~QStringHashNode()
    {
        if (isQString() && arrayData && !arrayData->deref())
            QTypedArrayData<char16_t>::deallocate(arrayData);
    }
 
    enum Tag {
        NodeIsCString,
        NodeIsQString
    };
 
    QTaggedPointer<QStringHashNode, Tag> next;
 
    qint32 length = 0;
    quint32 hash = 0;
    quint32 symbolId = 0;
 
    QTypedArrayData<char16_t> *arrayData = nullptr;
    union {
        const char *ckey = nullptr;
        char16_t *strData;
    };
 
    inline QHashedString key() const
    {
        if (isQString()) {
            if (arrayData)
                arrayData->ref();
            return QHashedString(QString(QStringPrivate(arrayData, strData, length)), hash);
        }
 
        return QHashedString(QString::fromLatin1(ckey, length), hash);
    }
 
    bool isQString() const { return next.tag() == NodeIsQString; }
    void setQString(bool v) { if (v) next.setTag(NodeIsQString); else next.setTag(NodeIsCString); }
 
    inline qsizetype size() const { return length; }
    inline const char *cStrData() const { return ckey; }
    inline const char16_t *utf16Data() const { return strData; }
 
    inline bool equals(const QV4::Value &string) const {
        QString s = string.toQStringNoThrow();
        if (isQString()) {
            return QStringView(utf16Data(), length) == s;
        } else {
            return QLatin1String(cStrData(), length) == s;
        }
    }
 
    inline bool equals(const QV4::String *string) const {
        if (length != string->d()->length() || hash != string->hashValue())
                return false;
        if (isQString()) {
            return QStringView(utf16Data(), length) == string->toQString();
        } else {
            return QLatin1String(cStrData(), length) == string->toQString();
        }
    }
 
    inline bool equals(const QHashedStringRef &string) const {
        return length == string.length() &&
               hash == string.hash() &&
               (isQString()? string == QStringView {utf16Data(), length}:
                            QHashedString::compare(string.constData(), cStrData(), length));
    }
 
    inline bool equals(const QHashedCStringRef &string) const {
        return length == string.length() &&
               hash == string.hash() &&
               (isQString()?QHashedString::compare((const QChar *)utf16Data(), string.constData(), length):
                            QHashedString::compare(string.constData(), cStrData(), length));
    }
};
 
class QStringHashData
{
    Q_DISABLE_COPY_MOVE(QStringHashData)
public:
    QStringHashData() = default;
    ~QStringHashData() = default;
 
    /*
        A QHash has initially around pow(2, MinNumBits) buckets. For
        example, if MinNumBits is 4, it has 17 buckets.
    */
    enum { MinNumBits = 4 };
 
    QStringHashNode **buckets = nullptr; // life cycle managed by QStringHash
    int numBuckets = 0;
    int size = 0;
    short numBits = 0;
 
    template<typename StringHash>
    struct IteratorData {
        IteratorData(QStringHashNode *n = nullptr, StringHash *p = nullptr) : n(n), p(p) {}
 
        template<typename OtherData>
        IteratorData(const OtherData &other) : n(other.n), p(other.p) {}
 
        QStringHashNode *n;
        StringHash *p;
    };
 
    void rehashToBits(short bits)
    {
        numBits = qMax(short(MinNumBits), bits);
 
        int nb = qPrimeForNumBits(numBits);
        if (nb == numBuckets && buckets)
            return;
 
        QStringHashNode **newBuckets = new QStringHashNode *[nb];
        ::memset(newBuckets, 0, sizeof(QStringHashNode *) * nb);
 
        // Preserve the existing order within buckets so that items with the
        // same key will retain the same find/findNext order
        for (int i = 0; i < numBuckets; ++i) {
            QStringHashNode *bucket = buckets[i];
            if (bucket)
                rehashNode(newBuckets, nb, bucket);
        }
 
        delete [] buckets;
        buckets = newBuckets;
        numBuckets = nb;
    }
 
    void rehashToSize(int size)
    {
        short bits = qMax(short(MinNumBits), numBits);
        while (qPrimeForNumBits(bits) < size)
            bits++;
 
        if (bits > numBits)
            rehashToBits(bits);
    }
 
    void rehashNode(QStringHashNode **newBuckets, int nb, QStringHashNode *node)
    {
        QStringHashNode *next = node->next.data();
        if (next)
            rehashNode(newBuckets, nb, next);
 
        int bucket = node->hash % nb;
        node->next = newBuckets[bucket];
        newBuckets[bucket] = node;
    }
};
 
// For a supplied key type, in what form do we need to keep a hashed version?
template<typename T>
struct HashedForm {};
 
template<> struct HashedForm<QString> { typedef QHashedString Type; };
template<> struct HashedForm<QStringView> { typedef QHashedStringRef Type; };
template<> struct HashedForm<QHashedString> { typedef const QHashedString &Type; };
template<> struct HashedForm<QV4::String *> { typedef const QV4::String *Type; };
template<> struct HashedForm<const QV4::String *> { typedef const QV4::String *Type; };
template<> struct HashedForm<QHashedStringRef> { typedef const QHashedStringRef &Type; };
template<> struct HashedForm<QLatin1String> { typedef QHashedCStringRef Type; };
template<> struct HashedForm<QHashedCStringRef> { typedef const QHashedCStringRef &Type; };
 
class QStringHashBase
{
public:
    static HashedForm<QString>::Type hashedString(const QString &s) { return QHashedString(s);}
    static HashedForm<QStringView>::Type hashedString(QStringView s)
    {
        Q_ASSERT(s.size() <= std::numeric_limits<int>::max());
        return QHashedStringRef(s.constData(), int(s.size()));
    }
    static HashedForm<QHashedString>::Type hashedString(const QHashedString &s) { return s; }
    static HashedForm<QV4::String *>::Type hashedString(QV4::String *s) { return s; }
    static HashedForm<const QV4::String *>::Type hashedString(const QV4::String *s) { return s; }
    static HashedForm<QHashedStringRef>::Type hashedString(const QHashedStringRef &s) { return s; }
 
    static HashedForm<QLatin1StringView>::Type hashedString(QLatin1StringView s)
    {
        Q_ASSERT(s.size() <= std::numeric_limits<int>::max());
        return QHashedCStringRef(s.data(), int(s.size()));
    }
    static HashedForm<QHashedCStringRef>::Type hashedString(const QHashedCStringRef &s) { return s; }
 
    static const QString &toQString(const QString &s) { return s; }
    static const QString &toQString(const QHashedString &s) { return s; }
    static QString toQString(const QV4::String *s) { return s->toQString(); }
    static QString toQString(const QHashedStringRef &s) { return s.toString(); }
 
    static QString toQString(const QLatin1String &s) { return QString(s); }
    static QString toQString(const QHashedCStringRef &s) { return s.toUtf16(); }
 
    static inline quint32 hashOf(const QHashedStringRef &s) { return s.hash(); }
    static inline quint32 hashOf(QV4::String *s) { return s->hashValue(); }
    static inline quint32 hashOf(const QV4::String *s) { return s->hashValue(); }
 
    template<typename K>
    static inline quint32 hashOf(const K &key) { return hashedString(key).hash(); }
};
 
template<class T>
class QStringHash : public QStringHashBase
{
public:
    typedef QHashedString key_type;
    typedef T mapped_type;
 
    using MutableIteratorData = QStringHashData::IteratorData<QStringHash<T>>;
    using ConstIteratorData = QStringHashData::IteratorData<const QStringHash<T>>;
 
    struct Node : public QStringHashNode {
        Node(const QHashedString &key, const T &value) : QStringHashNode(key), value(value) {}
        Node(const QHashedCStringRef &key, const T &value) : QStringHashNode(key), value(value) {}
        Node(const Node &o) : QStringHashNode(o), value(o.value) {}
        Node() {}
        T value;
    };
    struct NewedNode : public Node {
        NewedNode(const QHashedString &key, const T &value) : Node(key, value), nextNewed(nullptr) {}
        NewedNode(const QHashedCStringRef &key, const T &value) : Node(key, value), nextNewed(nullptr) {}
        NewedNode(const Node &o) : Node(o), nextNewed(nullptr) {}
        NewedNode *nextNewed;
    };
    struct ReservedNodePool
    {
        ReservedNodePool() : nodes(nullptr) {}
        ~ReservedNodePool() { delete [] nodes; }
        int count = 0;
        int used = 0;
        Node *nodes;
    };
 
    QStringHashData data;
    NewedNode *newedNodes;
    ReservedNodePool *nodePool;
 
    template<typename K>
    inline Node *findNode(const K &) const;
 
    inline Node *createNode(const Node &o);
 
    template<typename K>
    inline Node *createNode(const K &, const T &);
 
    inline Node *insertNode(Node *, quint32);
 
    inline void initializeNode(Node *, const QHashedString &key);
    inline void initializeNode(Node *, const QHashedCStringRef &key);
 
    template<typename K>
    inline Node *takeNode(const K &key, const T &value);
 
    inline Node *takeNode(const Node &o);
 
    inline void copy(const QStringHash<T> &);
 
    void copyNode(const QStringHashNode *otherNode);
 
    template<typename StringHash, typename Data>
    static inline Data iterateFirst(StringHash *self);
 
    template<typename Data>
    static inline Data iterateNext(const Data &);
 
public:
    inline QStringHash();
    inline QStringHash(const QStringHash &);
    inline ~QStringHash();
 
    QStringHash &operator=(const QStringHash<T> &);
 
    void copyAndReserve(const QStringHash<T> &other, int additionalReserve);
 
    inline bool isEmpty() const;
    inline void clear();
    inline int count() const;
 
    inline int numBuckets() const;
 
    template<typename Data, typename Value>
    class Iterator {
    public:
        inline Iterator() = default;
        inline Iterator(const Data &d) : d(d) {}
 
        inline Iterator &operator++()
        {
            d = QStringHash<T>::iterateNext(d);
            return *this;
        }
 
        inline bool operator==(const Iterator &o) const { return d.n == o.d.n; }
        inline bool operator!=(const Iterator &o) const { return d.n != o.d.n; }
 
        template<typename K>
        inline bool equals(const K &key) const { return d.n->equals(key); }
 
        inline QHashedString key() const { return static_cast<Node *>(d.n)->key(); }
        inline Value &value() const { return static_cast<Node *>(d.n)->value; }
        inline Value &operator*() const { return static_cast<Node *>(d.n)->value; }
 
        Node *node() const { return static_cast<Node *>(d.n); }
    private:
        Data d;
    };
 
    using MutableIterator = Iterator<MutableIteratorData, T>;
    using ConstIterator = Iterator<ConstIteratorData, const T>;
 
    template<typename K>
    inline void insert(const K &, const T &);
    inline void insert(const MutableIterator &);
    inline void insert(const ConstIterator &);
 
    template<typename K>
    inline T *value(const K &) const;
    inline T *value(const QV4::String *string) const;
    inline T *value(const MutableIterator &) const;
    inline T *value(const ConstIterator &) const;
 
    template<typename K>
    inline bool contains(const K &) const;
 
    template<typename K>
    inline T &operator[](const K &);
 
    inline MutableIterator begin();
    inline ConstIterator begin() const;
    inline ConstIterator constBegin() const { return begin(); }
 
    inline MutableIterator end();
    inline ConstIterator end() const;
    inline ConstIterator constEnd() const { return end(); }
 
    template<typename K>
    inline MutableIterator find(const K &);
 
    template<typename K>
    inline ConstIterator find(const K &) const;
 
    inline void reserve(int);
};
 
template<class T>
QStringHash<T>::QStringHash()
: newedNodes(nullptr), nodePool(nullptr)
{
}
 
template<class T>
QStringHash<T>::QStringHash(const QStringHash<T> &other)
: newedNodes(nullptr), nodePool(nullptr)
{
    data.numBits = other.data.numBits;
    data.size = other.data.size;
    reserve(other.count());
    copy(other);
}
 
template<class T>
QStringHash<T> &QStringHash<T>::operator=(const QStringHash<T> &other)
{
    if (&other == this)
        return *this;
 
    clear();
 
    data.numBits = other.data.numBits;
    data.size = other.data.size;
    reserve(other.count());
    copy(other);
 
    return *this;
}
 
template<class T>
void QStringHash<T>::copyAndReserve(const QStringHash<T> &other, int additionalReserve)
{
    clear();
    data.numBits = other.data.numBits;
    reserve(other.count() + additionalReserve);
    copy(other);
}
 
template<class T>
QStringHash<T>::~QStringHash()
{
    clear();
}
 
template<class T>
void QStringHash<T>::clear()
{
    // Delete the individually allocated nodes
    NewedNode *n = newedNodes;
    while (n) {
        NewedNode *c = n;
        n = c->nextNewed;
        delete c;
    }
    // Delete the pool allocated nodes
    if (nodePool) delete nodePool;
    delete [] data.buckets;
 
    data.buckets = nullptr;
    data.numBuckets = 0;
    data.numBits = 0;
    data.size = 0;
 
    newedNodes = nullptr;
    nodePool = nullptr;
}
 
template<class T>
bool QStringHash<T>::isEmpty() const
{
    return data.size== 0;
}
 
template<class T>
int QStringHash<T>::count() const
{
    return data.size;
}
 
template<class T>
int QStringHash<T>::numBuckets() const
{
    return data.numBuckets;
}
 
template<class T>
void QStringHash<T>::initializeNode(Node *node, const QHashedString &key)
{
    node->length = key.size();
    node->hash = key.hash();
    node->arrayData = mutableStringData(key).d_ptr();
    node->strData = mutableStringData(key).data();
    if (node->arrayData)
        node->arrayData->ref();
    node->setQString(true);
}
 
template<class T>
void QStringHash<T>::initializeNode(Node *node, const QHashedCStringRef &key)
{
    node->length = key.length();
    node->hash = key.hash();
    node->ckey = key.constData();
}
 
template<class T>
template<class K>
typename QStringHash<T>::Node *QStringHash<T>::takeNode(const K &key, const T &value)
{
    if (nodePool && nodePool->used != nodePool->count) {
        Node *rv = nodePool->nodes + nodePool->used++;
        initializeNode(rv, hashedString(key));
        rv->value = value;
        return rv;
    } else {
        NewedNode *rv = new NewedNode(hashedString(key), value);
        rv->nextNewed = newedNodes;
        newedNodes = rv;
        return rv;
    }
}
 
template<class T>
typename QStringHash<T>::Node *QStringHash<T>::takeNode(const Node &o)
{
    if (nodePool && nodePool->used != nodePool->count) {
        Node *rv = nodePool->nodes + nodePool->used++;
        rv->length = o.length;
        rv->hash = o.hash;
        rv->arrayData = o.arrayData;
        if (o.isQString()) {
            rv->strData = o.strData;
            rv->setQString(true);
            if (rv->arrayData)
                rv->arrayData->ref();
        } else {
            rv->ckey = o.ckey;
        }
        rv->symbolId = o.symbolId;
        rv->value = o.value;
        return rv;
    } else {
        NewedNode *rv = new NewedNode(o);
        rv->nextNewed = newedNodes;
        newedNodes = rv;
        return rv;
    }
}
 
template<class T>
void QStringHash<T>::copyNode(const QStringHashNode *otherNode)
{
    // Copy the predecessor before the successor
    QStringHashNode *next = otherNode->next.data();
    if (next)
        copyNode(next);
 
    Node *mynode = takeNode(*(const Node *)otherNode);
    int bucket = mynode->hash % data.numBuckets;
    mynode->next = data.buckets[bucket];
    data.buckets[bucket] = mynode;
}
 
template<class T>
void QStringHash<T>::copy(const QStringHash<T> &other)
{
    Q_ASSERT(data.size == 0);
 
    data.size = other.data.size;
 
    // Ensure buckets array is created
    data.rehashToBits(data.numBits);
 
    // Preserve the existing order within buckets
    for (int i = 0; i < other.data.numBuckets; ++i) {
        QStringHashNode *bucket = other.data.buckets[i];
        if (bucket)
            copyNode(bucket);
    }
}
 
template<class T>
template<typename Data>
Data QStringHash<T>::iterateNext(const Data &d)
{
    auto *This = d.p;
    Node *node = (Node *)d.n;
 
    if (This->nodePool && node >= This->nodePool->nodes &&
        node < (This->nodePool->nodes + This->nodePool->used)) {
        node--;
        if (node < This->nodePool->nodes)
            node = nullptr;
    } else {
        NewedNode *nn = (NewedNode *)node;
        node = nn->nextNewed;
 
        if (node == nullptr && This->nodePool && This->nodePool->used)
            node = This->nodePool->nodes + This->nodePool->used - 1;
    }
 
    Data rv;
    rv.n = node;
    rv.p = d.p;
    return rv;
}
 
template<class T>
template<typename StringHash, typename Data>
Data QStringHash<T>::iterateFirst(StringHash *self)
{
    typename StringHash::Node *n = nullptr;
    if (self->newedNodes)
        n = self->newedNodes;
    else if (self->nodePool && self->nodePool->used)
        n = self->nodePool->nodes + self->nodePool->used - 1;
 
    Data rv;
    rv.n = n;
    rv.p = self;
    return rv;
}
 
template<class T>
typename QStringHash<T>::Node *QStringHash<T>::createNode(const Node &o)
{
    Node *n = takeNode(o);
    return insertNode(n, n->hash);
}
 
template<class T>
template<class K>
typename QStringHash<T>::Node *QStringHash<T>::createNode(const K &key, const T &value)
{
    Node *n = takeNode(key, value);
    return insertNode(n, hashOf(key));
}
 
template<class T>
typename QStringHash<T>::Node *QStringHash<T>::insertNode(Node *n, quint32 hash)
{
    if (data.size >= data.numBuckets)
        data.rehashToBits(data.numBits + 1);
 
    int bucket = hash % data.numBuckets;
    n->next = data.buckets[bucket];
    data.buckets[bucket] = n;
 
    data.size++;
 
    return n;
}
 
template<class T>
template<class K>
void QStringHash<T>::insert(const K &key, const T &value)
{
    Node *n = findNode(key);
    if (n)
        n->value = value;
    else
        createNode(key, value);
}
 
template<class T>
void QStringHash<T>::insert(const MutableIterator &iter)
{
    insert(iter.key(), iter.value());
}
 
template<class T>
void QStringHash<T>::insert(const ConstIterator &iter)
{
    insert(iter.key(), iter.value());
}
 
template<class T>
template<class K>
typename QStringHash<T>::Node *QStringHash<T>::findNode(const K &key) const
{
    QStringHashNode *node = data.numBuckets?data.buckets[hashOf(key) % data.numBuckets]:nullptr;
 
    typename HashedForm<K>::Type hashedKey(hashedString(key));
    while (node && !node->equals(hashedKey))
        node = node->next.data();
 
    return (Node *)node;
}
 
template<class T>
template<class K>
T *QStringHash<T>::value(const K &key) const
{
    Node *n = findNode(key);
    return n?&n->value:nullptr;
}
 
template<typename T>
T *QStringHash<T>::value(const MutableIterator &iter) const
{
    return value(iter.node()->key());
}
 
template<class T>
T *QStringHash<T>::value(const ConstIterator &iter) const
{
    return value(iter.node()->key());
}
 
template<class T>
T *QStringHash<T>::value(const QV4::String *string) const
{
    Node *n = findNode(string);
    return n?&n->value:nullptr;
}
 
template<class T>
template<class K>
bool QStringHash<T>::contains(const K &key) const
{
    return nullptr != value(key);
}
 
template<class T>
template<class K>
T &QStringHash<T>::operator[](const K &key)
{
    Node *n = findNode(key);
    if (n) return n->value;
    else return createNode(key, T())->value;
}
 
template<class T>
void QStringHash<T>::reserve(int n)
{
    if (nodePool || 0 == n)
        return;
 
    nodePool = new ReservedNodePool;
    nodePool->count = n;
    nodePool->used = 0;
    nodePool->nodes = new Node[n];
 
    data.rehashToSize(n);
}
 
template<class T>
typename QStringHash<T>::MutableIterator QStringHash<T>::begin()
{
    return MutableIterator(iterateFirst<QStringHash<T>, MutableIteratorData>(this));
}
 
template<class T>
typename QStringHash<T>::ConstIterator QStringHash<T>::begin() const
{
    return ConstIterator(iterateFirst<const QStringHash<T>, ConstIteratorData>(this));
}
 
template<class T>
typename QStringHash<T>::MutableIterator QStringHash<T>::end()
{
    return MutableIterator();
}
 
template<class T>
typename QStringHash<T>::ConstIterator QStringHash<T>::end() const
{
    return ConstIterator();
}
 
template<class T>
template<class K>
typename QStringHash<T>::MutableIterator QStringHash<T>::find(const K &key)
{
    Node *n = findNode(key);
    return n ? MutableIterator(MutableIteratorData(n, this)) : MutableIterator();
}
 
template<class T>
template<class K>
typename QStringHash<T>::ConstIterator QStringHash<T>::find(const K &key) const
{
    Node *n = findNode(key);
    return n ? ConstIterator(ConstIteratorData(n, this)) : ConstIterator();
}
 
QT_END_NAMESPACE
 
#endif // QSTRINGHASH_P_H