1 /*

     2  * Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.

     3  *

     4  * This library is free software; you can redistribute it and/or

     5  * modify it under the terms of the GNU Library General Public

     6  * License as published by the Free Software Foundation; either

     7  * version 2 of the License, or (at your option) any later version.

     8  *

     9  * This library is distributed in the hope that it will be useful,

    10  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    12  * Library General Public License for more details.

    13  *

    14  * You should have received a copy of the GNU Library General Public License

    15  * along with this library; see the file COPYING.LIB.  If not, write to

    16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

    17  * Boston, MA 02110-1301, USA.

    18  *

    19  */

    20 

    21 #include "config.h"

    22 

    23 #include "AtomicString.h"

    24 

    25 #include "StringHash.h"

    26 #include <wtf/HashSet.h>

    27 #include <wtf/Threading.h>

    28 #include <wtf/WTFThreadData.h>

    29 

    30 namespace WebCore {

    31 

    32 COMPILE_ASSERT(sizeof(AtomicString) == sizeof(String), atomic_string_and_string_must_be_same_size);

    33 

    34 class AtomicStringTable {

    35 public:

    36     static AtomicStringTable* create()

    37     {

    38         AtomicStringTable* table = new AtomicStringTable;

    39 

    40         WTFThreadData& data = wtfThreadData();

    41         data.m_atomicStringTable = table;

    42         data.m_atomicStringTableDestructor = AtomicStringTable::destroy;

    43 

    44         return table;

    45     }

    46 

    47     HashSet<StringImpl*>& table()

    48     {

    49         return m_table;

    50     }

    51 

    52 private:

    53     static void destroy(AtomicStringTable* table)

    54     {

    55         HashSet<StringImpl*>::iterator end = table->m_table.end();

    56         for (HashSet<StringImpl*>::iterator iter = table->m_table.begin(); iter != end; ++iter)

    57             (*iter)->setIsAtomic(false);

    58         delete table;

    59     }

    60 

    61     HashSet<StringImpl*> m_table;

    62 };

    63 

    64 static inline HashSet<StringImpl*>& stringTable()

    65 {

    66     // Once possible we should make this non-lazy (constructed in WTFThreadData's constructor).

    67     AtomicStringTable* table = wtfThreadData().atomicStringTable();

    68     if (UNLIKELY(!table))

    69         table = AtomicStringTable::create();

    70     return table->table();

    71 }

    72 

    73 struct CStringTranslator {

    74     static unsigned hash(const char* c)

    75     {

    76         return StringImpl::computeHash(c);

    77     }

    78 

    79     static bool equal(StringImpl* r, const char* s)

    80     {

    81         int length = r->length();

    82         const UChar* d = r->characters();

    83         for (int i = 0; i != length; ++i) {

    84             unsigned char c = s[i];

    85             if (d[i] != c)

    86                 return false;

    87         }

    88         return s[length] == 0;

    89     }

    90 

    91     static void translate(StringImpl*& location, const char* const& c, unsigned hash)

    92     {

    93         location = StringImpl::create(c).releaseRef(); 

    94         location->setHash(hash);

    95         location->setIsAtomic(true);

    96     }

    97 };

    98 

    99 bool operator==(const AtomicString& a, const char* b)

   100 { 

   101     StringImpl* impl = a.impl();

   102     if ((!impl || !impl->characters()) && !b)

   103         return true;

   104     if ((!impl || !impl->characters()) || !b)

   105         return false;

   106     return CStringTranslator::equal(impl, b); 

   107 }

   108 

   109 PassRefPtr<StringImpl> AtomicString::add(const char* c)

   110 {

   111     if (!c)

   112         return 0;

   113     if (!*c)

   114         return StringImpl::empty();    

   115     pair<HashSet<StringImpl*>::iterator, bool> addResult = stringTable().add<const char*, CStringTranslator>(c);

   116     if (!addResult.second)

   117         return *addResult.first;

   118     return adoptRef(*addResult.first);

   119 }

   120 

   121 struct UCharBuffer {

   122     const UChar* s;

   123     unsigned length;

   124 };

   125 

   126 static inline bool equal(StringImpl* string, const UChar* characters, unsigned length)

   127 {

   128     if (string->length() != length)

   129         return false;

   130 

   131     // FIXME: perhaps we should have a more abstract macro that indicates when

   132     // going 4 bytes at a time is unsafe

   133 #if CPU(ARM) || CPU(SH4)

   134     const UChar* stringCharacters = string->characters();

   135     for (unsigned i = 0; i != length; ++i) {

   136         if (*stringCharacters++ != *characters++)

   137             return false;

   138     }

   139     return true;

   140 #else

   141     /* Do it 4-bytes-at-a-time on architectures where it's safe */

   142 

   143     const uint32_t* stringCharacters = reinterpret_cast<const uint32_t*>(string->characters());

   144     const uint32_t* bufferCharacters = reinterpret_cast<const uint32_t*>(characters);

   145 

   146     unsigned halfLength = length >> 1;

   147     for (unsigned i = 0; i != halfLength; ++i) {

   148         if (*stringCharacters++ != *bufferCharacters++)

   149             return false;

   150     }

   151 

   152     if (length & 1 &&  *reinterpret_cast<const uint16_t*>(stringCharacters) != *reinterpret_cast<const uint16_t*>(bufferCharacters))

   153         return false;

   154 

   155     return true;

   156 #endif

   157 }

   158 

   159 struct UCharBufferTranslator {

   160     static unsigned hash(const UCharBuffer& buf)

   161     {

   162         return StringImpl::computeHash(buf.s, buf.length);

   163     }

   164 

   165     static bool equal(StringImpl* const& str, const UCharBuffer& buf)

   166     {

   167         return WebCore::equal(str, buf.s, buf.length);

   168     }

   169 

   170     static void translate(StringImpl*& location, const UCharBuffer& buf, unsigned hash)

   171     {

   172         location = StringImpl::create(buf.s, buf.length).releaseRef(); 

   173         location->setHash(hash);

   174         location->setIsAtomic(true);

   175     }

   176 };

   177 

   178 struct HashAndCharacters {

   179     unsigned hash;

   180     const UChar* characters;

   181     unsigned length;

   182 };

   183 

   184 struct HashAndCharactersTranslator {

   185     static unsigned hash(const HashAndCharacters& buffer)

   186     {

   187         ASSERT(buffer.hash == StringImpl::computeHash(buffer.characters, buffer.length));

   188         return buffer.hash;

   189     }

   190 

   191     static bool equal(StringImpl* const& string, const HashAndCharacters& buffer)

   192     {

   193         return WebCore::equal(string, buffer.characters, buffer.length);

   194     }

   195 

   196     static void translate(StringImpl*& location, const HashAndCharacters& buffer, unsigned hash)

   197     {

   198         location = StringImpl::create(buffer.characters, buffer.length).releaseRef();

   199         location->setHash(hash);

   200         location->setIsAtomic(true);

   201     }

   202 };

   203 

   204 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length)

   205 {

   206     if (!s)

   207         return 0;

   208 

   209     if (length == 0)

   210         return StringImpl::empty();

   211     

   212     UCharBuffer buf = { s, length }; 

   213     pair<HashSet<StringImpl*>::iterator, bool> addResult = stringTable().add<UCharBuffer, UCharBufferTranslator>(buf);

   214 

   215     // If the string is newly-translated, then we need to adopt it.

   216     // The boolean in the pair tells us if that is so.

   217     return addResult.second ? adoptRef(*addResult.first) : *addResult.first;

   218 }

   219 

   220 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length, unsigned existingHash)

   221 {

   222     ASSERT(s);

   223     ASSERT(existingHash);

   224 

   225     if (length == 0)

   226         return StringImpl::empty();

   227     

   228     HashAndCharacters buffer = { existingHash, s, length }; 

   229     pair<HashSet<StringImpl*>::iterator, bool> addResult = stringTable().add<HashAndCharacters, HashAndCharactersTranslator>(buffer);

   230     if (!addResult.second)

   231         return *addResult.first;

   232     return adoptRef(*addResult.first);

   233 }

   234 

   235 PassRefPtr<StringImpl> AtomicString::add(const UChar* s)

   236 {

   237     if (!s)

   238         return 0;

   239 

   240     int length = 0;

   241     while (s[length] != UChar(0))

   242         length++;

   243 

   244     if (length == 0)

   245         return StringImpl::empty();

   246 

   247     UCharBuffer buf = {s, length}; 

   248     pair<HashSet<StringImpl*>::iterator, bool> addResult = stringTable().add<UCharBuffer, UCharBufferTranslator>(buf);

   249 

   250     // If the string is newly-translated, then we need to adopt it.

   251     // The boolean in the pair tells us if that is so.

   252     return addResult.second ? adoptRef(*addResult.first) : *addResult.first;

   253 }

   254 

   255 PassRefPtr<StringImpl> AtomicString::addSlowCase(StringImpl* r)

   256 {

   257     if (!r || r->isAtomic())

   258         return r;

   259 

   260     if (r->length() == 0)

   261         return StringImpl::empty();

   262 

   263     StringImpl* result = *stringTable().add(r).first;

   264     if (result == r)

   265         r->setIsAtomic(true);

   266     return result;

   267 }

   268 

   269 AtomicStringImpl* AtomicString::find(const UChar* s, unsigned length, unsigned existingHash)

   270 {

   271     ASSERT(s);

   272     ASSERT(existingHash);

   273 

   274     if (length == 0)

   275         return static_cast<AtomicStringImpl*>(StringImpl::empty());

   276 

   277     HashAndCharacters buffer = { existingHash, s, length }; 

   278     HashSet<StringImpl*>::iterator iterator = stringTable().find<HashAndCharacters, HashAndCharactersTranslator>(buffer);

   279     if (iterator == stringTable().end())

   280         return 0;

   281     return static_cast<AtomicStringImpl*>(*iterator);

   282 }

   283 

   284 void AtomicString::remove(StringImpl* r)

   285 {

   286     stringTable().remove(r);

   287 }

   288     

   289 AtomicString AtomicString::lower() const

   290 {

   291     // Note: This is a hot function in the Dromaeo benchmark.

   292     StringImpl* impl = this->impl();

   293     RefPtr<StringImpl> newImpl = impl->lower();

   294     if (LIKELY(newImpl == impl))

   295         return *this;

   296     return AtomicString(newImpl);

   297 }

   298 

   299 }