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 | |
48 | IdentifierHashData::IdentifierHashData(IdentifierTable *table, int numBits) |
49 | : size(0) |
50 | , numBits(numBits) |
51 | , identifierTable(table) |
52 | { |
53 | refCount.storeRelaxed(newValue: 1); |
54 | alloc = qPrimeForNumBits(numBits); |
55 | entries = (IdentifierHashEntry *)malloc(size: alloc*sizeof(IdentifierHashEntry)); |
56 | memset(s: entries, c: 0, n: alloc*sizeof(IdentifierHashEntry)); |
57 | identifierTable->addIdentifierHash(h: this); |
58 | } |
59 | |
60 | IdentifierHashData::IdentifierHashData(IdentifierHashData *other) |
61 | : size(other->size) |
62 | , numBits(other->numBits) |
63 | , identifierTable(other->identifierTable) |
64 | { |
65 | refCount.storeRelaxed(newValue: 1); |
66 | alloc = other->alloc; |
67 | entries = (IdentifierHashEntry *)malloc(size: alloc*sizeof(IdentifierHashEntry)); |
68 | memcpy(dest: entries, src: other->entries, n: alloc*sizeof(IdentifierHashEntry)); |
69 | identifierTable->addIdentifierHash(h: this); |
70 | } |
71 | |
72 | IdentifierHashData::~IdentifierHashData() { |
73 | free(ptr: entries); |
74 | if (identifierTable) |
75 | identifierTable->removeIdentifierHash(h: this); |
76 | } |
77 | |
78 | IdentifierHash::IdentifierHash(ExecutionEngine *engine) |
79 | { |
80 | d = new IdentifierHashData(engine->identifierTable, 3); |
81 | } |
82 | |
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 | |
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(numBits: d->numBits); |
104 | IdentifierHashEntry *newEntries = (IdentifierHashEntry *)malloc(size: newAlloc * sizeof(IdentifierHashEntry)); |
105 | memset(s: newEntries, c: 0, n: 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(ptr: 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 | |
133 | 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 | |
150 | const IdentifierHashEntry *IdentifierHash::lookup(const QString &str) const |
151 | { |
152 | if (!d) |
153 | return nullptr; |
154 | |
155 | PropertyKey id = d->identifierTable->asPropertyKey(s: str); |
156 | return lookup(identifier: id); |
157 | } |
158 | |
159 | 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(identifier: id); |
166 | return lookup(str: str->toQString()); |
167 | } |
168 | |
169 | const PropertyKey IdentifierHash::toIdentifier(const QString &str) const |
170 | { |
171 | Q_ASSERT(d); |
172 | return d->identifierTable->asPropertyKey(s: str); |
173 | } |
174 | |
175 | const PropertyKey IdentifierHash::toIdentifier(Heap::String *str) const |
176 | { |
177 | Q_ASSERT(d); |
178 | return d->identifierTable->asPropertyKey(str); |
179 | } |
180 | |
181 | 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 | |
193 | 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 | |