2 * Copyright (c) 2021 Samsung Electronics Co., Ltd.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
19 #include <dali/internal/common/const-string.h>
29 #include <dali/public-api/common/dali-common.h>
44 for(auto& page : mPages)
49 char* Allocate(uint32_t size, uint32_t alignment)
51 uintptr_t mask = alignment - 1;
52 uintptr_t alignedOffset = (~reinterpret_cast<uintptr_t>(mCursor) + 1) & mask;
53 uintptr_t totalSize = size + alignedOffset;
55 if(totalSize > static_cast<uintptr_t>(mEnd - mCursor))
58 alignedOffset = (~reinterpret_cast<uintptr_t>(mCursor) + 1) & mask;
60 char* ptr = mCursor + alignedOffset;
68 constexpr size_t pageSize = 4096;
69 char* page = new char[pageSize];
70 mPages.push_back(page);
72 mEnd = mCursor + pageSize;
75 char* mCursor{nullptr};
77 std::vector<char*> mPages;
83 explicit StringEntry(uint16_t stringLength)
84 : mStringLength(stringLength)
87 size_t getStringLength() const
91 const char* GetStringData() const
93 return reinterpret_cast<const char*>(this + 1);
96 std::string_view GetString() const
98 return std::string_view(GetStringData(), getStringLength());
101 * GetStringEntryFromData - Given key data that is known to be embedded
102 * into a StringEntry, return the StringEntry itself.
104 static StringEntry& GetStringEntryFromData(const char* stringData)
106 char* ptr = const_cast<char*>(stringData) - sizeof(StringEntry);
107 return *reinterpret_cast<StringEntry*>(ptr);
110 * Create a StringEntry from string_view
113 static StringEntry* Create(std::string_view str, ArenaAllocator& allocator)
115 size_t length = str.size();
117 // Allocate a new item with space for the string at the end and a null
119 size_t allocSize = sizeof(StringEntry) + length + 1;
120 size_t alignment = alignof(StringEntry);
122 // Construct the value.
123 StringEntry* newItem = new(allocator.Allocate(allocSize, alignment)) StringEntry(length);
125 // Copy the string information.
126 char* strBuffer = const_cast<char*>(newItem->GetStringData());
128 memcpy(strBuffer, str.data(), length);
129 strBuffer[length] = 0; // Null terminate.
134 uint16_t mStringLength;
140 unsigned Size() const
149 static StringPool& Instance()
151 static StringPool object;
155 const char* Intern(std::string_view str)
157 const std::lock_guard<std::mutex> lock(mMutex);
159 auto bucketNumber = FindBucket(str);
160 auto& bucket = mTable[bucketNumber];
164 // string already exists
165 return bucket->GetStringData();
168 // assign the newly created StringEntry to the designated bucket.
169 bucket = StringEntry::Create(str, mAllocator);
173 bucketNumber = RehashTable(bucketNumber);
175 return mTable[bucketNumber]->GetStringData();
179 unsigned NextBucket(unsigned currentBucket, unsigned totalBucket, unsigned ProbeAmount)
181 return (currentBucket + ProbeAmount) & (totalBucket - 1);
186 unsigned newBuckets = 512;
188 * for memory efficiency and cache locality we store the StringEntry and corresponding HashValue in separate
189 * segments in this way each entry in the bucket will take 12byte instead of 16 if we keep them together.
190 * So we allocate one memory and treat 1st segment as a array of StringEntry* and the second segment as array of
193 mTable = static_cast<StringEntry**>(calloc(newBuckets + 1, sizeof(StringEntry**) + sizeof(unsigned)));
194 DALI_ASSERT_ALWAYS(mTable && "calloc returned nullptr");
196 mBuckets = newBuckets;
199 unsigned FindBucket(std::string_view name)
201 unsigned bucketSize = mBuckets;
202 unsigned fullHashValue = std::hash<std::string_view>{}(name);
203 unsigned bucketNumber = fullHashValue & (bucketSize - 1);
204 // point to the start of the hashvalue segment.
205 unsigned* hashTable = reinterpret_cast<unsigned*>(mTable + mBuckets + 1);
207 unsigned probeAmt = 1;
210 StringEntry* bucketItem = mTable[bucketNumber];
211 // If we found an empty bucket, this key isn't in the table yet, return it.
214 hashTable[bucketNumber] = fullHashValue;
218 if(hashTable[bucketNumber] == fullHashValue)
220 // If the full hash value matches, check deeply for a match.
221 if(name == bucketItem->GetString())
228 // Okay, we didn't find the item. Probe to the next bucket.
229 bucketNumber = NextBucket(bucketNumber, bucketSize, probeAmt);
231 // Use quadratic probing, it has fewer clumping artifacts than linear
235 unsigned RehashTable(unsigned bucketNumber)
238 unsigned* hashTable = reinterpret_cast<unsigned*>(mTable + mBuckets + 1);
240 // If the hash table is now more than 3/4 full.
241 // grow/rehash the table.
242 if((mItems * 4) > (mBuckets * 3))
244 newSize = mBuckets * 2;
250 unsigned newBucketNumber = bucketNumber;
252 // Allocate one extra bucket which will always be non-empty.
253 auto newTable = static_cast<StringEntry**>(calloc(newSize + 1, sizeof(StringEntry*) + sizeof(unsigned)));
254 DALI_ASSERT_ALWAYS(newTable && "calloc returned nullptr");
256 // point to the start of the hashvalue segment. as the pointer is of type StringEntry* , but the
257 // second segment keeps only unsigned data hence the reinterpret_cast.
258 unsigned* newHashTable = reinterpret_cast<unsigned*>(newTable + newSize + 1);
260 // Rehash all the items into their new buckets.
261 for(unsigned i = 0, j = mBuckets; i != j; ++i)
263 StringEntry* bucket = mTable[i];
266 // Fast case, bucket available.
267 unsigned fullHash = hashTable[i];
268 unsigned newBucket = fullHash & (newSize - 1);
269 if(!newTable[newBucket])
271 newTable[fullHash & (newSize - 1)] = bucket;
272 newHashTable[fullHash & (newSize - 1)] = fullHash;
273 if(i == bucketNumber)
274 newBucketNumber = newBucket;
278 // Otherwise probe for a spot.
279 unsigned ProbeSize = 1;
282 newBucket = NextBucket(newBucket, newSize, ProbeSize++);
283 } while(newTable[newBucket]);
285 // Finally found a slot. Fill it in.
286 newTable[newBucket] = bucket;
287 newHashTable[newBucket] = fullHash;
288 if(i == bucketNumber)
289 newBucketNumber = newBucket;
297 return newBucketNumber;
302 ArenaAllocator mAllocator;
303 StringEntry** mTable{nullptr};
304 unsigned mBuckets{0};
310 Dali::Internal::ConstString::ConstString(std::string_view str)
312 mString = StringPool::Instance().Intern(str);
315 size_t Dali::Internal::ConstString::GetLength() const
317 return mString ? StringEntry::GetStringEntryFromData(mString).getStringLength() : 0;
320 void Dali::Internal::ConstString::SetString(std::string_view str)
328 mString = StringPool::Instance().Intern(str);