dali/internal/update/manager/free-list.h

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