OLD | NEW |
| (Empty) |
1 /* | |
2 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2013 Apple Inc. All rights reserv
ed. | |
3 * Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com> | |
4 * Copyright (C) 2012 Google Inc. All rights reserved. | |
5 * | |
6 * This library is free software; you can redistribute it and/or | |
7 * modify it under the terms of the GNU Library General Public | |
8 * License as published by the Free Software Foundation; either | |
9 * version 2 of the License, or (at your option) any later version. | |
10 * | |
11 * This library is distributed in the hope that it will be useful, | |
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 * Library General Public License for more details. | |
15 * | |
16 * You should have received a copy of the GNU Library General Public License | |
17 * along with this library; see the file COPYING.LIB. If not, write to | |
18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | |
19 * Boston, MA 02110-1301, USA. | |
20 * | |
21 */ | |
22 | |
23 #include "config.h" | |
24 | |
25 #include "AtomicString.h" | |
26 | |
27 #include "StringHash.h" | |
28 #include <wtf/HashSet.h> | |
29 #include <wtf/Threading.h> | |
30 #include <wtf/WTFThreadData.h> | |
31 #include <wtf/unicode/UTF8.h> | |
32 | |
33 #if USE(WEB_THREAD) | |
34 #include <wtf/MainThread.h> | |
35 #include <wtf/TCSpinLock.h> | |
36 #endif | |
37 | |
38 namespace WTF { | |
39 | |
40 using namespace Unicode; | |
41 | |
42 COMPILE_ASSERT(sizeof(AtomicString) == sizeof(String), atomic_string_and_string_
must_be_same_size); | |
43 | |
44 #if USE(WEB_THREAD) | |
45 class AtomicStringTableLocker : public SpinLockHolder { | |
46 WTF_MAKE_NONCOPYABLE(AtomicStringTableLocker); | |
47 | |
48 static SpinLock s_stringTableLock; | |
49 public: | |
50 AtomicStringTableLocker() | |
51 : SpinLockHolder(&s_stringTableLock) | |
52 { | |
53 } | |
54 }; | |
55 | |
56 SpinLock AtomicStringTableLocker::s_stringTableLock = SPINLOCK_INITIALIZER; | |
57 #else | |
58 | |
59 class AtomicStringTableLocker { | |
60 WTF_MAKE_NONCOPYABLE(AtomicStringTableLocker); | |
61 public: | |
62 AtomicStringTableLocker() { } | |
63 ~AtomicStringTableLocker() { } | |
64 }; | |
65 #endif // USE(WEB_THREAD) | |
66 | |
67 class AtomicStringTable { | |
68 WTF_MAKE_FAST_ALLOCATED; | |
69 public: | |
70 static AtomicStringTable* create(WTFThreadData& data) | |
71 { | |
72 #if USE(WEB_THREAD) | |
73 // On iOS, one AtomicStringTable is shared between the main UI thread an
d the WebThread. | |
74 static AtomicStringTable* sharedStringTable = new AtomicStringTable; | |
75 | |
76 bool currentThreadIsWebThread = isWebThread(); | |
77 if (currentThreadIsWebThread || isUIThread()) | |
78 data.m_atomicStringTable = sharedStringTable; | |
79 else | |
80 data.m_atomicStringTable = new AtomicStringTable; | |
81 | |
82 // We do the following so that its destruction happens only | |
83 // once - on the main UI thread. | |
84 if (!currentThreadIsWebThread) | |
85 data.m_atomicStringTableDestructor = AtomicStringTable::destroy; | |
86 #else | |
87 data.m_atomicStringTable = new AtomicStringTable; | |
88 data.m_atomicStringTableDestructor = AtomicStringTable::destroy; | |
89 #endif // USE(WEB_THREAD) | |
90 return data.m_atomicStringTable; | |
91 } | |
92 | |
93 HashSet<StringImpl*>& table() | |
94 { | |
95 return m_table; | |
96 } | |
97 | |
98 private: | |
99 static void destroy(AtomicStringTable* table) | |
100 { | |
101 HashSet<StringImpl*>::iterator end = table->m_table.end(); | |
102 for (HashSet<StringImpl*>::iterator iter = table->m_table.begin(); iter
!= end; ++iter) | |
103 (*iter)->setIsAtomic(false); | |
104 delete table; | |
105 } | |
106 | |
107 HashSet<StringImpl*> m_table; | |
108 }; | |
109 | |
110 static inline HashSet<StringImpl*>& stringTable() | |
111 { | |
112 // Once possible we should make this non-lazy (constructed in WTFThreadData'
s constructor). | |
113 WTFThreadData& data = wtfThreadData(); | |
114 AtomicStringTable* table = data.atomicStringTable(); | |
115 if (UNLIKELY(!table)) | |
116 table = AtomicStringTable::create(data); | |
117 return table->table(); | |
118 } | |
119 | |
120 template<typename T, typename HashTranslator> | |
121 static inline PassRefPtr<StringImpl> addToStringTable(const T& value) | |
122 { | |
123 AtomicStringTableLocker locker; | |
124 | |
125 HashSet<StringImpl*>::AddResult addResult = stringTable().add<T, HashTransla
tor>(value); | |
126 | |
127 // If the string is newly-translated, then we need to adopt it. | |
128 // The boolean in the pair tells us if that is so. | |
129 return addResult.isNewEntry ? adoptRef(*addResult.iterator) : *addResult.ite
rator; | |
130 } | |
131 | |
132 struct CStringTranslator { | |
133 static unsigned hash(const LChar* c) | |
134 { | |
135 return StringHasher::computeHashAndMaskTop8Bits(c); | |
136 } | |
137 | |
138 static inline bool equal(StringImpl* r, const LChar* s) | |
139 { | |
140 return WTF::equal(r, s); | |
141 } | |
142 | |
143 static void translate(StringImpl*& location, const LChar* const& c, unsigned
hash) | |
144 { | |
145 location = StringImpl::create(c).leakRef(); | |
146 location->setHash(hash); | |
147 location->setIsAtomic(true); | |
148 } | |
149 }; | |
150 | |
151 PassRefPtr<StringImpl> AtomicString::add(const LChar* c) | |
152 { | |
153 if (!c) | |
154 return 0; | |
155 if (!*c) | |
156 return StringImpl::empty(); | |
157 | |
158 return addToStringTable<const LChar*, CStringTranslator>(c); | |
159 } | |
160 | |
161 template<typename CharacterType> | |
162 struct HashTranslatorCharBuffer { | |
163 const CharacterType* s; | |
164 unsigned length; | |
165 }; | |
166 | |
167 typedef HashTranslatorCharBuffer<UChar> UCharBuffer; | |
168 struct UCharBufferTranslator { | |
169 static unsigned hash(const UCharBuffer& buf) | |
170 { | |
171 return StringHasher::computeHashAndMaskTop8Bits(buf.s, buf.length); | |
172 } | |
173 | |
174 static bool equal(StringImpl* const& str, const UCharBuffer& buf) | |
175 { | |
176 return WTF::equal(str, buf.s, buf.length); | |
177 } | |
178 | |
179 static void translate(StringImpl*& location, const UCharBuffer& buf, unsigne
d hash) | |
180 { | |
181 location = StringImpl::create8BitIfPossible(buf.s, buf.length).leakRef()
; | |
182 location->setHash(hash); | |
183 location->setIsAtomic(true); | |
184 } | |
185 }; | |
186 | |
187 template<typename CharacterType> | |
188 struct HashAndCharacters { | |
189 unsigned hash; | |
190 const CharacterType* characters; | |
191 unsigned length; | |
192 }; | |
193 | |
194 template<typename CharacterType> | |
195 struct HashAndCharactersTranslator { | |
196 static unsigned hash(const HashAndCharacters<CharacterType>& buffer) | |
197 { | |
198 ASSERT(buffer.hash == StringHasher::computeHashAndMaskTop8Bits(buffer.ch
aracters, buffer.length)); | |
199 return buffer.hash; | |
200 } | |
201 | |
202 static bool equal(StringImpl* const& string, const HashAndCharacters<Charact
erType>& buffer) | |
203 { | |
204 return WTF::equal(string, buffer.characters, buffer.length); | |
205 } | |
206 | |
207 static void translate(StringImpl*& location, const HashAndCharacters<Charact
erType>& buffer, unsigned hash) | |
208 { | |
209 location = StringImpl::create(buffer.characters, buffer.length).leakRef(
); | |
210 location->setHash(hash); | |
211 location->setIsAtomic(true); | |
212 } | |
213 }; | |
214 | |
215 struct HashAndUTF8Characters { | |
216 unsigned hash; | |
217 const char* characters; | |
218 unsigned length; | |
219 unsigned utf16Length; | |
220 }; | |
221 | |
222 struct HashAndUTF8CharactersTranslator { | |
223 static unsigned hash(const HashAndUTF8Characters& buffer) | |
224 { | |
225 return buffer.hash; | |
226 } | |
227 | |
228 static bool equal(StringImpl* const& string, const HashAndUTF8Characters& bu
ffer) | |
229 { | |
230 if (buffer.utf16Length != string->length()) | |
231 return false; | |
232 | |
233 // If buffer contains only ASCII characters UTF-8 and UTF16 length are t
he same. | |
234 if (buffer.utf16Length != buffer.length) { | |
235 const UChar* stringCharacters = string->characters(); | |
236 | |
237 return equalUTF16WithUTF8(stringCharacters, stringCharacters + strin
g->length(), buffer.characters, buffer.characters + buffer.length); | |
238 } | |
239 | |
240 if (string->is8Bit()) { | |
241 const LChar* stringCharacters = string->characters8(); | |
242 | |
243 for (unsigned i = 0; i < buffer.length; ++i) { | |
244 ASSERT(isASCII(buffer.characters[i])); | |
245 if (stringCharacters[i] != buffer.characters[i]) | |
246 return false; | |
247 } | |
248 | |
249 return true; | |
250 } | |
251 | |
252 const UChar* stringCharacters = string->characters16(); | |
253 | |
254 for (unsigned i = 0; i < buffer.length; ++i) { | |
255 ASSERT(isASCII(buffer.characters[i])); | |
256 if (stringCharacters[i] != buffer.characters[i]) | |
257 return false; | |
258 } | |
259 | |
260 return true; | |
261 } | |
262 | |
263 static void translate(StringImpl*& location, const HashAndUTF8Characters& bu
ffer, unsigned hash) | |
264 { | |
265 UChar* target; | |
266 RefPtr<StringImpl> newString = StringImpl::createUninitialized(buffer.ut
f16Length, target); | |
267 | |
268 bool isAllASCII; | |
269 const char* source = buffer.characters; | |
270 if (convertUTF8ToUTF16(&source, source + buffer.length, &target, target
+ buffer.utf16Length, &isAllASCII) != conversionOK) | |
271 ASSERT_NOT_REACHED(); | |
272 | |
273 if (isAllASCII) | |
274 newString = StringImpl::create(buffer.characters, buffer.length); | |
275 | |
276 location = newString.release().leakRef(); | |
277 location->setHash(hash); | |
278 location->setIsAtomic(true); | |
279 } | |
280 }; | |
281 | |
282 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length) | |
283 { | |
284 if (!s) | |
285 return 0; | |
286 | |
287 if (!length) | |
288 return StringImpl::empty(); | |
289 | |
290 UCharBuffer buffer = { s, length }; | |
291 return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer); | |
292 } | |
293 | |
294 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length, unsign
ed existingHash) | |
295 { | |
296 ASSERT(s); | |
297 ASSERT(existingHash); | |
298 | |
299 if (!length) | |
300 return StringImpl::empty(); | |
301 | |
302 HashAndCharacters<UChar> buffer = { existingHash, s, length }; | |
303 return addToStringTable<HashAndCharacters<UChar>, HashAndCharactersTranslato
r<UChar> >(buffer); | |
304 } | |
305 | |
306 PassRefPtr<StringImpl> AtomicString::add(const UChar* s) | |
307 { | |
308 if (!s) | |
309 return 0; | |
310 | |
311 unsigned length = 0; | |
312 while (s[length] != UChar(0)) | |
313 ++length; | |
314 | |
315 if (!length) | |
316 return StringImpl::empty(); | |
317 | |
318 UCharBuffer buffer = { s, length }; | |
319 return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer); | |
320 } | |
321 | |
322 struct SubstringLocation { | |
323 StringImpl* baseString; | |
324 unsigned start; | |
325 unsigned length; | |
326 }; | |
327 | |
328 struct SubstringTranslator { | |
329 static unsigned hash(const SubstringLocation& buffer) | |
330 { | |
331 return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->chara
cters() + buffer.start, buffer.length); | |
332 } | |
333 | |
334 static bool equal(StringImpl* const& string, const SubstringLocation& buffer
) | |
335 { | |
336 return WTF::equal(string, buffer.baseString->characters() + buffer.start
, buffer.length); | |
337 } | |
338 | |
339 static void translate(StringImpl*& location, const SubstringLocation& buffer
, unsigned hash) | |
340 { | |
341 location = StringImpl::create(buffer.baseString, buffer.start, buffer.le
ngth).leakRef(); | |
342 location->setHash(hash); | |
343 location->setIsAtomic(true); | |
344 } | |
345 }; | |
346 | |
347 PassRefPtr<StringImpl> AtomicString::add(StringImpl* baseString, unsigned start,
unsigned length) | |
348 { | |
349 if (!baseString) | |
350 return 0; | |
351 | |
352 if (!length || start >= baseString->length()) | |
353 return StringImpl::empty(); | |
354 | |
355 unsigned maxLength = baseString->length() - start; | |
356 if (length >= maxLength) { | |
357 if (!start) | |
358 return add(baseString); | |
359 length = maxLength; | |
360 } | |
361 | |
362 SubstringLocation buffer = { baseString, start, length }; | |
363 return addToStringTable<SubstringLocation, SubstringTranslator>(buffer); | |
364 } | |
365 | |
366 typedef HashTranslatorCharBuffer<LChar> LCharBuffer; | |
367 struct LCharBufferTranslator { | |
368 static unsigned hash(const LCharBuffer& buf) | |
369 { | |
370 return StringHasher::computeHashAndMaskTop8Bits(buf.s, buf.length); | |
371 } | |
372 | |
373 static bool equal(StringImpl* const& str, const LCharBuffer& buf) | |
374 { | |
375 return WTF::equal(str, buf.s, buf.length); | |
376 } | |
377 | |
378 static void translate(StringImpl*& location, const LCharBuffer& buf, unsigne
d hash) | |
379 { | |
380 location = StringImpl::create(buf.s, buf.length).leakRef(); | |
381 location->setHash(hash); | |
382 location->setIsAtomic(true); | |
383 } | |
384 }; | |
385 | |
386 typedef HashTranslatorCharBuffer<char> CharBuffer; | |
387 struct CharBufferFromLiteralDataTranslator { | |
388 static unsigned hash(const CharBuffer& buf) | |
389 { | |
390 return StringHasher::computeHashAndMaskTop8Bits(reinterpret_cast<const L
Char*>(buf.s), buf.length); | |
391 } | |
392 | |
393 static bool equal(StringImpl* const& str, const CharBuffer& buf) | |
394 { | |
395 return WTF::equal(str, buf.s, buf.length); | |
396 } | |
397 | |
398 static void translate(StringImpl*& location, const CharBuffer& buf, unsigned
hash) | |
399 { | |
400 location = StringImpl::createFromLiteral(buf.s, buf.length).leakRef(); | |
401 location->setHash(hash); | |
402 location->setIsAtomic(true); | |
403 } | |
404 }; | |
405 | |
406 PassRefPtr<StringImpl> AtomicString::add(const LChar* s, unsigned length) | |
407 { | |
408 if (!s) | |
409 return 0; | |
410 | |
411 if (!length) | |
412 return StringImpl::empty(); | |
413 | |
414 LCharBuffer buffer = { s, length }; | |
415 return addToStringTable<LCharBuffer, LCharBufferTranslator>(buffer); | |
416 } | |
417 | |
418 PassRefPtr<StringImpl> AtomicString::addFromLiteralData(const char* characters,
unsigned length) | |
419 { | |
420 ASSERT(characters); | |
421 ASSERT(length); | |
422 | |
423 CharBuffer buffer = { characters, length }; | |
424 return addToStringTable<CharBuffer, CharBufferFromLiteralDataTranslator>(buf
fer); | |
425 } | |
426 | |
427 PassRefPtr<StringImpl> AtomicString::addSlowCase(StringImpl* r) | |
428 { | |
429 if (!r->length()) | |
430 return StringImpl::empty(); | |
431 | |
432 AtomicStringTableLocker locker; | |
433 StringImpl* result = *stringTable().add(r).iterator; | |
434 if (result == r) | |
435 r->setIsAtomic(true); | |
436 ASSERT(!r->isStatic() || result->isStatic()); | |
437 return result; | |
438 } | |
439 | |
440 template<typename CharacterType> | |
441 static inline HashSet<StringImpl*>::iterator findString(const StringImpl* string
Impl) | |
442 { | |
443 HashAndCharacters<CharacterType> buffer = { stringImpl->existingHash(), stri
ngImpl->getCharacters<CharacterType>(), stringImpl->length() }; | |
444 return stringTable().find<HashAndCharacters<CharacterType>, HashAndCharacter
sTranslator<CharacterType> >(buffer); | |
445 } | |
446 | |
447 AtomicStringImpl* AtomicString::find(const StringImpl* stringImpl) | |
448 { | |
449 ASSERT(stringImpl); | |
450 ASSERT(stringImpl->existingHash()); | |
451 | |
452 if (!stringImpl->length()) | |
453 return static_cast<AtomicStringImpl*>(StringImpl::empty()); | |
454 | |
455 AtomicStringTableLocker locker; | |
456 HashSet<StringImpl*>::iterator iterator; | |
457 if (stringImpl->is8Bit()) | |
458 iterator = findString<LChar>(stringImpl); | |
459 else | |
460 iterator = findString<UChar>(stringImpl); | |
461 if (iterator == stringTable().end()) | |
462 return 0; | |
463 return static_cast<AtomicStringImpl*>(*iterator); | |
464 } | |
465 | |
466 void AtomicString::remove(StringImpl* r) | |
467 { | |
468 AtomicStringTableLocker locker; | |
469 stringTable().remove(r); | |
470 } | |
471 | |
472 AtomicString AtomicString::lower() const | |
473 { | |
474 // Note: This is a hot function in the Dromaeo benchmark. | |
475 StringImpl* impl = this->impl(); | |
476 if (UNLIKELY(!impl)) | |
477 return *this; | |
478 RefPtr<StringImpl> newImpl = impl->lower(); | |
479 if (LIKELY(newImpl == impl)) | |
480 return *this; | |
481 return AtomicString(newImpl); | |
482 } | |
483 | |
484 AtomicString AtomicString::fromUTF8Internal(const char* charactersStart, const c
har* charactersEnd) | |
485 { | |
486 HashAndUTF8Characters buffer; | |
487 buffer.characters = charactersStart; | |
488 buffer.hash = calculateStringHashAndLengthFromUTF8MaskingTop8Bits(characters
Start, charactersEnd, buffer.length, buffer.utf16Length); | |
489 | |
490 if (!buffer.hash) | |
491 return nullAtom; | |
492 | |
493 AtomicString atomicString; | |
494 atomicString.m_string = addToStringTable<HashAndUTF8Characters, HashAndUTF8C
haractersTranslator>(buffer); | |
495 return atomicString; | |
496 } | |
497 | |
498 #ifndef NDEBUG | |
499 void AtomicString::show() const | |
500 { | |
501 m_string.show(); | |
502 } | |
503 #endif | |
504 | |
505 } // namespace WTF | |
OLD | NEW |