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