dali/devel-api/common/free-list.h

   1 #ifndef DALI_FREE_LIST_H
   2 #define DALI_FREE_LIST_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
  21 // EXTERNAL INCLUDES
  22 #include <cstdint> // uint32_t
  23
  24 // INTERNAL INCLUDES
  25 #include <dali/public-api/common/dali-vector.h>
  26
  27 namespace Dali
  28 {
  29 /**
  30  * @brief FreeList operates by connecting unused elements of a vector together in a linked list using the
  31  * value of each unused cell as a pointer to the next. When a new element is added, it will be added
  32  * to the first free index of the vector and the new free index will be the value which was on that
  33  * cell
  34  */
  35 struct FreeList
  36 {
  37   /**
  38    * @brief Constructor
  39    */
  40   FreeList()
  41   : mData(),
  42     mFirstFreeIndex(0)
  43   {
  44   }
  45
  46   /**
  47    * @brief Destructor
  48    */
  49   ~FreeList() = default;
  50
  51   /**
  52    * @brief Adds a new item to the list. If there is no more space in the vector it will
  53    * allocate more space, otherwise, it will use the first free cell to store the
  54    * new value and will update the first free index.
  55    *
  56    * @param[in] value The value to add
  57    * @return The index where the value has been added
  58    */
  59   uint32_t Add(uint32_t value)
  60   {
  61     const uint32_t size = static_cast<uint32_t>(mData.Size()); // 4,294,967,295 entries is enough
  62     if(mData.Empty() || mFirstFreeIndex == size)
  63     {
  64       //Make room for another item
  65       mData.PushBack(size + 1);
  66       mFirstFreeIndex = size;
  67     }
  68
  69     //Update first free index
  70     uint32_t index  = mFirstFreeIndex;
  71     mFirstFreeIndex = mData[mFirstFreeIndex];
  72
  73     mData[index] = value;
  74     return index;
  75   }
  76
  77   /**
  78    * @brief Removes the item at position "index" from the list and
  79    * updates the first free index
  80    *
  81    * @param[in] index The index of the element to remove
  82    */
  83   void Remove(uint32_t index)
  84   {
  85     mData[index]    = mFirstFreeIndex;
  86     mFirstFreeIndex = index;
  87   }
  88
  89   /**
  90    * @brief Subscript operator.
  91    *
  92    * @param[in]  index Index of the element.
  93    * @return Reference to the element for given index.
  94    */
  95   uint32_t& operator[](uint32_t index)
  96   {
  97     return mData[index];
  98   }
  99
 100   /**
 101    * @brief Subscript operator (const).
 102    *
 103    * @param[in]  index Index of the element.
 104    * @return Reference to the element for given index.
 105    */
 106   uint32_t operator[](uint32_t index) const
 107   {
 108     return mData[index];
 109   }
 110
 111 private:
 112   Dali::Vector<uint32_t> mData;           ///< data
 113   uint32_t               mFirstFreeIndex; ///< Index where a new element will be added
 114 };
 115
 116 } // namespace Dali
 117
 118 #endif /* DALI_FREE_LIST_H */