dali/internal/common/const-string.cpp

   1 /*
   2  * Copyright (c) 2021 Samsung Electronics Co., Ltd.
   3  *
   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
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  *
  16  */
  17
  18 // CLASS HEADER
  19 #include <dali/internal/common/const-string.h>
  20
  21 // EXTERNAL INCLUDES
  22 #include <cstddef>
  23 #include <cstring>
  24 #include <functional>
  25 #include <mutex>
  26 #include <vector>
  27
  28 // INTERNAL INCLUDES
  29 #include <dali/public-api/common/dali-common.h>
  30
  31 // local namespace
  32 namespace
  33 {
  34 class ArenaAllocator
  35 {
  36 public:
  37   ArenaAllocator()
  38   {
  39     mPages.reserve(10);
  40     EnsureSpace();
  41   }
  42   ~ArenaAllocator()
  43   {
  44     for(auto& page : mPages)
  45     {
  46       delete[] page;
  47     }
  48   }
  49   char* Allocate(uint32_t size, uint32_t alignment)
  50   {
  51     uintptr_t mask          = alignment - 1;
  52     uintptr_t alignedOffset = (~reinterpret_cast<uintptr_t>(mCursor) + 1) & mask;
  53     uintptr_t totalSize     = size + alignedOffset;
  54
  55     if(totalSize > static_cast<uintptr_t>(mEnd - mCursor))
  56     {
  57       EnsureSpace();
  58       alignedOffset = (~reinterpret_cast<uintptr_t>(mCursor) + 1) & mask;
  59     }
  60     char* ptr = mCursor + alignedOffset;
  61     mCursor   = ptr + size;
  62     return ptr;
  63   }
  64
  65 private:
  66   void EnsureSpace()
  67   {
  68     constexpr size_t pageSize = 4096;
  69     char*            page     = new char[pageSize];
  70     mPages.push_back(page);
  71     mCursor = page;
  72     mEnd    = mCursor + pageSize;
  73   }
  74
  75   char*              mCursor{nullptr};
  76   char*              mEnd{nullptr};
  77   std::vector<char*> mPages;
  78 };
  79
  80 class StringEntry
  81 {
  82 public:
  83   explicit StringEntry(uint16_t stringLength)
  84   : mStringLength(stringLength)
  85   {
  86   }
  87   size_t getStringLength() const
  88   {
  89     return mStringLength;
  90   }
  91   const char* GetStringData() const
  92   {
  93     return reinterpret_cast<const char*>(this + 1);
  94   }
  95
  96   std::string_view GetString() const
  97   {
  98     return std::string_view(GetStringData(), getStringLength());
  99   }
 100   /**
 101    * GetStringEntryFromData - Given key data that is known to be embedded
 102    * into a StringEntry, return the StringEntry itself.
 103    */
 104   static StringEntry& GetStringEntryFromData(const char* stringData)
 105   {
 106     char* ptr = const_cast<char*>(stringData) - sizeof(StringEntry);
 107     return *reinterpret_cast<StringEntry*>(ptr);
 108   }
 109   /**
 110    * Create a StringEntry from string_view
 111    *
 112    */
 113   static StringEntry* Create(std::string_view str, ArenaAllocator& allocator)
 114   {
 115     size_t length = str.size();
 116
 117     // Allocate a new item with space for the string at the end and a null
 118     // terminator.
 119     size_t allocSize = sizeof(StringEntry) + length + 1;
 120     size_t alignment = alignof(StringEntry);
 121
 122     // Construct the value.
 123     StringEntry* newItem = new(allocator.Allocate(allocSize, alignment)) StringEntry(length);
 124
 125     // Copy the string information.
 126     char* strBuffer = const_cast<char*>(newItem->GetStringData());
 127     if(length > 0)
 128       memcpy(strBuffer, str.data(), length);
 129     strBuffer[length] = 0; // Null terminate.
 130     return newItem;
 131   }
 132
 133 private:
 134   uint16_t mStringLength;
 135 };
 136
 137 class StringPool
 138 {
 139 public:
 140   unsigned Size() const
 141   {
 142     return mItems;
 143   }
 144   StringPool()
 145   {
 146     Init();
 147   }
 148
 149   static StringPool& Instance()
 150   {
 151     static StringPool object;
 152     return object;
 153   }
 154
 155   const char* Intern(std::string_view str)
 156   {
 157     const std::lock_guard<std::mutex> lock(mMutex);
 158
 159     auto  bucketNumber = FindBucket(str);
 160     auto& bucket       = mTable[bucketNumber];
 161
 162     if(bucket)
 163     {
 164       // string already exists
 165       return bucket->GetStringData();
 166     }
 167
 168     // assign the newly created StringEntry to the designated bucket.
 169     bucket = StringEntry::Create(str, mAllocator);
 170
 171     ++mItems;
 172
 173     bucketNumber = RehashTable(bucketNumber);
 174
 175     return mTable[bucketNumber]->GetStringData();
 176   }
 177
 178 private:
 179   unsigned NextBucket(unsigned currentBucket, unsigned totalBucket, unsigned ProbeAmount)
 180   {
 181     return (currentBucket + ProbeAmount) & (totalBucket - 1);
 182   }
 183
 184   void Init()
 185   {
 186     unsigned newBuckets = 512;
 187     /**
 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
 191      * unsigned*.
 192      */
 193     mTable = static_cast<StringEntry**>(calloc(newBuckets + 1, sizeof(StringEntry**) + sizeof(unsigned)));
 194     DALI_ASSERT_ALWAYS(mTable && "calloc returned nullptr");
 195
 196     mBuckets = newBuckets;
 197   }
 198
 199   unsigned FindBucket(std::string_view name)
 200   {
 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);
 206
 207     unsigned probeAmt = 1;
 208     while(true)
 209     {
 210       StringEntry* bucketItem = mTable[bucketNumber];
 211       // If we found an empty bucket, this key isn't in the table yet, return it.
 212       if(!bucketItem)
 213       {
 214         hashTable[bucketNumber] = fullHashValue;
 215         return bucketNumber;
 216       }
 217
 218       if(hashTable[bucketNumber] == fullHashValue)
 219       {
 220         // If the full hash value matches, check deeply for a match.
 221         if(name == bucketItem->GetString())
 222         {
 223           // We found a match!
 224           return bucketNumber;
 225         }
 226       }
 227
 228       // Okay, we didn't find the item.  Probe to the next bucket.
 229       bucketNumber = NextBucket(bucketNumber, bucketSize, probeAmt);
 230
 231       // Use quadratic probing, it has fewer clumping artifacts than linear
 232       ++probeAmt;
 233     }
 234   }
 235   unsigned RehashTable(unsigned bucketNumber)
 236   {
 237     unsigned  newSize;
 238     unsigned* hashTable = reinterpret_cast<unsigned*>(mTable + mBuckets + 1);
 239
 240     // If the hash table is now more than 3/4 full.
 241     // grow/rehash the table.
 242     if((mItems * 4) > (mBuckets * 3))
 243     {
 244       newSize = mBuckets * 2;
 245     }
 246     else
 247     {
 248       return bucketNumber;
 249     }
 250     unsigned newBucketNumber = bucketNumber;
 251
 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");
 255
 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);
 259
 260     // Rehash all the items into their new buckets.
 261     for(unsigned i = 0, j = mBuckets; i != j; ++i)
 262     {
 263       StringEntry* bucket = mTable[i];
 264       if(bucket)
 265       {
 266         // Fast case, bucket available.
 267         unsigned fullHash  = hashTable[i];
 268         unsigned newBucket = fullHash & (newSize - 1);
 269         if(!newTable[newBucket])
 270         {
 271           newTable[fullHash & (newSize - 1)]     = bucket;
 272           newHashTable[fullHash & (newSize - 1)] = fullHash;
 273           if(i == bucketNumber)
 274             newBucketNumber = newBucket;
 275           continue;
 276         }
 277
 278         // Otherwise probe for a spot.
 279         unsigned ProbeSize = 1;
 280         do
 281         {
 282           newBucket = NextBucket(newBucket, newSize, ProbeSize++);
 283         } while(newTable[newBucket]);
 284
 285         // Finally found a slot.  Fill it in.
 286         newTable[newBucket]     = bucket;
 287         newHashTable[newBucket] = fullHash;
 288         if(i == bucketNumber)
 289           newBucketNumber = newBucket;
 290       }
 291     }
 292
 293     free(mTable);
 294
 295     mTable   = newTable;
 296     mBuckets = newSize;
 297     return newBucketNumber;
 298   }
 299
 300 private:
 301   std::mutex     mMutex;
 302   ArenaAllocator mAllocator;
 303   StringEntry**  mTable{nullptr};
 304   unsigned       mBuckets{0};
 305   unsigned       mItems{0};
 306 };
 307
 308 } // namespace
 309
 310 Dali::Internal::ConstString::ConstString(std::string_view str)
 311 {
 312   mString = StringPool::Instance().Intern(str);
 313 }
 314
 315 size_t Dali::Internal::ConstString::GetLength() const
 316 {
 317   return mString ? StringEntry::GetStringEntryFromData(mString).getStringLength() : 0;
 318 }
 319
 320 void Dali::Internal::ConstString::SetString(std::string_view str)
 321 {
 322   if(str.empty())
 323   {
 324     mString = nullptr;
 325   }
 326   else
 327   {
 328     mString = StringPool::Instance().Intern(str);
 329   }
 330 }