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  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public License
  16  * along with this library; see the file COPYING.LIB.  If not, write to
  17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18  * Boston, MA 02110-1301, USA.
  19  *
  20  */
  21
  22 #include "config.h"
  23
  24 #include "AtomicString.h"
  25
  26 #include "StringHash.h"
  27 #include <wtf/HashSet.h>
  28 #include <wtf/Threading.h>
  29 #include <wtf/WTFThreadData.h>
  30 #include <wtf/unicode/UTF8.h>
  31
  32 #include <libkern/OSAtomic.h>
  33
  34 namespace WTF {
  35
  36 using namespace Unicode;
  37
  38 COMPILE_ASSERT(sizeof(AtomicString) == sizeof(String), atomic_string_and_string_must_be_same_size);
  39
  40 class AtomicStringTableLocker {
  41     static OSSpinLock s_stringTableLock;
  42 public:
  43     AtomicStringTableLocker() { OSSpinLockLock(&s_stringTableLock); }
  44     ~AtomicStringTableLocker() { OSSpinLockUnlock(&s_stringTableLock); }
  45 };
  46 OSSpinLock AtomicStringTableLocker::s_stringTableLock = OS_SPINLOCK_INIT;
  47
  48 class AtomicStringTable {
  49 public:
  50     static AtomicStringTable* create()
  51     {
  52         static AtomicStringTable* sharedStringTable = new AtomicStringTable;
  53
  54         WTFThreadData& data = wtfThreadData();
  55         if (pthread_main_np() || WTF::isWebThread())
  56             data.m_atomicStringTable = sharedStringTable;
  57         else
  58             data.m_atomicStringTable = new AtomicStringTable;
  59
  60         // The AtomicStringTable is shared between the main UI thread and the
  61         // WebThread. We do the following so that its destruction happens only
  62         // once - on the main UI thread.
  63         if (!WTF::isWebThread())
  64             data.m_atomicStringTableDestructor = AtomicStringTable::destroy;
  65         return data.m_atomicStringTable;
  66     }
  67
  68     HashSet<StringImpl*>& table()
  69     {
  70         return m_table;
  71     }
  72
  73 private:
  74     static void destroy(AtomicStringTable* table)
  75     {
  76         HashSet<StringImpl*>::iterator end = table->m_table.end();
  77         for (HashSet<StringImpl*>::iterator iter = table->m_table.begin(); iter != end; ++iter)
  78             (*iter)->setIsAtomic(false);
  79         delete table;
  80     }
  81
  82     HashSet<StringImpl*> m_table;
  83 };
  84
  85 static inline HashSet<StringImpl*>& stringTable()
  86 {
  87     // Once possible we should make this non-lazy (constructed in WTFThreadData's constructor).
  88     AtomicStringTable* table = wtfThreadData().atomicStringTable();
  89     if (UNLIKELY(!table))
  90         table = AtomicStringTable::create();
  91     return table->table();
  92 }
  93
  94 template<typename T, typename HashTranslator>
  95 static inline PassRefPtr<StringImpl> addToStringTable(const T& value)
  96 {
  97     pair<HashSet<StringImpl*>::iterator, bool> addResult = stringTable().add<T, HashTranslator>(value);
  98
  99     // If the string is newly-translated, then we need to adopt it.
 100     // The boolean in the pair tells us if that is so.
 101     return addResult.second ? adoptRef(*addResult.first) : *addResult.first;
 102 }
 103
 104 struct CStringTranslator {
 105     static unsigned hash(const char* c)
 106     {
 107         return StringHasher::computeHash(c);
 108     }
 109
 110     static bool equal(StringImpl* r, const char* s)
 111     {
 112         int length = r->length();
 113         const UChar* d = r->characters();
 114         for (int i = 0; i != length; ++i) {
 115             unsigned char c = s[i];
 116             if (d[i] != c)
 117                 return false;
 118         }
 119         return !s[length];
 120     }
 121
 122     static void translate(StringImpl*& location, const char* const& c, unsigned hash)
 123     {
 124         location = StringImpl::create(c).leakRef();
 125         location->setHash(hash);
 126         location->setIsAtomic(true);
 127     }
 128 };
 129
 130 bool operator==(const AtomicString& a, const char* b)
 131 {
 132     StringImpl* impl = a.impl();
 133     if ((!impl || !impl->characters()) && !b)
 134         return true;
 135     if ((!impl || !impl->characters()) || !b)
 136         return false;
 137     return CStringTranslator::equal(impl, b);
 138 }
 139
 140 PassRefPtr<StringImpl> AtomicString::add(const char* c)
 141 {
 142     if (!c)
 143         return 0;
 144     if (!*c)
 145         return StringImpl::empty();
 146
 147     AtomicStringTableLocker locker;
 148     return addToStringTable<const char*, CStringTranslator>(c);
 149 }
 150
 151 struct UCharBuffer {
 152     const UChar* s;
 153     unsigned length;
 154 };
 155
 156 static inline bool equal(StringImpl* string, const UChar* characters, unsigned length)
 157 {
 158     if (string->length() != length)
 159         return false;
 160
 161     // FIXME: perhaps we should have a more abstract macro that indicates when
 162     // going 4 bytes at a time is unsafe
 163 #if CPU(ARM) || CPU(SH4) || CPU(MIPS) || CPU(SPARC)
 164     const UChar* stringCharacters = string->characters();
 165     for (unsigned i = 0; i != length; ++i) {
 166         if (*stringCharacters++ != *characters++)
 167             return false;
 168     }
 169     return true;
 170 #else
 171     /* Do it 4-bytes-at-a-time on architectures where it's safe */
 172
 173     const uint32_t* stringCharacters = reinterpret_cast<const uint32_t*>(string->characters());
 174     const uint32_t* bufferCharacters = reinterpret_cast<const uint32_t*>(characters);
 175
 176     unsigned halfLength = length >> 1;
 177     for (unsigned i = 0; i != halfLength; ++i) {
 178         if (*stringCharacters++ != *bufferCharacters++)
 179             return false;
 180     }
 181
 182     if (length & 1 &&  *reinterpret_cast<const uint16_t*>(stringCharacters) != *reinterpret_cast<const uint16_t*>(bufferCharacters))
 183         return false;
 184
 185     return true;
 186 #endif
 187 }
 188
 189 bool operator==(const AtomicString& string, const Vector<UChar>& vector)
 190 {
 191     return string.impl() && equal(string.impl(), vector.data(), vector.size());
 192 }
 193
 194 struct UCharBufferTranslator {
 195     static unsigned hash(const UCharBuffer& buf)
 196     {
 197         return StringHasher::computeHash(buf.s, buf.length);
 198     }
 199
 200     static bool equal(StringImpl* const& str, const UCharBuffer& buf)
 201     {
 202         return WTF::equal(str, buf.s, buf.length);
 203     }
 204
 205     static void translate(StringImpl*& location, const UCharBuffer& buf, unsigned hash)
 206     {
 207         location = StringImpl::create(buf.s, buf.length).leakRef();
 208         location->setHash(hash);
 209         location->setIsAtomic(true);
 210     }
 211 };
 212
 213 struct HashAndCharacters {
 214     unsigned hash;
 215     const UChar* characters;
 216     unsigned length;
 217 };
 218
 219 struct HashAndCharactersTranslator {
 220     static unsigned hash(const HashAndCharacters& buffer)
 221     {
 222         ASSERT(buffer.hash == StringHasher::computeHash(buffer.characters, buffer.length));
 223         return buffer.hash;
 224     }
 225
 226     static bool equal(StringImpl* const& string, const HashAndCharacters& buffer)
 227     {
 228         return WTF::equal(string, buffer.characters, buffer.length);
 229     }
 230
 231     static void translate(StringImpl*& location, const HashAndCharacters& buffer, unsigned hash)
 232     {
 233         location = StringImpl::create(buffer.characters, buffer.length).leakRef();
 234         location->setHash(hash);
 235         location->setIsAtomic(true);
 236     }
 237 };
 238
 239 struct HashAndUTF8Characters {
 240     unsigned hash;
 241     const char* characters;
 242     unsigned length;
 243     unsigned utf16Length;
 244 };
 245
 246 struct HashAndUTF8CharactersTranslator {
 247     static unsigned hash(const HashAndUTF8Characters& buffer)
 248     {
 249         return buffer.hash;
 250     }
 251
 252     static bool equal(StringImpl* const& string, const HashAndUTF8Characters& buffer)
 253     {
 254         if (buffer.utf16Length != string->length())
 255             return false;
 256
 257         const UChar* stringCharacters = string->characters();
 258
 259         // If buffer contains only ASCII characters UTF-8 and UTF16 length are the same.
 260         if (buffer.utf16Length != buffer.length)
 261             return equalUTF16WithUTF8(stringCharacters, stringCharacters + string->length(), buffer.characters, buffer.characters + buffer.length);
 262
 263         for (unsigned i = 0; i < buffer.length; ++i) {
 264             ASSERT(isASCII(buffer.characters[i]));
 265             if (stringCharacters[i] != buffer.characters[i])
 266                 return false;
 267         }
 268
 269         return true;
 270     }
 271
 272     static void translate(StringImpl*& location, const HashAndUTF8Characters& buffer, unsigned hash)
 273     {
 274         UChar* target;
 275         location = StringImpl::createUninitialized(buffer.utf16Length, target).releaseRef();
 276
 277         const char* source = buffer.characters;
 278         if (convertUTF8ToUTF16(&source, source + buffer.length, &target, target + buffer.utf16Length) != conversionOK)
 279             ASSERT_NOT_REACHED();
 280
 281         location->setHash(hash);
 282         location->setIsAtomic(true);
 283     }
 284 };
 285
 286 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length)
 287 {
 288     if (!s)
 289         return 0;
 290
 291     if (!length)
 292         return StringImpl::empty();
 293
 294     UCharBuffer buffer = { s, length };
 295     AtomicStringTableLocker locker;
 296     return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
 297 }
 298
 299 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length, unsigned existingHash)
 300 {
 301     ASSERT(s);
 302     ASSERT(existingHash);
 303
 304     if (!length)
 305         return StringImpl::empty();
 306
 307     HashAndCharacters buffer = { existingHash, s, length };
 308     AtomicStringTableLocker locker;
 309     return addToStringTable<HashAndCharacters, HashAndCharactersTranslator>(buffer);
 310 }
 311
 312 PassRefPtr<StringImpl> AtomicString::add(const UChar* s)
 313 {
 314     if (!s)
 315         return 0;
 316
 317     int length = 0;
 318     while (s[length] != UChar(0))
 319         length++;
 320
 321     if (!length)
 322         return StringImpl::empty();
 323
 324     UCharBuffer buffer = { s, length };
 325     AtomicStringTableLocker locker;
 326     return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
 327 }
 328
 329 PassRefPtr<StringImpl> AtomicString::addSlowCase(StringImpl* r)
 330 {
 331     if (!r || r->isAtomic())
 332         return r;
 333
 334     if (!r->length())
 335         return StringImpl::empty();
 336
 337     AtomicStringTableLocker locker;
 338     StringImpl* result = *stringTable().add(r).first;
 339     if (result == r)
 340         r->setIsAtomic(true);
 341     return result;
 342 }
 343
 344 AtomicStringImpl* AtomicString::find(const UChar* s, unsigned length, unsigned existingHash)
 345 {
 346     ASSERT(s);
 347     ASSERT(existingHash);
 348
 349     if (!length)
 350         return static_cast<AtomicStringImpl*>(StringImpl::empty());
 351
 352     HashAndCharacters buffer = { existingHash, s, length };
 353     AtomicStringTableLocker locker;
 354     HashSet<StringImpl*>::iterator iterator = stringTable().find<HashAndCharacters, HashAndCharactersTranslator>(buffer);
 355     if (iterator == stringTable().end())
 356         return 0;
 357     return static_cast<AtomicStringImpl*>(*iterator);
 358 }
 359
 360 void AtomicString::remove(StringImpl* r)
 361 {
 362     AtomicStringTableLocker locker;
 363     stringTable().remove(r);
 364 }
 365
 366 AtomicString AtomicString::lower() const
 367 {
 368     // Note: This is a hot function in the Dromaeo benchmark.
 369     StringImpl* impl = this->impl();
 370     if (UNLIKELY(!impl))
 371         return *this;
 372     RefPtr<StringImpl> newImpl = impl->lower();
 373     if (LIKELY(newImpl == impl))
 374         return *this;
 375     return AtomicString(newImpl);
 376 }
 377
 378 AtomicString AtomicString::fromUTF8Internal(const char* charactersStart, const char* charactersEnd)
 379 {
 380     HashAndUTF8Characters buffer;
 381     buffer.characters = charactersStart;
 382     buffer.hash = calculateStringHashAndLengthFromUTF8(charactersStart, charactersEnd, buffer.length, buffer.utf16Length);
 383
 384     if (!buffer.hash)
 385         return nullAtom;
 386
 387     AtomicString atomicString;
 388     AtomicStringTableLocker locker;
 389     atomicString.m_string = addToStringTable<HashAndUTF8Characters, HashAndUTF8CharactersTranslator>(buffer);
 390     return atomicString;
 391 }
 392
 393 } // namespace WTF