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()
  53   {}
  54
  55   /**
  56    * Adds a new item to the list. If there is no more space in the vector it will
  57    * allocate more space, otherwise, it will use the first free cell to store the
  58    * new value and will update the first free index.
  59    *
  60    * @param[in] value The value to add
  61    * @return The index where the value has been added
  62    */
  63   uint32_t Add( uint32_t value )
  64   {
  65     const uint32_t size = static_cast<uint32_t>( mData.Size() ); // 4,294,967,295 entries is enough
  66     if( mData.Empty() || mFirstFreeIndex == size )
  67     {
  68       //Make room for another item
  69       mData.PushBack( size + 1 );
  70       mFirstFreeIndex = size;
  71     }
  72
  73     //Update first free index
  74     uint32_t index = mFirstFreeIndex;
  75     mFirstFreeIndex = mData[mFirstFreeIndex];
  76
  77     mData[index] = value;
  78     return index;
  79   }
  80
  81   /**
  82    * Removes the item at position "index" from the list and
  83    * updates the first free index
  84    *
  85    * @param[in] index The index of the element to remove
  86    */
  87   void Remove( uint32_t index )
  88   {
  89     mData[index] = mFirstFreeIndex;
  90     mFirstFreeIndex = index;
  91   }
  92
  93   /**
  94    * Subscript operator.
  95    *
  96    * @param[in]  index Index of the element.
  97    * @return Reference to the element for given index.
  98    */
  99   uint32_t& operator[]( uint32_t index )
 100   {
 101     return mData[index];
 102   }
 103
 104   /**
 105    * Subscript operator (const).
 106    *
 107    * @param[in]  index Index of the element.
 108    * @return Reference to the element for given index.
 109    */
 110   uint32_t operator[]( uint32_t index ) const
 111   {
 112     return mData[index];
 113   }
 114
 115 private:
 116   Dali::Vector< uint32_t > mData; ///< data
 117   uint32_t mFirstFreeIndex;     ///< Index where a new element will be added
 118 };
 119
 120 }
 121 }
 122
 123 #endif /* FREE_LIST_H_ */