dali/internal/common/const-string.cpp

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