Add ability to create AtomicString using LChar* buffer and length
[WebKit.git] / Source / WTF / wtf / text / AtomicString.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006, 2007, 2008 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
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 namespace WTF {
34
35 using namespace Unicode;
36
37 COMPILE_ASSERT(sizeof(AtomicString) == sizeof(String), atomic_string_and_string_must_be_same_size);
38
39 class AtomicStringTable {
40 public:
41     static AtomicStringTable* create()
42     {
43         AtomicStringTable* table = new AtomicStringTable;
44
45         WTFThreadData& data = wtfThreadData();
46         data.m_atomicStringTable = table;
47         data.m_atomicStringTableDestructor = AtomicStringTable::destroy;
48
49         return table;
50     }
51
52     HashSet<StringImpl*>& table()
53     {
54         return m_table;
55     }
56
57 private:
58     static void destroy(AtomicStringTable* table)
59     {
60         HashSet<StringImpl*>::iterator end = table->m_table.end();
61         for (HashSet<StringImpl*>::iterator iter = table->m_table.begin(); iter != end; ++iter)
62             (*iter)->setIsAtomic(false);
63         delete table;
64     }
65
66     HashSet<StringImpl*> m_table;
67 };
68
69 static inline HashSet<StringImpl*>& stringTable()
70 {
71     // Once possible we should make this non-lazy (constructed in WTFThreadData's constructor).
72     AtomicStringTable* table = wtfThreadData().atomicStringTable();
73     if (UNLIKELY(!table))
74         table = AtomicStringTable::create();
75     return table->table();
76 }
77
78 template<typename T, typename HashTranslator>
79 static inline PassRefPtr<StringImpl> addToStringTable(const T& value)
80 {
81     HashSet<StringImpl*>::AddResult addResult = stringTable().add<T, HashTranslator>(value);
82
83     // If the string is newly-translated, then we need to adopt it.
84     // The boolean in the pair tells us if that is so.
85     return addResult.isNewEntry ? adoptRef(*addResult.iterator) : *addResult.iterator;
86 }
87
88 struct CStringTranslator {
89     static unsigned hash(const LChar* c)
90     {
91         return StringHasher::computeHashAndMaskTop8Bits(c);
92     }
93
94     static inline bool equal(StringImpl* r, const LChar* s)
95     {
96         return WTF::equal(r, s);
97     }
98
99     static void translate(StringImpl*& location, const LChar* const& c, unsigned hash)
100     {
101         location = StringImpl::create(c).leakRef();
102         location->setHash(hash);
103         location->setIsAtomic(true);
104     }
105 };
106
107 PassRefPtr<StringImpl> AtomicString::add(const LChar* c)
108 {
109     if (!c)
110         return 0;
111     if (!*c)
112         return StringImpl::empty();
113
114     return addToStringTable<const LChar*, CStringTranslator>(c);
115 }
116
117 template<typename CharacterType>
118 struct HashTranslatorCharBuffer {
119     const CharacterType* s;
120     unsigned length;
121 };
122
123 typedef HashTranslatorCharBuffer<UChar> UCharBuffer;
124 struct UCharBufferTranslator {
125     static unsigned hash(const UCharBuffer& buf)
126     {
127         return StringHasher::computeHashAndMaskTop8Bits(buf.s, buf.length);
128     }
129
130     static bool equal(StringImpl* const& str, const UCharBuffer& buf)
131     {
132         return WTF::equal(str, buf.s, buf.length);
133     }
134
135     static void translate(StringImpl*& location, const UCharBuffer& buf, unsigned hash)
136     {
137         location = StringImpl::create(buf.s, buf.length).leakRef();
138         location->setHash(hash);
139         location->setIsAtomic(true);
140     }
141 };
142
143 template<typename CharacterType>
144 struct HashAndCharacters {
145     unsigned hash;
146     const CharacterType* characters;
147     unsigned length;
148 };
149
150 template<typename CharacterType>
151 struct HashAndCharactersTranslator {
152     static unsigned hash(const HashAndCharacters<CharacterType>& buffer)
153     {
154         ASSERT(buffer.hash == StringHasher::computeHashAndMaskTop8Bits(buffer.characters, buffer.length));
155         return buffer.hash;
156     }
157
158     static bool equal(StringImpl* const& string, const HashAndCharacters<CharacterType>& buffer)
159     {
160         return WTF::equal(string, buffer.characters, buffer.length);
161     }
162
163     static void translate(StringImpl*& location, const HashAndCharacters<CharacterType>& buffer, unsigned hash)
164     {
165         location = StringImpl::create(buffer.characters, buffer.length).leakRef();
166         location->setHash(hash);
167         location->setIsAtomic(true);
168     }
169 };
170
171 struct HashAndUTF8Characters {
172     unsigned hash;
173     const char* characters;
174     unsigned length;
175     unsigned utf16Length;
176 };
177
178 struct HashAndUTF8CharactersTranslator {
179     static unsigned hash(const HashAndUTF8Characters& buffer)
180     {
181         return buffer.hash;
182     }
183
184     static bool equal(StringImpl* const& string, const HashAndUTF8Characters& buffer)
185     {
186         if (buffer.utf16Length != string->length())
187             return false;
188
189         const UChar* stringCharacters = string->characters();
190
191         // If buffer contains only ASCII characters UTF-8 and UTF16 length are the same.
192         if (buffer.utf16Length != buffer.length)
193             return equalUTF16WithUTF8(stringCharacters, stringCharacters + string->length(), buffer.characters, buffer.characters + buffer.length);
194
195         for (unsigned i = 0; i < buffer.length; ++i) {
196             ASSERT(isASCII(buffer.characters[i]));
197             if (stringCharacters[i] != buffer.characters[i])
198                 return false;
199         }
200
201         return true;
202     }
203
204     static void translate(StringImpl*& location, const HashAndUTF8Characters& buffer, unsigned hash)
205     {
206         UChar* target;
207         location = StringImpl::createUninitialized(buffer.utf16Length, target).leakRef();
208
209         const char* source = buffer.characters;
210         if (convertUTF8ToUTF16(&source, source + buffer.length, &target, target + buffer.utf16Length) != conversionOK)
211             ASSERT_NOT_REACHED();
212
213         location->setHash(hash);
214         location->setIsAtomic(true);
215     }
216 };
217
218 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length)
219 {
220     if (!s)
221         return 0;
222
223     if (!length)
224         return StringImpl::empty();
225     
226     UCharBuffer buffer = { s, length };
227     return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
228 }
229
230 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length, unsigned existingHash)
231 {
232     ASSERT(s);
233     ASSERT(existingHash);
234
235     if (!length)
236         return StringImpl::empty();
237
238     HashAndCharacters<UChar> buffer = { existingHash, s, length };
239     return addToStringTable<HashAndCharacters<UChar>, HashAndCharactersTranslator<UChar> >(buffer);
240 }
241
242 PassRefPtr<StringImpl> AtomicString::add(const UChar* s)
243 {
244     if (!s)
245         return 0;
246
247     int length = 0;
248     while (s[length] != UChar(0))
249         length++;
250
251     if (!length)
252         return StringImpl::empty();
253
254     UCharBuffer buffer = { s, length };
255     return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
256 }
257
258 struct SubstringLocation {
259     StringImpl* baseString;
260     unsigned start;
261     unsigned length;
262 };
263
264 struct SubstringTranslator {
265     static unsigned hash(const SubstringLocation& buffer)
266     {
267         return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters() + buffer.start, buffer.length);
268     }
269
270     static bool equal(StringImpl* const& string, const SubstringLocation& buffer)
271     {
272         return WTF::equal(string, buffer.baseString->characters() + buffer.start, buffer.length);
273     }
274
275     static void translate(StringImpl*& location, const SubstringLocation& buffer, unsigned hash)
276     {
277         location = StringImpl::create(buffer.baseString, buffer.start, buffer.length).leakRef();
278         location->setHash(hash);
279         location->setIsAtomic(true);
280     }
281 };
282
283 PassRefPtr<StringImpl> AtomicString::add(StringImpl* baseString, unsigned start, unsigned length)
284 {
285     if (!baseString)
286         return 0;
287
288     if (!length || start >= baseString->length())
289         return StringImpl::empty();
290
291     unsigned maxLength = baseString->length() - start;
292     if (length >= maxLength) {
293         if (!start)
294             return add(baseString);
295         length = maxLength;
296     }
297
298     SubstringLocation buffer = { baseString, start, length };
299     return addToStringTable<SubstringLocation, SubstringTranslator>(buffer);
300 }
301     
302 typedef HashTranslatorCharBuffer<LChar> LCharBuffer;
303 struct LCharBufferTranslator {
304     static unsigned hash(const LCharBuffer& buf)
305     {
306         return StringHasher::computeHashAndMaskTop8Bits(buf.s, buf.length);
307     }
308
309     static bool equal(StringImpl* const& str, const LCharBuffer& buf)
310     {
311         return WTF::equal(str, buf.s, buf.length);
312     }
313
314     static void translate(StringImpl*& location, const LCharBuffer& buf, unsigned hash)
315     {
316         location = StringImpl::create(buf.s, buf.length).leakRef();
317         location->setHash(hash);
318         location->setIsAtomic(true);
319     }
320 };
321
322 typedef HashTranslatorCharBuffer<char> CharBuffer;
323 struct CharBufferFromLiteralDataTranslator {
324     static unsigned hash(const CharBuffer& buf)
325     {
326         return StringHasher::computeHashAndMaskTop8Bits(reinterpret_cast<const LChar*>(buf.s), buf.length);
327     }
328
329     static bool equal(StringImpl* const& str, const CharBuffer& buf)
330     {
331         return WTF::equal(str, buf.s, buf.length);
332     }
333
334     static void translate(StringImpl*& location, const CharBuffer& buf, unsigned hash)
335     {
336         location = StringImpl::createFromLiteral(buf.s, buf.length).leakRef();
337         location->setHash(hash);
338         location->setIsAtomic(true);
339     }
340 };
341
342 PassRefPtr<StringImpl> AtomicString::add(const LChar* s, unsigned length)
343 {
344     if (!s)
345         return 0;
346
347     if (!length)
348         return StringImpl::empty();
349
350     LCharBuffer buffer = { s, length };
351     return addToStringTable<LCharBuffer, LCharBufferTranslator>(buffer);
352 }
353
354 PassRefPtr<StringImpl> AtomicString::addFromLiteralData(const char* characters, unsigned length)
355 {
356     ASSERT(characters);
357     ASSERT(length);
358
359     CharBuffer buffer = { characters, length };
360     return addToStringTable<CharBuffer, CharBufferFromLiteralDataTranslator>(buffer);
361 }
362
363 PassRefPtr<StringImpl> AtomicString::addSlowCase(StringImpl* r)
364 {
365     if (!r->length())
366         return StringImpl::empty();
367
368     StringImpl* result = *stringTable().add(r).iterator;
369     if (result == r)
370         r->setIsAtomic(true);
371     return result;
372 }
373
374 template<typename CharacterType>
375 static inline HashSet<StringImpl*>::iterator findString(const StringImpl* stringImpl)
376 {
377     HashAndCharacters<CharacterType> buffer = { stringImpl->existingHash(), stringImpl->getCharacters<CharacterType>(), stringImpl->length() };
378     return stringTable().find<HashAndCharacters<CharacterType>, HashAndCharactersTranslator<CharacterType> >(buffer);
379 }
380
381 AtomicStringImpl* AtomicString::find(const StringImpl* stringImpl)
382 {
383     ASSERT(stringImpl);
384     ASSERT(stringImpl->existingHash());
385
386     if (!stringImpl->length())
387         return static_cast<AtomicStringImpl*>(StringImpl::empty());
388
389     HashSet<StringImpl*>::iterator iterator;
390     if (stringImpl->is8Bit())
391         iterator = findString<LChar>(stringImpl);
392     else
393         iterator = findString<UChar>(stringImpl);
394     if (iterator == stringTable().end())
395         return 0;
396     return static_cast<AtomicStringImpl*>(*iterator);
397 }
398
399 void AtomicString::remove(StringImpl* r)
400 {
401     stringTable().remove(r);
402 }
403
404 AtomicString AtomicString::lower() const
405 {
406     // Note: This is a hot function in the Dromaeo benchmark.
407     StringImpl* impl = this->impl();
408     if (UNLIKELY(!impl))
409         return *this;
410     RefPtr<StringImpl> newImpl = impl->lower();
411     if (LIKELY(newImpl == impl))
412         return *this;
413     return AtomicString(newImpl);
414 }
415
416 AtomicString AtomicString::fromUTF8Internal(const char* charactersStart, const char* charactersEnd)
417 {
418     HashAndUTF8Characters buffer;
419     buffer.characters = charactersStart;
420     buffer.hash = calculateStringHashAndLengthFromUTF8MaskingTop8Bits(charactersStart, charactersEnd, buffer.length, buffer.utf16Length);
421
422     if (!buffer.hash)
423         return nullAtom;
424
425     AtomicString atomicString;
426     atomicString.m_string = addToStringTable<HashAndUTF8Characters, HashAndUTF8CharactersTranslator>(buffer);
427     return atomicString;
428 }
429
430 #ifndef NDEBUG
431 void AtomicString::show() const
432 {
433     m_string.show();
434 }
435 #endif
436
437 } // namespace WTF