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