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

   1
   2 #ifndef FREE_LIST_H_
   3 #define FREE_LIST_H_
   4
   5 /*
   6  * Copyright (c) 2016 Samsung Electronics Co., Ltd.
   7  *
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  * http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  *
  20  */
  21
  22 //INTERNAL INCLUDES
  23 #include <dali/public-api/common/dali-vector.h>
  24
  25 namespace Dali
  26 {
  27
  28 namespace Internal
  29 {
  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    * Destructor
  49    */
  50   ~FreeList()
  51   {}
  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   unsigned int Add( unsigned int value )
  62   {
  63     if( mData.Empty() || mFirstFreeIndex == mData.Size() )
  64     {
  65       //Make room for another item
  66       size_t size = mData.Size();
  67       mData.PushBack( size+1 );
  68       mFirstFreeIndex = size;
  69     }
  70
  71     //Update first free index
  72     unsigned int 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( unsigned int 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   unsigned int& operator[]( unsigned int 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   unsigned int operator[]( unsigned int index ) const
 109   {
 110     return mData[index];
 111   }
 112
 113 private:
 114   Dali::Vector<unsigned int> mData; ///< data
 115   unsigned int mFirstFreeIndex;     ///< Index where a new element will be added
 116 };
 117
 118 }
 119 }
 120
 121 #endif /* FREE_LIST_H_ */