7bd3237468193334d6079c1bfe75cca808fc0f6b
[WebKit-https.git] / Source / WTF / wtf / text / AtomicString.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2013 Apple Inc. All rights reserved.
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 #include "AtomicString.h"
25
26 #include "AtomicStringTable.h"
27 #include "HashSet.h"
28 #include "IntegerToStringConversion.h"
29 #include "StringHash.h"
30 #include "Threading.h"
31 #include "WTFThreadData.h"
32 #include "dtoa.h"
33 #include <wtf/unicode/UTF8.h>
34
35 #if USE(WEB_THREAD)
36 #include "TCSpinLock.h"
37 #endif
38
39 namespace WTF {
40
41 using namespace Unicode;
42
43 static_assert(sizeof(AtomicString) == sizeof(String), "AtomicString and String must be same size!");
44
45 #if USE(WEB_THREAD)
46
47 class AtomicStringTableLocker : public SpinLockHolder {
48     WTF_MAKE_NONCOPYABLE(AtomicStringTableLocker);
49
50     static SpinLock s_stringTableLock;
51 public:
52     AtomicStringTableLocker()
53         : SpinLockHolder(&s_stringTableLock)
54     {
55     }
56 };
57
58 SpinLock AtomicStringTableLocker::s_stringTableLock = SPINLOCK_INITIALIZER;
59
60 #else
61
62 class AtomicStringTableLocker {
63     WTF_MAKE_NONCOPYABLE(AtomicStringTableLocker);
64 public:
65     AtomicStringTableLocker() { }
66 };
67
68 #endif // USE(WEB_THREAD)
69
70 static ALWAYS_INLINE HashSet<StringImpl*>& stringTable()
71 {
72     return wtfThreadData().atomicStringTable()->table();
73 }
74
75 template<typename T, typename HashTranslator>
76 static inline PassRefPtr<StringImpl> addToStringTable(const T& value)
77 {
78     AtomicStringTableLocker locker;
79
80     HashSet<StringImpl*>::AddResult addResult = stringTable().add<HashTranslator>(value);
81
82     // If the string is newly-translated, then we need to adopt it.
83     // The boolean in the pair tells us if that is so.
84     return addResult.isNewEntry ? adoptRef(*addResult.iterator) : *addResult.iterator;
85 }
86
87 struct CStringTranslator {
88     static unsigned hash(const LChar* c)
89     {
90         return StringHasher::computeHashAndMaskTop8Bits(c);
91     }
92
93     static inline bool equal(StringImpl* r, const LChar* s)
94     {
95         return WTF::equal(r, s);
96     }
97
98     static void translate(StringImpl*& location, const LChar* const& c, unsigned hash)
99     {
100         location = StringImpl::create(c).leakRef();
101         location->setHash(hash);
102         location->setIsAtomic(true);
103     }
104 };
105
106 PassRefPtr<StringImpl> AtomicString::add(const LChar* c)
107 {
108     if (!c)
109         return 0;
110     if (!*c)
111         return StringImpl::empty();
112
113     return addToStringTable<const LChar*, CStringTranslator>(c);
114 }
115
116 template<typename CharacterType>
117 struct HashTranslatorCharBuffer {
118     const CharacterType* s;
119     unsigned length;
120 };
121
122 typedef HashTranslatorCharBuffer<UChar> UCharBuffer;
123 struct UCharBufferTranslator {
124     static unsigned hash(const UCharBuffer& buf)
125     {
126         return StringHasher::computeHashAndMaskTop8Bits(buf.s, buf.length);
127     }
128
129     static bool equal(StringImpl* const& str, const UCharBuffer& buf)
130     {
131         return WTF::equal(str, buf.s, buf.length);
132     }
133
134     static void translate(StringImpl*& location, const UCharBuffer& buf, unsigned hash)
135     {
136         location = StringImpl::create8BitIfPossible(buf.s, buf.length).leakRef();
137         location->setHash(hash);
138         location->setIsAtomic(true);
139     }
140 };
141
142 template<typename CharacterType>
143 struct HashAndCharacters {
144     unsigned hash;
145     const CharacterType* characters;
146     unsigned length;
147 };
148
149 template<typename CharacterType>
150 struct HashAndCharactersTranslator {
151     static unsigned hash(const HashAndCharacters<CharacterType>& buffer)
152     {
153         ASSERT(buffer.hash == StringHasher::computeHashAndMaskTop8Bits(buffer.characters, buffer.length));
154         return buffer.hash;
155     }
156
157     static bool equal(StringImpl* const& string, const HashAndCharacters<CharacterType>& buffer)
158     {
159         return WTF::equal(string, buffer.characters, buffer.length);
160     }
161
162     static void translate(StringImpl*& location, const HashAndCharacters<CharacterType>& buffer, unsigned hash)
163     {
164         location = StringImpl::create(buffer.characters, buffer.length).leakRef();
165         location->setHash(hash);
166         location->setIsAtomic(true);
167     }
168 };
169
170 struct HashAndUTF8Characters {
171     unsigned hash;
172     const char* characters;
173     unsigned length;
174     unsigned utf16Length;
175 };
176
177 struct HashAndUTF8CharactersTranslator {
178     static unsigned hash(const HashAndUTF8Characters& buffer)
179     {
180         return buffer.hash;
181     }
182
183     static bool equal(StringImpl* const& string, const HashAndUTF8Characters& buffer)
184     {
185         if (buffer.utf16Length != string->length())
186             return false;
187
188         // If buffer contains only ASCII characters UTF-8 and UTF16 length are the same.
189         if (buffer.utf16Length != buffer.length) {
190             const UChar* stringCharacters = string->characters();
191
192             return equalUTF16WithUTF8(stringCharacters, stringCharacters + string->length(), buffer.characters, buffer.characters + buffer.length);
193         }
194
195         if (string->is8Bit()) {
196             const LChar* stringCharacters = string->characters8();
197
198             for (unsigned i = 0; i < buffer.length; ++i) {
199                 ASSERT(isASCII(buffer.characters[i]));
200                 if (stringCharacters[i] != buffer.characters[i])
201                     return false;
202             }
203
204             return true;
205         }
206
207         const UChar* stringCharacters = string->characters16();
208
209         for (unsigned i = 0; i < buffer.length; ++i) {
210             ASSERT(isASCII(buffer.characters[i]));
211             if (stringCharacters[i] != buffer.characters[i])
212                 return false;
213         }
214
215         return true;
216     }
217
218     static void translate(StringImpl*& location, const HashAndUTF8Characters& buffer, unsigned hash)
219     {
220         UChar* target;
221         RefPtr<StringImpl> newString = StringImpl::createUninitialized(buffer.utf16Length, target);
222
223         bool isAllASCII;
224         const char* source = buffer.characters;
225         if (convertUTF8ToUTF16(&source, source + buffer.length, &target, target + buffer.utf16Length, &isAllASCII) != conversionOK)
226             ASSERT_NOT_REACHED();
227
228         if (isAllASCII)
229             newString = StringImpl::create(buffer.characters, buffer.length);
230
231         location = newString.release().leakRef();
232         location->setHash(hash);
233         location->setIsAtomic(true);
234     }
235 };
236
237 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length)
238 {
239     if (!s)
240         return 0;
241
242     if (!length)
243         return StringImpl::empty();
244     
245     UCharBuffer buffer = { s, length };
246     return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
247 }
248
249 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length, unsigned existingHash)
250 {
251     ASSERT(s);
252     ASSERT(existingHash);
253
254     if (!length)
255         return StringImpl::empty();
256
257     HashAndCharacters<UChar> buffer = { existingHash, s, length };
258     return addToStringTable<HashAndCharacters<UChar>, HashAndCharactersTranslator<UChar>>(buffer);
259 }
260
261 PassRefPtr<StringImpl> AtomicString::add(const UChar* s)
262 {
263     if (!s)
264         return 0;
265
266     unsigned length = 0;
267     while (s[length] != UChar(0))
268         ++length;
269
270     if (!length)
271         return StringImpl::empty();
272
273     UCharBuffer buffer = { s, length };
274     return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
275 }
276
277 struct SubstringLocation {
278     StringImpl* baseString;
279     unsigned start;
280     unsigned length;
281 };
282
283 struct SubstringTranslator {
284     static unsigned hash(const SubstringLocation& buffer)
285     {
286         return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters() + buffer.start, buffer.length);
287     }
288
289     static bool equal(StringImpl* const& string, const SubstringLocation& buffer)
290     {
291         return WTF::equal(string, buffer.baseString->characters() + buffer.start, buffer.length);
292     }
293
294     static void translate(StringImpl*& location, const SubstringLocation& buffer, unsigned hash)
295     {
296         location = StringImpl::create(buffer.baseString, buffer.start, buffer.length).leakRef();
297         location->setHash(hash);
298         location->setIsAtomic(true);
299     }
300 };
301
302 PassRefPtr<StringImpl> AtomicString::add(StringImpl* baseString, unsigned start, unsigned length)
303 {
304     if (!baseString)
305         return 0;
306
307     if (!length || start >= baseString->length())
308         return StringImpl::empty();
309
310     unsigned maxLength = baseString->length() - start;
311     if (length >= maxLength) {
312         if (!start)
313             return add(baseString);
314         length = maxLength;
315     }
316
317     SubstringLocation buffer = { baseString, start, length };
318     return addToStringTable<SubstringLocation, SubstringTranslator>(buffer);
319 }
320     
321 typedef HashTranslatorCharBuffer<LChar> LCharBuffer;
322 struct LCharBufferTranslator {
323     static unsigned hash(const LCharBuffer& buf)
324     {
325         return StringHasher::computeHashAndMaskTop8Bits(buf.s, buf.length);
326     }
327
328     static bool equal(StringImpl* const& str, const LCharBuffer& buf)
329     {
330         return WTF::equal(str, buf.s, buf.length);
331     }
332
333     static void translate(StringImpl*& location, const LCharBuffer& buf, unsigned hash)
334     {
335         location = StringImpl::create(buf.s, buf.length).leakRef();
336         location->setHash(hash);
337         location->setIsAtomic(true);
338     }
339 };
340
341 typedef HashTranslatorCharBuffer<char> CharBuffer;
342 struct CharBufferFromLiteralDataTranslator {
343     static unsigned hash(const CharBuffer& buf)
344     {
345         return StringHasher::computeHashAndMaskTop8Bits(reinterpret_cast<const LChar*>(buf.s), buf.length);
346     }
347
348     static bool equal(StringImpl* const& str, const CharBuffer& buf)
349     {
350         return WTF::equal(str, buf.s, buf.length);
351     }
352
353     static void translate(StringImpl*& location, const CharBuffer& buf, unsigned hash)
354     {
355         location = StringImpl::createFromLiteral(buf.s, buf.length).leakRef();
356         location->setHash(hash);
357         location->setIsAtomic(true);
358     }
359 };
360
361 PassRefPtr<StringImpl> AtomicString::add(const LChar* s, unsigned length)
362 {
363     if (!s)
364         return 0;
365
366     if (!length)
367         return StringImpl::empty();
368
369     LCharBuffer buffer = { s, length };
370     return addToStringTable<LCharBuffer, LCharBufferTranslator>(buffer);
371 }
372
373 PassRefPtr<StringImpl> AtomicString::addFromLiteralData(const char* characters, unsigned length)
374 {
375     ASSERT(characters);
376     ASSERT(length);
377
378     CharBuffer buffer = { characters, length };
379     return addToStringTable<CharBuffer, CharBufferFromLiteralDataTranslator>(buffer);
380 }
381
382 PassRefPtr<StringImpl> AtomicString::addSlowCase(StringImpl* string)
383 {
384     if (!string->length())
385         return StringImpl::empty();
386
387     ASSERT_WITH_MESSAGE(!string->isAtomic(), "AtomicString should not hit the slow case if the string is already atomic.");
388
389     AtomicStringTableLocker locker;
390     HashSet<StringImpl*>::AddResult addResult = stringTable().add(string);
391
392     if (addResult.isNewEntry) {
393         ASSERT(*addResult.iterator == string);
394         string->setIsAtomic(true);
395     }
396
397     return *addResult.iterator;
398 }
399
400 template<typename CharacterType>
401 static inline HashSet<StringImpl*>::iterator findString(const StringImpl* stringImpl)
402 {
403     HashAndCharacters<CharacterType> buffer = { stringImpl->existingHash(), stringImpl->getCharacters<CharacterType>(), stringImpl->length() };
404     return stringTable().find<HashAndCharactersTranslator<CharacterType>>(buffer);
405 }
406
407 AtomicStringImpl* AtomicString::find(const StringImpl* stringImpl)
408 {
409     ASSERT(stringImpl);
410     ASSERT(stringImpl->existingHash());
411
412     if (!stringImpl->length())
413         return static_cast<AtomicStringImpl*>(StringImpl::empty());
414
415     AtomicStringTableLocker locker;
416     HashSet<StringImpl*>::iterator iterator;
417     if (stringImpl->is8Bit())
418         iterator = findString<LChar>(stringImpl);
419     else
420         iterator = findString<UChar>(stringImpl);
421     if (iterator == stringTable().end())
422         return 0;
423     return static_cast<AtomicStringImpl*>(*iterator);
424 }
425
426 void AtomicString::remove(StringImpl* string)
427 {
428     ASSERT(string->isAtomic());
429     AtomicStringTableLocker locker;
430     HashSet<StringImpl*>& atomicStringTable = stringTable();
431     HashSet<StringImpl*>::iterator iterator = atomicStringTable.find(string);
432     ASSERT_WITH_MESSAGE(iterator != atomicStringTable.end(), "The string being removed is atomic in the string table of an other thread!");
433     atomicStringTable.remove(iterator);
434 }
435
436 AtomicString AtomicString::lower() const
437 {
438     // Note: This is a hot function in the Dromaeo benchmark.
439     StringImpl* impl = this->impl();
440     if (UNLIKELY(!impl))
441         return AtomicString();
442
443     RefPtr<StringImpl> lowerImpl = impl->lower();
444     AtomicString returnValue;
445     if (LIKELY(lowerImpl == impl))
446         returnValue.m_string = lowerImpl.release();
447     else
448         returnValue.m_string = addSlowCase(lowerImpl.get());
449     return returnValue;
450 }
451
452 AtomicString AtomicString::fromUTF8Internal(const char* charactersStart, const char* charactersEnd)
453 {
454     HashAndUTF8Characters buffer;
455     buffer.characters = charactersStart;
456     buffer.hash = calculateStringHashAndLengthFromUTF8MaskingTop8Bits(charactersStart, charactersEnd, buffer.length, buffer.utf16Length);
457
458     if (!buffer.hash)
459         return nullAtom;
460
461     AtomicString atomicString;
462     atomicString.m_string = addToStringTable<HashAndUTF8Characters, HashAndUTF8CharactersTranslator>(buffer);
463     return atomicString;
464 }
465
466 AtomicString AtomicString::number(int number)
467 {
468     return numberToStringSigned<AtomicString>(number);
469 }
470
471 AtomicString AtomicString::number(unsigned number)
472 {
473     return numberToStringUnsigned<AtomicString>(number);
474 }
475
476 AtomicString AtomicString::number(double number)
477 {
478     NumberToStringBuffer buffer;
479     return String(numberToFixedPrecisionString(number, 6, buffer, true));
480 }
481
482 #if !ASSERT_DISABLED
483 bool AtomicString::isInAtomicStringTable(StringImpl* string)
484 {
485     AtomicStringTableLocker locker;
486     return stringTable().contains(string);
487 }
488 #endif
489
490 #ifndef NDEBUG
491 void AtomicString::show() const
492 {
493     m_string.show();
494 }
495 #endif
496
497 } // namespace WTF