wtf/text/AtomicString.cpp

   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 <libkern/OSAtomic.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
  32 namespace WebCore {
  33
  34 COMPILE_ASSERT(sizeof(AtomicString) == sizeof(String), atomic_string_and_string_must_be_same_size);
  35
  36 class AtomicStringTableLocker {
  37     static OSSpinLock s_stringTableLock;
  38 public:
  39     AtomicStringTableLocker() { OSSpinLockLock(&s_stringTableLock); }
  40     ~AtomicStringTableLocker() { OSSpinLockUnlock(&s_stringTableLock); }
  41 };
  42 OSSpinLock AtomicStringTableLocker::s_stringTableLock = OS_SPINLOCK_INIT;
  43
  44 class AtomicStringTable {
  45 public:
  46     static AtomicStringTable* create()
  47     {
  48         static AtomicStringTable* sharedStringTable = new AtomicStringTable;
  49
  50         WTFThreadData& data = wtfThreadData();
  51         if (pthread_main_np() || WTF::isWebThread())
  52             data.m_atomicStringTable = sharedStringTable;
  53         else
  54             data.m_atomicStringTable = new AtomicStringTable;
  55
  56         // The AtomicStringTable is shared between the main UI thread and the
  57         // WebThread. We do the following so that its destruction happens only
  58         // once - on the main UI thread.
  59         if (!WTF::isWebThread())
  60             data.m_atomicStringTableDestructor = AtomicStringTable::destroy;
  61         return data.m_atomicStringTable;
  62     }
  63
  64     HashSet<StringImpl*>& table()
  65     {
  66         return m_table;
  67     }
  68
  69 private:
  70     static void destroy(AtomicStringTable* table)
  71     {
  72         HashSet<StringImpl*>::iterator end = table->m_table.end();
  73         for (HashSet<StringImpl*>::iterator iter = table->m_table.begin(); iter != end; ++iter)
  74             (*iter)->setIsAtomic(false);
  75         delete table;
  76     }
  77
  78     HashSet<StringImpl*> m_table;
  79 };
  80
  81 static inline HashSet<StringImpl*>& stringTable()
  82 {
  83     // Once possible we should make this non-lazy (constructed in WTFThreadData's constructor).
  84     AtomicStringTable* table = wtfThreadData().atomicStringTable();
  85     if (UNLIKELY(!table))
  86         table = AtomicStringTable::create();
  87     return table->table();
  88 }
  89
  90 struct CStringTranslator {
  91     static unsigned hash(const char* c)
  92     {
  93         return StringImpl::computeHash(c);
  94     }
  95
  96     static bool equal(StringImpl* r, const char* s)
  97     {
  98         int length = r->length();
  99         const UChar* d = r->characters();
 100         for (int i = 0; i != length; ++i) {
 101             unsigned char c = s[i];
 102             if (d[i] != c)
 103                 return false;
 104         }
 105         return s[length] == 0;
 106     }
 107
 108     static void translate(StringImpl*& location, const char* const& c, unsigned hash)
 109     {
 110         location = StringImpl::create(c).releaseRef();
 111         location->setHash(hash);
 112         location->setIsAtomic(true);
 113     }
 114 };
 115
 116 bool operator==(const AtomicString& a, const char* b)
 117 {
 118     StringImpl* impl = a.impl();
 119     if ((!impl || !impl->characters()) && !b)
 120         return true;
 121     if ((!impl || !impl->characters()) || !b)
 122         return false;
 123     return CStringTranslator::equal(impl, b);
 124 }
 125
 126 PassRefPtr<StringImpl> AtomicString::add(const char* c)
 127 {
 128     if (!c)
 129         return 0;
 130     if (!*c)
 131         return StringImpl::empty();
 132     AtomicStringTableLocker locker;
 133     pair<HashSet<StringImpl*>::iterator, bool> addResult = stringTable().add<const char*, CStringTranslator>(c);
 134     if (!addResult.second)
 135         return *addResult.first;
 136     return adoptRef(*addResult.first);
 137 }
 138
 139 struct UCharBuffer {
 140     const UChar* s;
 141     unsigned length;
 142 };
 143
 144 static inline bool equal(StringImpl* string, const UChar* characters, unsigned length)
 145 {
 146     if (string->length() != length)
 147         return false;
 148
 149     // FIXME: perhaps we should have a more abstract macro that indicates when
 150     // going 4 bytes at a time is unsafe
 151 #if CPU(ARM) || CPU(SH4)
 152     const UChar* stringCharacters = string->characters();
 153     for (unsigned i = 0; i != length; ++i) {
 154         if (*stringCharacters++ != *characters++)
 155             return false;
 156     }
 157     return true;
 158 #else
 159     /* Do it 4-bytes-at-a-time on architectures where it's safe */
 160
 161     const uint32_t* stringCharacters = reinterpret_cast<const uint32_t*>(string->characters());
 162     const uint32_t* bufferCharacters = reinterpret_cast<const uint32_t*>(characters);
 163
 164     unsigned halfLength = length >> 1;
 165     for (unsigned i = 0; i != halfLength; ++i) {
 166         if (*stringCharacters++ != *bufferCharacters++)
 167             return false;
 168     }
 169
 170     if (length & 1 &&  *reinterpret_cast<const uint16_t*>(stringCharacters) != *reinterpret_cast<const uint16_t*>(bufferCharacters))
 171         return false;
 172
 173     return true;
 174 #endif
 175 }
 176
 177 struct UCharBufferTranslator {
 178     static unsigned hash(const UCharBuffer& buf)
 179     {
 180         return StringImpl::computeHash(buf.s, buf.length);
 181     }
 182
 183     static bool equal(StringImpl* const& str, const UCharBuffer& buf)
 184     {
 185         return WebCore::equal(str, buf.s, buf.length);
 186     }
 187
 188     static void translate(StringImpl*& location, const UCharBuffer& buf, unsigned hash)
 189     {
 190         location = StringImpl::create(buf.s, buf.length).releaseRef();
 191         location->setHash(hash);
 192         location->setIsAtomic(true);
 193     }
 194 };
 195
 196 struct HashAndCharacters {
 197     unsigned hash;
 198     const UChar* characters;
 199     unsigned length;
 200 };
 201
 202 struct HashAndCharactersTranslator {
 203     static unsigned hash(const HashAndCharacters& buffer)
 204     {
 205         ASSERT(buffer.hash == StringImpl::computeHash(buffer.characters, buffer.length));
 206         return buffer.hash;
 207     }
 208
 209     static bool equal(StringImpl* const& string, const HashAndCharacters& buffer)
 210     {
 211         return WebCore::equal(string, buffer.characters, buffer.length);
 212     }
 213
 214     static void translate(StringImpl*& location, const HashAndCharacters& buffer, unsigned hash)
 215     {
 216         location = StringImpl::create(buffer.characters, buffer.length).releaseRef();
 217         location->setHash(hash);
 218         location->setIsAtomic(true);
 219     }
 220 };
 221
 222 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length)
 223 {
 224     if (!s)
 225         return 0;
 226
 227     if (length == 0)
 228         return StringImpl::empty();
 229
 230     UCharBuffer buf = { s, length };
 231     AtomicStringTableLocker locker;
 232     pair<HashSet<StringImpl*>::iterator, bool> addResult = stringTable().add<UCharBuffer, UCharBufferTranslator>(buf);
 233
 234     // If the string is newly-translated, then we need to adopt it.
 235     // The boolean in the pair tells us if that is so.
 236     return addResult.second ? adoptRef(*addResult.first) : *addResult.first;
 237 }
 238
 239 PassRefPtr<StringImpl> AtomicString::add(const UChar* s, unsigned length, unsigned existingHash)
 240 {
 241     ASSERT(s);
 242     ASSERT(existingHash);
 243
 244     if (length == 0)
 245         return StringImpl::empty();
 246
 247     HashAndCharacters buffer = { existingHash, s, length };
 248     AtomicStringTableLocker locker;
 249     pair<HashSet<StringImpl*>::iterator, bool> addResult = stringTable().add<HashAndCharacters, HashAndCharactersTranslator>(buffer);
 250     if (!addResult.second)
 251         return *addResult.first;
 252     return adoptRef(*addResult.first);
 253 }
 254
 255 PassRefPtr<StringImpl> AtomicString::add(const UChar* s)
 256 {
 257     if (!s)
 258         return 0;
 259
 260     int length = 0;
 261     while (s[length] != UChar(0))
 262         length++;
 263
 264     if (length == 0)
 265         return StringImpl::empty();
 266
 267     UCharBuffer buf = {s, length};
 268     AtomicStringTableLocker locker;
 269     pair<HashSet<StringImpl*>::iterator, bool> addResult = stringTable().add<UCharBuffer, UCharBufferTranslator>(buf);
 270
 271     // If the string is newly-translated, then we need to adopt it.
 272     // The boolean in the pair tells us if that is so.
 273     return addResult.second ? adoptRef(*addResult.first) : *addResult.first;
 274 }
 275
 276 PassRefPtr<StringImpl> AtomicString::addSlowCase(StringImpl* r)
 277 {
 278     if (!r || r->isAtomic())
 279         return r;
 280
 281     if (r->length() == 0)
 282         return StringImpl::empty();
 283
 284     AtomicStringTableLocker locker;
 285     StringImpl* result = *stringTable().add(r).first;
 286     if (result == r)
 287         r->setIsAtomic(true);
 288     return result;
 289 }
 290
 291 AtomicStringImpl* AtomicString::find(const UChar* s, unsigned length, unsigned existingHash)
 292 {
 293     ASSERT(s);
 294     ASSERT(existingHash);
 295
 296     if (length == 0)
 297         return static_cast<AtomicStringImpl*>(StringImpl::empty());
 298
 299     HashAndCharacters buffer = { existingHash, s, length };
 300     AtomicStringTableLocker locker;
 301     HashSet<StringImpl*>::iterator iterator = stringTable().find<HashAndCharacters, HashAndCharactersTranslator>(buffer);
 302     if (iterator == stringTable().end())
 303         return 0;
 304     return static_cast<AtomicStringImpl*>(*iterator);
 305 }
 306
 307 void AtomicString::remove(StringImpl* r)
 308 {
 309     AtomicStringTableLocker locker;
 310     stringTable().remove(r);
 311 }
 312
 313 AtomicString AtomicString::lower() const
 314 {
 315     // Note: This is a hot function in the Dromaeo benchmark.
 316     StringImpl* impl = this->impl();
 317     RefPtr<StringImpl> newImpl = impl->lower();
 318     if (LIKELY(newImpl == impl))
 319         return *this;
 320     return AtomicString(newImpl);
 321 }
 322
 323 }