dali/internal/text/text-abstraction/plugin/lru-cache-container.h

   1 #ifndef DALI_TEXT_ABSTRACTION_INTERNAL_LRU_CACHE_CONTAINER_H
   2 #define DALI_TEXT_ABSTRACTION_INTERNAL_LRU_CACHE_CONTAINER_H
   3
   4 /*
   5  * Copyright (c) 2022 Samsung Electronics Co., Ltd.
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  * http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 // EXTERNAL INCLUDES
  21 #include <dali/public-api/common/dali-common.h>
  22 #include <dali/public-api/common/vector-wrapper.h>
  23 #include <limits> // for std::numeric_limits
  24 #include <unordered_map>
  25
  26 namespace Dali::TextAbstraction::Internal
  27 {
  28 /**
  29  * @brief Helper class to cache as LRU algirhtm.
  30  * It implement as double-linked-list with header and footer.
  31  *
  32  * HEADER <-> n(LatestId) <-> n <-> ... <-> n(OldestId) <-> FOOTER <-> n(FreeId) <-> n <-> .. <-> n <-> HEADER
  33  *
  34  * @note This container cannot control the KeyType and ElementType construct and destruct timming.
  35  *
  36  * @todo Could we make "iteration" system here?
  37  * @todo Could we move it into dali-core/devel-api?
  38  *
  39  * @tparam KeyType The type of the key that pairwise with element.
  40  * @tparam ElementType The type of the data that the container holds
  41  * @tparam KeyHash The custom hash funcion of KeyType. Default is std::hash
  42  * @tparam KeyEqual The custom equal function of KeyType. Default is std::equal_to
  43  */
  44 template<class KeyType, class ElementType, class KeyHash = std::hash<KeyType>, class KeyEqual = std::equal_to<KeyType>>
  45 class LRUCacheContainer
  46 {
  47 public:
  48   // Constructor
  49   LRUCacheContainer(std::size_t maxNumberOfCache = std::numeric_limits<std::size_t>::max() - 2u)
  50   : mCacheMaxSize(maxNumberOfCache)
  51   {
  52   }
  53
  54   // Destructor
  55   ~LRUCacheContainer() = default;
  56
  57   LRUCacheContainer(const LRUCacheContainer& rhs) = default;
  58   LRUCacheContainer(LRUCacheContainer&& rhs)      = default;
  59
  60   LRUCacheContainer& operator=(const LRUCacheContainer& rhs) = default;
  61   LRUCacheContainer& operator=(LRUCacheContainer&& rhs) = default;
  62
  63 public:
  64   // Public struct area.
  65   using CacheId          = std::size_t; ///< The id of cached element. It can be used until element poped out.
  66   using CacheIdContainer = std::unordered_map<KeyType, CacheId, KeyHash, KeyEqual>;
  67
  68   /**
  69    * @brief Special CacheId for header.
  70    */
  71   static constexpr CacheId CACHE_HEADER_ID = std::numeric_limits<std::size_t>::max();
  72   /**
  73    * @brief Special CacheId for footer.
  74    */
  75   static constexpr CacheId CACHE_FOOTER_ID = std::numeric_limits<std::size_t>::max() - 1u;
  76
  77 public:
  78   // iterator.
  79   /**
  80    * @brief Iterator of this LRU cache.
  81    *
  82    * Add, Get and Clear invalidate the itertator's validation.
  83    * Erase and Pop validate the iterator.
  84    *
  85    * Range based iteration doesn't supported.
  86    */
  87   struct iterator
  88   {
  89   public:
  90     iterator(LRUCacheContainer& owner, const CacheId& id)
  91     : owner(owner),
  92       id(id)
  93     {
  94     }
  95
  96     // copy constructor & assign
  97     iterator(const iterator& rhs)
  98     : owner(rhs.owner),
  99       id(rhs.id)
 100     {
 101     }
 102
 103     iterator& operator=(const iterator& rhs)
 104     {
 105       this->owner = rhs.owner;
 106       this->id    = rhs.id;
 107       return *this;
 108     }
 109
 110     // Move constructor & assign
 111     iterator(iterator&& rhs)
 112     : owner(std::move(rhs.owner)),
 113       id(rhs.id)
 114     {
 115     }
 116
 117     iterator& operator=(iterator&& rhs)
 118     {
 119       this->owner = std::move(rhs.owner);
 120       this->id    = rhs.id;
 121       return *this;
 122     }
 123
 124     // Prefix increment
 125     iterator& operator++()
 126     {
 127       id = owner.mData[id].next;
 128       return *this;
 129     }
 130
 131     // Postfix increment
 132     iterator operator++(int)
 133     {
 134       iterator temp = *this;
 135       ++(*this);
 136       return temp;
 137     }
 138
 139     // Prefix decrement
 140     iterator& operator--()
 141     {
 142       id = owner.mData[id].prev;
 143       return *this;
 144     }
 145
 146     // Postfix decrement
 147     iterator operator--(int)
 148     {
 149       iterator temp = *this;
 150       --(*this);
 151       return temp;
 152     }
 153
 154     bool operator==(const iterator& rhs)
 155     {
 156       return id == rhs.id && (&owner) == (&rhs.owner);
 157     }
 158     bool operator!=(const iterator& rhs)
 159     {
 160       return id != rhs.id || (&owner) != (&rhs.owner);
 161     }
 162
 163   public:
 164     LRUCacheContainer& owner; // The reference of owner of this iterator.
 165     CacheId            id;
 166   };
 167
 168 public:
 169   // Public API area.
 170
 171   /**
 172    * @brief Push an element into the cache. It will be marked as recent
 173    * If it is already existed key, it will replace element.
 174    *
 175    * @param[in] key The key to push
 176    * @param[in] element The element to push
 177    * @warning This method pop oldest elements if the user attempts to push
 178    * more elements than the maximum size specified in the constructor
 179    */
 180   void Push(const KeyType& key, const ElementType& element)
 181   {
 182     const auto iter = mCacheId.find(key);
 183
 184     // If already exist key, just replace element, and return.
 185     if(iter != mCacheId.end())
 186     {
 187       const CacheId id = iter->second;
 188
 189       // Mark as recently used.
 190       InternalPop(id);
 191       InternalInsertAfterHeader(id);
 192
 193       mData[id].element = element;
 194       return;
 195     }
 196
 197     if(DALI_UNLIKELY(IsFull()))
 198     {
 199       // Pop latest element automatically.
 200       Pop();
 201     }
 202
 203     if(DALI_UNLIKELY(mNumberOfElements == mData.size()))
 204     {
 205       InternalReserve(mNumberOfElements == 0 ? 1 : (mNumberOfElements << 1));
 206     }
 207
 208     ++mNumberOfElements;
 209
 210     const CacheId id = mFreeId;
 211
 212     // Mark as recently used.
 213     InternalPop(id);
 214     InternalInsertAfterHeader(id);
 215
 216     // Copy element
 217     mData[id].element = element;
 218
 219     // Store cache iterator.
 220     mData[id].cacheIdIterator = mCacheId.emplace(key, id).first;
 221   }
 222
 223   /**
 224    * @brief Pops an element off the oldest used element.
 225    * After pop, CacheId relative with this element cannot be used.
 226    * Access by poped element's CacheId is Undefined Behavior.
 227    *
 228    * @return A copy of the element
 229    * @warning This method asserts if the container is empty
 230    */
 231   ElementType Pop()
 232   {
 233     DALI_ASSERT_ALWAYS(!IsEmpty() && "Reading from empty container");
 234
 235     const CacheId id = mOldestId;
 236     InternalPop(id);
 237     InternalInsertAfterFooter(id);
 238
 239     --mNumberOfElements;
 240
 241     // Erase cache id.
 242     mCacheId.erase(mData[id].cacheIdIterator);
 243
 244     return mData[id].element;
 245   }
 246
 247   /**
 248    * @brief Get an element by the key. It will be marked as recent
 249    *
 250    * @param[in] key The key of element
 251    * @return A reference of the element
 252    * @warning This method asserts if invalid key inputed
 253    */
 254   ElementType& Get(const KeyType& key)
 255   {
 256     const auto iter = mCacheId.find(key);
 257     DALI_ASSERT_ALWAYS((iter != mCacheId.end()) && "Try to get invalid key");
 258
 259     const auto id = iter->second;
 260
 261     // Mark as recently used.
 262     InternalPop(id);
 263     InternalInsertAfterHeader(id);
 264
 265     return mData[id].element;
 266   }
 267
 268   /**
 269    * @brief Get an key by iterator. It will not be marked as recent
 270    *
 271    * @param[in] iter The iterator of element
 272    * @return A reference of the key
 273    * @warning This method don't check iterator validation
 274    */
 275   const KeyType& GetKey(iterator iter)
 276   {
 277     const auto id = iter.id;
 278
 279     return mData[id].cacheIdIterator->first;
 280   }
 281
 282   /**
 283    * @brief Get an element by iterator. It will not be marked as recent
 284    *
 285    * @param[in] iter The iterator of element
 286    * @return A reference of the element
 287    * @warning This method don't check iterator validation
 288    */
 289   ElementType& GetElement(iterator iter)
 290   {
 291     const auto id = iter.id;
 292
 293     return mData[id].element;
 294   }
 295
 296   /**
 297    * @brief Find an element by the key. It will not be marked as recent
 298    *
 299    * @param[in] key The key of element
 300    * @return A iterator of cache node. If key not exist, return End()
 301    */
 302   iterator Find(const KeyType& key)
 303   {
 304     if(mCacheId.find(key) == mCacheId.end())
 305     {
 306       return End();
 307     }
 308
 309     const auto id = mCacheId[key];
 310
 311     return iterator(*this, id);
 312   }
 313
 314   /**
 315    * @brief Clear all data
 316    */
 317   void Clear()
 318   {
 319     mCacheId.clear();
 320     mCacheId.rehash(0);
 321     mData.clear();
 322     mData.shrink_to_fit();
 323
 324     mNumberOfElements = 0;
 325     mLatestId         = CACHE_FOOTER_ID;
 326     mOldestId         = CACHE_HEADER_ID;
 327     mFreeId           = CACHE_HEADER_ID;
 328   }
 329
 330   /**
 331    * @brief Predicate to determine if the container is empty
 332    *
 333    * @return true if the container is empty
 334    */
 335   bool IsEmpty() const
 336   {
 337     return mNumberOfElements == 0;
 338   }
 339
 340   /**
 341    * @brief Predicate to determine if the container is full
 342    *
 343    * @return true if the container is full
 344    */
 345   bool IsFull() const
 346   {
 347     return (mNumberOfElements == mCacheMaxSize);
 348   }
 349
 350   iterator Begin()
 351   {
 352     return iterator(*this, mLatestId);
 353   }
 354
 355   iterator End()
 356   {
 357     return iterator(*this, CACHE_FOOTER_ID);
 358   }
 359
 360   /**
 361    * @brief Remove cache item by iterator.
 362    *
 363    * @param[in] iter The iterator what we want to remove.
 364    * @return iterator The next iterator after remove
 365    * @warning This method don't check iterator validation
 366    */
 367   iterator Erase(iterator iter)
 368   {
 369     const auto id     = iter.id;
 370     const auto nextId = mData[id].next;
 371     InternalPop(id);
 372     InternalInsertAfterFooter(id);
 373
 374     --mNumberOfElements;
 375
 376     // Erase cache id.
 377     mCacheId.erase(mData[id].cacheIdIterator);
 378
 379     return iterator(*this, nextId);
 380   }
 381
 382   /**
 383    * @brief Get a count of the elements in the container
 384    *
 385    * @return the number of elements in the container.
 386    */
 387   std::size_t Count() const
 388   {
 389     return mNumberOfElements;
 390   }
 391
 392 private:
 393   // Private API area.
 394
 395   /**
 396    * @brief Allocate cache memory as reserveSize.
 397    * @note We assume that mFreeId is header.
 398    *
 399    * @param reserveSize Reserved size of cache.
 400    */
 401   void InternalReserve(std::size_t reserveSize) noexcept
 402   {
 403     // Increase mData capacity
 404     if(reserveSize > mCacheMaxSize)
 405     {
 406       reserveSize = mCacheMaxSize;
 407     }
 408
 409     CacheId newCreatedIdBegin = mData.size();
 410     CacheId newCreatedIdEnd   = reserveSize - 1;
 411
 412     // Make temporary array for re-validate iterator.
 413     std::vector<KeyType> keyList(mData.size());
 414     for(auto i = static_cast<std::size_t>(0); i < newCreatedIdBegin; ++i)
 415     {
 416       keyList[i] = mData[i].cacheIdIterator->first;
 417     }
 418
 419     // Reserve data and cacheid capacity.
 420     mData.resize(reserveSize);
 421     mCacheId.rehash(reserveSize);
 422
 423     // Revalidate each iterator.
 424     for(auto i = static_cast<std::size_t>(0); i < newCreatedIdBegin; ++i)
 425     {
 426       mData[i].cacheIdIterator = mCacheId.find(keyList[i]);
 427     }
 428
 429     // Setup new created CacheNode's prev and next id.
 430     for(auto i = newCreatedIdBegin;; ++i)
 431     {
 432       mData[i].prev = DALI_UNLIKELY(i == newCreatedIdBegin) ? CACHE_FOOTER_ID : i - 1;
 433       mData[i].next = DALI_UNLIKELY(i == newCreatedIdEnd) ? CACHE_HEADER_ID : i + 1;
 434       if(DALI_UNLIKELY(i == newCreatedIdEnd))
 435       {
 436         break;
 437       }
 438     }
 439     mFreeId = newCreatedIdBegin;
 440   }
 441
 442   /**
 443    * @brief Temperary pop of node. After call this, we should call
 444    * InternalInsertAfterHeader or InternalInsertAfterFooter
 445    *
 446    * @param id CacheId that removed temperary.
 447    */
 448   void InternalPop(const CacheId& id) noexcept
 449   {
 450     const CacheId prev = mData[id].prev;
 451     const CacheId next = mData[id].next;
 452
 453     // Disconnect prev -> id. and connect prev -> next
 454     if(prev == CACHE_HEADER_ID)
 455     {
 456       mLatestId = next;
 457     }
 458     else if(prev == CACHE_FOOTER_ID)
 459     {
 460       mFreeId = next;
 461     }
 462     else
 463     {
 464       mData[prev].next = next;
 465     }
 466
 467     // Disconnect id <- next. and connect prev <- next
 468     if(next == CACHE_HEADER_ID)
 469     {
 470       // Do nothing.
 471     }
 472     else if(next == CACHE_FOOTER_ID)
 473     {
 474       mOldestId = prev;
 475     }
 476     else
 477     {
 478       mData[next].prev = prev;
 479     }
 480   }
 481
 482   /**
 483    * @brief Insert the node after the header. That mean, this id recently used.
 484    *
 485    * @param id CacheId that insert after header.
 486    */
 487   void InternalInsertAfterHeader(const CacheId& id) noexcept
 488   {
 489     const CacheId next = mLatestId;
 490
 491     // Connect Header -> id.
 492     mLatestId = id;
 493
 494     // Connect id <- next
 495     if(next == CACHE_FOOTER_ID)
 496     {
 497       mOldestId = id;
 498     }
 499     else
 500     {
 501       mData[next].prev = id;
 502     }
 503
 504     // Connect Header <- id -> next
 505     mData[id].prev = CACHE_HEADER_ID;
 506     mData[id].next = next;
 507   }
 508
 509   /**
 510    * @brief Insert the node after the footer. That mean, this id become free.
 511    *
 512    * @param id CacheId that insert after footer.
 513    */
 514   void InternalInsertAfterFooter(const CacheId& id) noexcept
 515   {
 516     const CacheId next = mFreeId;
 517
 518     // Connect Footer -> id.
 519     mFreeId = id;
 520
 521     // Connect id <- next
 522     if(next == CACHE_HEADER_ID)
 523     {
 524       // Do nothing.
 525     }
 526     else
 527     {
 528       mData[next].prev = id;
 529     }
 530
 531     // Connect Footer <- id -> next
 532     mData[id].prev = CACHE_FOOTER_ID;
 533     mData[id].next = next;
 534   }
 535
 536 private:
 537   // Private struct area.
 538   /**
 539    * @brief Double linked CacheNode that this container used.
 540    */
 541   struct CacheNode
 542   {
 543     CacheNode()  = default;
 544     ~CacheNode() = default;
 545
 546     CacheId     prev{CACHE_FOOTER_ID};
 547     CacheId     next{CACHE_HEADER_ID};
 548     ElementType element;
 549
 550     using CacheIdIterator = typename CacheIdContainer::iterator;
 551
 552     CacheIdIterator cacheIdIterator; ///< Note : It only validate until mCacheId rehashing.
 553   };
 554
 555 private:
 556   // Private member value area.
 557   std::size_t mCacheMaxSize{0};     ///< The maximum capacity of cache.
 558   std::size_t mNumberOfElements{0}; ///< The number of elements.
 559
 560   CacheId mLatestId{CACHE_FOOTER_ID}; ///< The recently used element id
 561   CacheId mOldestId{CACHE_HEADER_ID}; ///< The oldest used element id
 562   CacheId mFreeId{CACHE_HEADER_ID};   ///< The free element id that can be allocated.
 563
 564   std::unordered_map<KeyType, CacheId, KeyHash, KeyEqual> mCacheId{}; ///< LRU Cache id container
 565   std::vector<CacheNode>                                  mData{};    ///< The real data container.
 566 };
 567
 568 } // namespace Dali::TextAbstraction::Internal
 569
 570 #endif //DALI_TEXT_ABSTRACTION_INTERNAL_LRU_CACHE_CONTAINER_H