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

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