Revision control
Copy as Markdown
// Copyright (C) 2016 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
#include "qv4identifiertable_p.h"
#include "qv4symbol_p.h"
#include <private/qv4identifierhashdata_p.h>
#include <private/qprimefornumbits_p.h>
QT_BEGIN_NAMESPACE
namespace QV4 {
IdentifierTable::IdentifierTable(ExecutionEngine *engine, int numBits)
: engine(engine)
, size(0)
, numBits(numBits)
{
alloc = qPrimeForNumBits(numBits);
entriesByHash = (Heap::StringOrSymbol **)malloc(alloc*sizeof(Heap::StringOrSymbol *));
entriesById = (Heap::StringOrSymbol **)malloc(alloc*sizeof(Heap::StringOrSymbol *));
memset(entriesByHash, 0, alloc*sizeof(Heap::String *));
memset(entriesById, 0, alloc*sizeof(Heap::String *));
}
IdentifierTable::~IdentifierTable()
{
free(entriesByHash);
free(entriesById);
for (const auto &h : std::as_const(idHashes))
h->identifierTable = nullptr;
}
void IdentifierTable::addEntry(Heap::StringOrSymbol *str)
{
uint hash = str->hashValue();
if (str->subtype == Heap::String::StringType_ArrayIndex)
return;
str->identifier = PropertyKey::fromStringOrSymbol(engine, str);
bool grow = (alloc <= size*2);
if (grow) {
++numBits;
int newAlloc = qPrimeForNumBits(numBits);
Heap::StringOrSymbol **newEntries = (Heap::StringOrSymbol **)malloc(newAlloc*sizeof(Heap::String *));
memset(newEntries, 0, newAlloc*sizeof(Heap::StringOrSymbol *));
for (uint i = 0; i < alloc; ++i) {
Heap::StringOrSymbol *e = entriesByHash[i];
if (!e)
continue;
uint idx = e->stringHash % newAlloc;
while (newEntries[idx]) {
++idx;
idx %= newAlloc;
}
newEntries[idx] = e;
}
free(entriesByHash);
entriesByHash = newEntries;
newEntries = (Heap::StringOrSymbol **)malloc(newAlloc*sizeof(Heap::String *));
memset(newEntries, 0, newAlloc*sizeof(Heap::StringOrSymbol *));
for (uint i = 0; i < alloc; ++i) {
Heap::StringOrSymbol *e = entriesById[i];
if (!e)
continue;
uint idx = e->identifier.id() % newAlloc;
while (newEntries[idx]) {
++idx;
idx %= newAlloc;
}
newEntries[idx] = e;
}
free(entriesById);
entriesById = newEntries;
alloc = newAlloc;
}
uint idx = hash % alloc;
while (entriesByHash[idx]) {
++idx;
idx %= alloc;
}
entriesByHash[idx] = str;
idx = str->identifier.id() % alloc;
while (entriesById[idx]) {
++idx;
idx %= alloc;
}
entriesById[idx] = str;
++size;
}
Heap::String *IdentifierTable::insertString(const QString &s)
{
uint subtype;
uint hash = String::createHashValue(s.constData(), s.size(), &subtype);
if (subtype == Heap::String::StringType_ArrayIndex) {
Heap::String *str = engine->newString(s);
str->stringHash = hash;
str->subtype = subtype;
str->identifier = PropertyKey::fromArrayIndex(hash);
return str;
}
return resolveStringEntry(s, hash, subtype);
}
Heap::String *IdentifierTable::resolveStringEntry(const QString &s, uint hash, uint subtype)
{
uint idx = hash % alloc;
while (Heap::StringOrSymbol *e = entriesByHash[idx]) {
if (e->stringHash == hash && e->toQString() == s)
return static_cast<Heap::String *>(e);
++idx;
idx %= alloc;
}
Heap::String *str = engine->newString(s);
str->stringHash = hash;
str->subtype = subtype;
addEntry(str);
return str;
}
Heap::Symbol *IdentifierTable::insertSymbol(const QString &s)
{
Q_ASSERT(s.at(0) == QLatin1Char('@'));
uint subtype;
uint hash = String::createHashValue(s.constData(), s.size(), &subtype);
uint idx = hash % alloc;
while (Heap::StringOrSymbol *e = entriesByHash[idx]) {
if (e->stringHash == hash && e->toQString() == s)
return static_cast<Heap::Symbol *>(e);
++idx;
idx %= alloc;
}
Heap::Symbol *str = Symbol::create(engine, s);
str->stringHash = hash;
str->subtype = subtype;
addEntry(str);
return str;
}
PropertyKey IdentifierTable::asPropertyKeyImpl(const Heap::String *str)
{
if (str->identifier.isValid())
return str->identifier;
uint hash = str->hashValue();
if (str->subtype == Heap::String::StringType_ArrayIndex) {
str->identifier = PropertyKey::fromArrayIndex(hash);
return str->identifier;
}
uint idx = hash % alloc;
while (Heap::StringOrSymbol *e = entriesByHash[idx]) {
if (e->stringHash == hash && e->toQString() == str->toQString()) {
str->identifier = e->identifier;
QV4::WriteBarrier::markCustom(engine, [&](QV4::MarkStack *stack) {
e->identifier.asStringOrSymbol()->mark(stack);
});
return e->identifier;
}
++idx;
idx %= alloc;
}
addEntry(const_cast<QV4::Heap::String *>(str));
return str->identifier;
}
Heap::StringOrSymbol *IdentifierTable::resolveId(PropertyKey i) const
{
if (i.isArrayIndex())
return engine->newString(QString::number(i.asArrayIndex()));
if (!i.isValid())
return nullptr;
uint idx = i.id() % alloc;
while (1) {
Heap::StringOrSymbol *e = entriesById[idx];
if (!e || e->identifier == i)
return e;
++idx;
idx %= alloc;
}
}
Heap::String *IdentifierTable::stringForId(PropertyKey i) const
{
Heap::StringOrSymbol *s = resolveId(i);
Q_ASSERT(s && s->internalClass->vtable->isString);
return static_cast<Heap::String *>(s);
}
Heap::Symbol *IdentifierTable::symbolForId(PropertyKey i) const
{
Heap::StringOrSymbol *s = resolveId(i);
Q_ASSERT(!s || !s->internalClass->vtable->isString);
return static_cast<Heap::Symbol *>(s);
}
void IdentifierTable::markObjects(MarkStack *markStack) const
{
for (const auto &h : idHashes)
h->markObjects(markStack);
}
void IdentifierTable::sweep()
{
int freed = 0;
Heap::StringOrSymbol **newTable = (Heap::StringOrSymbol **)malloc(alloc*sizeof(Heap::String *));
memset(newTable, 0, alloc*sizeof(Heap::StringOrSymbol *));
memset(entriesById, 0, alloc*sizeof(Heap::StringOrSymbol *));
for (uint i = 0; i < alloc; ++i) {
Heap::StringOrSymbol *e = entriesByHash[i];
if (!e)
continue;
if (!e->isMarked()) {
++freed;
continue;
}
uint idx = e->hashValue() % alloc;
while (newTable[idx]) {
++idx;
if (idx == alloc)
idx = 0;
}
newTable[idx] = e;
idx = e->identifier.id() % alloc;
while (entriesById[idx]) {
++idx;
if (idx == alloc)
idx = 0;
}
entriesById[idx] = e;
}
free(entriesByHash);
entriesByHash = newTable;
size -= freed;
}
PropertyKey IdentifierTable::asPropertyKey(const QString &s,
IdentifierTable::KeyConversionBehavior conversionBehvior)
{
uint subtype;
uint hash = String::createHashValue(s.constData(), s.size(), &subtype);
if (subtype == Heap::String::StringType_ArrayIndex) {
if (Q_UNLIKELY(conversionBehvior == ForceConversionToId))
hash = String::createHashValueDisallowingArrayIndex(s.constData(), s.size(), &subtype);
else
return PropertyKey::fromArrayIndex(hash);
}
return resolveStringEntry(s, hash, subtype)->identifier;
}
}
QT_END_NAMESPACE