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 QtQml 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 #include "qv4identifier_p.h"
40 #include "qv4identifiertable_p.h"
41 #include "qv4string_p.h"
42 #include <private/qprimefornumbits_p.h>
43
44 QT_BEGIN_NAMESPACE
45
46 namespace QV4 {
47
IdentifierHashData(IdentifierTable * table,int numBits)48 IdentifierHashData::IdentifierHashData(IdentifierTable *table, int numBits)
49 : size(0)
50 , numBits(numBits)
51 , identifierTable(table)
52 {
53 refCount.storeRelaxed(1);
54 alloc = qPrimeForNumBits(numBits);
55 entries = (IdentifierHashEntry *)malloc(alloc*sizeof(IdentifierHashEntry));
56 memset(entries, 0, alloc*sizeof(IdentifierHashEntry));
57 identifierTable->addIdentifierHash(this);
58 }
59
IdentifierHashData(IdentifierHashData * other)60 IdentifierHashData::IdentifierHashData(IdentifierHashData *other)
61 : size(other->size)
62 , numBits(other->numBits)
63 , identifierTable(other->identifierTable)
64 {
65 refCount.storeRelaxed(1);
66 alloc = other->alloc;
67 entries = (IdentifierHashEntry *)malloc(alloc*sizeof(IdentifierHashEntry));
68 memcpy(entries, other->entries, alloc*sizeof(IdentifierHashEntry));
69 identifierTable->addIdentifierHash(this);
70 }
71
~IdentifierHashData()72 IdentifierHashData::~IdentifierHashData() {
73 free(entries);
74 if (identifierTable)
75 identifierTable->removeIdentifierHash(this);
76 }
77
IdentifierHash(ExecutionEngine * engine)78 IdentifierHash::IdentifierHash(ExecutionEngine *engine)
79 {
80 d = new IdentifierHashData(engine->identifierTable, 3);
81 }
82
detach()83 void IdentifierHash::detach()
84 {
85 if (!d || d->refCount.loadAcquire() == 1)
86 return;
87 IdentifierHashData *newData = new IdentifierHashData(d);
88 if (d && !d->refCount.deref())
89 delete d;
90 d = newData;
91 }
92
93
addEntry(PropertyKey identifier)94 IdentifierHashEntry *IdentifierHash::addEntry(PropertyKey identifier)
95 {
96 Q_ASSERT(identifier.isStringOrSymbol());
97
98 // fill up to max 50%
99 bool grow = (d->alloc <= d->size*2);
100
101 if (grow) {
102 ++d->numBits;
103 int newAlloc = qPrimeForNumBits(d->numBits);
104 IdentifierHashEntry *newEntries = (IdentifierHashEntry *)malloc(newAlloc * sizeof(IdentifierHashEntry));
105 memset(newEntries, 0, newAlloc*sizeof(IdentifierHashEntry));
106 for (int i = 0; i < d->alloc; ++i) {
107 const IdentifierHashEntry &e = d->entries[i];
108 if (!e.identifier.isValid())
109 continue;
110 uint idx = e.identifier.id() % newAlloc;
111 while (newEntries[idx].identifier.isValid()) {
112 ++idx;
113 idx %= newAlloc;
114 }
115 newEntries[idx] = e;
116 }
117 free(d->entries);
118 d->entries = newEntries;
119 d->alloc = newAlloc;
120 }
121
122 uint idx = identifier.id() % d->alloc;
123 while (d->entries[idx].identifier.isValid()) {
124 Q_ASSERT(d->entries[idx].identifier != identifier);
125 ++idx;
126 idx %= d->alloc;
127 }
128 d->entries[idx].identifier = identifier;
129 ++d->size;
130 return d->entries + idx;
131 }
132
lookup(PropertyKey identifier) const133 const IdentifierHashEntry *IdentifierHash::lookup(PropertyKey identifier) const
134 {
135 if (!d || !identifier.isStringOrSymbol())
136 return nullptr;
137 Q_ASSERT(d->entries);
138
139 uint idx = identifier.id() % d->alloc;
140 while (1) {
141 if (!d->entries[idx].identifier.isValid())
142 return nullptr;
143 if (d->entries[idx].identifier == identifier)
144 return d->entries + idx;
145 ++idx;
146 idx %= d->alloc;
147 }
148 }
149
lookup(const QString & str) const150 const IdentifierHashEntry *IdentifierHash::lookup(const QString &str) const
151 {
152 if (!d)
153 return nullptr;
154
155 PropertyKey id = d->identifierTable->asPropertyKey(str);
156 return lookup(id);
157 }
158
lookup(String * str) const159 const IdentifierHashEntry *IdentifierHash::lookup(String *str) const
160 {
161 if (!d)
162 return nullptr;
163 PropertyKey id = d->identifierTable->asPropertyKey(str);
164 if (id.isValid())
165 return lookup(id);
166 return lookup(str->toQString());
167 }
168
toIdentifier(const QString & str) const169 const PropertyKey IdentifierHash::toIdentifier(const QString &str) const
170 {
171 Q_ASSERT(d);
172 return d->identifierTable->asPropertyKey(str);
173 }
174
toIdentifier(Heap::String * str) const175 const PropertyKey IdentifierHash::toIdentifier(Heap::String *str) const
176 {
177 Q_ASSERT(d);
178 return d->identifierTable->asPropertyKey(str);
179 }
180
findId(int value) const181 QString QV4::IdentifierHash::findId(int value) const
182 {
183 IdentifierHashEntry *e = d->entries;
184 IdentifierHashEntry *end = e + d->alloc;
185 while (e < end) {
186 if (e->identifier.isValid() && e->value == value)
187 return e->identifier.toQString();
188 ++e;
189 }
190 return QString();
191 }
192
markObjects(MarkStack * markStack) const193 void IdentifierHashData::markObjects(MarkStack *markStack) const
194 {
195 IdentifierHashEntry *e = entries;
196 IdentifierHashEntry *end = e + alloc;
197 while (e < end) {
198 if (Heap::Base *o = e->identifier.asStringOrSymbol())
199 o->mark(markStack);
200 ++e;
201 }
202 }
203
204
205 }
206
207 QT_END_NAMESPACE
208