summaryrefslogtreecommitdiff
path: root/Source/WTF/wtf/text/AtomicStringImpl.cpp
diff options
context:
space:
mode:
authorLorry Tar Creator <lorry-tar-importer@lorry>2017-06-27 06:07:23 +0000
committerLorry Tar Creator <lorry-tar-importer@lorry>2017-06-27 06:07:23 +0000
commit1bf1084f2b10c3b47fd1a588d85d21ed0eb41d0c (patch)
tree46dcd36c86e7fbc6e5df36deb463b33e9967a6f7 /Source/WTF/wtf/text/AtomicStringImpl.cpp
parent32761a6cee1d0dee366b885b7b9c777e67885688 (diff)
downloadWebKitGtk-tarball-master.tar.gz
Diffstat (limited to 'Source/WTF/wtf/text/AtomicStringImpl.cpp')
-rw-r--r--Source/WTF/wtf/text/AtomicStringImpl.cpp540
1 files changed, 540 insertions, 0 deletions
diff --git a/Source/WTF/wtf/text/AtomicStringImpl.cpp b/Source/WTF/wtf/text/AtomicStringImpl.cpp
new file mode 100644
index 000000000..fb50b7fdd
--- /dev/null
+++ b/Source/WTF/wtf/text/AtomicStringImpl.cpp
@@ -0,0 +1,540 @@
+/*
+ * Copyright (C) 2004-2008, 2013-2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com>
+ * Copyright (C) 2012 Google Inc. All rights reserved.
+ * Copyright (C) 2015 Yusuke Suzuki<utatane.tea@gmail.com>. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ *
+ */
+
+#include "config.h"
+#include "AtomicStringImpl.h"
+
+#include "AtomicStringTable.h"
+#include "CommaPrinter.h"
+#include "DataLog.h"
+#include "HashSet.h"
+#include "IntegerToStringConversion.h"
+#include "StringHash.h"
+#include "StringPrintStream.h"
+#include "Threading.h"
+#include "WTFThreadData.h"
+#include <wtf/unicode/UTF8.h>
+
+#if USE(WEB_THREAD)
+#include "Lock.h"
+#endif
+
+namespace WTF {
+
+using namespace Unicode;
+
+#if USE(WEB_THREAD)
+
+class AtomicStringTableLocker : public LockHolder {
+ WTF_MAKE_NONCOPYABLE(AtomicStringTableLocker);
+
+ static StaticLock s_stringTableLock;
+public:
+ AtomicStringTableLocker()
+ : LockHolder(&s_stringTableLock)
+ {
+ }
+};
+
+StaticLock AtomicStringTableLocker::s_stringTableLock;
+
+#else
+
+class AtomicStringTableLocker {
+ WTF_MAKE_NONCOPYABLE(AtomicStringTableLocker);
+public:
+ AtomicStringTableLocker() { }
+};
+
+#endif // USE(WEB_THREAD)
+
+using StringTableImpl = HashSet<StringImpl*>;
+
+static ALWAYS_INLINE StringTableImpl& stringTable()
+{
+ return wtfThreadData().atomicStringTable()->table();
+}
+
+template<typename T, typename HashTranslator>
+static inline Ref<AtomicStringImpl> addToStringTable(AtomicStringTableLocker&, StringTableImpl& atomicStringTable, const T& value)
+{
+ auto addResult = atomicStringTable.add<HashTranslator>(value);
+
+ // If the string is newly-translated, then we need to adopt it.
+ // The boolean in the pair tells us if that is so.
+ if (addResult.isNewEntry)
+ return adoptRef(static_cast<AtomicStringImpl&>(**addResult.iterator));
+ return *static_cast<AtomicStringImpl*>(*addResult.iterator);
+}
+
+template<typename T, typename HashTranslator>
+static inline Ref<AtomicStringImpl> addToStringTable(const T& value)
+{
+ AtomicStringTableLocker locker;
+ return addToStringTable<T, HashTranslator>(locker, stringTable(), value);
+}
+
+struct CStringTranslator {
+ static unsigned hash(const LChar* c)
+ {
+ return StringHasher::computeHashAndMaskTop8Bits(c);
+ }
+
+ static inline bool equal(StringImpl* r, const LChar* s)
+ {
+ return WTF::equal(r, s);
+ }
+
+ static void translate(StringImpl*& location, const LChar* const& c, unsigned hash)
+ {
+ location = &StringImpl::create(c).leakRef();
+ location->setHash(hash);
+ location->setIsAtomic(true);
+ }
+};
+
+RefPtr<AtomicStringImpl> AtomicStringImpl::add(const LChar* c)
+{
+ if (!c)
+ return nullptr;
+ if (!*c)
+ return static_cast<AtomicStringImpl*>(StringImpl::empty());
+
+ return addToStringTable<const LChar*, CStringTranslator>(c);
+}
+
+template<typename CharacterType>
+struct HashTranslatorCharBuffer {
+ const CharacterType* s;
+ unsigned length;
+};
+
+typedef HashTranslatorCharBuffer<UChar> UCharBuffer;
+struct UCharBufferTranslator {
+ static unsigned hash(const UCharBuffer& buf)
+ {
+ return StringHasher::computeHashAndMaskTop8Bits(buf.s, buf.length);
+ }
+
+ static bool equal(StringImpl* const& str, const UCharBuffer& buf)
+ {
+ return WTF::equal(str, buf.s, buf.length);
+ }
+
+ static void translate(StringImpl*& location, const UCharBuffer& buf, unsigned hash)
+ {
+ location = &StringImpl::create8BitIfPossible(buf.s, buf.length).leakRef();
+ location->setHash(hash);
+ location->setIsAtomic(true);
+ }
+};
+
+template<typename CharacterType>
+struct HashAndCharacters {
+ unsigned hash;
+ const CharacterType* characters;
+ unsigned length;
+};
+
+template<typename CharacterType>
+struct HashAndCharactersTranslator {
+ static unsigned hash(const HashAndCharacters<CharacterType>& buffer)
+ {
+ ASSERT(buffer.hash == StringHasher::computeHashAndMaskTop8Bits(buffer.characters, buffer.length));
+ return buffer.hash;
+ }
+
+ static bool equal(StringImpl* const& string, const HashAndCharacters<CharacterType>& buffer)
+ {
+ return WTF::equal(string, buffer.characters, buffer.length);
+ }
+
+ static void translate(StringImpl*& location, const HashAndCharacters<CharacterType>& buffer, unsigned hash)
+ {
+ location = &StringImpl::create(buffer.characters, buffer.length).leakRef();
+ location->setHash(hash);
+ location->setIsAtomic(true);
+ }
+};
+
+struct HashAndUTF8Characters {
+ unsigned hash;
+ const char* characters;
+ unsigned length;
+ unsigned utf16Length;
+};
+
+struct HashAndUTF8CharactersTranslator {
+ static unsigned hash(const HashAndUTF8Characters& buffer)
+ {
+ return buffer.hash;
+ }
+
+ static bool equal(StringImpl* const& string, const HashAndUTF8Characters& buffer)
+ {
+ if (buffer.utf16Length != string->length())
+ return false;
+
+ // If buffer contains only ASCII characters UTF-8 and UTF16 length are the same.
+ if (buffer.utf16Length != buffer.length) {
+ if (string->is8Bit())
+ return equalLatin1WithUTF8(string->characters8(), buffer.characters, buffer.characters + buffer.length);
+
+ return equalUTF16WithUTF8(string->characters16(), buffer.characters, buffer.characters + buffer.length);
+ }
+
+ if (string->is8Bit()) {
+ const LChar* stringCharacters = string->characters8();
+
+ for (unsigned i = 0; i < buffer.length; ++i) {
+ ASSERT(isASCII(buffer.characters[i]));
+ if (stringCharacters[i] != buffer.characters[i])
+ return false;
+ }
+
+ return true;
+ }
+
+ const UChar* stringCharacters = string->characters16();
+
+ for (unsigned i = 0; i < buffer.length; ++i) {
+ ASSERT(isASCII(buffer.characters[i]));
+ if (stringCharacters[i] != buffer.characters[i])
+ return false;
+ }
+
+ return true;
+ }
+
+ static void translate(StringImpl*& location, const HashAndUTF8Characters& buffer, unsigned hash)
+ {
+ UChar* target;
+ auto newString = StringImpl::createUninitialized(buffer.utf16Length, target);
+
+ bool isAllASCII;
+ const char* source = buffer.characters;
+ if (convertUTF8ToUTF16(&source, source + buffer.length, &target, target + buffer.utf16Length, &isAllASCII) != conversionOK)
+ ASSERT_NOT_REACHED();
+
+ if (isAllASCII)
+ newString = StringImpl::create(buffer.characters, buffer.length);
+
+ location = &newString.leakRef();
+ location->setHash(hash);
+ location->setIsAtomic(true);
+ }
+};
+
+RefPtr<AtomicStringImpl> AtomicStringImpl::add(const UChar* s, unsigned length)
+{
+ if (!s)
+ return nullptr;
+
+ if (!length)
+ return static_cast<AtomicStringImpl*>(StringImpl::empty());
+
+ UCharBuffer buffer = { s, length };
+ return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
+}
+
+Ref<AtomicStringImpl> AtomicStringImpl::add(const UChar* s, unsigned length, unsigned existingHash)
+{
+ ASSERT(s);
+ ASSERT(existingHash);
+
+ if (!length)
+ return *static_cast<AtomicStringImpl*>(StringImpl::empty());
+
+ HashAndCharacters<UChar> buffer = { existingHash, s, length };
+ return addToStringTable<HashAndCharacters<UChar>, HashAndCharactersTranslator<UChar>>(buffer);
+}
+
+RefPtr<AtomicStringImpl> AtomicStringImpl::add(const UChar* s)
+{
+ if (!s)
+ return nullptr;
+
+ unsigned length = 0;
+ while (s[length] != UChar(0))
+ ++length;
+
+ if (!length)
+ return static_cast<AtomicStringImpl*>(StringImpl::empty());
+
+ UCharBuffer buffer = { s, length };
+ return addToStringTable<UCharBuffer, UCharBufferTranslator>(buffer);
+}
+
+struct SubstringLocation {
+ StringImpl* baseString;
+ unsigned start;
+ unsigned length;
+};
+
+struct SubstringTranslator {
+ static void translate(StringImpl*& location, const SubstringLocation& buffer, unsigned hash)
+ {
+ location = &StringImpl::createSubstringSharingImpl(*buffer.baseString, buffer.start, buffer.length).leakRef();
+ location->setHash(hash);
+ location->setIsAtomic(true);
+ }
+};
+
+struct SubstringTranslator8 : SubstringTranslator {
+ static unsigned hash(const SubstringLocation& buffer)
+ {
+ return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters8() + buffer.start, buffer.length);
+ }
+
+ static bool equal(StringImpl* const& string, const SubstringLocation& buffer)
+ {
+ return WTF::equal(string, buffer.baseString->characters8() + buffer.start, buffer.length);
+ }
+};
+
+struct SubstringTranslator16 : SubstringTranslator {
+ static unsigned hash(const SubstringLocation& buffer)
+ {
+ return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters16() + buffer.start, buffer.length);
+ }
+
+ static bool equal(StringImpl* const& string, const SubstringLocation& buffer)
+ {
+ return WTF::equal(string, buffer.baseString->characters16() + buffer.start, buffer.length);
+ }
+};
+
+RefPtr<AtomicStringImpl> AtomicStringImpl::add(StringImpl* baseString, unsigned start, unsigned length)
+{
+ if (!baseString)
+ return nullptr;
+
+ if (!length || start >= baseString->length())
+ return static_cast<AtomicStringImpl*>(StringImpl::empty());
+
+ unsigned maxLength = baseString->length() - start;
+ if (length >= maxLength) {
+ if (!start)
+ return add(baseString);
+ length = maxLength;
+ }
+
+ SubstringLocation buffer = { baseString, start, length };
+ if (baseString->is8Bit())
+ return addToStringTable<SubstringLocation, SubstringTranslator8>(buffer);
+ return addToStringTable<SubstringLocation, SubstringTranslator16>(buffer);
+}
+
+typedef HashTranslatorCharBuffer<LChar> LCharBuffer;
+struct LCharBufferTranslator {
+ static unsigned hash(const LCharBuffer& buf)
+ {
+ return StringHasher::computeHashAndMaskTop8Bits(buf.s, buf.length);
+ }
+
+ static bool equal(StringImpl* const& str, const LCharBuffer& buf)
+ {
+ return WTF::equal(str, buf.s, buf.length);
+ }
+
+ static void translate(StringImpl*& location, const LCharBuffer& buf, unsigned hash)
+ {
+ location = &StringImpl::create(buf.s, buf.length).leakRef();
+ location->setHash(hash);
+ location->setIsAtomic(true);
+ }
+};
+
+typedef HashTranslatorCharBuffer<char> CharBuffer;
+struct CharBufferFromLiteralDataTranslator {
+ static unsigned hash(const CharBuffer& buf)
+ {
+ return StringHasher::computeHashAndMaskTop8Bits(reinterpret_cast<const LChar*>(buf.s), buf.length);
+ }
+
+ static bool equal(StringImpl* const& str, const CharBuffer& buf)
+ {
+ return WTF::equal(str, buf.s, buf.length);
+ }
+
+ static void translate(StringImpl*& location, const CharBuffer& buf, unsigned hash)
+ {
+ location = &StringImpl::createFromLiteral(buf.s, buf.length).leakRef();
+ location->setHash(hash);
+ location->setIsAtomic(true);
+ }
+};
+
+RefPtr<AtomicStringImpl> AtomicStringImpl::add(const LChar* s, unsigned length)
+{
+ if (!s)
+ return nullptr;
+
+ if (!length)
+ return static_cast<AtomicStringImpl*>(StringImpl::empty());
+
+ LCharBuffer buffer = { s, length };
+ return addToStringTable<LCharBuffer, LCharBufferTranslator>(buffer);
+}
+
+Ref<AtomicStringImpl> AtomicStringImpl::addLiteral(const char* characters, unsigned length)
+{
+ ASSERT(characters);
+ ASSERT(length);
+
+ CharBuffer buffer = { characters, length };
+ return addToStringTable<CharBuffer, CharBufferFromLiteralDataTranslator>(buffer);
+}
+
+static inline Ref<AtomicStringImpl> addSubstring(AtomicStringTableLocker& locker, StringTableImpl& atomicStringTable, StringImpl& base)
+{
+ ASSERT(base.length());
+ ASSERT(base.isSymbol() || base.isStatic());
+
+ SubstringLocation buffer = { &base, 0, base.length() };
+ if (base.is8Bit())
+ return addToStringTable<SubstringLocation, SubstringTranslator8>(locker, atomicStringTable, buffer);
+ return addToStringTable<SubstringLocation, SubstringTranslator16>(locker, atomicStringTable, buffer);
+}
+
+static inline Ref<AtomicStringImpl> addSubstring(StringImpl& base)
+{
+ AtomicStringTableLocker locker;
+ return addSubstring(locker, stringTable(), base);
+}
+
+Ref<AtomicStringImpl> AtomicStringImpl::addSlowCase(StringImpl& string)
+{
+ if (!string.length())
+ return *static_cast<AtomicStringImpl*>(StringImpl::empty());
+
+ if (string.isSymbol() || string.isStatic())
+ return addSubstring(string);
+
+ ASSERT_WITH_MESSAGE(!string.isAtomic(), "AtomicStringImpl should not hit the slow case if the string is already atomic.");
+
+ AtomicStringTableLocker locker;
+ auto addResult = stringTable().add(&string);
+
+ if (addResult.isNewEntry) {
+ ASSERT(*addResult.iterator == &string);
+ string.setIsAtomic(true);
+ }
+
+ return *static_cast<AtomicStringImpl*>(*addResult.iterator);
+}
+
+Ref<AtomicStringImpl> AtomicStringImpl::addSlowCase(AtomicStringTable& stringTable, StringImpl& string)
+{
+ if (!string.length())
+ return *static_cast<AtomicStringImpl*>(StringImpl::empty());
+
+ if (string.isSymbol() || string.isStatic()) {
+ AtomicStringTableLocker locker;
+ return addSubstring(locker, stringTable.table(), string);
+ }
+
+ ASSERT_WITH_MESSAGE(!string.isAtomic(), "AtomicStringImpl should not hit the slow case if the string is already atomic.");
+
+ AtomicStringTableLocker locker;
+ auto addResult = stringTable.table().add(&string);
+
+ if (addResult.isNewEntry) {
+ ASSERT(*addResult.iterator == &string);
+ string.setIsAtomic(true);
+ }
+
+ return *static_cast<AtomicStringImpl*>(*addResult.iterator);
+}
+
+void AtomicStringImpl::remove(AtomicStringImpl* string)
+{
+ ASSERT(string->isAtomic());
+ AtomicStringTableLocker locker;
+ auto& atomicStringTable = stringTable();
+ auto iterator = atomicStringTable.find(string);
+ ASSERT_WITH_MESSAGE(iterator != atomicStringTable.end(), "The string being removed is atomic in the string table of an other thread!");
+ ASSERT(string == *iterator);
+ atomicStringTable.remove(iterator);
+}
+
+RefPtr<AtomicStringImpl> AtomicStringImpl::lookUpSlowCase(StringImpl& string)
+{
+ ASSERT_WITH_MESSAGE(!string.isAtomic(), "AtomicStringImpls should return from the fast case.");
+
+ if (!string.length())
+ return static_cast<AtomicStringImpl*>(StringImpl::empty());
+
+ AtomicStringTableLocker locker;
+ auto& atomicStringTable = stringTable();
+ auto iterator = atomicStringTable.find(&string);
+ if (iterator != atomicStringTable.end())
+ return static_cast<AtomicStringImpl*>(*iterator);
+ return nullptr;
+}
+
+RefPtr<AtomicStringImpl> AtomicStringImpl::addUTF8(const char* charactersStart, const char* charactersEnd)
+{
+ HashAndUTF8Characters buffer;
+ buffer.characters = charactersStart;
+ buffer.hash = calculateStringHashAndLengthFromUTF8MaskingTop8Bits(charactersStart, charactersEnd, buffer.length, buffer.utf16Length);
+
+ if (!buffer.hash)
+ return nullptr;
+
+ return addToStringTable<HashAndUTF8Characters, HashAndUTF8CharactersTranslator>(buffer);
+}
+
+RefPtr<AtomicStringImpl> AtomicStringImpl::lookUpInternal(const LChar* characters, unsigned length)
+{
+ AtomicStringTableLocker locker;
+ auto& table = stringTable();
+
+ LCharBuffer buffer = { characters, length };
+ auto iterator = table.find<LCharBufferTranslator>(buffer);
+ if (iterator != table.end())
+ return static_cast<AtomicStringImpl*>(*iterator);
+ return nullptr;
+}
+
+RefPtr<AtomicStringImpl> AtomicStringImpl::lookUpInternal(const UChar* characters, unsigned length)
+{
+ AtomicStringTableLocker locker;
+ auto& table = stringTable();
+
+ UCharBuffer buffer = { characters, length };
+ auto iterator = table.find<UCharBufferTranslator>(buffer);
+ if (iterator != table.end())
+ return static_cast<AtomicStringImpl*>(*iterator);
+ return nullptr;
+}
+
+#if !ASSERT_DISABLED
+bool AtomicStringImpl::isInAtomicStringTable(StringImpl* string)
+{
+ AtomicStringTableLocker locker;
+ return stringTable().contains(string);
+}
+#endif
+
+} // namespace WTF