- thread safe StringPool.
- uses arena allocator to allocate the StringEntry object.
- Internal strings are allocated in String pages instead of indivisual heap allocation.
- Both StringData and length are stored in same location(StringEntry).
- StringPool implements FlatHash with open addresssing and Quadratic Probing (adopted from llvm)
Change-Id: Ib1b1d3bc74718dd613e924236bb1845e83f42353
utc-Dali-Internal-RotationGesture.cpp
utc-Dali-Internal-TapGesture.cpp
utc-Dali-Internal-TapGestureProcessor.cpp
+ utc-Dali-Internal-ConstString.cpp
)
LIST(APPEND TC_SOURCES
--- /dev/null
+/*
+ * Copyright (c) 2020 Samsung Electronics Co., Ltd.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+
+#include <dali-test-suite-utils.h>
+#include <dali/public-api/dali-core.h>
+
+#include <random>
+#include <string>
+
+// Internal headers are allowed here
+#include <dali/internal/common/const-string.h>
+
+using namespace Dali;
+
+namespace
+{
+std::string RandomString(size_t length)
+{
+ static auto& chrs =
+ "0123456789"
+ "abcdefghijklmnopqrstuvwxyz"
+ "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+
+ thread_local static std::mt19937 rg{std::random_device{}()};
+ thread_local static std::uniform_int_distribution<std::string::size_type> pick(0, sizeof(chrs) - 2);
+
+ std::string s;
+
+ s.reserve(length);
+
+ while(length--)
+ s += chrs[pick(rg)];
+
+ return s;
+}
+} // namespace
+
+void utc_dali_internal_conststring_startup(void)
+{
+ test_return_value = TET_UNDEF;
+}
+
+void utc_dali_internal_conststring_cleanup(void)
+{
+ test_return_value = TET_PASS;
+}
+
+int UtcDaliConstStringEmpty(void)
+{
+ Internal::ConstString str1;
+ DALI_TEST_EQUALS(str1.IsEmpty(), true, TEST_LOCATION);
+
+ Internal::ConstString str2("hello");
+ DALI_TEST_EQUALS(str2.IsEmpty(), false, TEST_LOCATION);
+
+ str2.Clear();
+ DALI_TEST_EQUALS(str2.IsEmpty(), true, TEST_LOCATION);
+
+ END_TEST;
+}
+
+int UtcDaliConstStringConstruct(void)
+{
+ Internal::ConstString str1("string1");
+ DALI_TEST_EQUALS(str1.GetCString(), "string1", TEST_LOCATION);
+
+ Internal::ConstString str2("string1");
+
+ DALI_TEST_EQUALS(str2.GetCString(), "string1", TEST_LOCATION);
+
+ bool samePointer = (str1.GetCString() == str2.GetCString());
+ DALI_TEST_EQUALS(samePointer, true, TEST_LOCATION);
+
+ str1.Clear();
+ DALI_TEST_EQUALS(str2.GetCString(), "string1", TEST_LOCATION);
+
+ END_TEST;
+}
+
+int UtcDaliConstStringConstructStringView(void)
+{
+ Internal::ConstString str1(std::string_view("random string"));
+
+ DALI_TEST_EQUALS(str1.GetStringView().data(), "random string", TEST_LOCATION);
+ DALI_TEST_EQUALS(str1.GetStringView().size(), 13, TEST_LOCATION);
+
+ END_TEST;
+}
+
+int UtcDaliConstStringSetString(void)
+{
+ Internal::ConstString str1(std::string_view("current string"));
+
+ DALI_TEST_EQUALS(str1.GetStringView().data(), "current string", TEST_LOCATION);
+
+ str1.SetString("new string");
+
+ DALI_TEST_EQUALS(str1.GetCString(), "new string", TEST_LOCATION);
+
+ END_TEST;
+}
+
+int UtcDaliConstStringStressTest(void)
+{
+ static constexpr size_t DB_SIZE = 2000;
+
+ std::vector<std::string> Database;
+ Database.reserve(DB_SIZE);
+
+ std::vector<Internal::ConstString> constStringDB;
+ constStringDB.reserve(DB_SIZE);
+
+ std::vector<Internal::ConstString> constStringDB1;
+ constStringDB1.reserve(DB_SIZE);
+
+ for(auto i = 0u; i < DB_SIZE; i++)
+ {
+ if(i % 3 == 0)
+ {
+ Database.push_back(RandomString(10));
+ }
+ else if(i % 4 == 0)
+ {
+ Database.push_back(RandomString(7));
+ }
+ else
+ {
+ Database.push_back(RandomString(11));
+ }
+ constStringDB.push_back(Internal::ConstString(Database[i]));
+ constStringDB1.push_back(Internal::ConstString(Database[i]));
+ }
+
+ // check eqality betwwen original string and constString
+ for(auto i = 0u; i < DB_SIZE; i++)
+ {
+ DALI_TEST_EQUALS(constStringDB[i].GetCString(), Database[i].c_str(), TEST_LOCATION);
+ }
+
+ // check pointer eqality betwwen 2 constString
+ for(auto i = 0u; i < DB_SIZE; i++)
+ {
+ bool pointerEqual = (constStringDB[i] == constStringDB1[i]);
+ DALI_TEST_EQUALS(pointerEqual, true, TEST_LOCATION);
+ }
+
+ END_TEST;
+}
--- /dev/null
+/*
+ * Copyright (c) 2020 Samsung Electronics Co., Ltd.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+
+// CLASS HEADER
+#include <dali/internal/common/const-string.h>
+
+// EXTERNAL INCLUDES
+#include <cstddef>
+#include <cstring>
+#include <functional>
+#include <vector>
+#include <mutex>
+
+// local namespace
+namespace
+{
+class ArenaAllocator
+{
+
+public:
+ ArenaAllocator()
+ {
+ mPages.reserve(10);
+ EnsureSpace();
+ }
+ ~ArenaAllocator()
+ {
+ for(auto& page : mPages)
+ {
+ delete[] page;
+ }
+ }
+ char* Allocate(uint32_t size, uint32_t alignment)
+ {
+ uintptr_t mask = alignment - 1;
+ uintptr_t alignedOffset = (~reinterpret_cast<uintptr_t>(mCursor) + 1) & mask;
+ uintptr_t totalSize = size + alignedOffset;
+
+ if(totalSize > static_cast<uintptr_t>(mEnd - mCursor))
+ {
+ EnsureSpace();
+ alignedOffset = (~reinterpret_cast<uintptr_t>(mCursor) + 1) & mask;
+ }
+ char* ptr = mCursor + alignedOffset;
+ mCursor = ptr + size;
+ return ptr;
+ }
+
+private:
+ void EnsureSpace()
+ {
+ constexpr size_t pageSize = 4096;
+ char* page = new char[pageSize];
+ mPages.push_back(page);
+ mCursor = page;
+ mEnd = mCursor + pageSize;
+ }
+
+ char* mCursor{nullptr};
+ char* mEnd{nullptr};
+ std::vector<char*> mPages;
+};
+
+class StringEntry
+{
+public:
+ explicit StringEntry(uint16_t stringLength)
+ : mStringLength(stringLength)
+ {
+ }
+ size_t getStringLength() const
+ {
+ return mStringLength;
+ }
+ const char* GetStringData() const
+ {
+ return reinterpret_cast<const char*>(this + 1);
+ }
+
+ std::string_view GetString() const
+ {
+ return std::string_view(GetStringData(), getStringLength());
+ }
+ /**
+ * GetStringEntryFromData - Given key data that is known to be embedded
+ * into a StringEntry, return the StringEntry itself.
+ */
+ static StringEntry& GetStringEntryFromData(const char* stringData)
+ {
+ char* ptr = const_cast<char*>(stringData) - sizeof(StringEntry);
+ return *reinterpret_cast<StringEntry*>(ptr);
+ }
+ /**
+ * Create a StringEntry from string_view
+ *
+ */
+ static StringEntry* Create(std::string_view str, ArenaAllocator& allocator)
+ {
+ size_t length = str.size();
+
+ // Allocate a new item with space for the string at the end and a null
+ // terminator.
+ size_t allocSize = sizeof(StringEntry) + length + 1;
+ size_t alignment = alignof(StringEntry);
+
+ // Construct the value.
+ StringEntry* newItem = new(allocator.Allocate(allocSize, alignment)) StringEntry(length);
+
+ // Copy the string information.
+ char* strBuffer = const_cast<char*>(newItem->GetStringData());
+ if(length > 0)
+ memcpy(strBuffer, str.data(), length);
+ strBuffer[length] = 0; // Null terminate.
+ return newItem;
+ }
+
+private:
+ uint16_t mStringLength;
+};
+
+class StringPool
+{
+public:
+ unsigned Size() const
+ {
+ return mItems;
+ }
+ StringPool()
+ {
+ Init();
+ }
+
+ static StringPool& Instance()
+ {
+ static StringPool object;
+ return object;
+ }
+
+ const char* Intern(std::string_view str)
+ {
+ const std::lock_guard<std::mutex> lock(mMutex);
+
+ auto bucketNumber = FindBucket(str);
+ auto& bucket = mTable[bucketNumber];
+
+ if(bucket)
+ {
+ // string already exists
+ return bucket->GetStringData();
+ }
+
+ // assign the newly created StringEntry to the designated bucket.
+ bucket = StringEntry::Create(str, mAllocator);
+
+ ++mItems;
+
+ bucketNumber = RehashTable(bucketNumber);
+
+ return mTable[bucketNumber]->GetStringData();
+ }
+
+private:
+ unsigned NextBucket(unsigned currentBucket, unsigned totalBucket, unsigned ProbeAmount)
+ {
+ return (currentBucket + ProbeAmount) & (totalBucket - 1);
+ }
+
+ void Init()
+ {
+ unsigned newBuckets = 512;
+ /**
+ * for memory efficiency and cache locality we store the StringEntry and corresponding HashValue in separate
+ * segments in this way each entry in the bucket will take 12byte instead of 16 if we keep them together.
+ * So we allocate one memory and treat 1st segment as a array of StringEntry* and the second segment as array of
+ * unsigned*.
+ */
+ mTable = static_cast<StringEntry**>(calloc(newBuckets + 1, sizeof(StringEntry**) + sizeof(unsigned)));
+ mBuckets = newBuckets;
+ }
+
+ unsigned FindBucket(std::string_view name)
+ {
+ unsigned bucketSize = mBuckets;
+ unsigned fullHashValue = std::hash<std::string_view>{}(name);
+ unsigned bucketNumber = fullHashValue & (bucketSize - 1);
+ // point to the start of the hashvalue segment.
+ unsigned* hashTable = reinterpret_cast<unsigned*>(mTable + mBuckets + 1);
+
+ unsigned probeAmt = 1;
+ while(true)
+ {
+ StringEntry* bucketItem = mTable[bucketNumber];
+ // If we found an empty bucket, this key isn't in the table yet, return it.
+ if(!bucketItem)
+ {
+ hashTable[bucketNumber] = fullHashValue;
+ return bucketNumber;
+ }
+
+ if(hashTable[bucketNumber] == fullHashValue)
+ {
+ // If the full hash value matches, check deeply for a match.
+ if(name == bucketItem->GetString())
+ {
+ // We found a match!
+ return bucketNumber;
+ }
+ }
+
+ // Okay, we didn't find the item. Probe to the next bucket.
+ bucketNumber = NextBucket(bucketNumber, bucketSize, probeAmt);
+
+ // Use quadratic probing, it has fewer clumping artifacts than linear
+ ++probeAmt;
+ }
+ }
+ unsigned RehashTable(unsigned bucketNumber)
+ {
+ unsigned newSize;
+ unsigned* hashTable = reinterpret_cast<unsigned*>(mTable + mBuckets + 1);
+
+ // If the hash table is now more than 3/4 full.
+ // grow/rehash the table.
+ if((mItems * 4) > (mBuckets * 3))
+ {
+ newSize = mBuckets * 2;
+ }
+ else
+ {
+ return bucketNumber;
+ }
+ unsigned newBucketNumber = bucketNumber;
+ // Allocate one extra bucket which will always be non-empty.
+ auto newTable = static_cast<StringEntry**>(calloc(newSize + 1, sizeof(StringEntry*) + sizeof(unsigned)));
+ // point to the start of the hashvalue segment. as the pointer is of type StringEntry* , but the
+ // second segment keeps only unsigned data hence the reinterpret_cast.
+ unsigned* newHashTable = reinterpret_cast<unsigned*>(newTable + newSize + 1);
+
+ // Rehash all the items into their new buckets.
+ for(unsigned i = 0, j = mBuckets; i != j; ++i)
+ {
+ StringEntry* bucket = mTable[i];
+ if(bucket)
+ {
+ // Fast case, bucket available.
+ unsigned fullHash = hashTable[i];
+ unsigned newBucket = fullHash & (newSize - 1);
+ if(!newTable[newBucket])
+ {
+ newTable[fullHash & (newSize - 1)] = bucket;
+ newHashTable[fullHash & (newSize - 1)] = fullHash;
+ if(i == bucketNumber)
+ newBucketNumber = newBucket;
+ continue;
+ }
+
+ // Otherwise probe for a spot.
+ unsigned ProbeSize = 1;
+ do
+ {
+ newBucket = NextBucket(newBucket, newSize, ProbeSize++);
+ } while(newTable[newBucket]);
+
+ // Finally found a slot. Fill it in.
+ newTable[newBucket] = bucket;
+ newHashTable[newBucket] = fullHash;
+ if(i == bucketNumber)
+ newBucketNumber = newBucket;
+ }
+ }
+
+ free(mTable);
+
+ mTable = newTable;
+ mBuckets = newSize;
+ return newBucketNumber;
+ }
+
+private:
+ std::mutex mMutex;
+ ArenaAllocator mAllocator;
+ StringEntry** mTable{nullptr};
+ unsigned mBuckets{0};
+ unsigned mItems{0};
+};
+
+} // namespace
+
+Dali::Internal::ConstString::ConstString(std::string_view str)
+{
+ mString = StringPool::Instance().Intern(str);
+}
+
+size_t Dali::Internal::ConstString::GetLength() const
+{
+ return mString ? StringEntry::GetStringEntryFromData(mString).getStringLength() : 0;
+}
+
+void Dali::Internal::ConstString::SetString(std::string_view str)
+{
+ if(str.empty())
+ {
+ mString = nullptr;
+ }
+ else
+ {
+ mString = StringPool::Instance().Intern(str);
+ }
+}
\ No newline at end of file
--- /dev/null
+#ifndef DALI_INTERNAL_CONST_STRING_H
+#define DALI_INTERNAL_CONST_STRING_H
+
+/*
+ * Copyright (c) 2020 Samsung Electronics Co., Ltd.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+
+#include <string_view>
+
+namespace Dali
+{
+namespace Internal
+{
+/**
+ * A uniqued constant string class.
+ *
+ * Provides an efficient way to store strings as uniqued strings. After the
+ * strings are uniqued, finding strings that are equal to one another is very
+ * fast as just the pointers need to be compared. It also allows for many
+ * common strings from many different sources to be shared to keep the memory
+ * footprint low.
+ *
+ * No reference counting is done on strings that are added to the string
+ * pool, once strings are added they are in the string pool for the life of
+ * the program.
+ */
+class ConstString
+{
+public:
+ /**
+ * Default constructor
+ *
+ * Initializes the string to an empty string.
+ */
+ ConstString() = default;
+
+ explicit ConstString(std::string_view str);
+
+ /**
+ * Convert to bool operator.
+ *
+ * This allows code to check a ConstString object to see if it contains a
+ * valid string using code such as:
+ *
+ * \code
+ * ConstString str(...);
+ * if (str)
+ * { ...
+ * \endcode
+ *
+ * \return
+ * /b True this object contains a valid non-empty C string, \b
+ * false otherwise.
+ */
+ explicit operator bool() const
+ {
+ return !IsEmpty();
+ }
+
+ /**
+ * Equal to operator
+ *
+ * Returns true if this string is equal to the string in \a rhs. This
+ * operation is very fast as it results in a pointer comparison since all
+ * strings are in a uniqued in a global string pool.
+ *
+ * \param[in] rhs
+ * Another string object to compare this object to.
+ *
+ * \return
+ * true if this object is equal to \a rhs.
+ * false if this object is not equal to \a rhs.
+ */
+ bool operator==(ConstString rhs) const
+ {
+ // We can do a pointer compare to compare these strings since they must
+ // come from the same pool in order to be equal.
+ return mString == rhs.mString;
+ }
+
+ /**
+ * Equal to operator against a non-ConstString value.
+ *
+ * Returns true if this string is equal to the string in \a rhs.
+ *
+ * \param[in] rhs
+ * Another string object to compare this object to.
+ *
+ * \return
+ * \b true if this object is equal to \a rhs.
+ * \b false if this object is not equal to \a rhs.
+ */
+ bool operator==(const char* rhs) const
+ {
+ // ConstString differentiates between empty strings and nullptr strings, but
+ // StringRef doesn't. Therefore we have to do this check manually now.
+ if(mString == nullptr && rhs != nullptr)
+ return false;
+ if(mString != nullptr && rhs == nullptr)
+ return false;
+
+ return GetStringView() == rhs;
+ }
+
+ /**
+ * Not equal to operator
+ *
+ * Returns true if this string is not equal to the string in \a rhs. This
+ * operation is very fast as it results in a pointer comparison since all
+ * strings are in a uniqued in a global string pool.
+ *
+ * \param[in] rhs
+ * Another string object to compare this object to.
+ *
+ * \return
+ * \b true if this object is not equal to \a rhs.
+ * \b false if this object is equal to \a rhs.
+ */
+ bool operator!=(ConstString rhs) const
+ {
+ return mString != rhs.mString;
+ }
+
+ /**
+ * Not equal to operator against a non-ConstString value.
+ *
+ * Returns true if this string is not equal to the string in \a rhs.
+ *
+ * \param[in] rhs
+ * Another string object to compare this object to.
+ *
+ * \return \b true if this object is not equal to \a rhs, false otherwise.
+ */
+ bool operator!=(const char* rhs) const
+ {
+ return !(*this == rhs);
+ }
+
+ /**
+ * Get the string value as a std::string_view
+ *
+ * \return
+ * Returns a new std::string_view object filled in with the
+ * needed data.
+ */
+ std::string_view GetStringView() const
+ {
+ return mString ? std::string_view(mString, GetLength()) : std::string_view();
+ }
+
+ /**
+ * Get the string value as a C string.
+ *
+ * Get the value of the contained string as a NULL terminated C string
+ * value. This function will always return nullptr if the string is not valid.
+ * So this function is a direct accessor to the string pointer value.
+ *
+ * \return
+ * Returns nullptr the string is invalid, otherwise the C string
+ * value contained in this object.
+ */
+ const char* GetCString() const
+ {
+ return mString;
+ }
+
+ /**
+ * Get the length in bytes of string value.
+ *
+ * The string pool stores the length of the string, so we can avoid calling
+ * strlen() on the pointer value with this function.
+ *
+ * \return
+ * Returns the number of bytes that this string occupies in
+ * memory, not including the NULL termination byte.
+ */
+ size_t GetLength() const;
+
+ /**
+ * Clear this object's state.
+ *
+ * Clear any contained string and reset the value to the empty string
+ * value.
+ */
+ void Clear()
+ {
+ mString = nullptr;
+ }
+
+ /**
+ * Test for empty string.
+ *
+ * \return
+ * \b true if the contained string is empty.
+ * \b false if the contained string is not empty.
+ */
+ bool IsEmpty() const
+ {
+ return mString == nullptr || mString[0] == '\0';
+ }
+
+ /**
+ * Set the string_view value.
+ *
+ * Set the string value in the object by uniquing the \a str string value
+ * in our global string pool.
+ *
+ * If the string is already exists in the global string pool, it finds the
+ * current entry and returns the existing value. If it doesn't exist, it is
+ * added to the string pool.
+ *
+ * \param[in] str
+ * A string_view to add to the string pool.
+ */
+ void SetString(std::string_view str);
+
+private:
+ const char* mString{nullptr};
+};
+
+} // namespace Internal
+
+} // namespace Dali
+
+#endif // DALI_INTERNAL_CONST_STRING_H
${internal_src_dir}/common/image-sampler.cpp
${internal_src_dir}/common/image-attributes.cpp
${internal_src_dir}/common/fixed-size-memory-pool.cpp
+ ${internal_src_dir}/common/const-string.cpp
+
${internal_src_dir}/event/actors/actor-impl.cpp
${internal_src_dir}/event/actors/actor-property-handler.cpp
projects / platform / core / uifw / dali-core.git / commitdiff